[心之碎片] - 20240816模拟赛

柿子饼同学

总结与反思

ll = 1ll * int * int
取模要看好了, 不要把 ans 也乘了
一定要会打部分分!

A - 考虑条件的限制有什么巧方法水过去, 而不是一来就想高级算法

B - 中缀表达式求值要会

C - EXgcd 要更熟练一点

D - 计数题一定要有组合思想, 分类要细致, dfs 相关(做差, 栈, 树上差分) 之类的简单算法要先想, 树上路径其实是点

P7229 [COCI2015-2016#3] SLON
B 的 dfs 求中缀表达式

1. int dfs() {
   
2.     int res = 0, cur = 1, temp = 0;
   
3. 
   
4.     for (; s[pos] != ')' && s[pos]; pos++) {
   
5.         if (s[pos] == '(') {
   
6.             pos++;
   
7.             temp = dfs();
   
8.         } else if (isdigit(s[pos]) || s[pos] == 'x') {
   
9.             temp = temp * 10 + mp[s[pos]];
   
10.             temp %= m;
    
11.         } else {
    
12.             cur = 1ll * cur * temp % m;
    
13.             temp = 0;
    
14. 
    
15.             if (s[pos] != '*')
    
16.                 res = (res + cur + m) % m;
    
17.             if (s[pos] == '-')
    
18.                 cur = -1;
    
19.             if (s[pos] == '+')
    
20.                 cur = 1;
    
21.         }
    
22.     }
    
23. 
    
24.     cur = 1ll * cur * temp % m;
    
25.     return (res + cur + m) % m;
    
26. }

复制代码

C - P4031 [Code+#2] 可做题2
没啥可说的, 之前想的是枚举最后的 [l, r], 后来发现可以数论分块...

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef long long ll;
   
5. 
   
6. ll T, a1, l, r, k, p, m;
   
7. 
   
8. struct Matrix {
   
9.     ll mat[2][2];
   
10. 
    
11.     Matrix() { memset(mat, 0, sizeof(mat)); }
    
12. 
    
13.     Matrix operator*(const Matrix& t) const {
    
14.         Matrix temp;
    
15.         for (int k = 0; k < 2; k++) {
    
16.             for (int i = 0; i < 2; i++) {
    
17.                 for (int j = 0; j < 2; j++) {
    
18.                     temp.mat[i][j] += mat[i][k] * t.mat[k][j] % p;
    
19.                     temp.mat[i][j] %= p;
    
20.                 }
    
21.             }
    
22.         }
    
23.         return temp;
    
24.     }
    
25. } base;
    
26. 
    
27. ll Exgcd(ll a, ll b, ll& x, ll& y) {
    
28.     if (!b) {
    
29.         x = 1, y = 0;
    
30.         return a;
    
31.     }
    
32. 
    
33.     ll x1, y1;
    
34.     ll d = Exgcd(b, a % b, x1, y1);
    
35.     x = y1, y = x1 - a / b * y1;
    
36. 
    
37.     return d;
    
38. }
    
39. 
    
40. Matrix qp(Matrix a, ll b) {
    
41.     Matrix res;
    
42.     for (int i = 0; i < 2; i++) res.mat[i][i] = 1;
    
43. 
    
44.     while (b) {
    
45.         if (b & 1)
    
46.             res = res * a;
    
47.         a = a * a;
    
48.         b >>= 1;
    
49.     }
    
50. 
    
51.     return res;
    
52. }
    
53. 
    
54. int main() {
    
55.     ios::sync_with_stdio(0);
    
56.     cin.tie(0);
    
57. 
    
58.     freopen("fib.in", "r", stdin);
    
59.     freopen("fib.out", "w", stdout);
    
60. 
    
61.     base.mat[0][0] = base.mat[0][1] = base.mat[1][0] = 1;
    
62. 
    
63.     cin >> T;
    
64.     while (T--) {
    
65.         cin >> a1 >> l >> r >> k >> p >> m;
    
66. 
    
67.         a1 %= p;
    
68.         auto cur = qp(base, k - 1);
    
69. 
    
70.         ll ka1 = a1 * cur.mat[1][1] % p;
    
71.         ll ka2 = cur.mat[0][1] % p;
    
72.         ll gcd = __gcd(ka2, p);
    
73. 
    
74.         // ak = ka1 + ka2*a2
    
75.         // 得到不定方程:
    
76.         // ka2*x + p*y = m - ka1
    
77.         // A*x + B*y = C
    
78. 
    
79.         if ((m - ka1) % gcd) {
    
80.             cout << "0\n";
    
81.             continue;
    
82.         }
    
83. 
    
84.         ll A = ka2 / gcd, B = p / gcd, C = (m - ka1) / gcd;
    
85.         ll x, y, d;
    
86. 
    
87.         d = Exgcd(A, B, x, y);
    
88. 
    
89.         x = (x * C % B + B) % B;
    
90.         // x 是最小正整数解, x*a2 + ka1 = ak
    
91. 
    
92.         if (x > r) {
    
93.             cout << "0\n";
    
94.         } else {
    
95.             if (l <= x) {
    
96.                 cout << (r - x) / B + 1 << '\n';
    
97.             } else {
    
98.                 cout << (r - x) / B - (l - 1 - x) / B << '\n';
    
99.             }
    
100.         }
     
101.     }
     
102. 
     
103.     return 0;
     
104. }

复制代码

D - 树上路径交
知知有一棵n个节点的树，根节点为1，树上每条边长度为1，定义G路径是连接祖先节点和其子孙节点的路径。
她想要知道有多少对路径的路径交是长度在 [L, R] 之间的G路径。

首先想到枚举交的部分, 然后一上一下每个点求一个不在同一个子树里取两个点的方案数
然后这里相当于利用 dfs 栈批量处理了

1. typedef long long ll;
   
2. 
   
3. const int N = 3e6 + 5;
   
4. const ll P = 1e9 + 7;
   
5. 
   
6. int n, l, r;
   
7. // up[i], 除了 i 这个子树和她的父节点, 在剩余子树中选择两个点使得不在同一个子树的方案数
   
8. // dn[i], i 这个子树, 选择 2 个点使得不在同一子树的方案数(不包括 i)
   
9. ll up[N], dn[N], dep[N], siz[N], ans;
   
10. vector<int> e[N];
    
11. 
    
12. void dfs0(int u) {
    
13.     siz[u] = 1;
    
14. 
    
15.     for (auto v : e[u]) {
    
16.         dfs0(v);
    
17.         siz[u] += siz[v];
    
18.     }
    
19. 
    
20.     ll temp = 1ll * n * (n - 1) / 2;
    
21.     dn[u] = 1ll * siz[u] * (siz[u] - 1) / 2;
    
22. 
    
23.     for (auto v : e[u]) {
    
24.         // 强制减去两个点都在 v 子树的方案
    
25.         dn[u] -= siz[v] * (siz[v] - 1) / 2;
    
26.         temp -= siz[v] * (siz[v] - 1) / 2;
    
27.     }
    
28. 
    
29.     dn[u] %= P;
    
30.     temp -= (n - siz[u]) * (n - siz[u] - 1) / 2;
    
31. 
    
32.     for (auto v : e[u]) {
    
33.         // 上面已经减过重复情况了, 这里只需要减掉一个点在 v 子树内的方案数
    
34.         up[v] = temp - (n - siz[v]) * siz[v];
    
35.     }
    
36. }
    
37. 
    
38. ll stk[N];
    
39. int top;
    
40. 
    
41. void dfs(int u) {
    
42.     if (u != 1) {
    
43.         top++;
    
44.         stk[top] = (stk[top - 1] + up[u]) % P;
    
45. 
    
46.         if (top >= l) {
    
47.             // sum 是指这一区间内的点上方选取 2 个不在同子树的点的方案数
    
48.             ll sum = ((stk[top - l + 1] - stk[max(0, top - r)]) % P + P) % P;
    
49. 
    
50.             // u 的子节点和这些点的上方节点, *2 是因为有 2 种情况, a, b -- c, d , a 可以选 c 也可以选 d
    
51.             ans = (ans + 2 * sum % P * dn[u] % P) % P;
    
52. 
    
53.             // u 的子节点和这些点(相同结尾 都是在这个区间内的点)
    
54.             ans = (ans + (min(top, r) - l + 1) * dn[u] % P) % P;
    
55. 
    
56.             // u 自己和这些点(相同起点 u)
    
57.             ans = (ans + sum) % P;
    
58.         }
    
59.     }
    
60. 
    
61.     for (auto v : e[u]) {
    
62.         dfs(v);
    
63.     }
    
64. 
    
65.     if (u != 1) {
    
66.         top--;
    
67.     }
    
68. }

复制代码

某一个“天”

加油

简柠啦

很cool的阳

shuaijun

希儿的

日常膜拜

shuaijun

曾热爱这世界

&#128076;

zsy0226

膜拜日常/orz

trinityee

我看的是高手成长阶梯啊！

森林格格屋

谢谢

啵啵虎0506

good