主要是一些讨论复杂或者容易写错的模拟
1. CF912C
题意：$n$个敌人，给定每个敌人初始血量，最大血量，每秒恢复血量，还有$m$个更新操作，需要选出一个时间$t$释放技能，使得得分最大
2. CF118C
题意：给定串s，每次修改花费为新数与原数差的绝对值，求使$s$中至少$k$个相同的数时的最小代价，输出字典序最小的方案
3. CF704C
题意：给定$n$个表达式，$m$个变量，每个变量出现次数$le 2$，每个表达式至多含$2$个变量，求$2^m$种情况中有多少种情况使得$n$个表达式异或值为$1$
题意：给定四条边范围，求多少种情况能够成四边形
5. CF1320D
题意：给定01串，每次询问两个子串，是否能从其中一个变换为另一个，每次变换把"110"变为"011"或"011"变为"110"
6. gym102576I
题意：给定大数，求拆分为不超过25个回文数的和
7. CF1428D
题意：$n imes n$的网格，每行每列至多$2$个障碍，给定从每个位置往上扔回旋镖撞到障碍数，求构造合法方案
8. CF1332F
题意：给定树，求所有边集非空的边导出子图的独立集个数
题意：给定$w$天每人得分增加情况，求每个人平均排名
题意：给定平面$n$个点，求把每个点$(x_i,y_i)$变为$(x_i,0)$或$(0,y_i)$，使得任意两点距离最大值最小
题意：定义了序列$S$，给定长$n$序列$a$，求$S$每个长$n$子串与$a$的汉明距离和以及最小汉明距离
1. 考虑最优释放时间，一定是某个敌人血量增加到超过damage的前一秒或者一次更新操作的前一秒，用一个优先队列维护所有更新事件
#include <bits/stdc++.h> using namespace std; const int N = 1e5+10; struct event { int64_t time,val; int id,type; bool operator < (const event &rhs) const { if (time!=rhs.time) return time>rhs.time; return type>rhs.type; } }; priority_queue<event> q; int max_health[N],regen[N]; bool can[N]; int64_t vis[N]; int main() { int n, m, bounty, increase, damage; scanf("%d%d%d%d%d", &n, &m, &bounty, &increase, &damage); int cnt = 0; for (int i=0; i<n; ++i) { int start_health; scanf("%d%d%d", &max_health[i], &start_health, ®en[i]); if (max_health[i]<=damage) { if (increase) return puts("-1"),0; ++cnt; continue; } if (start_health<=damage) { ++cnt; can[i] = 1; if (regen[i]) { q.push({(damage-start_health)/regen[i],0ll,i,2}); q.push({(damage-start_health)/regen[i]+1,0ll,i,1}); } } } for (int i=0; i<m; ++i) { int time,enemy,health; scanf("%d%d%d", &time, &enemy, &health); if (max_health[enemy-1]<=damage) continue; q.push({time,health,enemy-1,0}); q.push({time-1,0ll,enemy-1,2}); } int64_t ans = 0; while (q.size()) { auto u = q.top(); q.pop(); if (u.type==2) ans = max(ans, (bounty+(int64_t)u.time*increase)*cnt); else if (u.type==1) { if (u.val!=vis[u.id]) continue; can[u.id] = 0; --cnt; } else { vis[u.id] = u.time; if (u.val<=damage) { if (!can[u.id]) can[u.id] = 1, ++cnt; if (regen[u.id]) { q.push({u.time+(damage-u.val)/regen[u.id],u.time,u.id,2}); q.push({u.time+(damage-u.val)/regen[u.id]+1,u.time,u.id,1}); } } else if (can[u.id]) can[u.id] = 0, --cnt; } } if (cnt) { if (increase) ans = -1; else ans = max(ans, bounty*(int64_t)cnt); } printf("%lld ", ans); }
2. 先求出最小花费，然后贪心枚举前缀，判断后缀是否合法即可
#include <bits/stdc++.h> using namespace std; const int N = 1e4+10, INF = 1e9; int cnt[10],cur[10]; char s[N]; int main() { int n, k; scanf("%d%d%s", &n, &k, s+1); for (int i=1; i<=n; ++i) ++cnt[s[i]-='0']; //当前每种数为cur，可修改的数为cnt时的最小花费 auto gao = [&]() { int ans = INF; for (int num=0; num<10; ++num) { int now = cur[num], cost = 0; for (int d=0; d<10; ++d) { int x = num+d, t; if (x<10) { t = min(k-now, cnt[x]); now += t; cost += t*d; } int y = num-d; if (y!=x&&y>=0) { t = min(k-now, cnt[y]); now += t; cost += t*d; } } if (now==k) ans = min(ans, cost); } return ans; }; int mi = gao(); printf("%d ", mi); for (int i=1; i<=n; ++i) { --cnt[s[i]]; for (int u=0; u<10; ++u) { ++cur[u]; int cost = gao()+abs(s[i]-u); if (cost==mi) { putchar(u+'0'); mi -= abs(s[i]-u); break; } --cur[u]; } } puts(""); }
3. 一个括号看做一个点，一个变量相当于连接两个点，可以看做边，由于每个点度数不超过$2$，这样得到的图一定是若干环和链，分别对每个连通块dp一下，最后再dp合并。实现略复杂，需要特判孤立点和自环
#include <bits/stdc++.h> using namespace std; const int N = 1e5+10, P = 1e9+7; int n, m, sz[N], L[N], R[N], vis[N], deg[N]; vector<pair<int,int>> g[N]; void add(int &a, int64_t b) {a=(a+b)%P;} array<int,2> solve1(int x) { int dp[2][2][2]; memset(dp,0,sizeof dp); if (sz[x]==2) { if (g[x][0].second) { dp[0][0][1] = dp[0][1][1] = 1; dp[0][1][0] = 2; } else { dp[0][0][0] = dp[0][1][0] = 1; dp[0][1][1] = 2; } } else { if (g[x][0].second) dp[0][0][1] = dp[0][1][0] = 1; else dp[0][0][0] = dp[0][1][1] = 1; } vis[x] = 1; x = g[x][0].first; int cur = 0; array<int,2> c{}; while (1) { cur ^= 1; memset(dp[cur],0,sizeof dp[0]); vis[x] = 1; if (g[x].size()==1&&vis[g[x][0].first]) { if (sz[x]==2) { for (int u=0; u<2; ++u) for (int v=0; v<2; ++v) { int w = dp[cur^1][u][v]; add(c[u^v],w), add(c[u^1],w); } } else { for (int u=0; u<2; ++u) for (int v=0; v<2; ++v) add(c[u^v],dp[cur^1][u][v]); } break; } else { int tp = vis[g[x][0].first]; for (int u=0; u<2; ++u) for (int v=0; v<2; ++v) { int w = dp[cur^1][u][v]; if (g[x][tp].second) { add(dp[cur][u^v][1],w); add(dp[cur][u^1][0],w); } else { add(dp[cur][u^v][0],w); add(dp[cur][u^1][1],w); } } x = g[x][tp].first; } } return c; } array<int,2> solve2(int x) { int dp[2][2][2][2]; memset(dp,0,sizeof dp); if (g[x][0].second==0&&g[x][1].second==0) { dp[0][0][0][0] = dp[0][1][1][0] = dp[0][1][0][1] = dp[0][1][1][1] = 1; } else if (g[x][0].second&&g[x][1].second==0) { dp[0][0][1][0] = dp[0][1][0][0] = dp[0][1][1][1] = dp[0][1][0][1] = 1; } else if (g[x][0].second==0&&g[x][1].second) { dp[0][0][0][1] = dp[0][1][1][1] = dp[0][1][0][0] = dp[0][1][1][0] = 1; } else { dp[0][0][1][1] = dp[0][1][0][1] = dp[0][1][1][0] = dp[0][1][0][0] = 1; } vis[x] = 1; x = g[x][0].first; int cur = 0; array<int,2> c{}; while (1) { cur ^= 1; memset(dp[cur],0,sizeof dp[0]); vis[x] = 1; int tp; if (!vis[g[x][0].first]) tp = 0; else if (!vis[g[x][1].first]) tp = 1; else { for (int u=0; u<2; ++u) for (int v=0; v<2; ++v) for (int z=0; z<2; ++z) add(c[u^(v|z)],dp[cur^1][u][v][z]); break; } for (int z=0; z<2; ++z) { for (int u=0; u<2; ++u) for (int v=0; v<2; ++v) { int w = dp[cur^1][u][v][z]; if (g[x][tp].second) { add(dp[cur][u^v][1][z],w); add(dp[cur][u^1][0][z],w); } else { add(dp[cur][u^v][0][z],w); add(dp[cur][u^1][1][z],w); } } } x = g[x][tp].first; } return c; } int main() { scanf("%d%d", &n, &m); for (int i=1; i<=n; ++i) { int t, x; scanf("%d", &t); sz[i] = t; while (t--) { scanf("%d", &x); if (L[abs(x)]==0) { if (x<0) L[abs(x)] = -i; else L[x] = i; } else { if (x<0) R[abs(x)] = -i; else R[x] = i; } } } int cnt = 0; for (int x=1; x<=m; ++x) { if (!L[x]) ++cnt; else if (R[x]) { if (L[x]==R[x]) { deg[abs(L[x])] = -1; continue; } else if (L[x]==-R[x]) { deg[abs(L[x])] = -2; continue; } if (L[x]<0&&R[x]<0) L[x]=-L[x],R[x]=-R[x]; if (L[x]>0&&R[x]>0) { g[L[x]].push_back({R[x],0}); g[R[x]].push_back({L[x],0}); ++deg[L[x]]; ++deg[R[x]]; } else { L[x] = abs(L[x]), R[x] = abs(R[x]); g[L[x]].push_back({R[x],1}); g[R[x]].push_back({L[x],1}); ++deg[L[x]]; ++deg[R[x]]; } } } array<int64_t,2> c{}; c[0] = 1; for (int i=1; i<=n; ++i) { if (deg[i]==0&&sz[i]==2) { c = {(c[0]+c[1]*3)%P,(c[0]*3+c[1])%P}; vis[i] = 1; } else if (deg[i]==0||deg[i]==-1) { c = {(c[0]+c[1])%P,(c[0]+c[1])%P}; vis[i] = 1; } else if (deg[i]==-2) { c = {2*c[1]%P,2*c[0]%P}; vis[i] = 1; } } for (int i=1; i<=n; ++i) if (deg[i]==1&&!vis[i]) { auto t = solve1(i); c = {(c[0]*t[0]+c[1]*t[1])%P,(c[0]*t[1]+c[1]*t[0])%P}; } for (int i=1; i<=n; ++i) if (!vis[i]) { auto t = solve2(i); c = {(c[0]*t[0]+c[1]*t[1])%P,(c[0]*t[1]+c[1]*t[0])%P}; } for (int i=1; i<=cnt; ++i) c[1] = c[1]*2%P; printf("%lld ", c[1]); }
4. 枚举每条边作为最大值的情况，那么剩余三条边方案数形式是$sum limits_{i}sum limits_{j}sum limits_{k} [i+j+k>x]$，暴力分类讨论即可$O(1)$算，总复杂度就是$O(T(a+b+c+d))$
当然也可以再分类讨论去掉最外层min，从而优化到$O(T)$，但是过于麻烦
#include <bits/stdc++.h> using namespace std; int64_t s0(int l, int r) { return r-l+1; } int64_t s1(int l, int r) { return (r+l)*(r-l+1ll)/2; } int64_t s2(int64_t l, int64_t r) { return (r-l+1)*(2*l*l+2*r*r+2*l*r+r-l)/6; } int64_t solve(int l1, int r1, int l2, int r2, int l3, int r3, int x) { if (l3>r3||l1>r1||l2>r2) return 0; int64_t ans = 0; int lx = max(l1,x-l2-l3+1), rx = r1; if (lx<=rx) ans += s0(l2,r2)*s0(l3,r3)*s0(lx,rx); lx = max(l1,x-l3+1-r2), rx = min(r1, x-l2-l3); if (lx<=rx) ans += s0(l3,r3)*(s0(lx,rx)*(r2-x+l3)+s1(lx,rx)); lx = max(l1, x-l2+1-r3), rx = min(r1, x-l3-r2); if (lx<=rx) ans += (s0(l2,r2)*(r3-x)+s1(l2,r2))*s0(lx,rx)+s0(l2,r2)*s1(lx,rx); lx = max({l1,x-l2+1-r3,x-l3-r2+1}), rx = min(r1,x-l2-l3); int64_t ret = 0; if (lx<=rx) { ans += s0(lx,rx)*(1+x-l3-l2)*(r3-x)-s2(lx,rx)+s1(lx,rx)*(1+2*x-l3-l2-r3); ret += s0(lx,rx)*(l2+x-l3)*(x-l3-l2+1)-s1(lx,rx)*(x-l3+x-l3+1)+s2(lx,rx); } lx = max(l1,x-r2+1-r3), rx = min({r1,x-l2-r3,x-l3-r2}); if (lx<=rx) { ans += s0(lx,rx)*(r2-x+r3)*(r3-x)+s1(lx,rx)*(r2-2*x+2*r3)+s2(lx,rx); ret += s0(lx,rx)*(r2-x+r3)*(r2+x+1-r3)+s1(lx,rx)*(x-r3+x-r3+1)-s2(lx,rx); } if (r3-l3>=1) { int lx = max(l1,x-l3-r2+1), rx = min(r1,x-l2-r3); if (lx<=rx) { ans += s0(lx,rx)*(r3-l3)*(r3-x)+s1(lx,rx)*(r3-l3); ret += s0(lx,rx)*(r3-l3)*(2*x+1-l3-r3)+s1(lx,rx)*(2*l3-2*r3); } } return ans+ret/2; } int main() { int T; scanf("%d", &T); while (T--) { int L[4], R[4]; for (int i=0; i<4; ++i) scanf("%d%d", &L[i], &R[i]); int64_t ans = 0; for (int x=L[0]; x<=R[0]; ++x) { ans += solve(L[1],min(R[1],x),L[2],min(R[2],x),L[3],min(R[3],x),x); } for (int x=L[1]; x<=R[1]; ++x) { ans += solve(L[0],min(R[0],x-1),L[2],min(R[2],x),L[3],min(R[3],x),x); } for (int x=L[2]; x<=R[2]; ++x) { ans += solve(L[0],min(R[0],x-1),L[1],min(R[1],x-1),L[3],min(R[3],x),x); } for (int x=L[3]; x<=R[3]; ++x) { ans += solve(L[0],min(R[0],x-1),L[1],min(R[1],x-1),L[2],min(R[2],x-1),x); } printf("%lld ", ans); } }
5. 可以观察到两个串如果每个长为奇数的极长连续1段的左侧0的个数都相同，那么就可以互相转换，否则一定不能
考虑hash，把每个0看做1，把长为奇数的极长连续1段看做1个2，长为偶数的1直接忽略即可
询问的时候特判下端点情况，相当于要把几段hash值合并
#include <bits/stdc++.h> using namespace std; const int N = 2e5+10; const int P = 876756319, B = 99999991; int fac[N], f[N], sum[N], cnt[N], L[N], R[N]; char s[N]; int main() { int n; scanf("%d%s", &n, s+1); fac[0] = 1; for (int i=1; i<=n; ++i) fac[i] = fac[i-1]*(int64_t)B%P; int now = 0; for (int i=1; i<=n; ++i) { sum[i] = sum[i-1]+(s[i]=='0'); } for (int i=1; i<=n; ++i) { if (s[i]=='1') { int j = i; while (j+1<=n&&s[j+1]=='1') ++j; for (int k=i; k<=j; ++k) { L[k] = i; R[k] = j; } if (j-i+1&1) f[j] = (f[i-1]*(int64_t)B+2)%P, cnt[j] = cnt[i-1]+1; else f[j] = f[i-1], cnt[j] = cnt[i-1]; i = j; } else { f[i] = (f[i-1]*(int64_t)B+1)%P; cnt[i] = cnt[i-1]+1; } } int q; scanf("%d", &q); while (q--) { int l1, l2, len; scanf("%d%d%d", &l1, &l2, &len); int r1 = l1+len-1, r2 = l2+len-1; if (sum[r1]-sum[l1-1]!=sum[r2]-sum[l2-1]) { puts("No"); continue; } if (sum[r1]-sum[l1-1]==0||sum[r1]-sum[l1-1]==r1-l1+1) { puts("Yes"); continue; } auto get = [&](int l, int r) { int len = cnt[r]-cnt[l]+1; int ans = (f[r]-f[l-1]*(int64_t)fac[len])%P; if (ans<0) ans += P; return pair<int,int>{ans,len}; }; auto add = [&](pair<int,int> a, pair<int,int> b) { int va = a.first, lena = a.second, vb = b.first, lenb = b.second; return pair<int,int>((va*(int64_t)fac[lenb]+vb)%P,lena+lenb); }; auto Hash = [&](int l, int r) { pair<int,int> ans; if (R[l]) { if (R[l]-l+1&1) ans = {2,1}; l = R[l]+1; } if (L[r]) { ans = add(ans,get(l,L[r]-1)); if (r-L[r]+1&1) ans = add(ans,{2,1}); } else ans = add(ans,get(l,r)); return ans; }; puts(Hash(l1,r1)==Hash(l2,r2)?"Yes":"No"); } }
6. 每次将$n$贪心减掉最大的回文，一定不超过25
具体实现就是从高位到低位枚举第一位不能与原数相等的位置，然后中间全填9
做减法的时候没判$ile {len}_{now}$，WA了一发
#include <bits/stdc++.h> using namespace std; const int N = 1e5+10; int len[N], cnt[N]; char s[N], ans[25][N]; int main() { int T; scanf("%d", &T); while (T--) { scanf("%s", s+1); int n = strlen(s+1); reverse(s+1,s+1+n); for (int i=1; i<=n; ++i) s[i] -= '0'; int now = 0; auto gao = [&](char *t) { int ok = 1; for (int i=1; i<=n; ++i) if (s[i]!=s[n-i+1]) ok = 0; if (ok) { for (int i=1; i<=n; ++i) t[i] = s[i]; return n; } for (int i=1; i<=n; ++i) cnt[i] = cnt[i-1]+(s[i]!=0); if (n>1&&cnt[n-1]==0&&s[n]==1) { for (int i=1; i<=n-1; ++i) t[i] = 9; return n-1; } int tp = 0; for (int i=n; i>=n-i+1; --i) { if (i*2-1!=n) { if (s[i]>s[n-i+1]) tp = 1; else if (s[i]<s[n-i+1]) tp = 0; if (cnt[i-1]-cnt[n-i+1]) continue; if (tp) { for (int j=n; j>i; --j) t[j] = t[n-j+1] = s[j]; t[i] = t[n-i+1] = s[i]-1; for (int j=i-1; j>=n-i+2; --j) t[j] = 9; return n; } } else { for (int j=n; j>i; --j) t[j] = t[n-j+1] = s[j]; if (tp) t[i] = s[i]-1; else t[i] = s[i]; return n; } } for (int i=n; i>n/2; --i) t[i] = t[n-i+1] = s[i]; return n; }; while (n) { len[now] = gao(ans[now]); for (int i=1; i<=n; ++i) { if (i<=len[now]) s[i] -= ans[now][i]; if (s[i]<0) s[i] += 10, --s[i+1]; } ++now; while (n&&!s[n]) --n; } printf("%d ", now); for (int i=0; i<now; ++i) { for (int j=len[i]; j>=1; --j) putchar(ans[i][j]+'0'); puts(""); } } }
7. 经过分析可以发现如果$a_x=3$，那么要匹配一个$y(y>x)$，并且$a_y=1,2,3$
如果$a_x=2$，那么要匹配一个$y(y>x)$，并且$a_y=1$
然后就是考虑$2$和$3$分配优先级的问题，再画一下可以发现交换两个匹配位置的话产生影响是不变的
所以只要碰到$1$就分给之前没匹配的$y$即可
#include <bits/stdc++.h> using namespace std; const int N = 1e5+10; int a[N], h[N][2]; int main() { int n; scanf("%d", &n); for (int i=1; i<=n; ++i) scanf("%d", &a[i]); for (int i=1; i<=n; ++i) h[i][0] = h[i][1] = 0; queue<int> q2, q3; auto chk = [&]() { int now = 1; for (int i=1; i<=n; ++i) { if (a[i]==1) { if (q2.size()) { h[i][0] = h[q2.front()][0]; q2.pop(); } else if (q3.size()) { if (now>n) return false; h[i][0] = now++; h[i][1] = h[q3.front()][0]; q3.pop(); } else { if (now>n) return false; h[i][0] = now++; } } else if (a[i]==2) { if (q3.size()) { if (now>n) return false; h[i][0] = now++; h[i][1] = h[q3.front()][0]; q3.pop(); } else { if (now>n) return false; h[i][0] = now++; } q2.push(i); } else if (a[i]==3) { if (q3.size()) { if (now>n) return false; h[i][0] = now++; h[i][1] = h[q3.front()][0]; q3.pop(); } else { if (now>n) return false; h[i][0] = now++; } q3.push(i); } } return q2.empty()&&q3.empty(); }; if (!chk()) puts("-1"); else { int tot = 0; for (int i=1; i<=n; ++i) { if (h[i][1]) tot += 2; else if (h[i][0]) ++tot; } printf("%d ", tot); for (int i=1; i<=n; ++i) { if (h[i][0]) printf("%d %d ", h[i][0], i); if (h[i][1]) printf("%d %d ", h[i][1], i); } } }
8. 树dp题，设${dp}_{x,0}$表示以$x$为根的子树导出子图含$x$且$x$不在独立集内且$x$可以不与儿子相连的方案，${dp}_{x,1}$表示以$x$为根的子树导出子图含$x$且$x$在独立集内且$x$可以不与儿子相连的方案，${dp}_{x,0}$为以$x$为根的子树导出子图不含$x$的方案
那么最终答案就是${dp}_{1,0}+{dp}_{1,1}-{dp}_{1,2}-1$
假设$x$的儿子集合为$T$，那么枚举每个儿子的边连还是不连可以得到转移为
${dp}_{x,0}=sumlimits_{Ssubseteq T} prodlimits_{yin S} ({dp}_{y,0}+{dp}_{y,1}) prodlimits_{y ot in S}({dp}_{y,0}+{dp}_{y,1}-{dp}_{y,2})$
${dp}_{x,1}=sumlimits_{Ssubseteq T} prodlimits_{yin S}{dp}_{y,0} prodlimits_{y ot in S} ({dp}_{y,0}+{dp}_{y,1}-{dp}_{y,2})$
${dp}_{x,2}=prodlimits_{yin T} ({dp}_{y,0}+{dp}_{y,1}-{dp}_{y,2})$
#include <bits/stdc++.h> using namespace std; const int N = 3e5+10, P = 998244353; vector<int> g[N]; int dp[N][3]; void dfs(int x, int f) { dp[x][0] = dp[x][1] = dp[x][2] = 1; for (int y:g[x]) if (y!=f) { dfs(y,x); dp[x][2] = dp[x][2]*(dp[y][0]+dp[y][1]-(int64_t)dp[y][2])%P; dp[x][0] = dp[x][0]*(2ll*dp[y][0]+2ll*dp[y][1]-dp[y][2])%P; dp[x][1] = dp[x][1]*(2ll*dp[y][0]+dp[y][1]-dp[y][2])%P; } } int main() { int n; scanf("%d", &n); for (int i=1; i<n; ++i) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(1,0); int ans = (dp[1][0]+dp[1][1]-(int64_t)dp[1][2]-1)%P; if (ans<0) ans += P; printf("%d ", ans); }