2019 SDNU ACM-ICPC Provincial Team Selection Round 1【完结】

发表于 | 更新于 | 分类于
－－－－－－－－－－山东省第十届acm大学程序设计竞赛山师选拔赛第一场－－－－－－－－－－

A - Albert_s and Chocolate【签到】

题意：超市搞活动，每买$a$个巧克力棒就会赠给你$b$个，现在你有$s$元，每个巧克力棒花费$c$元，问你最多能获得多少巧克力棒。

思路：直接做。注意乘除关系以及long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

int t;
ll s, a, b, c;
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld%lld%lld%lld", &s,&a,&b,&c);
        ll tmp = s / c;
        ll res = tmp + tmp / a * b;
        printf("%lld\n", res);
    }
    return 0;
}

B - Birthday Tears【暴力】

题意：略。

思路：直接做。如果觉得不优美，可以随便加点东西，我做的⽐较繁琐，⽤了⼀个带log的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
 
const int MAXN = 100000 + 10;
const int MAXC = 20;
 
char s[MAXN];
int f[MAXN][MAXC];
int log2[MAXN];
 
bool check(int x, int y)
{
    int k = log2[y - x + 1];
    if (f[x][k] == f[y - (1 << k) + 1][k] && f[x][k] > -1)
        return true;
    else
        return false;
}
 
int main()
{
    int testCase;
    scanf("%d", &testCase);
 
    for (int j = 0; (1 << j) < MAXN; ++j)
        for (int i = 1 << j; i < min(MAXN, (1 << (j + 1))); ++i)
            log2[i] = j;
    
    while (testCase--)
    {
        scanf("%s", s);
        int n = strlen(s);
 
        for (int i = 0; i < n; ++i)
            f[i][0] = s[i] - 'a';
 
        for (int j = 1; (1 << j) <= n; ++j)
            for (int i = 0; i + (1 << j) - 1 < n; ++i)
                if (f[i][j - 1] == f[i + (1 << (j - 1))][j - 1])
                    f[i][j] = f[i][j - 1];
                else
                    f[i][j] = -1;
    
        int ans = -1;
        for (int len = n, tear = 0; len > 0; tear++, len /= 2)
        {
            for (int i = 0; i < n; i += len)
                if (check(i, i + len - 1))
                {
                    ans = tear;
                    break;
                }
            if (ans != -1)
                break;
 
            if (len % 2 != 0) break;
        }
 
        cout << ans << endl;
    }
    return 0;
}

C - Cheat in the Game【博弈】【DP】

http://www.hankcs.com/program/algorithm/poj-3688-cheat-in-the-game.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 10010;
const int M = 100010;

int n, m, res, a[N], dp[M][2];

int main()
{
    while(scanf("%d%d", &n,&m) && (n || m))
    {
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for(int i = 1; i <= n; ++i)
        {
            for(int j = m; j > a[i]; --j)
            {
                if(dp[j - a[i]][0])
                    dp[j][1] = 1;
                if(dp[j - a[i]][1])
                    dp[j][0] = 1;
            }
            dp[a[i]][1] = 1;
        }

//        for(int i = 1; i <= m; ++i)
//            cout << dp[i][0] << ' ' << dp[i][1] << endl;

        res = 0;
        for(int i = 1; i <= m; ++i)
            if(dp[i][1] && !dp[i][0])
                ++res;
        printf("%d\n", res);
    }
    return 0;
}

D - Decompressing Of Matrix【最大流】

题意：略。

思路：略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
int id[25][25];
const int maxn = 115;
const int maxm = 10010;
const int inf = 0x3f3f3f3f;
struct fuck {
	int v, w, ne, u;
}ed[maxm];
int n, m, cnt;
int head[maxn], dis[maxn], cur[maxn];
void init() {
	cnt = 0;
	memset(head, -1, sizeof(head));
}
void add(int u, int v, int w) {
	ed[cnt].v = v; ed[cnt].w = w; ed[cnt].u = u;
	ed[cnt].ne = head[u]; head[u] = cnt++;
	ed[cnt].v = u, ed[cnt].w = 0; ed[cnt].u = v;
	ed[cnt].ne = head[v]; head[v] = cnt++;
}
int bfs(int st, int en) {
	queue<int>q;
	memset(dis, 0, sizeof(dis));
	dis[st] = 1;
	q.push(st);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		if (u == en)return 1;
		for (int s = head[u]; ~s; s = ed[s].ne) {
			int v = ed[s].v;
			if (dis[v] == 0 && ed[s].w > 0) {
				dis[v] = dis[u] + 1; q.push(v);
			}
		}
	}
	return dis[en] != 0;
}
int dfs(int st, int en, int flow) {
	int ret = flow, a;
	if (st == en || flow == 0)return flow;
	for (int &s = cur[st]; ~s; s = ed[s].ne) {
		int v = ed[s].v;
		if (dis[v] == dis[st] + 1 && (a = dfs(v, en, min(ret, ed[s].w)))) {
			ed[s].w -= a;
			ed[s ^ 1].w += a;
			ret -= a;
			if (!ret)break;
		}
	}
	if (ret == flow)dis[st] = 0;
	return flow - ret;
}
int dinic(int st, int en) {
	int ans = 0;
	while (bfs(st, en)) {
		for (int s = 0; s <= en; s++) //这里！！
			cur[s] = head[s];
		ans += dfs(st, en, inf);
	}
	return ans;
}
int main() {
	int te, cas = 1;
	ios::sync_with_stdio(0);
	cin >> te;
	while (te--) {
		init();
		cin >> n >> m;
		int last = 0;
		int st = 0;
		for (int i = 1; i <= n; i++) {
			int d;
			cin >> d;
			add(st, i, d - last - m);
			last = d;
			for (int j = 1; j <= m; j++){	
				id[i][j] = cnt;
				add(i, j + n, 19);
			}
		}
		last = 0;
		int en = 105;
		for (int i = 1; i <= m; i++) {
			int d; cin >> d;
			add(n + i, en, d - n - last);
			last = d;
		}
		dinic(st, en);
		cout << "Matrix " << cas++ << "\n";
		for (int i = 1; i <= n; i++) {
			cout << ed[id[i][1] ^ 1].w + 1;
			for (int j = 2; j <= m; j++) {
				cout << " " << ed[id[i][j] ^ 1].w + 1;
			}
			cout << "\n";
		}
	}
	return 0;
}

E - Easy Basic remains【大数】

题意：求$b$进制下的$p$ mod $m$的结果

思路：模拟 || 开上Java直接做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin = new Scanner(System.in);
		int base;
		BigInteger n, m, res;
		while(cin.hasNext())
		{
			base = cin.nextInt();
			if(base == 0)	break;
			n = cin.nextBigInteger(base);
			m = cin.nextBigInteger(base);
			res = n.mod(m);
			System.out.println(res.toString(base));
		}
	}
}

F - Fast Matrix Operations【线段树】

题意：略。

思路：开上20颗线段树直接搞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 1e6 + 10;
struct fuck {
	int sum, maxn, minn;
}c[maxn * 3][21];
int add[maxn * 3][21], chan[maxn * 2][21];
int l[maxn * 3][21], r[maxn * 3][21];
void pushup(int x, int rt) {
	c[rt][x].sum = c[rt << 1][x].sum + c[rt << 1 | 1][x].sum;
	c[rt][x].maxn = max(c[rt << 1][x].maxn, c[rt << 1 | 1][x].maxn);
	c[rt][x].minn = min(c[rt << 1][x].minn, c[rt << 1 | 1][x].minn);
}
void pushdown(int x, int rt, int len) {
	if (chan[rt][x] != -1) {
		c[rt << 1][x].maxn = chan[rt][x];
		c[rt << 1][x].minn = chan[rt][x];
		c[rt << 1][x].sum = (len + 1) / 2 * chan[rt][x];
		add[rt << 1][x] = 0;
		chan[rt << 1][x] = chan[rt][x];
		c[rt << 1 | 1][x].maxn = chan[rt][x];
		c[rt << 1 | 1][x].minn = chan[rt][x];
		c[rt << 1 | 1][x].sum = (len) / 2 * chan[rt][x];
		add[rt << 1 | 1][x] = 0;
		chan[rt << 1 | 1][x] = chan[rt][x];
	}
	if (add[rt][x] != 0) {
		c[rt << 1][x].maxn += add[rt][x];
		c[rt << 1][x].minn += add[rt][x];
		c[rt << 1][x].sum += (len + 1) / 2 * add[rt][x];
		add[rt << 1][x] += add[rt][x];
		c[rt << 1 | 1][x].maxn += add[rt][x];
		c[rt << 1 | 1][x].minn += add[rt][x];
		c[rt << 1 | 1][x].sum += (len) / 2 * add[rt][x];
		add[rt << 1 | 1][x] += add[rt][x];
	}
	chan[rt][x] = -1; add[rt][x] = 0;
}
void build(int x, int l, int r, int rt) {
	add[rt][x] = 0; chan[rt][x] = -1;
	if (l == r) {
		c[rt][x].sum = 0;
		c[rt][x].minn = 0;
		c[rt][x].maxn = 0;
		return;
	}
	int m = (l + r) >> 1;
	build(x, lson);
	build(x, rson);
	pushup(x, rt);
}
void change(int x, int L, int R, int l, int r, int rt, int k) {
	if (L <= l&&r <= R) {
		c[rt][x].sum = (r - l + 1)*k;
		c[rt][x].maxn = c[rt][x].minn = k;
		add[rt][x] = 0; chan[rt][x] = k;
		return;
	}
	int m = (l + r) >> 1; int len = (r - l + 1);
	pushdown(x, rt, len);
	if (L <= m)
		change(x, L, R, lson, k);
	if (R > m)
		change(x, L, R, rson, k);
	pushup(x, rt);
}
void addnum(int x, int L, int R, int l, int r, int rt, int k) {
	if (L <= l&&r <= R) {
		c[rt][x].sum += (r - l + 1)*k;
		c[rt][x].maxn += k; c[rt][x].minn += k;
		add[rt][x] += k;
		return;
	}
	int m = (l + r) >> 1; int len = (r - l + 1);
	pushdown(x, rt, len);
	if (L <= m)
		addnum(x, L, R, lson, k);
	if (R > m)
		addnum(x, L, R, rson, k);
	pushup(x, rt);
}
int query(int x, int L, int R, int l, int r, int rt, int &maxn, int &minn) {
	if (L <= l&&r <= R) {
		maxn = max(maxn, c[rt][x].maxn);
		minn = min(minn, c[rt][x].minn);
		return c[rt][x].sum;
	}
	int m = (l + r) >> 1, len = (r - l + 1);
	int sum = 0;
	pushdown(x, rt, len);
	if (L <= m) {
		sum += query(x, L, R, lson, maxn, minn);
	}
	if (R > m) {
		sum += query(x, L, R, rson, maxn, minn);
	}
	pushup(x, rt);
	return  sum;
}
int main() {
	int n, m, q;
	ios::sync_with_stdio(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
		build(i, 1, m, 1);
	while (q--) {
		int a; cin >> a;
		int b, c, d, e, f;
		if (a == 1) {
			cin >> b >> c >> d >> e >> f;
			if (b > d)swap(b, d);
			if (c > e)swap(c, e);
			for (int i = b; i <= d; i++) {
				addnum(i, c, e, 1, m, 1, f);
			}
		}
		else if (a == 2) {
			cin >> b >> c >> d >> e >> f;
			if (b > d)swap(b, d);
			if (c > e)swap(c, e);
			for (int i = b; i <= d; i++) {
				change(i, c, e, 1, m, 1, f);
			}
		}
		else {
			cin >> b >> c >> d >> e;
			if (b > d)swap(b, d);
			if (c > e)swap(c, e);
			int ans = 0, maxn = -1, minn = 2147483647;
			for (int i = b; i <= d; i++) {
				ans += query(i, c, e, 1, m, 1, maxn, minn);
			}
			cout << ans << " " << minn << " " << maxn << "\n";
		}
	}
	return 0;
}

G. Game of Stones【优先队列】

题意：略。

思路：模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

int t, n, p, d, res;

struct node
{
    int p, d;
} now;

struct cmp
{
    bool operator() (const node &u, const node &v)
    {
        if(u.p == v.p)
            return u.d > v.d;
        return u.p > v.p;
    }
};

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        priority_queue<node, vector<node>, cmp> Q;
        res = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d%d", &p,&d);
            //感觉这里需要加上才更完善，但没加也过了。
            //res = max(res, p);
            now.p = p, now.d = d;
            Q.push(now);
        }
        bool flag = 0;
        while(1)
        {
            flag = !flag;
            now = Q.top();
            Q.pop();
            if(flag)
            {
                if(Q.empty())
                {
                    //res = max(res, now.p + now.d);
                    res = now.p + now.d;
                    break;
                }
                now.p = now.p + now.d;
                Q.push(now);
            }
            else
                continue;
        }
        printf("%d\n", res);
    }
    return 0;
}

H - Hacker, pack your bags!【贪心】

题意&思路：见https://alberts97.github.io/cf-822c/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int N = 200010;
const int oo = 2e9+7;

int n, x, l, r, c, res, tem;
vector< pair<int, int> > G[N];
int main()
{
    scanf("%d%d", &n, &x);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d%d%d", &l, &r, &c);
        G[r - l + 1].push_back({l, c});
    }
    for(int i = 1; i < x; ++i)
        sort(G[i].begin(), G[i].end());
    res = oo;
    for(int cost = 1; cost < x; ++cost)
    {
        tem = oo;
        auto &u = G[cost], &v = G[x - cost];
        for(int i = 0, j = 0; i < v.size(); ++i)
        {
            while(j < u.size() && u[j].first + cost - 1 < v[i].first)
            {
                tem = min(tem, u[j].second);
                ++j;
            }
            if(tem != oo)
                res = min(res, tem + v[i].second);
        }
    }
    printf("%d\n", res == oo ? -1 : res);
    return 0;
}

I - Interesting String【Manacher模板】

题意：求最长回文子串的长度。

思路：无。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN=1000010;
char Ma[MAXN*2];
int Mp[MAXN*2];
void Manacher(char s[],int len)
{
    int l=0;
    Ma[l++]='$';
    Ma[l++]='#';
    for(int i=0; i<len; i++)
    {
        Ma[l++]=s[i];
        Ma[l++]='#';
    }
    Ma[l]=0;
    int mx=0,id=0;
    for(int i=0; i<l; i++)
    {
        Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
        while(Ma[i+Mp[i]]==Ma[i-Mp[i]])
            Mp[i]++;
        if(i+Mp[i]>mx)
        {
            mx=i+Mp[i];
            id=i;
        }
    }
}
char s[MAXN];
int main()
{
    for(int cas = 1; scanf("%s",s)==1; ++cas)
    {
        if(s[0] == 'E') break;
        int len=strlen(s);
        Manacher(s,len);
        int ans=0;
        for(int i=0; i<2*len+2; i++)
            ans=max(ans,Mp[i]-1);
        printf("Case %d: %d\n",cas, ans);
    }
    return 0;
}

J - Joseph【数据结构】

题意：略。

思路：但是什么都不管暴⼒模拟也是可以的，⽤任意⼀个带 log 的数据结构。中档题的原因是因为优美做法需要想⼀下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <cstdio>
using namespace std;
 
const int MAXN = 1000000 + 10;
 
int c[MAXN];
int N, K;
 
void add(int x, int y)
{
    for (; x <= N; x += x & -x)
        c[x] += y;
}
 
int get(int x)
{
    int res = 0;
    for (; x; x -= x & -x)
        res += c[x];
    return res;
}
 
int findk(int K)
{
    int k = 1;
    int p = 0;
    while ((k >> 1) <= N) { ++p; k <<= 1; }
 
    int ans = 0;
    int res = 0;
 
    for (int i = p; i >= 0; --i)
    {
        if (ans + k <= N && res + c[ans + k] < K)
        {
            res += c[ans + k];
            ans += k;
        }
        k >>= 1;
    }
    return ans + 1;
}
 
int main()
{
    int testCase;
    scanf("%d", &testCase);
 
    while (testCase--)
    {
        scanf("%d%d", &N, &K);
 
        fill_n(c, N + 1, 0);
        for (int i = 1; i <= N; ++i)
            add(i, 1);
 
        bool inverse = false;
        if (K < 0) 
        {
            K = -K;
            inverse = true;
        }
        long long cnt = K;
        int now = K % N;
        if (now == 0) now = N;
        int d = 1;
 
        for (int n = N; n > 1; --n)
        {
            int pos = findk(now);
            add(pos, -1);
 
            //cout << "pos = " << pos << endl;
            //cout << "now = " << now << endl;
 
            d = -d;
            cnt = cnt + K;
            int cnm = (cnt - 1) % (n - 1);
 
            if (d < 0) now--;
            if (d > 0)
            {
                now = (now + cnm) % (n - 1);
                if (now == 0) now = n - 1;
            }
            else
            {
                now = (now - cnm + n - 1 + n - 1) % (n - 1);
                if (now == 0) now = n - 1;
            }
        }
 
        int ans = findk(1);
        if (inverse)
            if (ans > 1)
                ans = N - 1 - (ans - 1) + 2;
 
        cout << ans << endl;
    }
    return 0;
}

K - K-th Power【拉格朗日插值】

题意：求$\sum_{i=1}^n i^k = 1^k + 2^k +\ldots + n^k $ % $10^9 + 7$的值

思路：嗯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

typedef long long ll;

const int maxn = 1e6+15;
const ll mod = 1e9+7;

int tot;
ll pri[maxn];
bool is[maxn];
ll f[maxn];
ll jc[maxn];
ll ijc[maxn];

int n, k;

ll qm (ll a, ll b)
{
    ll ans = 1;
    a %= mod;
    while (b)
    {
        if (b&1)
        {
            ans = a*ans%mod;
        }
        a = a*a%mod;
        b >>= 1;
    }
    return ans%mod;
}

ll inv (ll k)
{
    return qm(k, mod-2)%mod;
}

void init (int maxn)
{
    f[0] = 0;
    f[1] = 1;
    is[0] = is[1] = 1;
    for (int i = 2; i < maxn; ++i)
    {
        if (!is[i])
        {
            pri[++tot] = i;
            f[i] = qm(i, k);
        }
        for (int j = 1; j <= tot && 1ll*i*pri[j] < maxn; ++j)
        {
            is[i*pri[j]] = 1;
            f[i*pri[j]] = f[i]*f[pri[j]]%mod;
            if (i % pri[j] == 0)
            {
                break;
            }
        }
    }
    for (int i = 0; i < maxn; ++i)
    {
        f[i] = f[i]+f[i-1];
        f[i] %= mod;
    }
    ijc[0] = ijc[1] = jc[0] = jc[1] = 1;
    for (int i = 2; i < maxn; ++i)
    {
        jc[i] = jc[i-1]*i%mod;
        ijc[i] = inv(jc[i]);
    }
}

int main ()
{
    cin >> n >> k;
    init(k+15);
    if (n <= k+2)
    {
        cout << f[n] << '\n';
        return 0;
    }
    k += 2;
    ll ans = 0;
    ll tmp = 1;
    for(int i = 1; i<= k; i++) {
        tmp = (tmp*(n-i))%mod;
    }
    for (int i = 1; i <= k; ++i)
    {
        if ((k-i)%2 == 0)
        {
            ans += f[i]*inv(n-i)%mod*ijc[i-1]%mod*ijc[k-i]%mod*tmp%mod;
            ans = (ans%mod+mod)%mod;
        }
        else
        {
            ans -= f[i]*inv(n-i)%mod*ijc[i-1]%mod*ijc[k-i]%mod*tmp%mod;
            ans = (ans%mod+mod)%mod;
        }
    }
    cout << (ans%mod+mod)%mod << '\n';
    return 0;
}

L - Let‘s Find The Biggest Out【暴力】

题意：略。

思路：答案是倒数第⼆⼤的数，或者暴⼒模拟最⼤的数模其他的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
 
int main()
{
    int testCase;
    cin >> testCase;
    
    while (testCase--)
    {
        int n;
        cin >> n;
        vector<int> a;
        for (int i = 0; i < n; ++i)
        {
            int t;
            cin >> t;
            a.push_back(t);
        }
        sort(a.begin(), a.end());
        n = unique(a.begin(), a.end()) - a.begin();
 
        int ans = 0;
        if (n > 1)
            ans = a[n - 2];
 
        for (int i = 0; i < n; ++i)
            ans = max(ans, a[n - 1] % a[i]);
 
        cout << ans << endl;
    }
    return 0;
}
Donate comment here
0%