• 大三第三周学习笔记

    周一

    Guess

    打了网络赛，还可以，但是不知道哪里可以补题，就写写思路吧

    这道题关键就是从特例推出普遍规律，先讨论简单的情况

    稍微分析一下可以发现，只有2的次幂影响结果，所以设两数为pt 2pt

    t为奇数，p为2的次幂，t不影响结果所以设t=1

    如果是1 2   显然2的人赢

    如果是4 2   2的人说自己i dont know那么到4的时候就知道自己不是1，4的人赢

    如果是4 8   4的人说自己i dont know  8的人就知道自己不是2，8的人赢

    总结一下，数字大的人赢，这里有点递推的感觉。

    Mutiple Set

    这题不难，不要有畏难情绪，自己给自己设限

    稍微推一下，设l为l/x上取整，r为r/x上取整，那么K=2^(r-l-1)x(l+r)(r-l+1)

    这个式子的变量是x，l和r是题目给的。可以发现x是K的因子，对于这个式子，只要确定了x，那么可以计算l和r，那么就可以验证是否等于K

    因子需要求K的所有因子，K是10^14,直接根号K枚举的话加上多组数据会T。因此考虑对K进行质因数分解，通过枚举指数来枚举因子。

    这里有两种方法，一种是预处理10^7的质数，用这些质数去质因数分解，一种是大数分解。

    poj 1811（素数测试和大数质因数分解）

    主要是熟悉板子

    Miller_Rabin素数测试可以迅速测试一个大数（long long级别）是否为质数

    pollard_rho算法可以对一个long long级别的数质因数分解。

    注意板子中质因数分解的结果是无序重复的素数，如24就是2 3 2 2

    1. #include <cstdio>
    2. #include <ctime>
    3. #include <cstdlib>
    4. #include <algorithm>
    5. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    6. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    7. using namespace std;
    8.  
    9. typedef long long ll;
    10. const int S = 8;
    11.  
    12. ll mult_mod(ll a, ll b, ll c)
    13. {
    14.     a %= c;
    15.     b %= c;
    16.     ll ret = 0, tmp = a;
    17.     while(b)
    18.     {
    19.         if(b & 1) 
    20.         {
    21.             ret += tmp;
    22.             if(ret > c) ret -= c;
    23.         }
    24.         tmp <<= 1;
    25.         if(tmp > c) tmp -= c;
    26.         b >>= 1;
    27.     }
    28.     return ret;
    29. }
    30.  
    31. ll pow_mod(ll a, ll n, ll mod)
    32. {
    33.     ll ret = 1;
    34.     ll temp = a % mod;
    35.     while(n)
    36.     {
    37.         if(n & 1) ret = mult_mod(ret, temp, mod);
    38.         temp = mult_mod(temp, temp, mod);
    39.         n >>= 1;
    40.     }
    41.     return ret;
    42. }
    43.  
    44. bool check(ll a, ll n, ll x, ll t)
    45. {
    46.     ll ret = pow_mod(a, x, n);
    47.     ll last = ret;
    48.     _for(i, 1, t)
    49.     {
    50.         ret = mult_mod(ret, ret, n);
    51.         if(ret == 1 && last != 1 && last != n - 1) return true;
    52.         last = ret;
    53.     }
    54.     if(ret != 1) return true;
    55.     return false;
    56. }
    57.  
    58. bool Miller_Rabin(ll n)
    59. {
    60.     if(n < 2) return false;
    61.     if(n == 2) return true;
    62.     if((n & 1) == 0) return false;
    63.     ll x = n - 1, t = 0;
    64.     while((x & 1) == 0) x >>= 1, t++;
    66.     srand(time(0));
    67.  
    68.     rep(i, 0, S)
    69.     {
    70.         ll a = rand() % (n - 1) + 1;
    71.         if(check(a, n, x, t)) return false;
    72.     }
    73.     return true;
    74. }
    75.  
    76. ll factor[100]; //储存质因数分解结果 有重复 无序
    77. int tol;  //标号0~tol-1
    78.  
    79. ll gcd(ll a, ll b)
    80. {
    81.     ll t;
    82.     while(b)
    83.     {
    84.         t = a;
    85.         a = b;
    86.         b = t % b;
    87.     }
    88.     if(a >= 0) return a;
    89.     return -a;
    90. }
    91.  
    92. ll pollard_rho(ll x, ll c)
    93. {
    94.     ll i = 1, k = 2;
    95.     srand(time(0));
    96.     ll x0 = rand() % (x - 1) + 1;
    97.     ll y = x0;
    98.     while(1)
    99.     {
    100.         i++;
    101.         x0 = (mult_mod(x0, x0, x) + c) % x;
    102.         ll d = gcd(y - x0, x);
    103.         if(d != 1 && d != x) return d;
    104.         if(y == x0) return x;
    105.         if(i == k) y = x0, k += k;
    106.     }
    107. }
    108.  
    109. void findfac(ll n, ll k)
    110. {
    111.     if(n == 1) return;
    112.     if(Miller_Rabin(n))
    113.     {
    114.         factor[tol++] = n;
    115.         return;
    116.     }
    117.     ll p = n;
    118.     int c = k;
    119.     while(p >= n) p = pollard_rho(p, c--);
    120.     findfac(p, k);
    121.     findfac(n / p, k);
    122. }
    123.  
    124. int main()
    125. {
    126.     int T; scanf("%d", &T);
    127.     while(T--)
    128.     {
    129.         ll n;
    130.         scanf("%lld", &n);
    131.         if(Miller_Rabin(n)) puts("Prime");
    132.         else
    133.         {
    134.             tol = 0;
    135.             findfac(n, 107);
    136.             ll ans = factor[0];
    137.             rep(i, 1, tol)
    138.                 ans = min(ans, factor[i]);
    139.             printf("%lld\n", ans);
    140.         }
    141.     }
    142.     return 0;
    143. }

    Tree Partition（二分+贪心+树上dp）

    二分答案读完题就知道了，关键是确定了最大值后，怎么操作使得删掉的边最少，这是这道题的关键。

    这里要用到树形dp，dp[u]表示以u为根的子树符合条件的情况下，u所在的连通块的权值和是多少。

    那么每次u自己和全部dp[v]算上，如果超过了最大值，那么就考虑删边。

    为了使得删的边数最少，一次删边要去掉尽可能多的权值，所以删去最大的dp[v],还是超就删第二大的dp[v]以此类推。

    这样子贪心下来就可以求出删了多少边了

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7. const int N = 2e5 + 10;
    8. int a[N], n, k, mx, cnt;
    9. vector<int> g[N];
    10. ll key, dp[N];
    11.  
    12. void dfs(int u, int fa)
    13. {
    14.     dp[u] = a[u];
    15.     ll sum = a[u];
    16.     vector<ll> ve;
    17.     for(int v: g[u])
    18.     {
    19.         if(v == fa) continue;
    20.         dfs(v, u);
    21.         ve.push_back(dp[v]);
    22.         sum += dp[v];
    23.     }
    24.  
    25.     if(!ve.size()) return;
    26.     sort(ve.begin(), ve.end(), greater<ll>());
    27.     rep(i, 0, ve.size())
    28.     {
    29.         if(sum > key) sum -= ve[i], cnt++;
    30.         else break;
    31.     }
    32.     dp[u] = sum;
    33. }
    34.  
    35. bool check(ll x)
    36. {
    37.     cnt = 0;
    38.     key = x;
    39.     dfs(1, 0);
    40.     return cnt <= k;
    41. }
    42.  
    43. int main()
    44. {
    45.     int T, kase = 0; 
    46.     scanf("%d", &T);
    47.     while(T--)
    48.     {
    49.         mx = 0;
    50.         scanf("%d%d", &n, &k); k--;
    51.         _for(i, 1, n) g[i].clear();
    52.         _for(i, 1, n - 1)
    53.         {
    54.             int u, v;
    55.             scanf("%d%d", &u, &v);
    56.             g[u].push_back(v);
    57.             g[v].push_back(u);
    58.         }
    59.         _for(i, 1, n) scanf("%d", &a[i]), mx = max(mx, a[i]);
    60.         
    61.         ll l = mx - 1, r = 1e15;
    62.         while(l + 1 < r)
    63.         {
    64.             ll m = l + r >> 1;
    65.             if(check(m)) r = m;
    66.             else l = m;
    67.         }
    68.         printf("Case #%d: %lld\n", ++kase, r);
    69.     }
    70.  
    71.     return 0;
    72. }

    C. Digital Logarithm（思维）

    很容易发现操作几次就变1了，考虑怎么让它最小。

    注意到每次操作都是变小的，所以如果一个数是最大的，大于另一个序列的最大值，那么它一定要变小，这个是必须要操作的。因此就根据这一点，比较两者的最大值，相等就不用操作，否则就变小，用优先队列实现。

    cf题解的stl用的很秀啊，代码很短。

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. int main()
    7. { 
    8.     int T; scanf("%d", &T);
    9.     while(T--)
    10.     {
    11.         int n; scanf("%d", &n);
    12.         vector<int> a(n), b(n);
    13.         rep(i, 0, n) scanf("%d", &a[i]);
    14.         rep(i, 0, n) scanf("%d", &b[i]);
    15.  
    16.         int ans = 0;
    17.         priority_queue<int> qa(a.begin(), a.end());
    18.         priority_queue<int> qb(b.begin(), b.end());
    19.         while(!qa.empty())
    20.         {
    21.             if(qa.top() == qb.top())
    22.             {
    23.                 qa.pop(); qb.pop();
    24.                 continue;
    25.             }
    26.             else if(qa.top() > qb.top())
    27.             {
    28.                 qa.push(to_string(qa.top()).size());
    29.                 qa.pop(); ans++;
    30.             }
    31.             else
    32.             {
    33.                 qb.push(to_string(qb.top()).size());
    34.                 qb.pop(); ans++;
    35.             }
    36.         }
    37.         printf("%d\n", ans);
    38.     }
    39.  
    40.     return 0;
    41. }

    但我比赛时是另一个思路，大致是先去重，然后把二位数以上的操作，再去重，然后把非1的操作。但是我写去重的时候用了很多stl，常数很大，赛时AC，赛后T了……

    其实就排个序然后用两个指针即可，不用弄那么复杂。改成这么写后AC了

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 2e5 + 10;
    7. int a[N], b[N], visa[N], visb[N], n;
    8. vector<int> va, vb;
    9.  
    10. int get(int x)
    11. {
    12.     int res = 0;
    13.     while(x)
    14.     {
    15.         x /= 10;
    16.         res++;
    17.     }
    18.     return res;
    19. }
    20.  
    21. void deal(int a[], int b[], int n)
    22. {
    23.     _for(i, 1, n) visa[i] = visb[i] = 0;
    24.     sort(a + 1, a + n + 1);
    25.     sort(b + 1, b + n + 1);
    26.  
    27.     int pa = 1, pb = 1;
    28.     while(pa <= n && pb <= n)
    29.     {
    30.         if(a[pa] == b[pb])
    31.         {
    32.             visa[pa] = visb[pb] = 1;
    33.             pa++; pb++;
    34.         }
    35.         else if(a[pa] > b[pb]) pb++;
    36.         else pa++;
    37.     }
    38.  
    39.     va.clear();
    40.     vb.clear();
    41.     _for(i, 1, n)
    42.         if(!visa[i])
    43.             va.push_back(a[i]);
    44.     _for(i, 1, n)
    45.         if(!visb[i])
    46.             vb.push_back(b[i]);
    47. }
    48.  
    49. int main()
    50. { 
    51.     int T; scanf("%d", &T);
    52.     while(T--)
    53.     {
    54.         scanf("%d", &n);
    55.         _for(i, 1, n) scanf("%d", &a[i]);
    56.         _for(i, 1, n) scanf("%d", &b[i]);
    57.         deal(a, b, n);
    58.  
    59.         int ans = 0;
    60.         rep(i, 0, va.size())
    61.             if(va[i] >= 10)
    62.             {
    63.                 va[i] = get(va[i]);
    64.                 ans++;
    65.             }
    66.         rep(i, 0, vb.size())
    67.             if(vb[i] >= 10)
    68.             {
    69.                 vb[i] = get(vb[i]);
    70.                 ans++;
    71.             }
    72.         
    73.         int cnt = 0;
    74.         for(int x: va) a[++cnt] = x;
    75.         cnt = 0;
    76.         for(int x: vb) b[++cnt] = x;
    77.         deal(a, b, cnt);
    78.  
    79.         rep(i, 0, va.size()) 
    80.             if(va[i] > 1)
    81.                 ans++;
    82.         rep(i, 0, vb.size()) 
    83.             if(vb[i] > 1)
    84.                 ans++;
    85.         printf("%d\n", ans);
    86.     }
    87.  
    88.     return 0;
    89. }

    周二

    D. Letter Picking（dp）

    之前做过一道优点类似的，也是赢平局输，用dp做的，这题也类似。

    考试时用dp过的，但是写的比较复杂，但大体思路和题解是一致的

    我是在状态转移分类讨论的，而题解是直接取min max的，写起来很方便

    令1为Alice，0为Draw，-1为Bob

    那么Alice的目标是使值变大，Bob是使值变小，所以就转化成了博弈里面的min-max搜索。

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 2000 + 10;
    7. int dp[N][N], n;
    8. char s[N];
    9.  
    10. int check(char a, char b)
    11. {
    12.     return a > b ? 1 : (a == b ? 0 : -1);
    13. }
    14.  
    15. int main()
    16. { 
    17.     int T; scanf("%d", &T);
    18.     while(T--)
    19.     {
    20.         scanf("%s", s + 1);
    21.         n = strlen(s + 1);
    22.  
    23.         _for(i, 1, n - 1)
    24.         {
    25.             if(s[i] == s[i + 1]) dp[i][i + 1] = 0;  
    26.             else dp[i][i + 1] = 1;  
    27.         }
    28.  
    29.         for(int len = 4; len <= n; len += 2)
    30.             _for(l, 1, n)
    31.             {
    32.                 int r = l + len - 1;
    33.                 if(r > n) break;
    34.  
    35.                 int cl = 1;
    36.                 if(dp[l + 1][r - 1] != 0) cl = min(cl, dp[l + 1][r - 1]);
    37.                 else cl = min(cl, check(s[l], s[r]));
    38.                 if(dp[l + 2][r] != 0) cl = min(cl, dp[l + 2][r]);
    39.                 else cl = min(cl, check(s[l], s[l + 1]));
    40.  
    41.                 int cr = 1;
    42.                 if(dp[l + 1][r - 1] != 0) cl = min(cl, dp[l + 1][r - 1]);
    43.                 else cr = min(cr, check(s[r], s[l]));
    44.                 if(dp[l][r - 2] != 0) cl = min(cl, dp[l][r - 2]);
    45.                 else cr = min(cr, check(s[r], s[r - 1]));
    46.  
    47.                 dp[l][r] = max(cl, cr);
    48.             }
    49.  
    50.         if(dp[1][n] == 1) puts("Alice");
    51.         else if(dp[1][n] == -1) puts("Bob");
    52.         else puts("Draw");
    53.     }
    54.  
    55.     return 0;
    56. }

    还有一种O(n)的做法，比赛时我就猜测Bob不可能赢，我尝试构造了Bob赢得情况没构造出来。

    如果有了这个结论，那么其实只要判断什么时候平局即可，不是平局就是Alice赢

    如果是平局，那么就是两边拿到字符串是一样的，考虑什么时候会一样。

    因为每次拿都是两侧的，或者一侧两个，那么需要它们是一样的。

    两侧一样的就是对称的，一侧两个就是aabbcc这样

    那么都存在呢，可以发现可以外面是对称的，里面是aabbcc的，那么判断是否是这样的串就可以了

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 2000 + 10;
    7. char s[N];
    8. int n;
    9.  
    10. int main()
    11. { 
    12.     int T; scanf("%d", &T);
    13.     while(T--)
    14.     {
    15.         scanf("%s", s + 1);
    16.         n = strlen(s + 1);
    17.  
    18.         int l = 1, r = n;
    19.         while(l < r && s[l] == s[r]) l++, r--;
    20.         
    21.         int flag = 1;
    22.         for(int i = l; i <= r; i += 2)
    23.             if(s[i] != s[i + 1])
    24.             {
    25.                 flag = 0;
    26.                 break;
    27.             }
    28.         puts(flag ? "Draw" : "Alice");
    29.     }
    30.  
    31.     return 0;
    32. }

    B. Appleman and Tree（树形dp）

    这种切割的，就设在以u为根的子树中，包含u的联通块即可

    还要分当前联通块是否有一个黑色，然后分类讨论即可。

    注意儿子所在联通块无黑色时不能切断

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7. const int N = 1e5 + 10;
    8. const int mod = 1e9 + 7;
    9. vector<int> g[N];
    10. ll dp[N][2];
    11. int c[N], n;
    12.  
    13. ll binpow(ll a, ll b)
    14. {
    15.     ll res = 1;
    16.     for(; b; b >>= 1)
    17.     {
    18.         if(b & 1) res = res * a % mod;
    19.         a = a * a % mod;
    20.     }
    21.     return res;
    22. }
    23.  
    24. ll inv(ll x) { return binpow(x, mod - 2); }
    25.  
    26. void dfs(int u, int fa)
    27. {
    28.     ll res = 1;
    29.     if(c[u] == 1)
    30.     {
    31.         for(int v: g[u])
    32.         {
    33.             if(v == fa) continue;
    34.             dfs(v, u);
    35.             if(c[v]) res = res * dp[v][1] % mod;
    36.             else res = res * (dp[v][1] + dp[v][0]) % mod; 
    37.         }
    38.         dp[u][1] = res;
    39.     }
    40.     else
    41.     {
    42.         for(int v: g[u])
    43.         {
    44.             if(v == fa) continue;
    45.             dfs(v, u);
    46.             if(c[v]) res = res * dp[v][1] % mod;
    47.             else res = res * (dp[v][1] + dp[v][0]) % mod; 
    48.         }
    49.         dp[u][0] = res;
    50.  
    51.         ll sum = 0;
    52.         for(int v: g[u])
    53.         {
    54.             if(v == fa) continue;
    55.             if(c[v]) sum = (sum + res) % mod;
    56.             else sum = (sum + res * inv(dp[v][1] + dp[v][0]) % mod * dp[v][1] % mod) % mod;
    57.         }
    58.         dp[u][1] = sum;
    59.     }
    60. }
    61.  
    62. int main()
    63. { 
    64.     scanf("%d", &n);
    65.     _for(i, 2, n)
    66.     {
    67.         int x; scanf("%d", &x); x++;
    68.         g[x].push_back(i);
    69.         g[i].push_back(x);
    70.     }
    71.     _for(i, 1, n) scanf("%d", &c[i]);
    72.  
    73.     dfs(1, 0);
    74.     printf("%lld\n", dp[1][1]);
    75.  
    76.     return 0;
    77. }

    周三

    D. Toss a Coin to Your Graph...（删点+图上最长路径）

    从提问的方式可以看出是二分答案

    二分一个答案，然后先删点。删点的实现可以用一个数组标记，后面遍历点的时候都要判断这是没有被删去的点。注意新图的点数要重新计算，不是n

    得到一个新图后，这时候点权没有用了，只需要判断是否存在长度大于等于k的路径

    如果有环则一定存在，否则用拓扑排序加dp求最长度。判环用拓扑排序。

    注意有-1的情况，二分的边界要注意一下

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7. const int N = 2e5 + 10;
    8. vector<int> g[N];
    9. int a[N], d[N], dp[N], ban[N], n, m;
    10. ll k;
    11.  
    12. bool check(int key)
    13. {
    14.     int cnt = 0;
    15.     _for(i, 1, n)
    16.     {
    17.         if(a[i] <= key) ban[i] = 0, cnt++, dp[i] = 1;
    18.         else ban[i] = 1;
    19.         d[i] = 0;
    20.     }
    21.  
    22.     _for(u, 1, n)
    23.         for(int v: g[u])
    24.             if(!ban[u] && !ban[v])
    25.                 d[v]++;
    26.  
    27.     queue<int> q;
    28.     vector<int> topo;
    29.     _for(i, 1, n)
    30.         if(!ban[i] && !d[i])
    31.             q.push(i);
    32.     while(!q.empty())
    33.     {
    34.         int u = q.front(); q.pop();
    35.         topo.push_back(u);
    36.         for(int v: g[u])
    37.             if(!ban[v] && --d[v] == 0)
    38.                 q.push(v);
    39.     }
    40.     if(topo.size() < cnt) return true;
    41.  
    42.     int res = 0;
    43.     for(int u: topo)
    44.         for(int v: g[u])
    45.             if(!ban[v])
    46.                 dp[v] = max(dp[v], dp[u] + 1);
    47.     for(int u: topo) res = max(res, dp[u]);
    48.     return res >= k;
    49. }
    50.  
    51. int main()
    52. { 
    53.     scanf("%d%d%lld", &n, &m, &k);  
    54.     _for(i, 1, n) scanf("%d", &a[i]);
    55.     while(m--)
    56.     {
    57.         int u, v;
    58.         scanf("%d%d", &u, &v);
    59.         g[u].push_back(v);
    60.     }
    61.  
    62.     int l = 0, r = 1e9 + 1;
    63.     while(l + 1 < r)
    64.     {
    65.         int m = l + r >> 1;
    66.         if(check(m)) r = m;
    67.         else l = m;
    68.     }
    69.     printf("%d\n", r == 1e9 + 1 ? -1 : r);
    70.  
    71.     return 0;
    72. }

    C. Where is the Pizza?（思维）

    先考虑简单的情况，c全是0

    可以发现确定了一个数，就有一堆数连着被确定，形成一个环。

    于是ai和bi连边，就会形成很多个环。

    环中的一个点确定了就都确定了，可以确定使用a或b

    因此每一个大于1的环就有两种选择

    对于c已经有数，就是已经确定了，不对答案有贡献。

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7. const int mod = 1e9 + 7;
    8. const int N = 1e5 + 10;
    9. int f[N], a[N], b[N], ban[N], siz[N], n;
    10.  
    11. ll binpow(ll a, ll b)
    12. {
    13.     ll res = 1;
    14.     for(; b; b >>= 1)
    15.     {
    16.         if(b & 1) res = res * a % mod;
    17.         a = a * a % mod;
    18.     }
    19.     return res;
    20. }
    21.  
    22. int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
    23.  
    24. void Union(int x, int y)
    25. {
    26.     int fx = find(x), fy = find(y);
    27.     if(fx == fy) return;
    28.     siz[fx] += siz[fy];
    29.     f[fy] = fx;
    30. }
    31.  
    32. int main()
    33. { 
    34.     int T; scanf("%d", &T);
    35.     while(T--)
    36.     {
    37.         scanf("%d", &n);
    38.         _for(i, 1, n) f[i] = i, ban[i] = 0, siz[i] = 1;
    39.         _for(i, 1, n) scanf("%d", &a[i]);
    40.         _for(i, 1, n) scanf("%d", &b[i]);
    41.  
    42.         _for(i, 1, n) Union(a[i], b[i]);
    43.         _for(i, 1, n)
    44.         {
    45.             int x; scanf("%d", &x);
    46.             ban[find(x)] = 1;
    47.         }
    48.  
    49.         int cnt = 0;
    50.         _for(i, 1, n)
    51.             if(f[i] == i && !ban[i] && siz[i] > 1)
    52.                 cnt++;
    53.         printf("%lld\n", binpow(2, cnt));
    54.     }
    55.  
    56.     return 0;
    57. }

    C. Tokitsukaze and Two Colorful Tapes（并查集找环+贪心）

    这题的关键就是像上一题一样，ai向bi连边可以形成环。如果没有做过上一题，很难想到

    有环之后考虑怎么分配数字。一个直觉的想法是一大一小分配，这样让差最大，如何证明呢？

    当存在a1 > a2 > a3时，对答案的贡献是等价于a1 > a3的，也就是中间的a2并没有用。那么对于任意一种分配，删去这种没有用的点后，一定是一大一小交替。而且可以发现，一大一小交替的话，个数一定是偶数。

    这时大的绝对值取正，小的绝对值取负，所以我们让大的尽可能大，小的尽可能小。

    因此，如果环是偶数，那么就大的位置放尽可能大的，小的放尽可能小的。

    对于环是奇数，有一个位置是没有用的，所以要填一个最差的，也就是中间的值，把极值留给其他地方。

    最后注意开long long

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7. const int N = 1e5 + 10;
    8. int f[N], a[N], b[N], v[N], n, l, r, pos;
    9. vector<int> k[N], num;
    10.  
    11. int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
    12.  
    13. void Union(int x, int y) { f[find(x)] = find(y); } 
    14.  
    15. ll cal(int x)
    16. {
    17.     if(x <= 1) return 0;
    18.     if(x % 2 == 1) x--;
    19.     rep(i, 0, x) v[i] = num[pos++];
    20.  
    21.     ll res = 0;
    22.     rep(i, 0, x)
    23.     {
    24.         int j = (i + 1) % x;
    25.         res += abs(v[j] - v[i]);
    26.     }
    27.     return res;
    28. }
    29.  
    30. int main()
    31. { 
    32.     int T; scanf("%d", &T);
    33.     while(T--)
    34.     {
    35.         scanf("%d", &n);
    36.         _for(i, 1, n) f[i] = i, k[i].clear();
    37.         _for(i, 1, n) scanf("%d", &a[i]);
    38.         _for(i, 1, n) scanf("%d", &b[i]);
    39.  
    40.         _for(i, 1, n) Union(a[i], b[i]);
    41.         _for(i, 1, n) k[find(i)].push_back(i);
    42.  
    43.         ll ans = 0;
    44.         l = 1, r = n;
    45.         num.clear(); pos = 0;
    46.         while(l <= r)
    47.         {
    48.             num.push_back(l); l++;
    49.             num.push_back(r); r--;
    50.         }
    51.         
    52.         _for(i, 1, n) ans += cal(k[i].size());
    53.         printf("%lld\n", ans);
    54.     }
    55.  
    56.     return 0;
    57. }

    周四

    D. K-good（数学）

    首先注意一波推导，注意余数取k而不是取0，因为数字要是正数，同时两边乘以2去掉分数

    可以得到2n = k(k + 1 + 2t)

    我自己做的时候推到这里就不知道怎么分析了

    首先注意k和k+1+2t，一个是偶数一个奇数

    也就是说2n可以分解为一个偶数和一个奇数相乘。

    因为奇数部分没有2的因子

    所以就直接把2n一直除以2来分解

    然后就成了一个奇数和偶数。但是注意奇数部分不能为1，因为k和k+1+2t不可能为1

    分解完之后，哪一个是k呢，注意到k+1+2t更大，所以k就取奇数和偶数更小的那个即可

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. typedef long long ll;
    7.  
    8. int main()
    9. { 
    10.     int T; scanf("%d", &T);
    11.     while(T--)
    12.     {
    13.         ll n;
    14.         scanf("%lld", &n);
    15.         n *= 2;
    16.         
    17.         ll t = 1;
    18.         while(n % 2 == 0)
    19.         {
    20.             n /= 2;
    21.             t *= 2;
    22.         }
    23.  
    24.         if(n == 1) puts("-1");
    25.         else printf("%lld\n", min(t, n));
    26.     }
    27.  
    28.     return 0;
    29. }

    D. Not Adding（思维）

    首先可以发现，新出现的数肯定是当前数子集的gcd

    然后每个数都是不同的，所以当前序列没有的数很少，那么就去枚举这些输数，然后枚举它的倍数，然后将它的倍数取gcd，如果是它那么就答案加一。

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. unordered_map<int, bool> vis;
    7. int n, mx;
    8.  
    9. int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
    10.  
    11. int main()
    12. { 
    13.     scanf("%d", &n);
    14.     _for(i, 1, n)
    15.     {
    16.         int x; scanf("%d", &x);
    17.         vis[x] = 1;
    18.         mx = max(mx, x);
    19.     }
    20.  
    21.     int ans = 0;
    22.     _for(i, 1, mx)
    23.         if(!vis[i])
    24.         {
    25.             int cur = 0;
    26.             for(int j = i; j <= mx; j += i)
    27.                 if(vis[j])
    28.                     cur = gcd(cur, j);
    29.             if(cur == i) ans++;
    30.         }
    31.     printf("%d\n", ans);
    32.  
    33.     return 0;
    34. }

    D2. Half of Same（思维）

    一开始的想法是枚举当前数的因数，然后用这个因数看是多少个数的公因数

    一次的复杂度是max(根号ai,因数个数 * n)  我一开始算成根号ai*n了,然后觉得会T

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 50;
    7. int a[N], n;
    8. unordered_map<int, int> mp;
    9.  
    10. int main()
    11. { 
    12.     int T; scanf("%d", &T);
    13.     while(T--)
    14.     {
    15.         mp.clear();
    16.         scanf("%d", &n);
    17.  
    18.         int flag = 0;
    19.         _for(i, 1, n) 
    20.         {
    21.             scanf("%d", &a[i]);
    22.             if(++mp[a[i]] >= n / 2) flag = 1;
    23.         }
    24.         if(flag)
    25.         {
    26.             puts("-1");
    27.             continue;
    28.         }
    29.  
    30.         int ans = 1;
    31.         _for(id, 1, n)
    32.         {
    33.             vector<int> ve;
    34.             _for(j, 1, n)
    35.                 if(a[j] - a[id] >= 0)
    36.                     ve.push_back(a[j] - a[id]);
    37.  
    38.             if(ve.size() < n / 2) continue;
    39.  
    40.             rep(i, 0, ve.size())
    41.             {
    42.                 for(int j = 1; j * j <= ve[i]; j++)
    43.                     if(ve[i] % j == 0)
    44.                     {
    45.                         int cnt = 0;
    46.                         rep(k, 0, ve.size())
    47.                             if(ve[k] % j == 0)
    48.                                 cnt++;
    49.                         if(cnt >= n / 2) ans = max(ans, j);
    50.  
    51.                         cnt = 0;
    52.                         rep(k, 0, ve.size())
    53.                             if(ve[k] % (ve[i] / j) == 0)
    54.                                 cnt++;
    55.                         if(cnt >= n / 2) ans = max(ans, ve[i] / j);
    56.                     }
    57.             }
    58.         }
    59.         printf("%d\n", ans);
    60.     }
    61.  
    62.     return 0;
    63. }

    题解的方法优美一些，把所有因子扔到map里面统计一下有无超过一半，注意相同的情况。

    1. #include <bits/stdc++.h>
    2. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    3. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    4. using namespace std;
    5.  
    6. const int N = 50;
    7. int a[N], n;
    8. unordered_map<int, int> mp, vis;
    9.  
    10. int main()
    11. { 
    12.     int T; scanf("%d", &T);
    13.     while(T--)
    14.     {
    15.         mp.clear();
    16.         scanf("%d", &n);
    17.  
    18.         int flag = 0;
    19.         _for(i, 1, n) 
    20.         {
    21.             scanf("%d", &a[i]);
    22.             if(++mp[a[i]] >= n / 2) flag = 1;
    23.         }
    24.         if(flag)
    25.         {
    26.             puts("-1");
    27.             continue;
    28.         }
    29.  
    30.         int ans = 1;
    31.         _for(id, 1, n)
    32.         {
    33.             int same = 0;
    34.             vector<int> ve;
    35.             _for(j, 1, n)
    36.             {
    37.                 if(a[j] - a[id] == 0) same++;
    38.                 else if(a[j] - a[id] > 0) ve.push_back(a[j] - a[id]);
    39.             }
    40.  
    41.             vis.clear();
    42.             rep(i, 0, ve.size())
    43.             {
    44.                 for(int j = 1; j * j <= ve[i]; j++)
    45.                     if(ve[i] % j == 0)
    46.                     {
    47.                        vis[j]++;
    48.                        if(j * j != ve[i]) vis[ve[i] / j]++;
    49.                     }
    50.             }
    51.             for(auto x : vis)
    52.                 if(x.second + same >= n / 2)
    53.                     ans = max(ans, x.first);
    54.         }
    55.         printf("%d\n", ans);
    56.     }
    57.  
    58.     return 0;
    59. }

  • 相关阅读:
    navicat16 破解（注意破解时候要断网）
    javascript实现常用数组方法重写
    【无标题】mysql 普通用户连接报错： MySql server has gone away
    向量检索之一：Faiss 在工业界的应用和常见问题解决
    使用es实现轻量级分布式锁
    pacemaker+corosync 搭建一主两从PG集群
    集美大学第九届程序设计竞赛 L.序列 逆序对
    “手印”惠及你我，共赴绿色降碳之路
    Java SE 16 新增特性
    【图像融合】基于matlab粒子群优化自适应多光谱图像融合【含Matlab源码 004期】
  • 原文地址：https://blog.csdn.net/qq_34416123/article/details/126813911