前言D 和 E 阴到没边了……一、A - illegal#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 ; typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; 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() { string s; cins; int ns.length(); if(n%5) { 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; }没啥好说的判断直接输出即可。二、B - Personnel Change#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 ; typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; 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,m; cinnm; vectorintcnts(m1); for(int i1,a,b;in;i) { cinab; cnts[b]; cnts[a]--; } for(int i1;im;i) { coutcnts[i]endl; } } 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 的贡献所以每次统计一下贡献输出即可。三、C - Understory#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 ; typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; 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 q; cinq; mapint,intcnts; int sum0; int op,h; while(q--) { cinoph; if(op1) { cnts[h]; sum; } else { vectorintdel; for(auto [k,v]:cnts) { if(kh) { break; } sum-cnts[k]; del.push_back(k); } for(auto k:del) { cnts.erase(k); } } coutsumendl; } } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }因为每个数会被添加一次被删除一次所以就可以每次暴力删除复杂度是 O(n)。那么考虑用一个 map 来维护每次暴力删除即可。四、D - Concat Power of 2#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 ; typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; 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; const int MAXN30; vectorllpow(MAXN); vectorlllen(MAXN); for(int i0;iMAXN;i) { pow[i]1i; len[i]to_string(pow[i]).length(); } vectorllbit(10); bit[0]1; for(int i1;i10;i) { bit[i]10*bit[i-1]; } vectorsetllnums(10); nums[0].insert(0); for(int i1;i9;i) { for(int j0;jMAXN;j) { if(len[j]i) { break; } for(auto x:nums[i-len[j]]) { nums[i].insert(x*bit[len[j]]pow[j]); } } } setllres; for(int i1;i9;i) { for(auto x:nums[i]) { res.insert(x); } } for(auto x:res) { if(--n0) { coutxendl; return ; } } } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; init(); while(t--) { solve(); } return 0; }沟槽的 Attention is all you need……观察样例三注意到当好数逼近 10^9 时此时 n 的规模是 10^6。那么其实是可以暴力搜反正最多不超过 10^6 个。考虑根据长度暴力搜那么就是一个类似 dp 的过程。对于当前长度 i枚举每个 2 的幂。若当前幂的长度为 j那么就可以拼在所有长度为 i-j 的数转移过来。五、E - Tree Distance#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 ; typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; 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}; struct DSU{ vectorintfather; //自定义 DSU(int n){ father.assign(n,0); for(int i0;in;i){ father[i]i; } } int find(int i){ if(i!father[i]){ father[i]find(father[i]); } return father[i]; } bool same(int x,int y){ return find(x)find(y); } bool merge(int x,int y){ int fxfind(x); int fyfind(y); if(fxfy){ return false; } father[fx]fy; return true; } }; void solve() { int n; cinn; vectorvectorlla(n1,vectorll(n1)); vectorarrayll,3edge; for(int i1;in;i) { for(int ji1;jn;j) { cina[i][j]; edge.push_back({i,j,a[i][j]}); } } sort(edge.begin(),edge.end(),[](auto x,auto y) { return x[2]y[2]; }); DSU dsu(n1); vectorvectorpllg(n1); for(auto [u,v,w]:edge) { if(!dsu.same(u,v)) { dsu.merge(u,v); g[u].push_back({v,w}); g[v].push_back({u,w}); } } vectorvectorllans(n1,vectorll(n1)); for(int i1;in;i) { auto dfs[](auto self,int u,int fa,ll dis)-void { ans[i][u]dis; for(auto [v,w]:g[u]) { if(v!fa) { self(self,v,u,disw); } } }; dfs(dfs,i,0,0); } for(int i1;in;i) { for(int ji1;jn;j) { if(ans[i][j]!a[i][j]) { 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; }纯你妈 guess 啊……注意到在暴力按给定关系连边后若树存在那么其一定是这张图的最小生成树。考虑证明这个结论。运用反证法假设该合法的树不是最小生成树。那么在 Kruskal 构建最小生成树的过程中对于当前要选的边 (u,v)其必然是连接 u 和 v 两个连通块权值最小的边。那么如果不选这条边而是选择 (x,y) 这条边来连接这两个连通块则必有权值也就是有。那么因为此时选择了 (x,y) 这条边且边权非负所以就导致从 u 到 v 的路径必然大于从 x 到 y 的路径也就是有。这是矛盾的所以可以说明合法的树必然是最小生成树。六、F - Make Bipartite 3#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 ; typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; 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}; struct DSU{ vectorintfather; //自定义 vectorintsz; vectorintcolor; vectorintcnts; vectorvectorintchild; DSU(int n){ father.assign(n,0); sz.assign(n,1); color.assign(n,0); cnts.assign(n,0); child.assign(n,vectorint(0)); for(int i0;in;i){ father[i]i; child[i].push_back(i); } } int find(int i){ if(i!father[i]){ father[i]find(father[i]); } return father[i]; } bool same(int x,int y){ return find(x)find(y); } bool merge(int fx,int fy){ father[fx]fy; sz[fy]sz[fx]; for(auto u:child[fx]) { color[u]^1; if(color[u]) { cnts[fy]; } child[fy].push_back(u); } return true; } }; void solve() { int n,q; cinnq; int ans0; DSU dsu(n1); int u,v; while(q--) { cinuv; if(ans-1) { cout-1endl; continue; } if(dsu.same(u,v)) { if(dsu.color[u]dsu.color[v]) { ans-1; } } else { int fudsu.find(u); int fvdsu.find(v); ans-min(dsu.cnts[fu],dsu.sz[fu]-dsu.cnts[fu]); ans-min(dsu.cnts[fv],dsu.sz[fv]-dsu.cnts[fv]); int chg(dsu.color[u]dsu.color[v]); if(dsu.sz[fu]dsu.sz[fv]) { swap(fu,fv); } for(auto x:dsu.child[fu]) { dsu.color[x]^chg; if(dsu.color[x]) { dsu.cnts[fv]; } dsu.child[fv].push_back(x); } dsu.father[fu]fv; dsu.sz[fv]dsu.sz[fu]; ansmin(dsu.cnts[fv],dsu.sz[fv]-dsu.cnts[fv]); } 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; }这就是启发式合并嘛感觉以前是见过的。首先不难想到因为每次只能加边所以若当前图不是个二分图了之后不管怎么操作这张图就都不可能是二分图了。首先可以发现对于同一个连通块内的点其染色情况是可以任意翻转的。那么由于要求黑色的个数最少所以就是连通块内黑色和白色的点数取最小。所以若黑色点的个数是 cnt连通块的大小是 size那么答案就是 min(cnt,size-cnt)。所以可以发现不管如何翻转最终答案都是不变的。所以考虑用并查集维护出当前所有连通块内的染色情况然后对当前要连的边 (u,v) 进行讨论。第一种情况若原本 u 和 v 在同一个连通块内那么若 u 和 v 同色则此时就必然不合法了。否则就什么也不用做即可。第二种情况若 u 和 v 不在同一个连通块内若此时 u 和 v 不同色那么直接连接即可。若是同色的那么此时就需要把其中一个连通块内所有点的颜色翻转一下然后再连接。对于第二种情况首先需要把原本这两个连通块的贡献减掉再加上连接后大连通块的贡献。之后需要考虑翻转问题。由于直接随意暴力全翻转的话最差会一直把所有点都翻转一遍所以复杂度是 O(n^2) 的。此时就涉及到启发式合并了即每次暴力翻转较小的连通块内的所有点。观察每个点被翻转的次数对于当前两个连通块 A 和 B其中就有。所以每次合并后较小的连通块的大小至少翻一倍。所以对于每个点初始只有自己大小为 1每合并一次大小翻一倍所以其最多就只会被翻转 O(log n) 次所以是可以的。七、G - Minimum XOR Walk#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 ; typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; 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}; templateint BIT,typename Tll struct Xor_Basis{ int cnt; bool zero; bool normal; T data[BIT1]; Xor_Basis(){reset();} void reset(){ cnt0; zerofalse; normalfalse; for(int i0;iBIT;i)data[i]0; } bool insert(T x){ for(int iBIT;i0x;i--){ if(xi1){ if(data[i]0){ data[i]x; cnt; normalfalse; return true; } x^data[i]; } } zerotrue; return false; } void rebuild(){ if(normal){ return; } for(int iBIT;i0;i--){ if(data[i]0){ continue; } for(int ji-1;j0;j--){ if(data[i]j1){ data[i]^data[j]; } } } normaltrue; } T query_max(T x0){ for(int iBIT;i0;i--){ if(~(xi)1){ x^data[i]; } } return x; } T query_min(T x){ for(int iBIT;i0;i--){ if(xi1){ x^data[i]; } } return x; } //kth minimum T query_kth(ll k){ rebuild(); if(zero){ k--; } if(k0||k(1llcnt)){ return -1; } T res0; for(int i0;iBIT;i){ if(data[i]){ if(k1){ res^data[i]; } k1; } } return res; } ll query_rank(T x){ rebuild(); ll res0,k1; for(int i0;iBIT;i){ if(data[i]){ if(xi1){ res|k; } k1; } } return reszero; } //线性基合并 friend constexpr Xor_Basis operator|(const Xor_Basis lhs, const Xor_Basis rhs){ Xor_Basis reslhs; for(int i0;iBIT;i){ if(rhs.data[i]){ res.insert(rhs.data[i]); } } res.zerolhs.zero|rhs.zero; return res; } constexpr Xor_Basis operator|(const Xor_Basis rhs){ for(int i0;iBIT;i){ if(rhs.data[i]){ insert(rhs.data[i]); } } return *this; } //线性基求交 friend constexpr Xor_Basis operator(const Xor_Basis lhs, const Xor_Basis rhs){ using i128__int128_t; Xor_BasisBIT*2,i128tmp; for(int i0;iBIT;i){ tmp.insert(((i128)lhs.data[i]BIT)|lhs.data[i]); tmp.insert((i128)rhs.data[i]BIT); } Xor_Basis res; for(int i0; iBIT;i){ if(tmp.data[i]){ res.data[i]tmp.data[i]; res.cnt; } } res.zerotrue; return res; } }; templatetypename T struct Trie{ vectorvectorinttrie; vectorintpass; vectorintend; int cnt; int n; int kind; int base; Trie(int _n,int _kind,int _base){ n_n; kind_kind; base_base; trie.assign(n,vectorint(kind)); pass.assign(n,0); end.assign(n,0); cnt1; } void insert(const T s){ int cur1; pass[cur]; for(int i30,path;i0;i--){ pathsi1; if(trie[cur][path]0){ trie[cur][path]cnt; } curtrie[cur][path]; pass[cur]; } end[cur]; } ll query(int x,int k) { ll ans0; int cur1; for(int i30;i0;i--) { int pathxi1; if(ki1) { anspass[trie[cur][path]]; curtrie[cur][path^1]; } else { curtrie[cur][path]; } } return anspass[cur]; } }; void solve() { int n,m,k; cinnmk; vectorvectorpiig(n1); for(int i1,u,v,w;im;i) { cinuvw; g[u].push_back({v,w}); g[v].push_back({u,w}); } Xor_Basis30,intbase; vectorintpath(n1); vectorintvis(n1); auto dfs[](auto self,int u,int fa,int cur)-void { path[u]cur; vis[u]1; for(auto [v,w]:g[u]) { if(v!fa) { int nxtcur^w; if(vis[v]) { base.insert(nxt^path[v]); } else { self(self,v,u,nxt); } } } }; dfs(dfs,1,0,0); Trieinttrie(31*n,2,0); ll ans0; for(int i1;in;i) { int curbase.query_min(path[i]); anstrie.query(cur,k); trie.insert(cur); } 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; }首先是一个Trick对于图上异或问题考虑构建生成树然后将每个环的异或和插入线性基解决。首先在对整张图搞出一棵生成树后从根节点开始递归构建出从根节点到每个点 u 的异或和。那么对于从 u 到 v 路径上的异或和就是因为其 LCA 往上的部分可以异或消掉。而对于非树边所构成的每个环其都可以对这条路径的异或和产生影响。因为不管怎么去往每个环最后回来的时候是可以把这条路上的权值异或消掉的。而每个环都可以选择去或者不去那么问题就转化成了对于任意点对 (u,v)求其中 s 是所有环的异或和任意组合能搞出的某个异或和。那么就有一个Trick对于异或任意组合的问题就可以使用线性基解决。所以在将所有环的异或和插入线性基后由于暴力枚举点对的复杂度是 O(n^2) 的所以需要考虑优化。由于线性基可以满足任意组合所以考虑将转化为和。可以证明两者是等价的因为对于的结果因为想要和线性基组合搞出一个最小值所以对于是 1 的位肯定是要让其异或上线性基当前位消去的。那么由于这位是 1就说明这位上和的状态必然不同。所以其单独和线性基组合必然是一个异或上线性基的当前位一个不异或所以是不会影响合并结果的0 的情况类似。那么在构建出表示的最小值后此时问题就变为了计数有多少对 (i,j) 使得。这个就可以通过将前缀插入字典树每次考察每一位求得。具体方法是在将所有前缀插入字典树后对于当前数去字典树上从高位到低位考察每一位。保证在遍历的过程中考虑过的位和 K 相同。那么若当前位在 K 中是 1此时既可以选 1 也可以选 0。若选择了 0后续就可以任意选择所以直接加上当前节点的 pass然后去选 1 的情况往后考虑。否则即当前位在 K 中是 0那么就只能选 0 去后续考虑。最后注意要加上叶节点的 pass 然后将当前插入线性基即可。总结好不容易能补完一场 abc……END