• 大三第二周学习笔记

    训练！！！！

    周一

    hdu 5236(概率dp)

    首先要猜测一下策略，策略是将n个字符均分，每敲固定的字符就保存一下。

    比如将n分成i段，那么每一段的长度就是k或k+1，余数部分就分配到每个k，变成k+1

    那么这样就要处理没有保存的情况下，打k个字符的期望

    用dp[k]表示打k个字符的期望，注意这时不是逆推，因为需要的就是正推的。

    那么有dp[i] = dp[i - 1] + p(1 + dp[i]) + (1 - p) 可化为dp[i] = (dp[i - 1] + 1) / (1 - p)

    输出时6位小数即可，我输出了10位反而wa了

    1. #include<bits/stdc++.h>
    2. #define l(k) (k << 1)
    3. #define r(k) (k << 1 | 1)
    4. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    5. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    6. using namespace std;
    7.  
    8. const int N = 1e5 + 10;
    9. double dp[N], p;
    10. int n, x;
    11.  
    12. int main()
    13. {
    14.     int T, kase = 0; 
    15.     scanf("%d", &T);
    16.     while(T--)
    17.     {
    18.         scanf("%d%lf%d", &n, &p, &x);
    19.         _for(i, 1, n) dp[i] = (dp[i - 1] + 1) / (1 - p);
    20.  
    21.         double ans = 1e18;
    22.         _for(i, 1, n)
    23.         {
    24.             int k = n / i, r = n % i;
    25.             ans = min(ans, r * dp[k + 1] + (i - r) * dp[k] + i * x);
    26.         }
    27.         printf("Case #%d: %.6f\n", ++kase, ans);
    28.     }
    29.     
    30. 	return 0;
    31. }

    迷宫游戏（期望dp+处理方程）

    首先要写出方程，这个是简单的。注意这道题要求的是走过的边数的期望，而实际上三种情况只有一种情况会增加一条边，所以写方程时不要直接写1

    写出方程后发现有dp[1]和dp[fa[i]]两个未知量，那么就设dp[i] = aidp[1]+bidp[fa[i]]，然后代入dp方程中，化成dp[1]和dp[fa[i]]的形式，得到递推式。然后求一下叶子节点的式子即可。

    无解的话就是除0的情况。因为一般情况下是可以算出来的，只有分母为0是不能的。

    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 = 1e4 + 10;
    7. double k[N], e[N], a[N], b[N], c[N], t[N];
    8. vector<int> g[N];
    9. int n;
    10.  
    11. bool dfs(int u, int fa)
    12. {
    13.     if(g[u].size() == 1 && g[u][0] == fa)
    14.     {
    15.         a[u] = k[u];
    16.         b[u] = 1 - e[u] - k[u];
    17.         c[u] = 1 - e[u] - k[u];
    18.         return true;
    19.     }
    20.  
    21.     double suma = 0, sumb = 0, sumc = 0;
    22.     t[u] = (1 - e[u] - k[u]) / g[u].size();
    23.     for(int v: g[u])
    24.     {
    25.         if(v == fa) continue;
    26.         if(!dfs(v, u)) return false;
    27.         suma += a[v];
    28.         sumb += b[v];
    29.         sumc += c[v];
    30.     }
    31.     if(fabs(1 - t[u] * sumb) < 1e-8) return false;
    32.     a[u] = (k[u] + t[u] * suma) / (1 - t[u] * sumb);
    33.     b[u] = t[u] / (1 - t[u] * sumb);
    34.     c[u] = (t[u] * sumc + 1 - e[u] - k[u]) / (1 - t[u] * sumb);
    35.     return true;
    36. }
    37.  
    38. int main()
    39. {
    40.     scanf("%d", &n);
    41.     _for(i, 1, n - 1)
    42.     {
    43.         int u, v;
    44.         scanf("%d%d", &u, &v);
    45.         g[u].push_back(v);
    46.         g[v].push_back(u);
    47.     }
    48.     _for(i, 1, n) 
    49.     {
    50.         int x, y;
    51.         scanf("%d%d", &x, &y);
    52.         k[i] = 1.0 * x / 100;
    53.         e[i] = 1.0 * y / 100;
    54.     }
    55.  
    56.     if(!dfs(1, 0) || fabs(1 - a[1]) < 1e-8) puts("impossible");
    57.     else printf("%.10f\n", c[1] / (1 - a[1]));
    58.  
    59. 	return 0;
    60. }

    hdu 3535（混合背包）

    这题真的把各种背包结合起来

    强制选一个的操作很秀

    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 = 100 + 10;
    7. int dp[N][N], w[N], v[N], n, T, m, s;
    8.  
    9. int main()
    10. {
    11.     while(~scanf("%d%d", &n, &T))
    12.     {
    13.         memset(dp, 0, sizeof dp);
    14.         _for(i, 1, n)
    15.         {
    16.             scanf("%d%d", &m, &s);
    17.             _for(j, 1, m) scanf("%d%d", &w[j], &v[j]);
    18.  
    19.             if(s == 0)
    20.             {
    21.                 _for(j, 0, T) dp[i][j] = -1e9;  //因为必须取一个有不合法的状态，所以初始化为负无穷
    22.                 _for(k, 1, m)
    23.                     for(int j = T; j >= w[k]; j--)
    24.                         dp[i][j] = max(dp[i][j], max(dp[i][j - w[k]] + v[k], dp[i - 1][j - w[k]] + v[k])); //强制选一个，以及和前面的状态做背包
    25.             }
    26.             else if(s == 1)
    27.             {
    28.                 _for(j, 0, T) dp[i][j] = dp[i - 1][j];
    29.                 _for(k, 1, m)
    30.                     for(int j = T; j >= w[k]; j--)
    31.                         dp[i][j] = max(dp[i][j], dp[i - 1][j - w[k]] + v[k]);
    32.             }
    33.             else
    34.             {
    35.                 _for(j, 0, T) dp[i][j] = dp[i - 1][j];
    36.                 _for(k, 1, m)
    37.                     for(int j = T; j >= w[k]; j--)
    38.                         dp[i][j] = max(dp[i][j], dp[i][j - w[k]] + v[k]);
    39.             }
    40.         }
    41.         printf("%d\n", (dp[n][T] < 0) ? -1: dp[n][T]);
    42.     }
    43.  
    44. 	return 0;
    45. }

    周二

    D. 2+ doors（位运算+贪心）

    现在多刷刷cf的题，关键是学解题技巧。

    首先是位运算的题很常见的思路就是每一位独立出来考虑，这道题也是一样

    首先若边为0，那么肯定端点都是0，这是可以确定的，赋值。

    然后考虑什么时候字典序最小，那么就从前往后，每一位看能不能为0

    必须为1只有一种情况，就是边为1，而另一个端点为0。对于当前点，前面的点在已经确定了，为了尽量使得当前可以为1，我们可以把后面的位先全部设为1(除了零边赋值为0)

    那么就遍历当前点所有的边，看是否有不得不为1的情况，即一边且另一个端点是0。这样一位一位即可。有一个细节就是可能自己向自己连边，这个时候是一边的话那这一位就肯定为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. const int N = 2e5 + 10;
    7. int ans[N], t[N], n, m;
    8. vector<pair<int, int>> g[N];
    10. int main()
    11. {
    12.     scanf("%d%d", &n, &m);
    13.     while(m--)
    14.     {
    15.         int i, j, x;
    16.         scanf("%d%d%d", &i, &j, &x);
    17.         if(i > j) swap(i, j);
    18.         g[i].push_back({j, x});
    19.         g[j].push_back({i, x});
    20.     }
    21.  
    22.     _for(j, 0, 30)
    23.     {
    24.         _for(i, 1, n) t[i] = 1;
    25.         _for(i, 1, n)
    26.             for(auto x: g[i])
    27.                 if(!((x.second >> j) & 1))
    28.                     t[i] = t[x.first] = 0;
    29.         _for(i, 1, n)
    30.         {
    31.             if(!t[i]) continue;
    32.             int flag = 1;
    33.             for(auto x: g[i])
    34.                 if(!t[x.first] || i == x.first)
    35.                 {
    36.                     flag = 0;
    37.                     break;
    38.                 }
    39.             if(flag) t[i] = 0;
    40.         }
    41.         _for(i, 1, n) 
    42.             if(t[i])
    43.                 ans[i] |= 1 << j;
    44.     }
    45.     _for(i, 1, n) printf("%d ", ans[i]);
    46.  
    47. 	return 0;
    48. }

    D. Difference Array（暴力+优化）

    这是一类题，暴力看似不可行，实际上是可行的，加一些小优化，或者是复杂度计算。

    这题的关键就是发现计算的过程中会出现很多0，把0单独考虑可以大大加快速度，这样暴力也能过。

    考虑0的话，维护最后的0的位置，每次计算和排序都考虑后面的数，然后继续维护0的位置。注意可能有当前没有0的情况，要判断一下。

    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 = 1e5 + 10;
    7. int a[N], b[N], n;
    8.  
    9. int main()
    10. {
    11.     int T; scanf("%d", &T);
    12.     while(T--)
    13.     {
    14.         scanf("%d", &n);
    15.         _for(i, 1, n) scanf("%d", &a[i]);
    16.  
    17.         int pos = 0;
    18.         _for(i, 1, n)
    19.             if(a[i])
    20.             {
    21.                 pos = i - 1;
    22.                 break;
    23.             }
    24.  
    25.         while(n > 1 && a[n - 1])
    26.         {
    27.             _for(i, max(pos, 1), n) a[i] = a[i + 1] - a[i];
    28.             n--;
    29.             sort(a + max(pos, 1), a + n + 1);
    30.             if(pos) pos--;
    31.             while(pos + 1 <= n && !a[pos + 1]) pos++;
    32.         }
    33.         printf("%d\n", a[n]);
    34.     }
    35.  
    36. 	return 0;
    37. }

    C. Qpwoeirut And The City（括号匹配）

    思路挺妙，首先左边问号全部左括号，右边全部右括号一定是一个解

    然后看有无第二个解，那就把中间那里交换一下，也就是最右边的左括号和最左边的右括号，这样是影响最小的，然后看这样是否合法。

    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. bool check(string s)
    7. {
    8.     int len = s.size(), cnt = 0;
    9.     rep(i, 0, len)
    10.     {
    11.         if(s[i] == '(') cnt++;
    12.         else cnt--;
    13.         if(cnt < 0) return false;
    14.     }
    15.     return true;
    16. }
    17.  
    18. int main()
    19. { 
    20.     int T; scanf("%d", &T);
    21.     while(T--)
    22.     {
    23.         string s;
    24.         cin >> s;
    25.         int len = s.size();
    26.  
    27.         vector<int> pos;
    28.         int l = len / 2, r = len / 2;
    29.         rep(i, 0, len)
    30.         {
    31.             if(s[i] == '(') l--;
    32.             else if(s[i] == ')') r--;
    33.             else pos.push_back(i);
    34.         }
    35.         rep(i, 0, l) s[pos[i]] = '(';
    36.         rep(i, l, pos.size()) s[pos[i]] = ')';
    37.  
    38.         int ans = 0;
    39.         if(l && r)
    40.         {
    41.             swap(s[pos[l - 1]], s[pos[l]]);
    42.             if(check(s)) ans = 1;
    43.         }
    44.         puts(ans ? "NO" : "YES");
    45.     }
    46.    
    47.     return 0;
    48. }

    C. Qpwoeirut And The City（细节）

    这题不难，但写的时候写错了一个细节，调了很久才发现

    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. ll h[N], a[N];
    9. int n;
    10.  
    11. int main()
    12. { 
    13.     int T; scanf("%d", &T);
    14.     while(T--)
    15.     {
    16.         scanf("%d", &n);
    17.         _for(i, 1, n) scanf("%lld", &h[i]);
    18.         _for(i, 2, n - 1) a[i] = max(max(h[i - 1], h[i + 1]) + 1 - h[i], 0ll);
    19.  
    20.         if(n % 2 == 1)
    21.         {
    22.             ll ans = 0;
    23.             for(int i = 2; i <= n; i += 2) ans += a[i];
    24.             printf("%lld\n", ans);
    25.             continue;
    26.         }
    27.  
    28.         vector<pair<ll, ll>> ve;
    29.         for(int i = 2; i + 1 <= n; i += 2) ve.push_back({a[i], a[i + 1]});
    30.         //这里两个两个打进去时，注意退出条件是i+1<=n 不是i <= n 要用这一块的终点而不是起点
    31.  
    32.         ll cur = 0;
    33.         for(auto x: ve) cur += x.second;
    34.         ll ans = cur;
    35.         for(auto x: ve) 
    36.         {
    37.             cur += x.first - x.second;
    38.             ans = min(ans, cur);
    39.         }
    40.         printf("%lld\n", ans);
    41.     }
    42.    
    43.     return 0;
    44. }

    Yet Another FFT Problem?（复杂度计算）

    这题的关键在于，O(n^2)的算法看起来会T，实际上不会T

    先判断a，b中有没有相等的，都有的话直接输出答案，否则去重，之后就暴力枚举a，b

    因为要输出下标，我开始的做法是将值和下标绑在一起用pair，但是这种方法写起来复杂，而且交上去MLE了，应该是vector里面直接存下标即可。

    学了学菜狗的代码，学到了很多

    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 = 1e7 + 10;
    7.  
    8. int main()
    9. { 
    10.     ios::sync_with_stdio(false);
    11.     cin.tie(0);
    12.  
    13.     int n, m;
    14.     cin >> n >> m;
    16.     vector<int> a(n + 1), b(m + 1);
    17.     _for(i, 1, n) cin >> a[i];
    18.     _for(i, 1, m) cin >> b[i];
    20.     vector<int> posa(N, -1), posb(N, -1), va, vb;
    21.     array<int, 4> ans = {-1, -1, -1, -1};
    22.     _for(i, 1, n)
    23.     {
    24.         if(posa[a[i]] == -1)
    25.         {
    26.             posa[a[i]] = i;
    27.             va.push_back(i);
    28.         }
    29.         else
    30.         {
    31.             ans[0] = posa[a[i]];
    32.             ans[1] = i;
    33.         }
    34.     }
    35.     _for(i, 1, m)
    36.     {
    37.         if(posb[b[i]] == -1)
    38.         {
    39.             posb[b[i]] = i;
    40.             vb.push_back(i);
    41.         }
    42.         else
    43.         {
    44.             ans[2] = posb[b[i]];
    45.             ans[3] = i;
    46.         }
    47.     }
    48.     if(ans[0] != -1 && ans[2] != -1)
    49.     {
    50.         cout << ans[0] << " " << ans[1] << " " << ans[2] << " " << ans[3] << "\n";
    51.         return 0;
    52.     }
    53.  
    54.     vector<array<int, 2>> vis(2 * N, {-1, -1});
    55.     for(auto i : va)
    56.         for(auto j: vb)
    57.         {
    58.             if(vis[a[i] + b[j]][0] == -1) vis[a[i] + b[j]] = {i, j};
    59.             else
    60.             {
    61.                 cout << i << " " << vis[a[i] + b[j]][0] << " " << j << " " << vis[a[i] + b[j]][1];
    62.                 return 0;
    63.             }
    64.         }
    65.     cout << "-1\n" ;
    66.    
    67.     return 0;
    68. }

    Good red-string（贪心）

    这道题是比较复杂的贪心，思维量比较大

    首先不能直接从左到右先填r，再填e，再填e，比如r?d???  先填r的话就会导致在前缀中d比e多

    因此我们要先处理这种特殊情况，再贪心

    首先对所有前缀需要满足cntr >= cnte >= cntd

    对于所有后缀需要满足cntd >= cnte >= cntr

    结合那个特例，可以化简成对前缀需要d >= e 对后缀需要e >= r 满足这两个条件即满足上面的式子

    因为是对称的，所以我们只用考虑前缀，后缀类似处理即可。

    对于前缀，统计e的数量和d数量，如果不满足d比e多，那就把最近一个问号填为e，显然e越靠中间越优，所以是最近的。后缀同理填e

    这样填完后再进行r e d的贪心，最后再判断是否合法。

    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. bool solve()
    7. {
    8.     string s; cin >> s;
    9.     int len = s.size();
    10.     if(len % 3) return false;
    11.  
    12.     vector<int> pos;
    13.     int cnte = 0, cntd = 0, cntr = 0;
    14.     rep(i, 0, len)
    15.     {
    16.         if(s[i] == 'e') cnte++;
    17.         else if(s[i] == 'd') cntd++;
    18.         else if(s[i] == '?') pos.push_back(i);
    19.         if(cnte < cntd)
    20.         {
    21.             if(!pos.size()) return false;
    22.             s[pos.back()] = 'e'; pos.pop_back();
    23.             cnte++;
    24.         }
    25.     }
    26.     cntr = cnte = cntd = 0;
    27.     pos.clear();
    28.     for(int i = len - 1; i >= 0; i--)
    29.     {
    30.         if(s[i] == 'e') cnte++;
    31.         else if(s[i] == 'r') cntr++;
    32.         else if(s[i] == '?') pos.push_back(i);
    33.         else cntd++;
    34.         if(cnte < cntr)
    35.         {
    36.             if(!pos.size()) return false;
    37.             s[pos.back()] = 'e'; pos.pop_back();
    38.             cnte++;
    39.         }
    40.     }
    41.  
    42.     int r = len / 3 - cntr, e = len / 3 - cnte, d = len / 3 - cntd;
    43.     if(r < 0 || e < 0 || d < 0) return false;
    44.     rep(i, 0, len)
    45.         if(s[i] == '?')
    46.         {
    47.             if(r) s[i] = 'r', r--;
    48.             else if(e) s[i] = 'e', e--;
    49.             else if(d) s[i] = 'd', d--;
    50.         }
    51.     
    52.     cntr = cntd = cnte = 0;
    53.     rep(i, 0, len)
    54.     {
    55.         if(s[i] == 'r') cntr++;
    56.         if(s[i] == 'e') cnte++;
    57.         if(s[i] == 'd') cntd++;
    58.         if(!(cntr >= cnte && cnte >= cntd)) return false;
    59.     }
    60.     cntr = cntd = cnte = 0;
    61.     for(int i = len - 1; i >= 0; i--)
    62.     {
    63.         if(s[i] == 'r') cntr++;
    64.         if(s[i] == 'e') cnte++;
    65.         if(s[i] == 'd') cntd++;
    66.         if(!(cntd >= cnte && cnte >= cntr)) return false;
    67.     }
    68.     return true;
    69. }
    70.  
    71. int main()
    72. { 
    73.     int T; scanf("%d", &T);
    74.     while(T--) puts(solve() ? "Yes" : "No");
    75.     return 0;
    76. }

    周三

    poj 2287（贪心+分类讨论）

    比较需要思考的贪心，挺有趣的

    先看两边最高的

    首先如果左边最高的大于右边最高的，那就比一场。显然要以最小代价赢，这样赢得话两边得差是最小的，比较划算

    如果左边最高的小于右边最高的，那么这样左边怎么样都赢不了，那就拿左边最差的去送，代价最小

    如果左边最高的等于右边最高的，那就需要讨论一下

    这时有两种方法，一种是最高的比一个平局，一个是拿左边最差的去比。

    那么就需要讨论左边最差的那个有没有价值。

    如果左边最差的小于右边最差的：如果最高的比一个平局，那么就是一个平局，最差的输了，减200。如果拿左边最差的去比，输200，然而左边最好的可能大于右边第二好的。所以第二种要更优秀。

    如果左边最差的等于右边最差的，那么这时其实两种策略都是平手，都可以。

    如果左边最差的强于右边最差的。如果第一种策略，那就是平局加上赢一场，加200。如果第二种策略，那就是输一场，然后左边最高的可能赢右边第二高的。第一种策略必为+200，第二种可能+200，选第一种。

    所以综合一下上述的选择，可以发现就是最好的比一下，如果能赢就这么比，否则看最差的比一下，如果能赢就比，否则就最差的去比最好的。

    其实就是分类讨论，然后分析那种策略最优，然后总结

    1. #include <cstdio>
    2. #include <algorithm>
    3. #include <functional>
    4. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    5. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    6. using namespace std;
    7.  
    8. const int N = 1e3 + 10;
    9. int a[N], b[N], n;
    10.  
    11. int main()
    12. { 
    13.     while(scanf("%d", &n) && n)
    14.     {
    15.         _for(i, 1, n) scanf("%d", &a[i]);
    16.         _for(i, 1, n) scanf("%d", &b[i]);
    17.         sort(a + 1, a + n + 1, greater<int>());
    18.         sort(b + 1, b + n + 1, greater<int>());
    19.  
    20.         int al = 1, ar = n, bl = 1, br = n, ans = 0;
    21.         while(al <= ar)
    22.         {
    23.             if(a[al] > b[bl])
    24.             {
    25.                 ans += 200;
    26.                 al++; bl++;
    27.             }
    28.             else if(a[ar] > b[br])
    29.             {
    30.                 ans += 200;
    31.                 ar--; br--;
    32.             }
    33.             else
    34.             {
    35.                 if(a[ar] < b[bl]) ans -= 200;
    36.                 ar--; bl++;
    37.             }
    38.         }
    39.         printf("%d\n", ans);
    40.     }
    41.  
    42.     return 0;
    43. }

    hdu 6534（莫队+树状数组+离散化）

    因为数据范围比较小，所以可以考虑莫队。

    我离散化那里卡了一下，因为不仅要把a[i]离散化，还有差为k这个限制

    比较好写的做法是将a[i]-k,a[i]+k同样扔到离散化数组里面，这样就很好处理了

    1. #include <cstdio>
    2. #include <algorithm>
    3. #include <functional>
    4. #include <cmath>
    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 N = 27000 + 10;
    11. int a[N], L[N], R[N], lsh[N * 3], cnt, n, m, k, block, t;
    12. struct query
    13. {
    14.     int l, r, bl, id;
    15. }q[N];
    16. ll ans[N], f[N * 3], sum;
    17.  
    18. bool cmp(query x, query y)
    19. {
    20.     if(x.bl != y.bl) return x.bl < y.bl;
    21.     if(x.bl & 1) return x.r < y.r;
    22.     return x.r > y.r;
    23. }
    24.  
    25. int lowbit(int x) { return x & -x; }
    26.  
    27. void modify(int x, int p)
    28. {
    29.     for(; x <= t; x += lowbit(x))
    30.         f[x] += p;
    31. }
    32.  
    33. ll s(int x)
    34. {
    35.     ll res = 0;
    36.     for(; x; x -= lowbit(x))    
    37.         res += f[x];
    38.     return res;
    39. }
    40.  
    41. void add(int x)
    42. {
    43.     sum += s(R[x]) - s(L[x] - 1);
    44.     modify(a[x], 1);
    45. }
    46.  
    47. void erase(int x)
    48. {
    49.     modify(a[x], -1);
    50.     sum -= s(R[x]) - s(L[x] - 1);
    51. }
    52.  
    53. int main()
    54. { 
    55.     scanf("%d%d%d", &n, &m, &k);
    56.     _for(i, 1, n) 
    57.     {
    58.         scanf("%d", &a[i]);
    59.         lsh[++cnt] = a[i];
    60.         lsh[++cnt] = a[i] - k;
    61.         lsh[++cnt] = a[i] + k;
    62.     }
    63.     sort(lsh + 1, lsh + cnt + 1);
    64.     t = unique(lsh + 1, lsh + cnt + 1) - lsh - 1;
    65.     _for(i, 1, n)
    66.     {
    67.         L[i] = lower_bound(lsh + 1, lsh + t + 1, a[i] - k) - lsh;
    68.         R[i] = lower_bound(lsh + 1, lsh + t + 1, a[i] + k) - lsh;
    69.         a[i] = lower_bound(lsh + 1, lsh + t + 1, a[i]) - lsh;
    70.     }
    71.  
    72.     block = sqrt(n);
    73.     _for(i, 1, m)
    74.     {
    75.         int l, r; scanf("%d%d", &l, &r);
    76.         q[i] = {l, r, l / block, i};
    77.     }
    78.     sort(q + 1, q + m + 1, cmp);
    79.  
    80.     int l = 1, r = 0;
    81.     _for(i, 1, m)
    82.     {
    83.         int ll = q[i].l, rr = q[i].r;
    84.         while(l < ll) erase(l++);
    85.         while(l > ll) add(--l);
    86.         while(r < rr) add(++r);
    87.         while(r > rr) erase(r--);
    88.         ans[q[i].id] = sum;
    89.     }
    90.     _for(i, 1, m) printf("%lld\n", ans[i]);
    91.  
    92.     return 0;
    93. }

    Chiitoitsu（期望dp）

    最优策略就是能配对的配对，否则仍掉

    以手上的单牌和剩下牌的总数作为状态，用期望dp

    注意边界情况

    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. ll dp[20][150];
    9.  
    10. ll binpow(ll a, ll b)
    11. {
    12.     ll res = 1;
    13.     for(; b; b >>= 1)
    14.     {
    15.         if(b & 1) res = res * a % mod;
    16.         a = a * a % mod;
    17.     }
    18.     return res;
    19. }
    20.  
    21. ll inv(ll x) { return binpow(x, mod - 2); }
    22.  
    23. int main()
    24. { 
    25.     _for(i, 1, 13)
    26.         _for(j, 3 * i, 123)
    27.             dp[i][j] = (1 + 3 * i * inv(j) % mod * dp[max(i - 2, 0)][j - 1] % mod
    28.                         + (j - 3 * i) * inv(j) % mod * dp[i][j - 1] % mod) % mod;
    29.     
    30.     int T, kase = 0;
    31.     scanf("%d", &T);
    32.     while(T--)
    33.     {
    34.         string s; cin >> s;
    35.         int len = s.size();
    36.         map<string, int> mp;
    37.         for(int i = 0; i < len; i += 2)
    38.             mp[s.substr(i, 2)]++;
    39.  
    40.         int cnt = 0;
    41.         for(auto x: mp) 
    42.             if(x.second == 1)
    43.                 cnt++;
    44.         printf("Case #%d: %lld\n", ++kase, dp[cnt][123]);
    45.     }  
    46.  
    47.     return 0;
    48. }

    B. Mainak and Interesting Sequence

    比赛时当n为偶数，m为奇数的时候，构造了一下，发现构造不出来，就猜了一个肯定不成立，然后直接交了，A了。

    赛后可以证明一下，首先除了最大的数，其他的数都是成对的

    首先如果全部为一个数，那么n为偶数，和肯定为偶数，而m为奇数，排除

    那么不是全部为一个数，除了最大数外，其他的数因为是成对的，所以和为偶数，那么剩下最大数的位置也是偶数的，那么最后的和为偶数，不可能m为奇数

    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 = 1e5 + 10;
    7. int a[N], n, m;
    8.  
    9. int main()
    10. { 
    11.     int T; scanf("%d", &T);
    12.     while(T--) 
    13.     {
    14.         scanf("%d%d", &n, &m);
    15.         if(n % 2 == 1)
    16.         {
    17.             if(n > m) puts("No");
    18.             else
    19.             {
    20.                 _for(i, 1, n - 1) a[i] = 1, m--;
    21.                 a[n] = m;
    22.                 puts("Yes");
    23.                 _for(i, 1, n) printf("%d ", a[i]); puts("");
    24.             }
    25.         }
    26.         else
    27.         {
    28.             if(m % 2 == 1) puts("No");
    29.             else
    30.             {
    31.                 if(n > m) puts("No");
    32.                 else
    33.                 {
    34.                     _for(i, 1, n - 2) a[i] = 1, m--;
    35.                     a[n - 1] = a[n] = m / 2;
    36.                     puts("Yes");
    37.                     _for(i, 1, n) printf("%d ", a[i]); puts("");
    38.                 }
    39.             }
    40.         }
    41.     }
    42.  
    43.     return 0;
    44. }

    C. Jatayu's Balanced Bracket Sequence

    有两种边，一种是括号匹配的，一种是匹配与匹配之间的。比赛时用并查集写的，实际上并不会成环，可以直接统计右括号和)(的个数。

    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 f[N], st[N], top, n, cnt;
    8.  
    9. int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
    10.  
    11. void merge(int x, int y)
    12. {
    13.     int fx = find(x), fy = find(y);
    14.     if(fx != fy)
    15.     {
    16.         cnt--;
    17.         f[fx] = fy;
    18.     }
    19. }
    20.  
    21. int main()
    22. { 
    23.     int T; scanf("%d", &T);
    24.     while(T--) 
    25.     {
    26.         scanf("%d", &n);
    27.         _for(i, 1, 2 * n) f[i] = i;
    28.         
    29.         top = 0;
    30.         cnt = 2 * n;
    31.         string s; cin >> s;
    32.         s = " " + s;
    33.         int pre;
    34.         _for(i, 1, 2 * n)
    35.         {
    36.             if(s[i] == '(') 
    37.             {
    38.                 if(s[i - 1] == ')') merge(i, pre);
    39.                 st[++top] = i;
    40.             }
    41.             else 
    42.             {
    43.                 pre = i;
    44.                 merge(i, st[top--]);
    45.             }
    46.         }
    47.         printf("%d\n", cnt);
    48.     }
    49.  
    50.     return 0;
    51. }

    D. Edge Split

    这题等相通了发现不难，但比赛时还是想了一个小时，很不应该。

    显然可以生成树一种颜色，非树边一种颜色。当非数边成环时，将一条边加到生成树中，生成树新成的环删去一条边即可

    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. vector<pair<int, int>> g[N];
    8. int ans[N], vis[N], d[N], f[N], n, m; 
    9. vector<array<int, 3>> edge;
    11. void dfs(int u, int fa)
    12. {
    13.     d[u] = d[fa] + 1;
    14.     vis[u] = 1;
    15.     for(auto x: g[u])
    16.     {
    17.         int v = x.first, id = x.second;
    18.         if(v == fa) 
    19.         {
    20.             f[u] = id;
    21.             continue;
    22.         }
    23.         if(vis[v]) 
    24.         {
    25.             int flag = 1;
    26.             for(auto x: edge)
    27.                 if(x[2] == id)
    28.                 {
    29.                     flag = 0;
    30.                     break;
    31.                 }
    32.             if(flag) edge.push_back({u, v, id});
    33.         }
    34.         else dfs(v, u);
    35.     }
    36. }
    37.  
    38. int main()
    39. { 
    40.     int T; scanf("%d", &T);
    41.     while(T--) 
    42.     {
    43.         scanf("%d%d", &n, &m);
    44.         edge.clear();
    45.         _for(i, 1, n) g[i].clear(), vis[i] = 0;
    46.         _for(i, 1, m) ans[i] = 0;
    47.  
    48.         _for(i, 1, m)
    49.         {
    50.             int u, v;
    51.             scanf("%d%d", &u, &v);
    52.             g[u].push_back({v, i});
    53.             g[v].push_back({u, i});
    54.         }
    55.  
    56.         dfs(1, 0);
    57.  
    58.         int flag = 0;
    59.         if(edge.size() == 3)
    60.         {
    61.             set<int> s;
    62.             for(auto x: edge) 
    63.             {
    64.                 s.insert(x[0]);
    65.                 s.insert(x[1]);
    66.             }
    67.             if(s.size() == 3) flag = 1;
    68.         }
    69.         if(!flag) for(auto x: edge) ans[x[2]] = 1;
    70.         else
    71.         {
    72.             
    73.             ans[edge[0][2]] = ans[edge[1][2]] = 1;
    74.             int u = edge[2][0], v = edge[2][1];
    75.             if(d[u] < d[v]) swap(u, v);
    76.             ans[f[u]] = 1;
    77.         }
    78.         _for(i, 1, m) printf("%d", ans[i]); puts("");
    79.     }
    80.  
    81.     return 0;
    82. }

    A2. Burenka and Traditions (hard version)（异或+贪心区间覆盖）

    这题是由三个关键点嵌套起来。

    1.花费为区间除以2向上取整

    任何一个操作的花费都可以拆分成长度为1和长度为2的操作，这样考虑一定包含的最优的答案。这样拆分可以简化问题

    这样子答案的上界就是n，每个数都区间长度为1的操作

    为了让花费最小，显然要尽可能多的操作区间为2的且一起为0，也就是相等。

    考虑对于ai-1 和ai  如果本来就不等，那么如果使它们相等呢。在ai-1之前可以一直操作区间为2的，比如说a6，它可以通过前面的操作变成a6^a5,a6^a5^a4,a6^a5^a4^a3……

    那么怎么判断是否可以使得相等呢，这就用到了异或的性质，是第二个关键点

    2.异或的性质

    直接判断比较难，我们加入前缀异或和，也就是从1到ai-1，记为sum

    那么也就是存在前缀异或和为sum ^ a[i],注意这个前缀异或和包括0

    也就是对于一个ai,可以判断可能存在一个区间，使得答案更小。

    那么就由很多个区间，就转化为区间覆盖问题

    3.贪心求区间覆盖

    结论是按照右端点排序，然后遍历，能放就放

    因为可以按照右端点排序，所以可以直接枚举a1到an,然后如果当前可以使答案更小，那就操作，操作之后前缀异或和要重新记录，注意0始终存在。

    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 = 1e5 + 10;
    7. int a[N], n;
    8.  
    9. int main()
    10. { 
    11.     int T; scanf("%d", &T);
    12.     while(T--) 
    13.     {
    14.         scanf("%d", &n);
    15.         _for(i, 1, n) scanf("%d", &a[i]);
    16.  
    17.         set<int> s;
    18.         s.insert(0);
    19.         int ans = n, sum = 0;
    20.         _for(i, 1, n)
    21.         {
    22.             if(s.count(sum ^ a[i])) 
    23.             {
    24.                 ans--;
    25.                 s.clear();  s.insert(0);
    26.                 sum = 0;
    27.             }
    28.             else sum ^= a[i], s.insert(sum);
    29.         }
    30.         printf("%d\n", ans);
    31.     }
    32.  
    33.     return 0;
    34. }

    周四

    D. Madoka and The Corruption Scheme（思维+组合数）

    这题的关键在于反过来看，我一直按照题目的意思来看，结果感觉比较复杂。

    逆向思考，其实就是从根节点，每次选一条红边往下到叶子，叶子就是胜者。

    那么显然，要改变的话，只有改变这条路径上的边才有用，而且不同改变的结果一定是不同的，可以看作线段树向下，每次向左边或者向右边，只要有一次不同，结果一定不同。

    考虑改变能产生的不同的结果，修改0次就是c(n, 0) 修改1次就是c(n,1)……

    令k=min(k, n) 那么结果一共有c(n, 0) + c(n,1)……c(n, k)这么多可能

    那改变的人肯定取这么多可能的最大值，那么布置的人一定是布置1，2，3……这样可以使得最大值最小。

    所以最终的答案就是这个和

    预处理阶乘即可

    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. ll f[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. ll inv(ll x) { return binpow(x, mod - 2); } 
    23.  
    24. ll C(ll n, ll m)
    25. {
    26.     return f[n] * inv(f[m]) % mod * inv(f[n - m]) % mod;
    27. }
    28.  
    29. int main()
    30. { 
    31.     f[0] = 1;
    32.     _for(i, 1, 1e5) f[i] = f[i - 1] * i % mod;
    33.  
    34.     int n, k;
    35.     scanf("%d%d", &n, &k);
    36.     k = min(k, n);
    37.  
    38.     ll ans = 0;
    39.     _for(i, 0, k) ans = (ans + C(n, i)) % mod;
    40.     printf("%lld\n", ans);
    41.  
    42.     return 0;
    43. }

    Build a Tree and That Is It（思维+解方程）

    可以发现只有两种情况，要不是链式，要不是4号为根，然后1 2 3连向4

    第一种情况很好处理，第二种情况需要解方程。如果解出小数或者小于等于0就无解。

    最后还要注意一下点数和边数要满足限制。

    写的时候有想到，但是以为不会超，但实际上是会超的，WA了一发。其实写了也没错，应该一开始就写上去。

    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 n, d12, d23, d13, cnt, root;
    7. vector<pair<int, int>> ans;
    8. int dis[5][5];
    9.  
    10. void add(int u, int x)
    11. {
    12.     vector<int> ve;
    13.     ve.push_back(u);
    14.     _for(i, 1, x - 1) ve.push_back(cnt++);
    15.     ve.push_back(root);
    16.     rep(i, 0, ve.size() - 1) ans.push_back({ve[i], ve[i + 1]});
    17. }
    18.  
    19. int main()
    20. { 
    21.     int T; scanf("%d", &T);
    22.     while(T--)
    23.     {
    24.         cnt = 4;
    25.         ans.clear();
    26.         scanf("%d%d%d%d", &n, &d12, &d23, &d13);
    27.         dis[1][2] = dis[2][1] = d12;
    28.         dis[2][3] = dis[3][2] = d23;
    29.         dis[1][3] = dis[3][1] = d13;
    30.  
    31.         //case 1
    32.         vector<pair<int, int>> ve;
    33.         ve.push_back({d12, 3});
    34.         ve.push_back({d23, 1});
    35.         ve.push_back({d13, 2});
    36.         sort(ve.begin(), ve.end());
    37.         if(ve[0].first + ve[1].first == ve[2].first)
    38.         {
    39.             root = ve[2].second;
    40.             _for(i, 1, 3)
    41.                 if(i != root)
    42.                     add(i, dis[i][root]);
    43.         }
    44.         else //case 2
    45.         {
    46.             if((d13 + d12 - d23) % 2 != 0)
    47.             {
    48.                 puts("NO");
    49.                 continue;
    50.             }
    51.             int a, b, c;
    52.             a = (d13 + d12 - d23) / 2;
    53.             c = d13 - a;
    54.             b = d23 - c;
    55.             if(a <= 0 || b <= 0 || c <= 0)
    56.             {
    57.                 puts("NO");
    58.                 continue;
    59.             }
    60.  
    61.             root = cnt++;
    62.             if(root > n) 
    63.             {
    64.                 puts("NO");
    65.                 continue;
    66.             }
    67.             add(1, a); add(2, b); add(3, c);
    68.         }
    69.         while(cnt <= n) ans.push_back({cnt++, root});
    70.         if(cnt > n + 1) puts("NO");
    71.         else
    72.         {
    73.             puts("YES");
    74.             for(auto [u, v]: ans) printf("%d %d\n", u, v);
    75.         }
    76.     }
    77.  
    78.     return 0;
    79. }

    D. Magical Array（思维）

    妙啊，我自己思考的时候就觉得操作1和操作2会使得序列的某个性质改变，通过这个性质判断

    一开始想的是和，但是都是使得和不变的

    突破口是操作2的下标不同，所以我们把下标加入到序列的性质中，也就是ai * i的求和，可以发现操作2使得这个值+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 = 1e5 + 10;
    8. vector<pair<ll, int>> ve;
    10. int main()
    11. { 
    12.     int T; scanf("%d", &T);
    13.     while(T--)
    14.     {
    15.         ve.clear();
    16.         int n, m;
    17.         scanf("%d%d", &n, &m);
    18.         _for(i, 1, n)
    19.         {
    20.             ll sum = 0;
    21.             _for(j, 1, m)
    22.             {
    23.                 ll x; scanf("%lld", &x);
    24.                 sum += x * j;
    25.             }
    26.             ve.push_back({sum, i});
    27.         }
    28.         sort(ve.begin(), ve.end());
    29.         printf("%d %lld\n", ve.back().second, ve.back().first - ve[0].first);
    30.     }
    31.  
    32.     return 0;
    33. }

    G1. Passable Paths（dfs）

    我的思路是找所有点的lca，然后从这开始搜，看经过这一点的路径最大值是否为k。

    题目的思路简单一些，找深度最大的节点dfs，这个节点一定是路径的一端，然后后dfs能否走过所有选择的点

    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. vector<int> g[N];
    8. int d[N], up[N][21], c[N], n, q, k, ans, root;
    9.  
    10. void dfs(int u, int fa)
    11. {
    12.     d[u] = d[fa] + 1;
    13.     up[u][0] = fa;
    14.     _for(j, 1, 20) up[u][j] = up[up[u][j - 1]][j - 1];
    15.  
    16.     for(int v: g[u])
    17.     {
    18.         if(v == fa) continue;
    19.         dfs(v, u);
    20.     }
    21. }
    22.  
    23. int lca(int u, int v)
    24. {
    25.     if(d[u] < d[v]) swap(u, v);
    26.     for(int j = 20; j >= 0; j--)
    27.         if(d[up[u][j]] >= d[v])
    28.             u = up[u][j];
    29.     if(u == v) return u;
    30.     for(int j = 20; j >= 0; j--)
    31.         if(up[u][j] != up[v][j])
    32.             u = up[u][j], v = up[v][j];
    33.     return up[u][0];
    34. }
    35.  
    36. int dfs2(int u, int fa)
    37. {
    38.     int mx1 = 0, mx2 = 0;
    39.     for(int v: g[u])
    40.     {
    41.         if(v == fa) continue;
    42.         int t = dfs2(v, u);
    43.         if(t > mx1) mx2 = mx1, mx1 = t;
    44.         else mx2 = max(mx2, t);
    45.     }
    46.     if(u == root && c[u] + mx1 + mx2 == k) ans = 1;
    47.     return c[u] + mx1;
    48. }
    49.  
    50. int main()
    51. { 
    52.     scanf("%d", &n);
    53.     _for(i, 1, n) g[i].clear();
    54.     _for(i, 1, n - 1)
    55.     {
    56.         int u, v;
    57.         scanf("%d%d", &u, &v);
    58.         g[u].push_back(v);
    59.         g[v].push_back(u);
    60.     }
    61.     dfs(1, 0);
    62.  
    63.     scanf("%d", &q);
    64.     _for(i, 1, q)
    65.     {
    66.         root = 0;
    67.         _for(i, 1, n) c[i] = 0;
    68.         scanf("%d", &k);
    69.         _for(j, 1, k)
    70.         {
    71.             int x; scanf("%d", &x);
    72.             c[x] = 1;
    73.             if(!root) root = x;
    74.             else root = lca(root, x);
    75.         }
    76.         ans = 0;
    77.         dfs2(root, 0);
    78.         puts(ans ? "YES" : "NO");
    79.     }
    80.  
    81.     return 0;
    82. }

    D. Permutation Restoration（贪心）

    首先可以算出一个可能的取值范围，注意当分数小于一个值，转化为开区间可以向下取整+1

    然后就变成了怎么给每个区间分配点，我在这里卡住了，想把区间排序，然后不太行。

    正解是反过来思考，给点分配区间，从1遍历到n，对于当前点，给它分配一个右端点最小的区间。

    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 = 5e5 + 10;
    7. vector<int> v[N];
    8. int b[N], a[N], n;
    9.  
    10. int main()
    11. { 
    12.     int T; scanf("%d", &T);
    13.     while(T--)
    14.     {
    15.         scanf("%d", &n);
    16.         _for(i, 1, n) v[i].clear();
    17.         _for(i, 1, n) 
    18.         {
    19.             scanf("%d", &b[i]);
    20.             int l = i / (b[i] + 1) + 1;
    21.             v[l].push_back(i);
    22.         }
    23.  
    24.         set<pair<int, int>> s;
    25.         _for(i, 1, n)
    26.         {
    27.             for(int id: v[i]) s.insert({(b[id] == 0) ? n : id / b[id], id});
    28.             a[s.begin()->second] = i;
    29.             s.erase(s.begin());
    30.         }
    31.         _for(i, 1, n) printf("%d ", a[i]); puts("");
    32.     }
    33.  
    34.     return 0;
    35. }

    周五

    D. Guess The String（交互题+二分）

    交互题做的非常少……

    这题提供的主要信息就是一段区间右多少种字符

    考虑一个一个字符来猜，如果前面字符已知，现在猜第i个字符

    考虑f(j, i) 和f(j, i-1)  f(x,y)表示[x, y]中有多少种字符

    f(j, i) 和f(j, i-1)的差别就是多了一个s[i]

    显然，如果s[i]在(j,i-1)未出现过，那么f(j, i)会大1，否则相等

    当j离i越近，(j,i-1)就越小，越难包含s[i],如果j离i越远，那么就越可能包含s[i]

    考虑f(j, i) - f(j, i - 1) 那么随着j的增大，它的值一定是0 0 0 0 0 1 1 1 1

    最右边的0的位置就是s[i]

    因为0011具有单调性，所以我们可以二分来找这个s[i]

    当然，右可能前面每出现过找不到，此时就询问i

    那么这种做法询问是比较多的，因为有log(1000)    6000的数据范围意味着每个i最多6次

    考虑优化，显然只有每个字母最后出现的位置是有意义的，那么我们可以只存这个，那么二分次数就大大减小。

    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 = 1e3 + 10;
    7. int pos[30], cnt, n;
    8. char ans[N];
    9.  
    10. char ask1(int x)
    11. {
    12.     printf("? 1 %d\n", x);
    13.     fflush(stdout);
    14.     string s; cin >> s;   //输入一个字符时要额外小心 应该这么写
    15.     return s[0];
    16. }
    17.  
    18. int ask2(int l, int r)
    19. {
    20.     printf("? 2 %d %d\n", l, r);
    21.     fflush(stdout);
    22.     int t; scanf("%d", &t);
    23.     return t;
    24. }
    25.  
    26. int main()
    27. { 
    28.     scanf("%d", &n);
    29.     ans[1] = ask1(1);
    30.     pos[++cnt] = 1;
    31.     _for(i, 1, n)
    32.     {
    33.         sort(pos + 1, pos + cnt + 1);
    34.         int l = 0, r = cnt + 1;
    35.         while(l + 1 < r)
    36.         {
    37.             int m = l + r >> 1;
    38.             if(ask2(pos[m], i) == (cnt - m + 1)) l = m;
    39.             else r = m;
    40.         }
    41.         if(l == 0)
    42.         {
    43.             ans[i] = ask1(i);
    44.             pos[++cnt] = i;
    45.         }
    46.         else
    47.         {
    48.             ans[i] = ans[pos[l]];
    49.             pos[l] = i;
    50.         }
    51.     }
    52.  
    53.     printf("! ");
    54.     _for(i, 1, n) putchar(ans[i]);
    55.     fflush(stdout);
    56.  
    57.     return 0;
    58. }

    D. Permutation Graph（单调栈+线段树）

    这题妙啊，有两种做法。

    第一种做法比较直接，但写起来复杂一些，第二种不太好想到，但是写起来简单

    第一种做法

    首先，有一个贪心猜测，每一次走尽可能的远。我一开始有这个想法，但不知道这个贪心是不是对的。其实很好证明，如果u最远能达到v，那么u和v中间的节点一定不能连一条边超过v。因为如果可以，比如中间有个节点a，连一条边到v右边的b，那么可以发现u是可以连边到b的，就不满足v是最远的这个前提。

    有这个结论后，考虑怎么迅速求这个最远的点，比如当前节点是i，那么a[i]与a[i+1]的大小关系显然决定了a[i]是最大值还是最小值，如果a[i] > a[i+1]那么显然a[i]要作为最大值

    如果a[i]是作为最大值的话，设j为离i最近的使得a[j] > a[i]，那么可能得答案在[i + 1, j - 1]中

    这个j可以用单调栈O(n)求出

    在可能的答案区间中，求最小值，这个最小值就是我们要的答案。因为不可能有边从i越过这个最小值，因为i已经是最小值了。所以可以用线段树预处理区间最值，同时存对应的下标(用pair写起来非常简洁),那么就可以迅速求出

    每次跳一次的复杂度是线段树的O(logn),而每次至少可以往右移动一个，那么最多跳n次，所以复杂度是O(nlogn)的

    1. #include <bits/stdc++.h>
    2. #define l(k) (k << 1)
    3. #define r(k) (k << 1 | 1)
    4. #define rep(i, a, b) for(int i = (a); i < (b); i++)
    5. #define _for(i, a, b) for(int i = (a); i <= (b); i++)
    6. using namespace std;
    7.  
    8. typedef pair<int, int> pa;
    9. const int N = 2.5e5 + 10;
    10. int a[N], rmax[N], rmin[N], st[N], top, n;
    11. pa tmax[N << 2], tmin[N << 2];
    12.  
    13. void up(int k)
    14. {
    15.     tmax[k] = max(tmax[l(k)], tmax[r(k)]);
    16.     tmin[k] = min(tmin[l(k)], tmin[r(k)]);
    17. }
    18.  
    19. void build(int k, int l, int r)
    20. {
    21.     if(l == r)
    22.     {
    23.         tmax[k] = tmin[k] = {a[l], l};
    24.         return;
    25.     }
    26.     int m = l + r >> 1;
    27.     build(l(k), l, m);
    28.     build(r(k), m + 1, r);
    29.     up(k);
    30. }
    31.  
    32. pa ask_max(int k, int l, int r, int L, int R)
    33. {
    34.     if(L <= l && r <= R) return tmax[k];
    35.     int m = l + r >> 1;
    36.     pa res = {0, 0};
    37.     if(L <= m) res = max(res, ask_max(l(k), l, m, L, R));
    38.     if(R > m) res = max(res, ask_max(r(k), m + 1, r, L, R));
    39.     return res;
    40. }
    41.  
    42. pa ask_min(int k, int l, int r, int L, int R)
    43. {
    44.     if(L <= l && r <= R) return tmin[k];
    45.     int m = l + r >> 1;
    46.     pa res = {1e9, 0};
    47.     if(L <= m) res = min(res, ask_min(l(k), l, m, L, R));
    48.     if(R > m) res = min(res, ask_min(r(k), m + 1, r, L, R));
    49.     return res;
    50. }
    51.  
    52. int main()
    53. { 
    54.     int T; scanf("%d", &T);
    55.     while(T--)
    56.     {
    57.         scanf("%d", &n);
    58.         _for(i, 1, n) scanf("%d", &a[i]);
    59.  
    60.         top = 0;
    61.         for(int i = n; i >= 1; i--)   //单调栈不用先加入 直接从n开始  
    62.         {
    63.             while(top && a[i] > a[st[top]]) top--;
    64.             rmax[i] = top ? st[top] : n + 1;   //注意栈未空的情况 
    65.             st[++top] = i;
    66.         }
    67.         top = 0;
    68.         for(int i = n; i >= 1; i--)
    69.         {
    70.             while(top && a[i] < a[st[top]]) top--;
    71.             rmin[i] = top ? st[top] : n + 1;
    72.             st[++top] = i;
    73.         }
    74.  
    75.         build(1, 1, n);
    76.         int ans = 0, cur = 1;
    77.         while(cur != n)
    78.         {
    79.             if(a[cur + 1] > a[cur])
    80.             {
    81.                 pa t = ask_max(1, 1, n, cur + 1, rmin[cur] - 1);
    82.                 cur = t.second;
    83.             }
    84.             else
    85.             {
    86.                 pa t = ask_min(1, 1, n, cur + 1, rmax[cur] - 1);
    87.                 cur = t.second;
    88.             }
    89.             ans++;
    90.         }
    91.         printf("%d\n", ans);
    92.     }
    93.  
    94.     return 0;
    95. }

    第二种做法

    核心是一个点：不会有边跨过最值

    对于ai=n,一定不会有边跨过它，对于aj=1也是

    不能跨国它意味着一定要经过它 

    同时i和j存在一条边

    假设i

    所以dis(1, n) = dis(1, i) + 1 + dis(j, n)

    那么可以这样一直递归下去，只不过最值变成了当前区间的最值

    这里的区间要不是l=1，要不是r=n，所以只需要处理前缀最值和后缀最值

    还要存值对应的下标

    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 pair<int, int> pa;
    7. const int N = 2.5e5 + 10;
    8. int a[N], lmax[N], lmin[N], rmax[N], rmin[N], id[N], n;
    9.  
    10. int dfs(int l, int r)
    11. {
    12.     if(l == r) return 0;
    13.     int x, y;
    14.     if(l == 1)
    15.     {
    16.         x = min(id[lmax[r]], id[lmin[r]]);
    17.         y = max(id[lmax[r]], id[lmin[r]]);
    18.     }
    19.     else
    20.     {
    21.         x = min(id[rmax[l]], id[rmin[l]]);
    22.         y = max(id[rmax[l]], id[rmin[l]]);
    23.     }
    24.     return dfs(l, x) + 1 + dfs(y, r);
    25. }
    26.  
    27. int main()
    28. { 
    29.     int T; scanf("%d", &T);
    30.     while(T--)
    31.     {
    32.         scanf("%d", &n);
    33.         _for(i, 1, n) scanf("%d", &a[i]), id[a[i]] = i;
    34.  
    35.         lmax[1] = lmin[1] = a[1];
    36.         _for(i, 2, n)
    37.         {
    38.             lmax[i] = max(lmax[i - 1], a[i]);
    39.             lmin[i] = min(lmin[i - 1], a[i]);
    40.         }
    41.         rmax[n] = rmin[n] = a[n];
    42.         for(int i = n - 1; i >= 1; i--)
    43.         {
    44.             rmax[i] = max(rmax[i + 1], a[i]);
    45.             rmin[i] = min(rmin[i + 1], a[i]);
    46.         }
    47.  
    48.         printf("%d\n", dfs(1, n));
    49.     }
    50.  
    51.     return 0;
    52. }

    D. Lena and Matrix（拆式子）

    这题的关键在于把题目给的式子变换，拆开

    分类一下把那个绝对值拆开，发现最值一定是4个点之一，所以有用的只有4个点

    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 = 1e3 + 10;
    7. char s[N][N];
    8. int n, m;
    9.  
    10. int main()
    11. { 
    12.     int T; scanf("%d", &T);
    13.     while(T--)
    14.     {
    15.         vector<pair<int, int>> node(4, {-1, -1});
    17.         scanf("%d%d", &n, &m);
    18.         _for(i, 1, n)
    19.         {
    20.             scanf("%s", s[i] + 1);
    21.             _for(j, 1, m)
    22.             {
    23.                 if(s[i][j] == 'W') continue;
    24.                 if(node[0].first == -1) 
    25.                 {
    26.                     rep(k, 0, 4)
    27.                         node[k] = {i, j};
    28.                 }
    29.                 else
    30.                 {
    31.                     if(i + j > node[0].first + node[0].second) node[0] = {i, j};
    32.                     if(i + j < node[1].first + node[1].second) node[1] = {i, j};
    33.                     if(i - j > node[2].first - node[2].second) node[2] = {i, j};
    34.                     if(i - j < node[3].first - node[3].second) node[3] = {i, j};
    35.                 }
    36.             }
    37.         }
    38.  
    39.         int ans = 1e9, x, y;
    40.         _for(i, 1, n)
    41.             _for(j, 1, m)
    42.             {
    43.                 int cur = 0;
    44.                 for(auto [xx, yy]: node)
    45.                     cur = max(cur, abs(xx - i) + abs(yy - j));
    46.                 if(cur < ans)
    47.                 {
    48.                     ans = cur;
    49.                     x = i; y = j;
    50.                 }
    51.             }
    52.         printf("%d %d\n", x, y);
    53.     }
    54.  
    55.     return 0;
    56. }

  • 相关阅读:
    【特征选择】基于二进制粒子群算法的特征选择方法（GRNN广义回归神经网络分类）【Matlab代码#32】
    Allegro Design Entry HDL（OrCAD Capture HDL）软件设计管理图标详细介绍
    SSM SpringBoot vue学校办公自动化系统
    获取嵌套结构体字段总数
    docker搭建Jenkins及基本使用
    vue课后习题及答案
    SpringCloud微服务-SpringAMQP（RabbitMQ）
    LayaBox---TypeScript---类型兼容性
    微服务（基础篇-007-RabbitMQ部署指南）
    现代面试中的乱象
  • 原文地址：https://blog.csdn.net/qq_34416123/article/details/126700290