[心之碎片] - 20240807模拟赛

柿子饼同学

总结与反思

A - 只需要判断 可行性/可解性 要考虑前缀 min/max

B - 数学找规律先打表

C - 刷表法转化为填表法更好优化

D - 树剖是为了让我们 log 级别跳到顶, 并且维护一整条重链的信息, 轻孩子暴力存 (由一个一个跳祖先启发过来)

A - 牛宫
我们想知道 r 前面是否有小于她的, 这里只需要取前缀 min 就好

1. #include <bits/stdc++.h>
   
2. 
   
3. using namespace std;
   
4. 
   
5. const int N = 400 + 5;
   
6. const int inf = 114514;
   
7. 
   
8. int n, m, a[N][N], s[N][N], res, st[N], t, b[N];
   
9. 
   
10. inline int w(int u, int d, int i) { return s[d][i] - s[u - 1][i]; }
    
11. 
    
12. signed main() {
    
13.     ios::sync_with_stdio(0);
    
14.     cin.tie(0);
    
15.     cout.tie(0);
    
16. 
    
17.     freopen("rec.in", "r", stdin);
    
18.     freopen("rec.out", "w", stdout);
    
19. 
    
20.     cin >> n >> m;
    
21.     for (int i = 1; i <= n; i++) {
    
22.         for (int j = 1; j <= m; j++) {
    
23.             cin >> a[i][j];
    
24.             s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
    
25.         }
    
26.     }
    
27.     for (int p = 1; p <= n; p++) {
    
28.         for (int q = p; q <= n; q++) {
    
29.             for (int i = 1; i <= m; i++) b[i] = min(b[i - 1], w(p, q, i));
    
30.             t = 0;
    
31.             for (int i = 1; i <= m; i++)
    
32.                 while (t < i && w(p, q, i) >= b[i - t - 1]) t++;
    
33.             res = max(res, (q - p + 1) * t);
    
34.         }
    
35.     }
    
36. 
    
37.     cout << res;
    
38. 
    
39.     return 0;
    
40. }

复制代码

B - GCD
选出两个正整数a，b,使得通过辗转相除求最大公约数时，递归调用次数最多。
斐波那契数列最大公约数定理(这谁知道啊...打表吧)
Gcd(F(m),F(n))=F(gcd(m,n))
然后就是高精度每次加一下即可

1. #include <bits/stdc++.h>
   
2. #define LL long long
   
3. using namespace std;
   
4. char str[20005];
   
5. int m, b;
   
6. LL num[2505], A[2505], B[2505], C[2505], P = 1e18;
   
7. bool Cmp() {
   
8.     if (b != m)
   
9.         return b > m;
   
10.     for (int i = b - 1; i >= 0; i--) {
    
11.         if (C[i] != num[i])
    
12.             return C[i] > num[i];
    
13.     }
    
14.     return false;
    
15. }
    
16. void Print(LL s[]) {
    
17.     int k = b;
    
18.     while (s[k] == 0) k--;
    
19.     printf("%lld", s[k--]);
    
20.     while (k >= 0) printf("%018lld", s[k--]);
    
21. }
    
22. LL getnum(int L, int R) {
    
23.     LL res = 0;
    
24.     for (int i = L; i <= R; i++) res = (res << 3) + (res << 1) + (str[i] ^ 48);
    
25.     return res;
    
26. }
    
27. int main() {
    
28.     freopen("gcd.in", "r", stdin);
    
29.     freopen("gcd.out", "w", stdout);
    
30. 
    
31.     scanf("%s", str);
    
32.     int n = strlen(str);
    
33.     int p = n % 18;
    
34.     m = (n + 17) / 18;
    
35.     int k = m - 1;
    
36.     if (p != 0) {
    
37.         num[k] = getnum(0, p - 1);
    
38.         k--;
    
39.     }
    
40.     for (int i = p, j = 0; i < n; i += 18) {
    
41.         num[k] = getnum(i, i + 17);
    
42.         k--;
    
43.     }
    
44.     A[0] = 1, B[0] = 1, b = 1;
    
45.     while (1) {
    
46.         for (int i = 0; i < b; i++) {
    
47.             C[i] += A[i] + B[i];
    
48.             if (C[i] >= P) {
    
49.                 C[i] -= P;
    
50.                 C[i + 1]++;
    
51.             }
    
52.         }
    
53.         if (C[b] > 0)
    
54.             b++;
    
55.         if (Cmp())
    
56.             break;
    
57.         for (int i = 0; i < b; i++) {
    
58.             A[i] = B[i];
    
59.             B[i] = C[i];
    
60.             C[i] = 0;
    
61.         }
    
62.     }
    
63.     Print(A);
    
64.     putchar(' ');
    
65.     Print(B);
    
66.     return 0;
    
67. }

复制代码

C - 排列逆序对
构造 1-n 的排列, 使得逆序对为 k, 求方案数
线段树优化超时了, 后来发现改成填表法之间用前缀和优化即可

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 5005;
   
5. const int P = 1e9 + 7;
   
6. 
   
7. int f[N], s[N];
   
8. int n, m;
   
9. 
   
10. // i(前 i 个数), j(现在要填的数), k(逆序对数)
    
11. // f(i, k + i - j) += f(i - 1, k)
    
12. // 刷表法不好优化, 转换一下
    
13. // f(i, k) += f(i, k - i + j)
    
14. // 即 f(i, k) = f(i, x), x 属于 [k - i + 1, k]
    
15. // 于是乎前缀和优化
    
16. 
    
17. int main() {
    
18.     ios::sync_with_stdio(0);
    
19.     cin.tie(0);
    
20. 
    
21.     freopen("reverse.in", "r", stdin);
    
22.     freopen("reverse.out", "w", stdout);
    
23. 
    
24.     cin >> n >> m;
    
25.     // 逆序对为 0 永远只有一种情况
    
26.     s[0] = 1;
    
27. 
    
28.     for (int i = 1; i <= n; i++) {
    
29.         for (int k = 1; k <= m; k++) {
    
30.             s[k] = (f[k] + s[k - 1]) % P;
    
31.         }
    
32.         for (int k = 0; k <= m; k++) {
    
33.             if (k - i >= 0)
    
34.                 f[k] = (s[k] - s[k - i] + P) % P;
    
35.             else
    
36.                 f[k] = s[k];
    
37.         }
    
38.     }
    
39. 
    
40.     cout << f[m];
    
41. 
    
42.     return 0;
    
43. }

复制代码

D - [2010国家集训队]Crash的旅游计划

20% 的分数满足：n和指令的条数都不超过 1e3。
另 30% 的分数满足：n和指令的条数都不超过1e5 ，且输入的第 i 条道路，连接着 i 号地点和 i+1 号地点（详见样例2）。
另 20% 的分数满足：n和指令的条数都不超过1e5 ，除了 1 之外，每个点 i 与 (i + 1)/2 连边，即形成一棵完全二叉树。
另 10% 的分数满足：n和指令的条数都不超过1e5 ，且任何一个地点到 1 号地点需要通过的道路条数不超过 40。
100% 的分数满足：n和指令的条数都不超过1e5 。
80 分比较简单, 分别用暴力, 区间 max/min , 每个点向上跳, 同时维护这个点到除了这个子树的最长路径
100 分在向上跳的基础上, 直接维护整个重链的答案, 存上每个点出发去往一个轻孩子的最长路径, 向上就是 logn 的

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. typedef pair<int, int> pii;
   
5. 
   
6. const int N = 1e5 + 5;
   
7. 
   
8. // Global
   
9. vector<int> e[N];
   
10. int val[N], n;
    
11. 
    
12. // QTREE
    
13. int dfn[N], siz[N], hc[N];
    
14. int L[N], R[N], f[N], rdfn[N], tot;
    
15. // L, R -> u 所在的重链的两端点编号, L 即 top
    
16. 
    
17. void dfs0(int u, int pa) {
    
18.     f[u] = pa;
    
19.     siz[u] = 1;
    
20. 
    
21.     for (auto v : e[u]) {
    
22.         if (v == pa)
    
23.             continue;
    
24.         dfs0(v, u);
    
25. 
    
26.         siz[u] += siz[v];
    
27.         if (siz[hc[u]] < siz[v])
    
28.             hc[u] = v;
    
29.     }
    
30. }
    
31. 
    
32. void dfs1(int u, int t) {
    
33.     L[u] = t;
    
34.     dfn[u] = ++tot;
    
35.     rdfn[tot] = u;
    
36. 
    
37.     if (hc[u])
    
38.         dfs1(hc[u], t), R[u] = R[hc[u]];
    
39.     else
    
40.         R[u] = u;
    
41. 
    
42.     for (auto v : e[u]) {
    
43.         if (v == f[u] || v == hc[u])
    
44.             continue;
    
45.         dfs1(v, v);
    
46.     }
    
47. }
    
48. 
    
49. // s[u] 存和 u 相连的属于轻链的点, 第一个存该点所能拓展的最长路径, 第二个是她的编号
    
50. multiset<pii, greater<pii> > s[N];
    
51. // 如果这个点是重链的 top, rt[u] 就是对应线段树根
    
52. int rt[N];
    
53. 
    
54. struct Node {
    
55.     int sum, lmax, rmax;
    
56. 
    
57.     Node(){};
    
58.     // sum 这个链的路径和
    
59.     // lmax 这个链从上往下走, 再从轻孩子中下去的最长路径
    
60.     // rmax 这个链从下往上走的最长路径
    
61.     Node(int a, int b, int c) { sum = a, lmax = b, rmax = c; }
    
62. 
    
63.     // t 在下面
    
64.     Node operator+(const Node& t) {
    
65.         return Node(sum + t.sum, max(lmax, sum + t.lmax), max(t.rmax, t.sum + rmax));
    
66.     }
    
67. };
    
68. 
    
69. // SGT
    
70. struct SGT {
    
71.     int lc[N << 2], rc[N << 2], tot;
    
72.     Node t[N << 2];
    
73. 
    
74.     void Up(int u) { t[u] = t[lc[u]] + t[rc[u]]; }
    
75. 
    
76.     void Build(int& u, int l, int r) {
    
77.         if (!u)
    
78.             u = ++tot;
    
79.         if (l == r) {
    
80.             // 一个点的时候 s 就是答案
    
81.             t[u].sum = val[rdfn[l]];
    
82.             t[u].lmax = t[u].rmax = val[rdfn[l]] + s[rdfn[l]].begin()->first;
    
83.             return;
    
84.         }
    
85. 
    
86.         int mid = (l + r) >> 1;
    
87.         Build(lc[u], l, mid);
    
88.         Build(rc[u], mid + 1, r);
    
89.         Up(u);
    
90.     }
    
91. 
    
92.     void Modify(int u, int l, int r, int p) {
    
93.         if (l == r) {
    
94.             t[u].sum = val[rdfn[l]];
    
95.             t[u].lmax = t[u].rmax = val[rdfn[l]] + s[rdfn[l]].begin()->first;
    
96.             return;
    
97.         }
    
98. 
    
99.         int mid = (l + r) >> 1;
    
100.         if (p <= mid)
     
101.             Modify(lc[u], l, mid, p);
     
102.         if (p > mid)
     
103.             Modify(rc[u], mid + 1, r, p);
     
104.         Up(u);
     
105.     }
     
106. 
     
107.     Node Query(int u, int l, int r, int ql, int qr) {
     
108.         if (qr < ql)
     
109.             return Node(0, 0, 0);
     
110.         if (ql <= l && r <= qr) {
     
111.             return t[u];
     
112.         }
     
113. 
     
114.         int mid = (l + r) >> 1;
     
115.         if (qr <= mid)
     
116.             return Query(lc[u], l, mid, ql, qr);
     
117.         if (ql > mid)
     
118.             return Query(rc[u], mid + 1, r, ql, qr);
     
119.         return (Query(lc[u], l, mid, ql, qr) + Query(rc[u], mid + 1, r, ql, qr));
     
120.     }
     
121. } sgt;
     
122. 
     
123. void Init(int u) {
     
124.     s[u].emplace(0, u);
     
125. 
     
126.     for (auto v : e[u]) {
     
127.         if (v == f[u] || v == hc[u])
     
128.             continue;
     
129.         // 存的是轻孩子
     
130.         Init(v);
     
131.         s[u].emplace(sgt.t[rt[v]].lmax, v);
     
132.     }
     
133. 
     
134.     if (hc[u])
     
135.         Init(hc[u]);
     
136.     else
     
137.         sgt.Build(rt[L[u]], dfn[L[u]], dfn[u]);
     
138. }
     
139. 
     
140. int Query(int u) {
     
141.     int res = s[u].begin()->first + val[u];
     
142.     int sum = val[u], v;
     
143.     Node temp;
     
144. 
     
145.     while (u) {
     
146.         // 从上往下走
     
147.         temp = sgt.Query(rt[L[u]], dfn[L[u]], dfn[R[u]], dfn[u] + 1, dfn[R[u]]);
     
148.         res = max(res, temp.lmax + sum);
     
149.         // 从下往上走
     
150.         temp = sgt.Query(rt[L[u]], dfn[L[u]], dfn[R[u]], dfn[L[u]], dfn[u] - 1);
     
151.         res = max(res, temp.rmax + sum);
     
152. 
     
153.         sum += temp.sum;
     
154. 
     
155.         v = f[L[u]];
     
156.         if (!v)
     
157.             break;
     
158. 
     
159.         // 这样写的原因是第一个点取不到
     
160.         sum += val[v];
     
161.         auto it = s[v].begin();
     
162.         if (it->second == L[u])
     
163.             it++;
     
164. 
     
165.         res = max(res, it->first + sum);
     
166.         u = v;
     
167.     }
     
168. 
     
169.     return res;
     
170. }
     
171. 
     
172. void Modify(int u, int x) {
     
173.     val[u] = x;
     
174.     int v, last;
     
175. 
     
176.     // 一个点的更新会带动它上面的重链底点更新
     
177.     while (u) {
     
178.         v = L[u];
     
179.         last = sgt.t[rt[v]].lmax;
     
180.         sgt.Modify(rt[v], dfn[L[u]], dfn[R[u]], dfn[u]);
     
181. 
     
182.         // 无法造成影响就退
     
183.         if (sgt.t[rt[v]].lmax == last || v == 1) {
     
184.             break;
     
185.         }
     
186. 
     
187.         s[f[v]].erase(make_pair(last, v));
     
188.         s[f[v]].emplace(sgt.t[rt[v]].lmax, v);
     
189.         u = f[v];
     
190.     }
     
191. }
     
192. 
     
193. int main() {
     
194.     ios::sync_with_stdio(0);
     
195.     cin.tie(0);
     
196. 
     
197.     freopen("lycoris.in", "r", stdin);
     
198.     freopen("lycoris.out", "w", stdout);
     
199. 
     
200.     cin >> n;
     
201.     for (int i = 1; i <= n; i++) {
     
202.         cin >> val[i];
     
203.     }
     
204.     for (int i = 1; i < n; i++) {
     
205.         int u, v;
     
206.         cin >> u >> v;
     
207.         e[u].emplace_back(v);
     
208.         e[v].emplace_back(u);
     
209.     }
     
210. 
     
211.     dfs0(1, 0);
     
212.     dfs1(1, 1);
     
213.     Init(1);
     
214. 
     
215.     string op;
     
216.     int x, y;
     
217. 
     
218.     while (1) {
     
219.         cin >> op;
     
220.         if (op[0] == 'D') {
     
221.             break;
     
222.         } else if (op[0] == 'Q') {
     
223.             cin >> x;
     
224.             cout << Query(x) << '\n';
     
225.         } else {
     
226.             cin >> x >> y;
     
227.             Modify(x, y);
     
228.         }
     
229.     }
     
230. 
     
231.     return 0;
     
232. }

复制代码

很cool的阳

cc885544

额滴神

学习中！！！

liujun_fishc