题面：
签到题，很显然先分配那些补较少人数就能产生牌子的比赛，那么补全了之后如果还有剩的直接除k向下取整就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
| void solve() {
int n,k;
cin>>n>>k;
vector<int> a(n);
int ans = 0;
for(int i = 0;i<n;++i) cin>>a[i],ans += a[i] / k,a[i] %= k;
int m,p = 0;
cin>>m;
sort(all(a),greater());
while(p < n && m - (k - a[p]) >= 0) ans++,m -= (k - a[p++]);
ans += m / k;
cout<<ans<<endl;
}
|
观察样例可以发现当n == 4 || n == 1的时候归零了。
首先不难看出0,1,2,3;4,5,6,7;8,9,10,11;这样每四个连续的数异或都是0。
所以可以假设n是4的倍数<=>无解的（等于0）。
那么想让每一个前缀都大于0就要对其偏移一位就行，比如n == 2的时候是先1后0，即1 0,其他情况直接顺序排就行。
用队列实现比较容易一些。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void solve() {
int n;
cin>>n;
if(n % 4 == 0 || n == 1) return cout<<"impossible\n",void();
queue<int> q;
for(int i = 0;i<n;++i){
if((i + 1) % 4 == 0 || i == 0){
q.push(i);
continue;
}
cout<<i<<' ';
if(!q.empty()) cout<<q.front()<<' ',q.pop();
}
cout<<endl;
}
|
左移操作最优的情况就是把一段相同字符拆成两段，如果一个偶数拆成了两个奇数，那么答案能减小1，只有奇数不影响。
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
| void solve() {
string s;
cin >> s;
int n = si(s);
if (n == 1) return cout << 0 << endl, void();
vector<int> a;
for (int i = 0, j = 1; j <= n; ++j) {
if (j == n) {
a.push_back(j - i);
} else {
while (s[i] == s[j]) j++;
a.push_back(j - i);
i = j;
}
}
if(si(a) == 1) return cout<<a[0] / 2<<endl,void();
int ok = 0;
if (s.front() == s.back() && !a.empty()) {
a.front() += a.back();
a.pop_back();
}
int ans = 0;
for (auto i : a) ans += i >> 1,ok |= (i % 2 == 0);
cout << ans - ok << endl;
}
|
直接贪心就行，注意题目没有说每个比赛的评级是不一样的，所以可能有评级一样的比赛，但是分数不一样，下一评级的比赛必须要大于这一级比赛的最大的分数。
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
142
143
144
| void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<int> s(n), p;
vector<vector<int>> info(n, vector(m, 0ll));
for (int i = 0; i < n; ++i) {
p.push_back(i);
for (int j = -1; j < m; ++j) {
if (j == -1) cin >> s[i];
else cin >> info[i][j];
}
}
sort(all(p), [&](int x, int y) {
return s[x] < s[y];
});
int pre = -1, prep = -1;
int maxn = pre;
for (int i : p) {
int tot, cur = 0;
if(prep != s[i]) pre = maxn;
tot = pre + 1;
for (auto &j : info[i]) if(j != -1) cur += j;
for (auto &j : info[i]) {
if (j == -1) {
j = cur >= tot ? 0ll : min(k, tot - cur);
cur += j;
}
}
if (tot > cur) return cout << "No" << endl, void();
maxn = max(maxn, cur);
prep = s[i];
}
cout << "Yes" << endl;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) cout << info[i][j] << " \n"[j == m - 1];
}
|
致敬传奇二星级比赛ICPC。
问你一个长度为n的正整数序列，可以选一个连续的子序列（可以为空）加上k，k为非负整数，问你这样操作之后这个序列整个的gcd最大是多少。
首先想一下最暴力的解法。
枚举左右端点，这个区间内的所有数加k。那么最坏至少是$ O(n^2) $的。
考虑优化，把这个前后缀打表，如第一个样例的数据：
1
2
3
4
5
6
| 6 2
5 3 13 8 10 555
pre:
5 1 1 1 1 1 1
suf:
1 1 1 1 5 555
|
可以发现其实有很多都是重复的数，其实最大大致只有logN个，N是这个数组中具有最多因子数的数。
前缀一定是单调递减的，因为重复的数一定是连续的，那么贪心的想，选每次即将变小的位置作为加k的左端点一定是当前这个gcd最优的情况。因为这能尽可能地保证后缀是最大的。因为最多是log级别的，所以每固定一个l，然后枚举r。暴力跑一遍大致就是$ O(nlogN) $的。
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
| void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
vector<int> suf(n + 2), pre(n + 1);
for (int i = 0; i < n; ++i) pre[i + 1] = gcd(pre[i], a[i]);
for (int i = n; i > 0; --i) suf[i] = gcd(suf[i + 1], a[i-1]);
int maxn = pre[n];
for(int i = 1;i<=n;++i){
if(pre[i] != pre[i - 1]){
int g = pre[i-1];
for(int j = i;j<=n;++j){
g = gcd(g,a[j-1] + k);
maxn = max(maxn,gcd(g,suf[j+1]));
}
}
}
cout<<maxn<<endl;
}
|
