The 2017 China Collegiate Programming Contest, Hangzhou Site Solution

A: Super_palindrome

题面：给出一个字符串，求改变最少的字符个数使得这个串所有长度为奇数的子串都是回文串

思路：显然，这个字符串肯定要改成所有奇数位相同并且所有偶数位相同

那统计一下奇数位上哪个字符出现的个数最多，偶数位上哪个字符出现的个数最多

答案就是 n 减去它们

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define N 110
 6 #define INF 0x3f3f3f3f
 7 
 8 int t;
 9 char s[N];
10 
11 int odd[200];
12 int even[200];
13 
14 int main()
15 {
16     scanf("%d", &t);
17     while (t--)
18     {
19         scanf("%s", s);
20         memset(odd, 0, sizeof odd);
21         memset(even, 0, sizeof even);
22         int len = strlen(s);
23         int Maxodd = 0, Maxeven = 0;
24         for (int i = 0; i < len; ++i)
25         {
26             if (i & 1)
27                 odd[s[i]]++, Maxodd = max(Maxodd, odd[s[i]]);
28             else
29                 even[s[i]]++, Maxeven = max(Maxeven, even[s[i]]);
30         }
31         printf("%d
", len - Maxodd - Maxeven);
32     }
33     return 0;
34 }

View Code

B: Master of Phi

题意：给定一个n，接下来n行输入p和q代表数字num有q个p因子，计算题中式子

思路:根据题中数字提取出公因数n，然后每个式子只是每个数的质因子乘上（1-1/p）。对于所有要求的式子，对于每个质因子p仅可能0-q中可能，所以所求式子就变成了∏((1-1/pi)*qi+1)所得值。

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define N 110
 6 
 7 typedef long long ll;
 8 
 9 const int MOD = 998244353;
10 
11 inline ll qpow(ll x,ll n)
12 {
13     ll res = 1;
14     while(n)
15     {
16         if(n & 1) res = (res * x) % MOD;
17         x = (x * x) % MOD;
18         n >>= 1;
19     }
20     return res;
21 }
22 
23 int m;
24 ll p[N],q[N];
25 ll tmp[N];
26 
27 int main()
28 {
29     int t;
30     scanf("%d",&t);
31     while(t--)
32     {
33         scanf("%d",&m);
34         ll ans = 1;
35         for(int i = 1;i <= m; ++i)
36         {
37             scanf("%lld %lld",&p[i], &q[i]);
38             p[i] %= MOD;
39             ans = (ans * qpow(p[i], q[i])) % MOD;
40             p[i] = (p[i] - 1) * qpow(p[i], MOD - 2) % MOD;
41             tmp[i] = p[i] * q[i] % MOD;
42         }
43         for(int i = 1; i <= m; ++i)
44         {
45             ans = (ans * (tmp[i] + 1) % MOD) % MOD;
46         }
47         printf("%lld
",ans);
48     }
49     return 0;
50 }

View Code

C: Hakase and Nano

题面：有n堆石子，两个人轮流取，Hakase 一轮必须取两次，另一个人一轮取一次，最后取光的人胜利，给出先后手顺序，判断哪个人必胜

思路：通过两个人的简单模拟，可以发现Hakase的优势很大，它的必败情况很少。

以下四种为必败情况

H先手，并且所有石子堆都是1，并且石子堆数%3==0

H后手，并且所有石子堆都是1，并且石子堆数%3==1

H后手，并且有一个石子堆的个数不是1，其它全是1，并且石子堆数%3==0 || %3 == 1

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define N 1000010
 6 
 7 int n, d;
 8 int arr[N];
 9 
10 int main()
11 {
12     int t;
13     scanf("%d",&t);
14     while(t--)
15     {
16         scanf("%d %d",&n,&d);
17         int num = 0;
18         for(int i = 1; i <= n; ++i)
19         {
20             scanf("%d",&arr[i]);
21             if(arr[i] > 1) num++;
22         }
23         if(num >= 2)
24         {
25             puts("Yes");
26             continue;
27         }
28         if(d == 1)
29         {
30             if(num == 0 && n % 3 == 0) puts("No");
31             else puts("Yes");
32         }
33         else if(d == 2)
34         {
35             if(num == 0 && n % 3 == 1) puts("No");
36             else if(num == 1 && (n % 3 == 0 || n % 3 == 1)) puts("No");
37             else puts("Yes");
38         }
39     }
40     return 0;
41 }

View Code

D:Master of Random

题意：给出一棵树，每个节点都有一个权值，对于第i个节点，它的father是random(0, i-1)，求任意一颗子树的权值期望。

题意：对于一颗子树，它的权值为自身权值加上除自己以外的权值期望。对于节点i，那么i+1是节点i的子节点的概率为1/(1 + i)，对于第i+2个节点是节点i的子节点的概率为1/(i+2)+1/(i+1)*1/(i+2)=1/(i+1)，从而发现后面每个节点是i的子节点的概率都为1/(i+1)。那么第i个节点的权值期望就为ai+1/(i+1)*∑aj(j from i+1 to n-1)

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 
 7 const int MOD = 998244353;
 8 
 9 #define N 100010
10 
11 inline ll qpow(ll x,ll n)
12 {
13     ll res = 1;
14     while(n)
15     {
16         if(n & 1) res = (res * x) % MOD;
17         x = (x * x) % MOD;
18         n >>= 1;
19     }
20     return res;
21 }
22 
23 int n;
24 ll a[N];
25 ll sum[N];
26 
27 int main()
28 {
29     int t;
30     scanf("%d",&t);
31     while(t--)
32     {
33         scanf("%d",&n);
34         for(int i = 0;i < n; ++i)
35         {
36             scanf("%lld",&a[i]);
37         }
38         memset(sum, 0, sizeof sum);
39         for(int i = n - 1; i >= 0; --i)
40         {
41             sum[i] = (sum[i + 1] + a[i]) % MOD;
42         }
43         ll ans = 0;
44         for(int i = 0;i < n; ++i)
45         {
46             ans = (ans + (a[i] + sum[i + 1] * qpow(i + 1, MOD - 2) % MOD) % MOD) % MOD;
47         }
48         ans = (ans * qpow(n, MOD - 2)) % MOD;
49         printf("%lld
", ans);
50     }
51     return 0;
52 }

View Code

E:Master of Subgraph

留坑。

F:Hearthock

留坑。

G:Marriage

留坑。

H:Master of Connexted Component

留坑。

I:Master of Matrix

留坑

J:Master of GCD

题意：有n个数刚开始都是1，然后每次操作使得(l, r)区间的所有数都乘上x，x == 2 || x ==3 求所有数的最大公约数

思路：显然，我们找出乘2最少的次数n，以及乘3最少的次数m 答案就是2^n * 3*m

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 const int INF = 0x3f3f3f3f;
 7 const int p = 998244353;
 8 #define N 100010
 9 
10 int n, m;
11 
12 ll sum_2[N], sum_3[N];
13 
14 ll qpow(ll x,ll n)
15 {
16     ll res = 1;
17     while(n)
18     {
19         if(n & 1) res = (res * x) %p;
20         x = (x * x) % p;
21         n >>= 1;
22     }
23     return res;
24 }
25 
26 int main()
27 {
28     int t;
29     scanf("%d",&t);
30     while(t--)
31     {
32         memset(sum_2, 0, sizeof sum_2);
33         memset(sum_3, 0, sizeof sum_3);
34         scanf("%d %d",&n,&m);
35         for(int i = 0; i < m; ++i)
36         {
37             int l,r,x;
38             scanf("%d %d %d",&l ,&r ,&x);
39             if(x == 2)
40             {
41                 sum_2[l]++;
42                 sum_2[r + 1]--;
43             }
44             else 
45             {
46                 sum_3[l]++;
47                 sum_3[r + 1]--;
48             }
49         }
50         ll Min_2 = INF;
51         ll Min_3 = INF;
52         ll op_2 = 0, op_3 = 0;
53         for(int i = 1; i <= n; ++i)
54         {
55             op_2 += sum_2[i];
56             Min_2 = min(Min_2, op_2);
57             op_3 += sum_3[i];
58             Min_3 = min(Min_3, op_3);
59         }
60         ll ans = 1;
61         ans = (ans * qpow(2, Min_2)) % p;
62         ans = (ans * qpow(3, Min_3)) % p;
63         printf("%lld
",ans);
64     }    
65     return 0;
66 }

View Code

K:Master of Sequence

题意：两组序列，三种操作。

思路：ai很小，我们可以考虑对ai作文章。可以把那个式子拆开看成 floor(t / ai) - (bi / ai)

然后预处理出bi / ai 的整数部分和余数部分并且将所有整数部分相加得到sum

然后查询的时候二分枚举t，查询的时候用去考虑对于同一个ai, 如果t/ai 的余数小于 bi/ai 的余数那就需要多减一然后加上整数部分

然后前缀和处理一下，二分的时间复杂度为logn * 1000

修改的时间复杂度为O(1000)

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 #define N 100010
  6 
  7 #define M 1010
  8 
  9 #define ll long long
 10 
 11 #define INFLL (ll)1e12
 12 
 13 int arr[N], brr[N];
 14 
 15 int a[M][M];
 16 
 17 ll sum;
 18 
 19 int n, m;
 20 
 21 inline bool check(ll mid, ll k)
 22 {
 23     ll tot = -sum;
 24     for (int i = 1; i <= 1000; ++i)
 25     {
 26         ll tmp = mid / i;
 27         ll MOD = mid % i;
 28         tot += tmp * a[i][0];
 29         tot -= a[i][MOD + 1];
 30     }
 31     return tot >= k;
 32 }
 33 
 34 int main()
 35 {
 36     int t; scanf("%d", &t);
 37     while (t--)
 38     {
 39         scanf("%d%d", &n, &m);
 40         for (int i = 1; i <= n; ++i)
 41             scanf("%d", arr + i);
 42         for (int i = 1; i <= n; ++i)
 43             scanf("%d", brr + i);
 44         memset(a, 0, sizeof a);
 45         sum = 0;
 46         for (int i = 1; i <= n; ++i)
 47         {
 48             a[arr[i]][brr[i] % arr[i]]++;
 49             sum += brr[i] / arr[i];
 50         }
 51         for (int i = 1; i <= 1000; ++i)
 52         {
 53             for (int j = 999; j >= 0; --j)
 54             {
 55                 a[i][j] += a[i][j + 1];
 56             }
 57         }
 58         int op, x, y, k;
 59         while (m--)
 60         {
 61             scanf("%d", &op);
 62             if (op == 1)
 63             {
 64                 scanf("%d%d", &x, &y);
 65                 int tmp = arr[x]; arr[x] = y;
 66                 for (int i = 0; i <= brr[x] % tmp; ++i)
 67                     a[tmp][i]--;
 68                 sum -= brr[x] / tmp;
 69                 sum += brr[x] / arr[x];
 70                 for (int i = 0; i <= brr[x] % arr[x]; ++i)
 71                     a[arr[x]][i]++;
 72             }
 73             else if (op == 2)
 74             {
 75                 scanf("%d%d", &x, &y);
 76                 int tmp = brr[x]; brr[x] = y;
 77                 for (int i = 0; i <= tmp % arr[x]; ++i)
 78                     a[arr[x]][i]--;
 79                 sum -= tmp / arr[x];
 80                 sum += brr[x] / arr[x];
 81                 for (int i = 0; i <= brr[x] % arr[x]; ++i)
 82                     a[arr[x]][i]++;
 83             }
 84             else if (op == 3)
 85             {
 86                 scanf("%d", &k);
 87                 ll l = 0, r = INFLL, ans = -1;
 88                 while (r - l >= 0)
 89                 {
 90                     ll mid = (l + r) >> 1;
 91                     if (check(mid, (ll)k))
 92                     {
 93                         ans = mid;
 94                         r = mid - 1;
 95                     }
 96                     else
 97                     {
 98                         l = mid + 1;
 99                     }
100                 }
101                 printf("%lld
", ans);
102             }
103         }
104     }
105     return 0;
106 }

View Code

L:Mod, Xor and Everything

留坑。