本文最后编辑于 前，其中的内容可能需要更新。
题目大意：A就不写题意了。
解法：算一下最多的peak可能出现的次数，从左往右放数字就好，能放peak就放当前最大的数字，其他情况当前最小的数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
using namespace std;
int T, n, k, a[105], up, dw;
int main(){
cin >> T;
while(T--){
cin >> n >> k;
if(k > (n - 1) / 2) puts("-1");
else{
up = n, dw = 1;
for(int i = 1; i <= n; i++){
if(k && !(i & 1)) a[i] = up--, k--;
else a[i] = dw++;
}
for(int i = 1; i <= n; i++) cout << a[i] << (i == n ? '\n' : ' ');
}
}
return 0;
}
|
题目大意：B就不写题意了，注意当一个sequences是好的时候所有的划分都满足条件。
解法：显然若所有数二进制下某位均为1，该位无影响，若所有数二进制下某位有1有0，则第1个数和第n个数该位必为0，所以枚举头尾，中间n-2个数字直接排列就好。
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
| #include <bits/stdc++.h>
#define mo 1000000007
using namespace std;
int T, n, a[200005], can[200005], num[200];
long long ji[200005], cnt;
int main(){
cin >> T, ji[1] = ji[0] = 1;
for(int i = 2; i <= 200000; i++) ji[i] = (ji[i - 1] * i) % mo;
while(T--){
cin >> n, cnt = 0;
for(int i = 1; i <= n; i++) cin >> a[i], can[i] = 0;
for(int j = 0; j < 32; j++){
int pro = 1 << j; num[j] = 0;
for(int i = 1; i <= n; i++) if(a[i] & pro) num[j]++;
}
for(int j = 0; j < 32; j++){
int pro = 1 << j;
for(int i = 1; i <= n; i++) if((a[i] & pro) && num[j] != n) can[i] = 1;
}
for(int i = 1; i <= n; i++) if(!can[i]) cnt++;
if(cnt) cout << (1LL * cnt * (cnt - 1) % mo) * ji[n - 2] % mo << endl;
else cout << 0 << endl;
}
}
|
题目大意：C稍微写一点题意，每一次操作将一个数字的所有位数字+1,比如现在有一个数字19，进行一次操作就变成了210(9+1=10,将2位数10拆成2位),然后每组询问数字n经过m次操作之后得到的数字有多少位。
解法：实际上对于数字n来说每一位都是独立的，抓住这个性质之后直接预处理出对于0~9这9个数字单独一个数进行多少次操作后得到的位数，令dp[i][j]表示数字i经过j次操作之后是几位数，在计算这个的时候，再定义num[i][j]表示对于当前情况，操作了j次之后数字i的个数，具体的转移见代码，还是比较显然的。
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
| #include <bits/stdc++.h>
#define mo 1000000007
using namespace std;
int T;
long long num[10][200005], dp[10][200005], ans, n, m;
void init(int x){
memset(num, 0, sizeof(num));
num[x][0] = 1, dp[x][0] = 1;
for(int i = 1; i <= 200000; i++){
dp[x][i] = (dp[x][i - 1] + num[9][i - 1]) % mo;
for(int j = 0; j <= 9; j++)
num[j][i] = (num[(j - 1 + 10) % 10][i - 1]) % mo;
num[1][i] = (num[1][i] + num[9][i - 1]) % mo;
}
}
int main(){
for(int i = 0; i <= 9; i++) init(i);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin >> T;
while(T--){
cin >> n >> m;
while(n) ans = (ans + dp[n % 10][m] ) % mo, n /= 10;
cout << ans << '\n', ans = 0;
}
}
|
题目大意：D题给了一个序列，条件1：若某一段连续的数字的gcd是这段数字中最小的数字(设为w)，则这段数字的左端点向右端点连一条权值为w的边。条件2：若某两个点i,j(i<j)相邻，则从i向j连一条权值为给定值P的边。最后在所有连边连出来的图上求最小生成树。
解法：显然，假如某一条边的因为满足条件1产生的，而这条边的权值w>P，则这样一条边是一定不优的。所以我们从小到大枚举满足w<P的边，加完这些边之后做MST就是答案。而这样的边也会有很多，所以继续模拟我们刚才得到的算法，当前我们枚举的是最小值w1，最小值向左有一段数和最小值的gcd是最小值本身，向右也有这么一段数，即我们去找w1向左连续的、满足和w1的gcd为w1的最左的位置为l，向右同理的找到右端点r，那么l，r这一个区间实际上是可以通过r-l条权值为w1的边全部连通的。而由于我们枚举的顺序是从小到大，假如我们枚举到一个新的数字w2，若w2连接到了一个已经被连接好的区间内，之后w2就无法在这个方向继续扩展了(因为继续扩展的话不会更优，之前扩展的边权一定不大于当前的边权)。所以综上，一开始整个序列我们令其为n个长度为1的区间(即每个数都是一个长为1的区间)，我们从小到大枚举边权，依次针对这个边权从它所处的位置向左和向右分别扩展区间，连接到最后没有连起来的区间之间全部通过边权为P的边相连即可，这样的生成树就是一棵MST。
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
| #include <bits/stdc++.h>
#define mo 1000000007
using namespace std;
struct po{
int a, b;
}p[200005];
int T, n, v[200005], a[200005];
long long P, ans, cnt;
bool cmp(po x, po y){
return x.a < y.a;
}
int main(){
cin >> T;
while(T--){
cin >> n >> P, cnt = n - 1;
for(int i = 1; i <= n; i++) cin >> a[i], p[i].a = a[i], p[i].b = i, v[i] = 0;
sort(p + 1, p + 1 + n, cmp);
for(int i = 1; i <= n && p[i].a < P; i++) if(!v[p[i].b]){
v[p[i].b] = 1;
for(int j = p[i].b + 1; j <= n && __gcd(a[j], a[p[i].b]) == a[p[i].b]; j++){
ans += p[i].a, cnt--;
if(v[j]) break;
v[j] = 1;
}
for(int j = p[i].b - 1; j && __gcd(a[j], a[p[i].b]) == a[p[i].b]; j--){
ans += p[i].a, cnt--;
if(v[j]) break;
v[j] = 1;
}
}
cout << ans + cnt * P << endl, ans = 0;
}
return 0;
}
|
题目大意：一个序列，要通过一些操作让这个序列的每一个数字都变成同样的。操作是选择两个位置i,j，然后给a[i]加上x(正整数)并且给a[j]减去x，而这样的操作存在一个限制：当某一个数被变大之后，他就不可能再被变小。而这样一次操作会产生|i-j|*x的代价，若给出序列的某一个排列方式排完之后，无论怎样操作使得最终序列的每一个数字都变成同样的，所花费的代价都是相等的话，这样的排列就是棒的，要求给出这样的排列的数量。
解法：观察题面，对于一个既定的数组而言，其最小代价可通过贪心得到，既从左到右，每一个不满足当前情况的数（小于平均值）去寻找最近的大于平均值的数进行满足既可。反之，最大代价也是同样的方法，只不过寻找最远的大于平均值的数进行满足既可。
所以，当最小值与最大值相同时，大胆猜测，两部分若个数均大于1，则这两部分均连续(简单证一下，假如不连续，那么一定存在某一个部分的数字，左边和右边都有另一部分的数字，这个时候就可以通过上述的贪心操作得到代价不同的方式，不符合题意；或者找这样一个情况然后拿代价产生的公式化简一下，也可以证得)。若某一部分仅有一个，则所有情况均可(因为所有选的点对中一定有这个点，上边的产生代价的公式随手化一下就可以证明)。最后处理不需要操作的点，假如有num3个，直接给答案乘以n个位置选num3个位置的方案数即可。
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
| #include <bits/stdc++.h>
#define mo 1000000007
using namespace std;
long long ji[200005], inv[200005], num1, num2, num3, sum, a[200005], n, ans, Inv = 1, cnt;
long long qpow(long long x, long long y){
long long ret = 1;
while(y){
if(y & 1) ret *= x, ret %= mo;
x *= x, x %= mo, y >>= 1;
}
return ret;
}
int main(){
ji[0] = 1;
for(int i = 1; i <= 200000; i++) ji[i] = ji[i - 1] * i % mo;
for(int i = 0; i <= 200000; i++) inv[i] = qpow(ji[i], mo - 2);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
sort(a + 1, a + 1 + n), a[0] = a[n + 1] = -1;
for(int i = 1; i <= n + 1; i++){
if(a[i] == a[i - 1]) cnt++;
else{
Inv *= inv[cnt], Inv %= mo;
cnt = 1;
}
}
for(int i = 1; i <= n; i++) num1 += a[i] < (sum / n), num2 += a[i] > (sum / n);
num3 = n - num1 - num2;
if(sum / n * n != sum) ans = 0;
else if(num1 == 0 || num2 == 0) ans = 1;
else if(num1 == 1 || num2 == 1) ans = ji[n] * Inv % mo;
else{
ans = 2 * Inv % mo;
ans = ans * ji[num1] % mo * ji[num2] % mo * ji[num3] % mo;
ans = ans * ji[n] % mo * inv[num3] % mo * inv[n - num3] % mo;
}
cout << ans << endl;
return 0;
}
|
题目大意：俩数组a，b，对应位置元素做差的和是代价，现在可以选择b数组中的两个位置进行元素交换，问交换后的最小代价(原题面的数学描述比较简洁)。
解法：观察交换，假如选择的两个位置i,j，ai<bi且aj<bj，则这样交换并不会更优，那么实际上选择的方案对是i位置和j位置，元素大小是要反着的，即 ai>bi且aj<bj 或 ai<bi且aj>bj 这样的(这里其实并不需要严格小于或者大于，等于也是可以的，反正最后取最优情况的时候假如全是等号贡献也是0，不影响)。所以我们就把原来的点对(因为位置绑定了a和b数组的对应元素，就把这个同一位置的俩数当做点对)分成两个集合，分类依据是a数组的该元素是否大于b数组的对应元素，分完类之后按照我们之前得到的条件，答案一定是第一个集合出一个位置，第二个集合出一个位置。之后就是怎么得到最优的答案了，假设没有经过修改的答案是sum，我们选择的点对是上述的i和j(不妨设i是第一个集合，j是第二个集合，再不妨设bi≤aj≤ai≤bj，通过依据点对中最小的数字排序可以做到这一点)，那么修改过后的答案就是sum-2*(ai-aj)，至于剩下维护这个的最大值以及对上述“不妨设”的其他设定情况，可以通过分类讨论解决。
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
| #include<bits/stdc++.h>
using namespace std;
long long sum, ans, n, mx[2];;
struct po{
long long x, y, z;
}p[200005];
bool cmp(po x, po y){
return x.x < y.x;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> p[i].x;
for(int i = 1; i <= n; i++) cin >> p[i].y, sum += abs(p[i].y - p[i].x);
for(int i = 1; i <= n; i++) if(p[i].x > p[i].y)
p[i].z = 1, swap(p[i].x, p[i].y);
sort(p + 1, p + n + 1, cmp);
for(int i = 1; i <= n; i++){
ans = max(ans, min(mx[!p[i].z], p[i].y) - p[i].x);
mx[p[i].z] = max(mx[p[i].z], p[i].y);
}
cout << sum - ans * 2 << endl;
return 0;
}
|
总结
虽然这场是印度场，但是总的来说题面的表达还是十分简洁以及高效的。而所有问题都可以通过巧妙的解法，以一个很小的代码量完成，并没有出现题面恶心人\解法恶心人的情况，故而这套题坐下来的感觉还是十分不错的。