榜二体验单。https://www.luogu.com.cn/problem/P11751简单题但要注意 ‘ \ ’ 这个字符要写两个才行·。#includebits/stdc.h using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; string sa, sb; cin n; cin sa sb; for (int i 0; i sa.size(); i ) { if (sa[i] \\) { if (sa[i 4] .) { cout v; i 4; } else if (sa[i 4] \\){ cout w; i 8; } else{ cout v; } } } return 0; }https://www.luogu.com.cn/problem/P11752我想了半个小时这能不能过。后来被逼得没着了打了个骗分的结果是正解谁能告诉我是怎么过的还是做比赛不够多不然看到就知道可以打。如果一个区间计数问题区间合法性质可以转化成一个条件是是否满足。同时越扩大越糟糕找最大可能方案就可以用双指针。像本题如果问至少 k 个钉子就应该把问题转换成总数 - 至多 k - 1 个钉子解决。枚举上下界 双指针。#includebits/stdc.h using namespace std; typedef long long LL; const int N 510; char s[N]; LL a[N][N], sum[N][N]; LL get_(int sti, int edi, int stj, int edj) { return sum[edi][edj] - sum[sti - 1][edj] - sum[edi][stj - 1] sum[sti - 1][stj - 1]; } int main () { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; memset(a, 0, sizeof(a)); memset(sum, 0, sizeof(sum)); for (int i 1; i n; i ) { cin (s 1); for (int j 1; j m; j ) { if (s[j] #) { a[i][j] 1; } } } for (int i 1; i n; i ) { for (int j 1; j m; j ) { sum[i][j] a[i][j] sum[i - 1][j] sum[i][j - 1] - sum[i - 1][j - 1]; } } LL ans 0; for (int i 1; i n; i ) { for (int j i; j n; j ) { int tp 1; for (int k 1; k m; k ) { while (get_(i, j, k, tp) 1 tp m) { tp ; } ans (tp - k); } } } cout ans \n; return 0; }https://www.luogu.com.cn/problem/P11753wyh 给我透的做法我自己的话估计 st 表 二分乱搞。注意到可以分为和分别处理两边处理方式是一样的这里假设是处理左端点。对于每个点我们要找离它最近的不能被它整除的点即不是该点倍数的最近点所谓“截断点”。对于点和再它右边的点如果点是点的倍数无疑点是更好的“截断点”人选。因为点包含的因子少于可能等于点所包含的因子这样能成为别的点倍数的可能性更小。这类似滑动窗口取最小值我们考虑使用单调栈毕竟又没规定范围。#includebits/stdc.h using namespace std; typedef long long LL; const int N 1e6 10; LL a[N]; int sta[N], l[N], r[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i ) { cin a[i]; } int tp 1; sta[0] 0; sta[tp] 1; l[1] 1; for (int i 2; i n; i ) { while ((a[sta[tp]] % a[i] 0) tp 1) { tp --; } l[i] sta[tp] 1; tp ; sta[tp] i; } tp 1; sta[0] n 1; sta[tp] n; r[n] n; for (int i n - 1; i 1; i --) { while ((a[sta[tp]] % a[i] 0) tp 1) { tp --; } r[i] sta[tp] - 1; tp ; sta[tp] i; } for (int i 1; i n; i ) { cout (r[i] - l[i] 1) ; } cout \n; return 0; }https://www.luogu.com.cn/problem/P11754四人合力做出来的我在赛后 7 min AC 了。最终答案一定是乘法原理我们考虑连续的一段 0。对于第 i 个点我们可以选择涂 i 1 的颜色 / 涂自己的颜色 / 强制不涂填 -1。1涂 i 1 的颜色如果颜色 0涂 i 1 的时候顺着涂过来就好。如果颜色是 0也算 i 1 顺位过来的不管 i 1 是 0 还是 -1反正就是没有自己的选择。2涂自己的颜色我们这里从左到右涂色这样就可以保证每个点都有自主选择了。3强制不涂就是涂 -1然后发现如果总共有个答案就是。一群人想半天还用了牛顿二项式定理结果就是这么简单的东西 TwT考虑到数据范围用动态开点线段树就好。我这里为了方便用线段树管理值的 1 代表原来的 0管理值 0 代表原来的 -1。这样求 0 的个数用整一段的和就行反转操作用异或 lazy tag。你问我线段树开多大实测 1.5e7 能过害怕炸用 vector 就好。线段树里面就四个 long long 参啊不要学某人开六个。。81 分就看看是不是哪里有该开 long long 的没开0 的个数作为幂次是千千万万不能 % MOD 的#includebits/stdc.h using namespace std; typedef long long LL; const int N 15e6 10; const LL P 1e9 7; int a[N]; LL q_pow(LL a, LL b) { LL c 1; while (b) { if (b 1) { c c * a % P; } a a * a % P; b 1; } return c; } #define lc(p) tr[p].ls #define rc(p) tr[p].rs struct node { int ls, rs; LL siz; int lazy; } tr[N]; int rt, trlen; LL n; void newd(int p, LL L, LL R) { trlen ; p trlen; tr[p] {0, 0, R - L 1, 0}; } void pushup(int p) { tr[p].siz tr[lc(p)].siz tr[rc(p)].siz; } void pushdown(int p, LL L, LL R) { if (tr[p].lazy) { LL mid (L R) 1; if (!lc(p)) { newd(lc(p), L, mid); } if (!rc(p)) { newd(rc(p), mid 1, R); } tr[lc(p)].lazy ^ 1; tr[lc(p)].siz (mid - L 1) - tr[lc(p)].siz; tr[rc(p)].lazy ^ 1; tr[rc(p)].siz (R - (mid 1) 1) - tr[rc(p)].siz; tr[p].lazy 0; } } void change(int p, LL L, LL R, LL l, LL r) { if (!p) { newd(p, L, R); } if (r L || R l) { return ; } if (l L R r) { tr[p].siz (R - L 1) - tr[p].siz; tr[p].lazy ^ 1; return ; } LL mid (L R) 1; pushdown(p, L, R); change(lc(p), L, mid, l, r); change(rc(p), mid 1, R, l, r); pushup(p); } int main () { ios::sync_with_stdio(false); cin.tie(0); int q; cin n q; trlen 0; rt 0; while (q --) { LL l, r; cin l r; change(rt, 1ll, n, l, r); cout q_pow(3, tr[rt].siz) \n; } return 0; }