前言我只能说不喜欢打 cf 是有原因的全 nm 构造这还是算法竞赛吗……一、A. Construct an Array#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; for(int in1;i2*n;i) { couti ; } coutendl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }首先如果从小到大填那么相邻两数的加和是一定不会重复的。之后可以发现如果直接从 1 开始填那么相邻的两数是会加出在之后出现的数的考虑避免这种情况。注意到值域范围是 1 到 2n所以考虑从 n1 开始往 2n 填这样相邻两数的加和必然大于 2n不可能在数组中出现。二、B. Another Sorting Problem#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } //nondecreasing, which means set d[i]a[i]-a[i-1], for all d[i]0 //if a d[i]0, we need to add it to 0, this will make d[i1]-d[i] vectorintd(n2); for(int i1;in;i) { d[i]a[i]-a[i-1]; } int ans0; for(int i1;in;i) { if(d[i]0) { ansmax(ans,-d[i]); d[i1]d[i]; d[i]0; } } for(int i1;in;i) { if(a[i-1]a[i]) { a[i]ans; if(a[i-1]a[i]) { NO; } } } YES; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }对于非递减序列考虑从原数组的差分数组入手分析那么问题就等效于让差分数组的每个数都大于等于 0。那么对于差分数组小于 0 的元素 x就需要将其加上 -x 变成 0此时造成的影响是差分数组下一个位置的元素加上 x。由于需要一次操作满足所有位置所以要加的数必然需要满足每个位置的需求。那么就可以考虑遍历数组对所有差分数组小于 0 的位置取绝对值的最大值这个数就是满足所有约束的最小的 k。那么之后再遍历一遍检查能否通过这个 k 使得整个数组非递减即可。三、C. Chipmunk Theo and Equality逆天注意力题……#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } vectorarrayint,2v; for(int i1;in;i) { int xa[i]; if(x1) { v.push_back({1,0}); v.push_back({2,1}); continue; } int cur0; while(x1) { v.push_back({x,cur}); if(x%2) { x; } else { x/2; } cur; } v.push_back({1,cur}); } sort(v.begin(),v.end()); int mv.size(); int ansINF; for(int i0;im;i) { int ji; int cur0; while(jmv[j][0]v[i][0]) { curv[j][1]; j; } int lenj-i; if(lenn) { ansmin(ans,cur); } ij-1; } coutansendl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }由于操作相当于左移所以对于一个数总的操作次数就是 bit width 加上 popcount所以最多就只会操作 60 次。所以就可以考虑暴力模拟记录每个数出现的次数和需要的总次数。之后再 check 一遍取最小代价即可。需要注意的是直接拿 map 存会超时。又因为最差结果的空间不会太大所以可以考虑拿数组存每个结果最后排序一下每次考察相同的数即可。四、D. Maximum Prefix Sums傻逼题……#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; string s; cins; s s1; vectorlla(n2); for(int i1;in;i) { cina[i]; } a[n1]0; vectorllc(n2); for(int i1;in;i) { cinc[i]; } c[0]-INFLL; c[n1]c[n]; if(s[1]0) { a[1]c[1]; } else { if(a[1]!c[1]) { No; } } const ll V-2e11; vectorllb(n2); b[1]a[1]; for(int i1;in;i) { if(c[i]c[i-1]) { No; } int ji; while(jnc[j]c[i]) { j; } for(int ki1;kj;k) { if(s[k]0) { a[k]V; } b[k]b[k-1]a[k]; if(b[k]c[i]) { No; } } if(jn||s[j]0) { a[j]c[j]-b[j-1]; b[j]c[j]; } else { b[j]c[j]; ll realc[j]-a[j]; for(int kj-1;ki;k--) { if(realc[i]) { No; } if(s[k]0) { a[k]real-b[k-1]; } real-a[k]; } if(real!c[i]) { No; } } ij-1; } coutYesendl; for(int i1;in;i) { couta[i] ; } coutendl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }首先不难想到对于 c 中连续的相同段前缀和必然是递减的。所以考虑每次考虑一整个相同段对于其中没确定的位置可以直接贪心地填一个无穷小值。过程中每次计算前缀和 b若违反约束就必然无解。之后由于每次考虑相同的一段所以下一个位置必然是前缀和增大的位置所以就有前缀最大值 c 就是前缀和本身。所以若下一个位置没确定或超过范围了那么填的这个数就可以通过当前位的 c 和上一位的前缀和直接相减得到。否则的话此时就可以根据这个位置的数倒退算出之前的前缀和那么首先若违反约束也无解。若碰到一个没确定的位置就可以通过将这个位置修正正确使得前缀和符合实际要求。若这样倒推到最后发现和要求的前缀和对不上那同样说明无解。五、E. Graph Cutting无敌好题#include bits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; //dsu on tree void solve1() { int n,d; cinnd; vectorvectorintg(n1); for(int i1,u,v;in-1;i) { cinuv; g[u].push_back(v); g[v].push_back(u); } auto calc[](int root)-ll { vectorintdep(n1); vectorintfat(n1); vectorintsiz(n1); vectorintson(n1); auto dfs1[](auto self,int u,int fa)-void { fat[u]fa; dep[u]dep[fa]1; siz[u]1; for(auto v:g[u]) { if(v!fa) { self(self,v,u); siz[u]siz[v]; if(siz[v]siz[son[u]]) { son[u]v; } } } }; dfs1(dfs1,root,0); vectorllcnts(n1); ll ans0; auto add[](auto self,int u)-void { cnts[dep[u]]; for(auto v:g[u]) { if(v!fat[u]) { self(self,v); } } }; auto query[](auto self,int u,int lca)-void { ll needd-dep[lca]-(dep[u]-dep[lca])dep[lca]; if(need0) { anscnts[need]; } for(auto v:g[u]) { if(v!fat[u]) { self(self,v,lca); } } }; auto erase[](auto self,int u)-void { cnts[dep[u]]0; for(auto v:g[u]) { if(v!fat[u]) { self(self,v); } } }; auto dfs2[](auto self,int u,int keep)-void { for(auto v:g[u]) { if(v!fat[u]v!son[u]) { self(self,v,0); } } if(son[u]) { self(self,son[u],1); } if(u!root) { anscnts[d]; cnts[dep[u]]; } for(auto v:g[u]) { if(v!fat[u]v!son[u]) { query(query,v,u); add(add,v); } } if(keep0) { erase(erase,u); } }; dfs2(dfs2,root,0); return ans; }; ll ans0; for(int i1;in;i) { anscalc(i); } coutans/3endl; } //dp void solve2() { int n,d; cinnd; vectorvectorintg(n1); for(int i1,u,v;in-1;i) { cinuv; g[u].push_back(v); g[v].push_back(u); } vectorvectorvectorintdp(n1,vectorvectorint(d1,vectorint(4))); vectorintsiz(n1); auto dfs[](auto self,int u,int fa)-void { siz[u]1; dp[u][1][1]1; for(auto v:g[u]) { if(v!fa) { self(self,v,u); auto ndpdp[u]; for(int j1;jmin(siz[v],d-1);j) { for(int y1;y2;y) { ndp[j1][y]dp[v][j][y]; } } for(int i1;imin(siz[u],d);i) { for(int x1;x2;x) { for(int j1;jmin(siz[v],d)ijd;j) { for(int y1;xy3;y) //at least have one!! { ndp[ij][xy]dp[u][i][x]*dp[v][j][y]; } } } } dp[u]ndp; siz[u]siz[v]; } } }; dfs(dfs,1,0); ll ans0; for(int i1;in;i) { ansdp[i][d][3]; } coutansendl; } //long light decomposition void solve3() { int n,d; cinnd; vectorvectorintg(n1); for(int i1,u,v;in-1;i) { cinuv; g[u].push_back(v); g[v].push_back(u); } auto calc[](int root)-ll { vectorintdep(n1); vectorintfat(n1); vectorintsiz(n1); vectorintlen(n1); vectorintson(n1); auto dfs1[](auto self,int u,int fa)-void { fat[u]fa; dep[u]dep[fa]1; siz[u]1; len[u]1; for(auto v:g[u]){ if(v!fa){ self(self,v,u); siz[u]siz[v]; if(len[son[u]]len[v]){ son[u]v; } } } len[u]len[son[u]]1; }; dfs1(dfs1,root,0); vectorinttop(n1); vectorintdfn(n1); vectorintseg(n1); int cntd0; vectorlldp(n1); ll ans0; auto dfs2[](auto self,int u,int up)-void { top[u]up; dfn[u]cntd; seg[cntd]u; dp[dfn[u]]1; if(son[u]0){ return ; } self(self,son[u],up); for(auto v:g[u]){ if(v!fat[u]v!son[u]){ self(self,v,v); } } int needd-dep[u]; for(auto v:g[u]) { if(v!fat[u]v!son[u]) { for(int i0;ilen[v];i) { if(0need0need-i-1need-i-1len[u]) { ans1ll*dp[dfn[u]need-i-1]*dp[dfn[v]i]; } } for(int i0;ilen[v];i) { dp[dfn[u]i1]dp[dfn[v]i]; } } } if(u!root) { if(0needneedlen[u]) { ansdp[dfn[u]need]; } } }; dfs2(dfs2,root,0); return ans; }; ll ans0; for(int i1;in;i) { anscalc(i); } coutans/3endl; } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve3(); } return 0; }对于这种三元组问题还是可以考虑枚举一个点然后转化为求合法的二元组个数最后为了防止重复除以 3 即可。那么在枚举某个点的时候就可以将这个点看作根节点去操作。对于合法的二元组 (a,b)考虑从其 lca 入手那么最小连通子树首先就需要包括根节点到 lca 路径上的所有节点。若路径上点的个数为 x此时可以发现 a,b 两点到 lca 路径上的节点个数之和依然是定值 d-x。所以在枚举 lcau 的时候此时就需要枚举节点 a计算出 a 到 u 路径上的节点个数 y。此时能和 a 构成合法二元组的 b 的个数就是 u 子树内到 u 路径上点的个数为 d-x-y 的点的个数。1.树上启发式合并解由于要在 O(n) 时间内每次枚举 u 子树内的每个点所以考虑使用树上启发式合并。那么就可以维护一个高度数组 cnts表示当前 u 子树内高度为 i 的节点个数。那么在每次枚举轻儿子 v 的时候由于计算的是子树 v 内每个点和之前兄弟子树组合的答案所以需要先统计答案再合并。那么就是先枚举 v 子树内的每个点算出需要的节点个数注意边界累加答案然后再遍历一遍合并即可。需要注意当前节点 u 就是 a 的情况此时需要在继承完重儿子的之后若 u 不是根节点就特判累加答案即可。2.长链剖分解由上面的分析可知在最后统计的时候需要到 u 距离为某个定值的节点个数这个形式也可以使用长链剖分优化树型 dp 解决。那么就是定义为到 u 距离为 i 的节点个数然后每次还是枚举短儿子的长度让两个距离相乘累加之后再合并个数即可。注意此时不能在继承长儿子之后统计当前节点 u 为 a 情况的答案因为在枚举短儿子长度时统计不到当前节点 u所以需要在所有合并完成后再统计。3.树上背包解注意到数据范围不大可以允许开的数组那么也可以往多维的树型 dp 考虑。手玩可以发现二维的 dp 会漏状态而且很难转移。所以考虑定义为在当前节点 u 的子树内考虑当前节点 u 必须被选中在子树内构成大小为 i 的最小连通子树目前选了 j 个点的方案数答案就是。对于转移首先在来到当前节点 u 时初始化表示只选了 u 一个节点。 之后对于每个儿子节点 v首先需要考虑在之前考虑过的子树内不选节点只在 v 的子树内选择的方案数那么就是此时由于需要再加上 u 节点所以 y 的范围是 {1,2} 的。对于和之前节点组合的情况考虑双重循环枚举考虑过的每个节点和 v 子树内的每个节点这样的复杂度依然是因为等价于枚举 (u,v) 的二元组个数。那么若在之前选了 x 个节点构成了 i 的大小在 v 子树内选了 y 个节点构成了 j 的大小注意边界情况的讨论所以转移就是。总结多点算法少点 guess……END