A贪心填。先尽量填竖着的再填横着的。因为这样最多会浪费 $1$ 个，所以达到了答案的上界。求出上界判断是否 $\leq$ 即可。B枚举一个位置 $i$，前面只保留 $0$ 后面只保留 $1$，判断是否合法即可。C首先第一步横着走还是竖着走都是一样的。我们设第一步横着走。那么横着走只可能用奇数位置的 $c_i$，竖着走只可能用偶数位置的 $c_i$。枚举总共有几段，然后贪心选择最小的即可。注意要保证每个 $c_i$ 被至少选一次。D推一下式子：设 $g=\gcd(a,b)$：$$ c\frac{ab}{g}-dg = x\\ cab = gx + dg^2\\ $$设 $a' = \frac{a}{g},b' = \frac{b}{g}$：$$ ca'b' = \frac{x}{g}+d\\ a'b' = \frac{\frac{x}{g}+d}{c} $$我们枚举 $g|x$，相当于问有多少对数字 $(a',b')$，满足 $\gcd(a',b')=1$ 并且 $a'b' = x$，设 $x$ 有 $w(x)$ 个质因子，答案就是 $2^{w(x)}$。线性筛预处理 $w(x)$ 即可。复杂度 $O(n+\sqrt n)$ ，可能需要卡常。E暴力做法：枚举 $l_1,r_1$，然后以这个为开头整一个 dp：设 $f_{i,j,c}$ 表示当前考虑到位置 $s_i,t_j$ 了（这两个位置还没选），最后一次选的字符是 $c$，转移枚举下一步选哪个即可。复杂度 $O(n^4 |\Sigma|)$。复杂度瓶颈在于枚举 $l_1,r_1$，考虑把枚举这个的过程也扔到 dp 里：设 $f_{i,j,c,0/1}$ 表示考虑到位置 $s_i,t_j$，如果最后一维是 $0$，$c \in \{0,1\}$，表示当前是在枚举 $i$ 还是枚举 $j$（这里设计成先移动 $i$ 再移动 $j$ 是为了防止算枚举的方案数）；如果最后一维是 $1$ 表示当前已经选好了某个位置，$c$ 就是正常表示最后一个字母是啥了。最后枚举结束的位置把答案加起来即可。写下转移式子：对于第一种转移，有：$$ \begin{align*} f_{i,j,0,0} &\to f_{i+1,j,0,0}\\ f_{i,j,0,0} &\to f_{i,j,1,0}\\ f_{i,j,1,0} &\to f_{i,j+1,1,0}\\ f_{i,j,1,0} &\to f_{i+1,j,s[i],1}\\ f_{i,j,1,0} &\to f_{i,j+1,t[j],1} \end{align*} $$对于第二种转移，就是暴力时的转移式子，也就是：$$ \begin{align*} [c \neq s[i]]f_{i,j,c,1} &\to f_{i+1,j,s[i],1}\\ [c \neq t[j]]f_{i,j,c,1} &\to f_{i,j+1,t[j],1} \end{align*} $$不过注意到我们这样实际上只要某一个串开始选就会被计入答案了，也就是说我们会多算某一个字符串选空字符串的情况，最后减去即可。这里减去要枚举每一个区间，判断是否可行，然后减去能产生的贡献。复杂度 $O(n^2 |\Sigma|)$。空间需要稍微注意一下。F普及组树形 dp。考虑树形 dp 求直径我们会记录 $v$ 往下的最长单链的长度，这个题我们也这样搞：设 $f_{v,i}$ 表示 $v$ 子树，最长单链长度为 $i$ 的方案树，转移合并两个子树，枚举是否切割，如果不切的话， $f_{v,i} \times f_{x,j} \to f_{v,\max(i,j+1)}$，这里要求 $i+j+1 \leq k$ 即可。树形背包，两维只需要枚举到 $sz_v,sz_x$。复杂度 $O(n^2)$。转移（或许？）可以长链剖分优化，因为第二维只关于深度，转移整体平移一下，所以可以直接 $O(1)$ 继承长儿子，剩下的暴力合并打标记即可。G如果不需要修改，答案就是 $\sum_{v \in V} (\text{deg}(v) \bmod 2)$：因为我们可以构造欧拉回路，将奇点都连到一个工具点 $S$ 上，然后跑 $S$ 开始的欧拉回路，按照方向是入边还是出边来分配颜色就好了。考虑如何动态维护这个东西：一个直观的想法是根据两端点的度数奇偶性进行分类讨论，但是我们新加入的边某个端点是奇点的时候我们要依据这个端点多余的边来确定新的点的颜色，所以我们记录 $to_x$ 表示如果 $x$ 是奇点，那么 $x$ 没配对的边是哪一个；考虑现在加入边 $w=(u,v)$：如果两个端点都是偶点：那这个边给什么颜色都无所谓，不失一般性我们设这个边的颜色为 $0$；如果一个端点是奇点一个是偶点：设 $u$ 是奇点，那么 $w$ 的颜色和 $to_u$ 的应该相反，然后 $u$ 变成了偶点，$v$ 变成了奇点，所以还有 $to_v = w$；两个端点都是奇点：我们假设 $u$ 和 $v$ 不在一个联通块：首先先把 $w$ 加入 $u$ 中，发现 $w$ 的颜色和 $to_u$ 的应该相反；然后把 $w$ 加入 $v$ 中：发现这时候 $w$ 的颜色和 $to_v$ 应该相反，也就是 $to_u$ 和 $to_v$ 颜色应该相同；但是有可能不相同，解决方案是我们考虑一个联通块内反转所有颜色的边答案是不变的，所以我们把 $v$ 的联通块所有的边颜色反转即可。为了支持这些操作，我们要写一个并查集维护在同一联通块的边，每个集合维护一下 $0$ 边的哈希值和和 $1$ 边的哈希值和。支持某个集合反转可以用类似带权并查集的方法：我们让某个点 $v$ 的权值为 $v$ 到并查集根的所有点的颜色的异或，然后我们钦定并查集根的颜色为 $0$，就能支持反转了。复杂度 $O(n \alpha(n))$。注意小心维护全局答案和每个联通块的值的答案。注意细节：第三种类如果 $u,v$ 在一个连通块内不能进行反转，要不然会违反根颜色钦定为 $0$ 的性质。
A$g(x)$ 实际是求原数和去除后缀 $0$ 后的数的比值，发现第一个不同的值一定会在 $10^x$ 达到，所以答案就是字符串长度。B我们先假设走了 $m$ 步，并且都是走第一种，那么相当于就是走了 $\frac{m(m+1)}{2}$，发现将第 $i$ 个位置改成第二种操作会减少 $i+1$，我们先找到最小的 $m$ 满足 $\frac{m(m+1)}{2} \geq x$ ，设 $r=\frac{m(m+1)}{2}-x$，发现一定有 $r \leq m$，而我们发现所有位置更改后能减少的量分别是 $2,3,\ldots,m+1$，发现只有 $r=1$ 的时候不能被表示出来，所以 $r=1$ 的时候让 $m+1$ 就是答案了。C注意这两个人的策略都是最大化自己的胜利步数，显然后手可以一直不接球等到先手耗尽体力的时候将球打回去，剩下的球先手都接不到，所以后手最大胜利次数就是 $y$，先手由于最后一次球被接住了，胜利次数是 $x-1$。D贪心模拟，假设当前手里的数字是 $x$，正在考虑第 $i$ 个位置：$a_{i-1} > a_i$：如果换不了（$a_i \leq x$） 就直接输了，否则我们一定会交换，看下是否满足条件$a_{i-1} \leq a_i$：如果 $x < a_i$，因为这个序列是不降的，就意味着以后都不能交换了，所以这时候判一下 $i+1$ 后缀是否有序，如果不有序你一定要交换；如果 $x \geq a_i$ 就可以不管。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 500+5; int n,x,a[MAXN]; bool f[MAXN]; inline void Solve(){ scanf("%d%d",&n,&x); FOR(i,1,n) scanf("%d",a+i); int p = 1; ROF(i,n,2){ if(a[i-1] > a[i]){ p = i;break; } } if(p == 1){ puts("0"); return; } int ans = 0; if(x < a[1]) std::swap(x,a[1]),++ans; FOR(i,2,p){ if(a[i-1] > a[i]){ if(a[i] <= x){ puts("-1");return; } std::swap(a[i],x);++ans; if(a[i-1] > a[i]){ puts("-1");return; } } else if(x < a[i] && i != p){ std::swap(a[i],x);++ans; } } printf("%d\n",ans); } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }E我们设正方形左下角 $(x,y)$ 边长为 $d$，枚举四个点分别对应正方形的哪些点，现在有三个变量 $x,y,d$，但我们发现贡献式子最终是形如若干个 $|x-x_i|,|x+d-x_i|,|y-y_i|,|y+d-y_i|$ 的和，如果将 $d$ 看成常量，发现 $x,y$ 一定会取让某个绝对值为 $0$ 的点，枚举取什么，剩下就变成了求 $\sum_i |d+c_i|$ 的最大值，也是一定会取某个零点的位置，都算算就好了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<LL,LL> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl LL xx[5],yy[5],x[5],y[5]; int p[5]; inline LL mabs(LL x){ return x < 0 ? -x : x; } std::vector<LL> S; inline LL gao(){ std::sort(all(S)); int t = S.size()>>1; LL p = -S[t-1],res = 0; for(auto x:S) res += abs(x+p); return res; } inline void Solve(){ FOR(i,1,4) scanf("%lld%lld",xx+i,yy+i),p[i] = i; LL ans = 1e18; do{ FOR(i,1,4) x[p[i]] = xx[i],y[p[i]] = yy[i]; for(auto i:{1,3}){ for(auto j:{1,2}){ S.clear(); LL c = abs(x[1]-x[i])+abs(x[3]-x[i])+abs(y[1]-y[j])+abs(y[2]-y[j]); for(auto k:{2,4}) S.pb(x[i]-x[k]); for(auto k:{3,4}) S.pb(y[j]-y[k]); std::vector<LL> T = S; LL mn = 1e18; mn = std::min(mn,gao()); S=T;FOR(k,0,1) S[k] = -S[k]; mn = std::min(mn,gao()); S=T;FOR(k,2,3) S[k] = -S[k]; mn = std::min(mn,gao()); S=T;FOR(k,0,1) S[k] = -S[k]; mn = std::min(mn,gao()); c += mn; ans = std::min(ans,c); } } }while(std::next_permutation(p+1,p+4+1)); printf("%lld\n",ans); } int main(){ int T;scanf("%d",&T); while(T--) Solve(); return 0; }F这题非常好的地方在于 dp 状态表示的不一定是个数，还可以是个字符串（设 $f_i$ 表示操作完了 $1 \ldots i$ ，前缀的最小字典序，转移的时候分类讨论 $i+1,i+2$ 的操作：U/D ，$f_{i} \to f_{i+1}$L，$f_i \to f_{i+1}$R+U/D，$f_{i} \to f_{i+2}$RL，$f_i \to f_{i+2}$直接转移即可，复杂度 $O(n^2)$。可以用滚动数组+二分哈希做到 $O(n \log n)$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 500+5; int n,k; int mn[26]; std::string f[MAXN],str; inline std::string ctos(char x){ return std::string(1,x); } inline void Solve(){ std::cin >> n >> k >> str;str = "0"+str; mn[0] = 0;FOR(i,1,k-2) mn[i] = i-1;mn[k-1] = 0; f[0].clear();FOR(i,1,n) f[i] = "{"; FOR(i,0,n-1){ f[i+1] = std::min(f[i+1],f[i]+ctos('a'+mn[str[i+1]-'a'])); if(i) f[i+1] = std::min(f[i+1],f[i].substr(0,i-1)+ctos(str[i+1])+f[i].back()); if(i != n-1) f[i+2] = std::min(f[i+2],f[i]+ctos('a'+mn[str[i+2]-'a'])+ctos(str[i+1])); if(i && i != n-1) f[i+2] = std::min(f[i+2],f[i].substr(0,i-1)+ctos(str[i+2])+f[i].back()+ctos(str[i+1])); } std::cout << f[n] << std::endl; } int main(){ std::ios::sync_with_stdio(false); int T;std::cin >> T; while(T--) Solve(); return 0; }Gdp 合并可以启发式合并。。这个很妙先考虑没有 if 咋做：设 $f_{i,x}$ 表示执行了前 $i$ 条语句，当前值是 $x$ 的答案，直接做是 $O(n^2)$ 的。观察转移相当于全局加上一个值和求一个最小值并单点赋值，用数据结构维护可以做到 $O(n \log n)$。这里可以直接用一个 set 维护最小值，map 维护每个下标对应的在 set 里的值，再维护个整体加标记即可。我们只需要维护可能的值的 dp 值就好了。有 if 咋做呢？我们发现 if 内部是独立的，可以做一样的 dp，只是 dp 的初值需要改一下，所以我们遇到 if 就进去做 dp ，做完后考虑如何合并这两个块：我们可以用启发式合并，将大小小的每一种 dp 值都合并到大的里，注意要特判一下 if 条件给的值对应的 dp 值（这里不能单纯去 min，需要覆盖）。启发式合并复杂度对的原因在于一次转移可以放缩看成加入一个元素，于是复杂度就是显然的 $O(n \log^2 n)$ 了。细节挺多的。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl int n,s; struct Node{// 全局加 单点修改 询问最小值 LL tag; std::map<int,LL> mp;// 位置 i 在 set 内的值 std::multiset<LL> S; Node(LL tag=0) : tag(tag) {} inline void update(int p,LL d){ if(p == s) return; if(mp.count(p)) S.erase(S.find(mp[p])); mp[p] = d-tag; S.insert(mp[p]); } inline LL get(int p){ if(!mp.count(p)) return 1e18; return mp[p]+tag; } inline void upmin(int p,LL d){ if(p == s) return; if(get(p) > d) update(p,d); } inline LL query(){ return *S.begin() + tag; } }; std::vector<Node> st; std::vector<int> oo; int main(){ scanf("%d%d",&n,&s); Node v;v.update(0,0); st.pb(v);oo.pb(-114514); FOR(i,1,n){ char opt[12];scanf("%s",opt); if(opt[0] == 's'){ int x,y;scanf("%d%d",&x,&y); if(st.back().mp.empty()) continue; LL c = st.back().query(); st.back().tag += y;st.back().upmin(x,c); } if(opt[0] == 'i'){ int x;scanf("%d",&x); LL c = st.back().get(x); Node v;if(c != 1e18) v.update(x,c); st.pb(v);oo.pb(x); } if(opt[0] == 'e'){ int tp = (int)st.size()-1,o = oo.back();bool flag = 1; if(st[tp].mp.size() > st[tp-1].mp.size()) std::swap(st[tp],st[tp-1]),flag = 0; for(auto x:st[tp].mp){ if(x.fi != o) st[tp-1].upmin(x.fi,x.se+st[tp].tag); else{ if(flag) st[tp-1].update(x.fi,x.se+st[tp].tag); } } st.pop_back();oo.pop_back(); } } printf("%lld\n",st[0].query()); return 0; }
A贪心删除出现次数最少的数。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; int n,a[MAXN],b[MAXN],k; int main(){ scanf("%d%d",&n,&k); FOR(i,1,n) scanf("%d",a+i),b[a[i]]++; int t = 0;FOR(i,1,n) t += (b[i] != 0); std::sort(b+1,b+n+1); int ans = 0; FOR(i,1,n){ if(t <= k) break; if(!b[i]) continue; ans += b[i];t--; } printf("%d\n",ans); return 0; }B逆序对期望，根据期望的线性性转成考虑每一对数的期望，由于权值是 $0/1$，现在变成了对于一对数 $(x,y)$，计算是一对逆序对的概率。我们设 $x<y$，那么一定是先共同经过若干轮都没有被选中，然后在第 $i$ 轮选中了 $y$ 但没有选中 $x$，之后若干轮后选了 $x$；我们枚举 $i$ 可以得到概率：$$ \begin{aligned} \sum_{i=1}^{\infty} (1-p)^{i-1}p (1-p)^i &= p(1-p)\sum_{i=0}^{\infty}(1-p)^{2i}\\ &= p(1-p)\frac{1}{1-(1-p)^2} \end{aligned} $$注意到对数有 $\binom n 2$ 个，所以答案是 $\binom n 2 p(1-p)\frac{1}{1-(1-p)^2}$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int ha = 998244353; const int inv2 = 499122177; inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } int main(){ int n,x,y;scanf("%d%d%d",&n,&x,&y); int p = 1ll*x*qpow(y)%ha; int ans = 1ll*n*(n-1)%ha*inv2%ha; int t = (1+ha-p)%ha;t = 1ll*t*t%ha; t = (1+ha-t)%ha;t = qpow(t); ans = 1ll*ans*t%ha; ans = 1ll*ans*(1+ha-p)%ha; ans = 1ll*ans*p%ha; printf("%d\n",ans); return 0; }C提供我考场的思路和标程思路，我的思路应该是正规 NOIP 思路（（虽然代码本质是一样的首先我们考虑有以下恒等式：$$ x^k = \sum_{i_1=1}^x \sum_{i_2=1}^x \cdots\sum_{i_k=1}^x 1 $$所以对于一条路径的 $x^k$ 可以理解成有序可重地选出 $k$ 条边，所以一个暴力dp的思想就是设 $f_{v,i}$ 表示从 $1$ 到 $v$ 选了 $i$ 个边的方案数，每次转移 $O(k)$ 枚举当前边被选了 $j$ 次，系数是 $\binom{k-i}{j}$，这样复杂度是 $O(mk^2)$ 的。优化：我们可以考虑每条路径的系数只和选了多少条不同的边有关，假设选了 $m$ 条不同的边，系数和大概是这样的一个东西：$$ \sum_{x_1 + x_2 + \ldots + x_m = k} \binom{k}{x_1,x_2,\ldots,x_m} $$这个东西我考试的时候写了 $k^3$ dp 出来的，但是可以发现实际上它是将 $k$ 个有标号小球放进 $m$ 个有标号小球，要求非空的方案数，也就是 $\left\{^k_m\right\}m!$。所以我们 dp 的时候只需要求出 $f_{v,i}$ 到 $v$ 点，选了 $i$ 条边的方案数，转移直接枚举当前边是否选，$O(mk + k^2)$。题解做法（一点点省选知识）：考虑恒等式：$$ x^k = \sum_{i=0}^k \left\{^k_i\right\}x^{\underline k} = \sum_{i=0}^k \left\{^k_i\right\}\binom x k k! $$所以我们只需要求出 $f_{v,i}$ 表示到 $v$ 点，所有路径的 $\binom x k$ 的和即可，注意到有 $\binom n m = \binom {n-1}{m} + \binom {n-1}{m-1}$，转移的时候只要枚举当前边是否选就行了。对于这种只能从一个点出发的 DAG 游走，只需要初始化起点然后正常拓扑排序即可。#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; const int MAXK = 500 + 5; const int ha = 998244353; inline char nc(){ #define SIZE 1000000+3 static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE; if(p1 == p2){ p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin); if(p1 == p2) return -1; } return *p1++; #undef SIZE } template <typename T> inline void read(T &x){ x = 0;int flag = 0;char ch = nc(); while(!isdigit(ch)){ if(ch == '-') flag = 1; ch = nc(); } while(isdigit(ch)){ x = (x<<1) + (x<<3) + (ch^'0'); ch = nc(); } if(flag) x = -x; } struct Edge{ int to,nxt; }e[MAXN<<1]; bool vis[MAXN]; int head[MAXN],cnt,deg[MAXN]; inline void adde(int u,int v){ e[++cnt] = (Edge){v,head[u]};head[u] = cnt; deg[v]++; } inline void add(int &x,int y){ (x += y);if(x >= ha) x -= ha; } int f[MAXN][MAXK]; int n,m,k; int fac[MAXN],inv[MAXN]; inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } inline void prework(){ fac[0] = 1;FOR(i,1,MAXN-1) fac[i] = 1ll*fac[i-1]*i%ha; inv[MAXN-1] = qpow(fac[MAXN-1]); ROF(i,MAXN-2,0) inv[i] = 1ll*inv[i+1]*(i+1)%ha; } inline int C(int n,int m){ if(n < 0 || m < 0 || n < m) return 0; return 1ll*fac[n]*inv[m]%ha*inv[n-m]%ha; } int g[MAXK][MAXK]; // i个变量,和为 j int main(){ prework(); read(n);read(m);read(k); g[0][0] = 1; FOR(i,1,k){ FOR(j,i,k){ FOR(x,1,j){ add(g[i][j],1ll*g[i-1][j-x]*C(k-(j-x),x)%ha); } } } FOR(i,1,m){ int u,v;read(u);read(v); adde(u,v); } std::queue<int> q; q.push(1);vis[1] = 1; while(!q.empty()){ int v = q.front();q.pop(); for(int i = head[v];i;i = e[i].nxt){ if(vis[e[i].to]) continue; q.push(e[i].to);vis[e[i].to] = 1; } } FOR(v,1,n){ if(!vis[v]){ for(int i = head[v];i;i = e[i].nxt){ deg[e[i].to]--; } } } q.push(1); f[1][0] = 1; // assert(deg[1]==0); FOR(i,1,n) vis[i] = 0; while(!q.empty()){ int v = q.front();q.pop();vis[v] = 1; for(int i = head[v];i;i = e[i].nxt){ FOR(x,0,k){ if(!f[v][x]) continue; FOR(y,0,std::min(1,k-x)){ add(f[e[i].to][x+y],f[v][x]); } } if(!--deg[e[i].to]) q.push(e[i].to); } } FOR(i,1,n){ int ans = 0; FOR(j,1,k){ add(ans,1ll*f[i][j]*g[j][k]%ha); } printf("%d\n",ans); } return 0; }D曼哈顿距离两维独立考虑，一维上给你若干个点，求一个点满足曼哈顿距离和最小是经典问题：只需要取中位数即可。那么对于这个题我们肯定要二分中位数 $x$，然后变成了计算有多少个交点满足横坐标 $\leq x$（求纵坐标的时候只需要求一下反函数即可）。赛时思路：按照斜率排序，考虑 $i,j$ 两条直线（$i < j$）的交点横坐标是 $\frac{b_i-b_j}{k_j-k_i}$，也就是要判断是否 $\frac{b_i-b_j}{k_j-k_i} \leq x \Rightarrow b_i+k_ix \leq k_jx+b_j$，离散化+树状数组或者归并排序求顺序对都可以。题解思路：考虑我们按照 $-\infty$ 的值排序，观察走到 $x$ 的变化：如果有交点就会产生一对逆序对。所以我们只需要一开始按照 $-\infty$ 的值编号，每次 check 的时候按照 $x$ 的位置的 $y$ 值排序，逆序对就是答案。#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 40000+5; const int EPS = 1e-9; inline int sgn(double x){ if(std::fabs(x) <= EPS) return 0; if(x < 0) return -1; return 1; } int n; int aa[MAXN],bb[MAXN],cc[MAXN]; std::pair<double,double> seg[MAXN]; double a[MAXN]; int c[MAXN]; struct BIT{ int tree[MAXN]; #define lowbit(x) ((x)&(-(x))) inline void add(int pos,int x){ while(pos < MAXN){ tree[pos] += x; pos += lowbit(pos); } } inline int query(int pos){ int res = 0; while(pos){ res += tree[pos]; pos -= lowbit(pos); } return res; } }bit; inline bool chk(double x){ // <=x 的交点个数是否超过一半 LL ans = 0; std::sort(seg+1,seg+n+1); FOR(i,1,n) a[i] = seg[i].se+x*seg[i].fi; std::vector<double> S; FOR(i,1,n) S.pb(a[i]); std::sort(all(S));S.erase(std::unique(all(S)),S.end()); FOR(i,1,n) c[i] = std::lower_bound(all(S),a[i])-S.begin()+1; CLR(bit.tree,0); FOR(i,1,n){ ans += bit.query(c[i]); bit.add(c[i],1); } LL lim = 1ll*n*(n-1)/2; // DEBUG(ans); return ans >= lim - ans; } inline double work(){ std::sort(seg+1,seg+n+1); double l = -1e9,r = 1e9,ans=0; FOR(i,1,70){ double mid = (l + r)/2.0; if(chk(mid)) ans = mid,r = mid; else l = mid; } return ans; } int main(){ scanf("%d",&n); FOR(i,1,n){ scanf("%d%d%d",aa+i,bb+i,cc+i); seg[i] = MP(-1.0*(1.0*aa[i]/bb[i]),1.0*cc[i]/bb[i]); } printf("%.6f ",work()); FOR(i,1,n){ seg[i] = MP(-1.0*(1.0*bb[i]/aa[i]),1.0*cc[i]/aa[i]); } // DEBUG(chk(-4905.877264)); // exit(0); printf("%.6f\n",work()); return 0; }
A做法一：答案一定是相邻两个的差的最小值。考虑反证法：如果 $[l,r](l+1 < r)$ 是答案，那么中间一定能取到一段小于等于平均数的。做法二：二分答案。首先答案是 $\min_{i,j} \frac{a_i-a_j}{j-i}$，考虑二分最小值，那么相当于对于所有 $j>i$ 要有 $a_i-a_j \geq kj-ki$，也就是 $a_i+k_i \geq a_j+k_j$，判断是否不增就行。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; int n; LL a[MAXN]; inline bool chk(LL k){ FOR(i,2,n){ if(a[i-1]+k*(i-1) < a[i]+k*i) return 0; } return 1; } int main(){ scanf("%d",&n);FOR(i,1,n) scanf("%lld",a+i); LL l = 0,r = 2e9,ans = -1; while(l <= r){ LL mid = (l + r) >> 1; if(chk(mid)) ans = mid,l = mid+1; else r = mid-1; } printf("%lld\n",ans); return 0; }B意思是前 $\frac{n}{2}$ 是排名前 $\frac{n}{2}$ 小的，那么标记出来应该移动的点（本来应该在后半部分，但是最初在前半部分），从里向外配对即可。（也考虑跨过每个点的贡献，是两边点的个数的最小值）#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 5e5 + 5; int a[MAXN],n; P b[MAXN]; bool vis[MAXN]; int main(){ scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i),b[i] = MP(a[i],i); std::sort(b+1,b+n+1); FOR(i,1,n/2) vis[b[i].se] = 1; int tp = 0;FOR(i,n/2+1,n) tp += vis[i]; LL ans = 0; std::vector<int> p1,p2; FOR(i,1,n/2) if(!vis[i]) p1.pb(i); FOR(i,n/2+1,n) if(vis[i]) p2.pb(i); FOR(i,0,tp-1) ans += p2[i]-p1[tp-i-1]; printf("%lld\n",ans); return 0; }C$lcp$ 问题，可以考虑建 trie 树，两个串的 $lcp$ 就是 $lca$。然后发现我们在每一个点肯定是尽量匹配子树内的点，所以自下往上贪心即可。注意卡空间，用 map 或者 vector 优化。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e6 + 5; int n,k; //std::map<int,int> ch[MAXN]; std::vector ch[MAXN]; //std::vector<int> ch[MAXN]; int dep[MAXN]; char str[100000+5]; int rt = 1,tot = 1; int sm[MAXN]; inline int find(int v,int y){ for(auto x:ch[v]) if(x.fi == y) return x.se; return 0; } inline void insert(char str[]){ int len = strlen(str+1),v = rt; FOR(i,1,len){ int o = str[i]-'a'; int t = find(v,o); if(!t) ch[v].pb(MP(o,++tot)),dep[tot] = dep[v]+1,t = tot; v = t; } sm[v]++; } LL ans = 0; inline void dfs(int v){ for(auto x:ch[v]){ dfs(x.se); sm[v] += sm[x.se]; } ans += dep[v]*(sm[v]/k); sm[v] %= k; } int main(){ // freopen("C.in","r",stdin); // freopen("C.out","w",stdout); scanf("%d%d",&n,&k); FOR(i,1,n){ scanf("%s",str+1);insert(str); } dfs(1); printf("%lld\n",ans); return 0; }D比较有意思，但是数据太水了。这种东西显然我们有一个单次询问 $O(k^2 \log n)$ 的做法：转化为 $k^2$ 次二维数点。那么我们考虑对着根号分治一下：设 $T = \sqrt{\sum_i k_i}$，如果 $k \geq T$，这样的询问不会有超过 $T$ 个，暴力即可。如果 $k < T$，拆成 $k^2$ 个询问，我们来分析下询问次数最大有多少个（我之前一直以为是 $k^2$ 个，才发现不是）。那么可以使用 $O(T)-O(1)$ 的分块技巧实现单点修改，前缀查询，根号平衡后复杂度是 $O(k\sqrt k)$ 的。#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; int n,m,N,q; int ans[MAXN]; inline char nc(){ #define SIZE 1000000+3 static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE; if(p1 == p2){ p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin); if(p1 == p2) return -1; } return *p1++; #undef SIZE } template <typename T> inline void read(T &x){ x = 0;int flag = 0;char ch = nc(); while(!isdigit(ch)){ if(ch == '-') flag = 1; ch = nc(); } while(isdigit(ch)){ x = (x<<1) + (x<<3) + (ch^'0'); ch = nc(); } if(flag) x = -x; } struct Node{ int y;char opt,d;int id;// 0 = mod Node(int y=0,char opt=0,char d=0,int id=0) : y(y),opt(opt),d(d),id(id) {} }; std::vector<Node> G[MAXN]; int l[MAXN],r[MAXN],B; inline void add(int x1,int x2,int y1,int y2,int d,int id){ if(x1 > x2 || y1 > y2) return; G[x2].pb(Node(y2,1,1*d,id)); G[x2].pb(Node(y1-1,1,-1*d,id)); G[x1-1].pb(Node(y2,1,-1*d,id)); G[x1-1].pb(Node(y1-1,1,1*d,id)); } const int MAXM = 500+5; struct DS{// O(sqrt(n)) 单点修改 O(1) 查询前缀和 int B,n; int bel[MAXN]; int sm[MAXM][MAXM],pre[MAXM]; inline void build(int xxx){ n = xxx;B = std::sqrt(1.0*n); FOR(i,1,n) bel[i] = (i-1)/B+1; } inline void add(int pos,int x){ // FOR(i,pos,n) pre[i] += x; // return; FOR(i,bel[pos]+1,bel[n]) pre[i] += x; FOR(i,pos-(bel[pos]-1)*B,bel[pos]*B-(bel[pos]-1)*B) sm[bel[pos]][i] += x; } inline int query(int x){ // return pre[x]; return pre[bel[x]]+sm[bel[x]][x-(bel[x]-1)*B]; } }ds; bool vis[MAXN]; int uu[MAXN],vv[MAXN]; int main(){ // freopen("D.in","r",stdin); // freopen("D.out","w",stdout); read(n);read(m);read(q); FOR(i,1,m){ int u,v;read(u);read(v); if(u > v) std::swap(u,v); uu[i] = u;vv[i] = v; G[u].pb(Node(v,0)); } B = 300; FOR(id,1,q){ int k;read(k); if(k >= B){ FOR(i,1,n) vis[i] = 0; FOR(i,1,k){ int l,r;read(l);read(r); FOR(j,l,r) vis[j] = 1; } FOR(i,1,m) ans[id] += vis[uu[i]]&vis[vv[i]]; } else{ FOR(i,1,k) read(l[i]),read(r[i]); // if(id != 6) continue; FOR(i,1,k){ FOR(j,i,k){ add(l[i],r[i],l[j],r[j],1,id); } } } } ds.build(n); FOR(i,0,n){ for(auto x:G[i]){ if(x.opt == 0) ds.add(x.y,1); } for(auto x:G[i]){ if(x.opt == 1) ans[x.id] += x.d*ds.query(x.y); } } // DEBUG(ans[1]); FOR(i,1,q) puts(ans[i]?"GG":"SAFE"); return 0; }
A我们固定 $s$ ，循环位移所有 $t$，发现答案就是相同的字母对数。而循环位移 $s$ 是本质不变的，所以答案乘个 $n$ 就好了。所以你构造的串中每个字母都要保证是 $s$ 中出现次数最大的，设这样的字母有 $c$ 个，答案显然是 $n^c$。B从高到低位贪心一定是最优的。对于每个点，我们可以通过判断周围点是否存在来确定这个点是否可以取走，每次取走能取的最大/最小后更新周围的点即可。C考虑每个数的贡献。枚举这个数下一个加号在哪里（我们这里没有计算 $j=n$ 的情况，因为可以 $O(n)$ 简单计算。）$$ \begin{aligned} &\sum_{i=1}^n a_i\sum_{j=i}^{n-1} 10^{j-i}\binom{n-j+i-2}{k-1}\\ &= \sum_{i=1}^n \frac{a_i}{10^i}\sum_{j=0}^{n-1-i} \binom{n-j-2}{k-1} 10^{j+i}\\ &= \sum_{i=1}^n a_i\sum_{j=0}^{n-i-1}\binom {n-j-2}{k-1}10^j \end{aligned} $$处理 $\sum_{i=0}^x \binom {n-x-2}{k-1}10^j$。D一定是先赋值，再加法，再乘法。考虑将所有操作都转化为乘法，然后贪心即可。E观察一下三条不交路径，一定形成了两个相交的环。对于这种问题我们考虑它的反面：如果不存在解一定是不存在两个相交的环，也就是每一个边至多出现于一个环上，也就是个边仙人掌。判断边仙人掌可以树上差分，然后只需要按照构造找出来一对路径 $(u_1,v_1)$ 和 $(u_2,v_2)$ 满足有交，设 $dep_{u_1} < dep_{v_1},dep_{u_2} < dep_{v_2}$，如下图：其中 $lca = lca(v_1,v_2)$，设那个没有标记的点是 $x$，我们可以构造三条 $\text{lca} \to x$ 的路径：分别是 $\text{lca} \to x$；$\text{lca} \to v_1 \to u_1 \to x$；$\text{lca} \to v_2 \to u_2 \to x$。
A设第 $i$ 个女生的限制为 $mx_i$，意思是存在一个男生给她 $mx_i$ 的礼物。设第 $i$ 个男生的限制为 $mn_i$，意思是要给所有女生 $mn_i$ 的礼物。设男女生都根据限制大小从小到大排序，首先如果 $mx_n > b_1$ 那么就无解（所有女生至少收到了 $mx_n$ 的礼物，但是第一个女生说她没收到，矛盾了）对于每个女生，我们都要钦定好一个男生送给他礼物，我们肯定要找一个限制最宽的男生给女生送满足她限制的礼物（也就是 $n$），要注意如果 $mx_n < mn_1$ 需要留一个位置来送 $mx_n$ 的礼物来满足限制，这时候会贪心的让男 $n$ 送给女 $1$ 价值 $mx_n$ 的礼物，再让男 $n-1$ 送女 $1$ 价值 $mn_1$ 的礼物。B这题我只会找规律。为了方便找规律，先将 $k$ 的定义改为最大的 $k$ 满足 $[1 \ldots k]$ 的串要么没出现，要么出现 $\geq 2$ 次。（也就是 $k+1$ 时题目定义的实际答案）观察这样的串：10101010101010 100100100100100100 10001000100010001000 1000010000100001000010000设它们的一个循环节长度为 $d$，我们发现长度在 $\leq 3d-1$ 时答案一直是 $\leq d$，之后每增加一个长度答案就会 $+1$，所以可以得到一个式子：$3d-1+(k-d-1) = n \Rightarrow d = \frac{n-k+2}{2}$，而在题目的限制下又一定整除，就可以构造出来了。感觉完全看运气。。C相当于限定了一个数和一段区间的大小关系，线段树优化建图+拓扑排序即可。D也算是半个构造题？先考虑没有规定拐点顺序怎么做：这是个经典问题。我们一开始选取最左边的点，每次走的点只要保证所有的点都在两点连线的一边就好了。明白了这个就会有拐点顺序了：因为你选的“一边”可以是左边也可以是右边，根据题意调整即可。如果是 L 就选择最右边的点，R 就选择最左边的点。E神仙交互题。。这个询问的本质是将每个点 $i$ 距离自己 $\leq d_i$ 的点都染黑（不包含自己）然后输出来哪些点被染黑了。首先我们选取 $1$ 号点为根，我们考虑过程分两步走：求出每个点的深度一个 naive 的做法是询问出所有距离 $\leq i$ 的点，做个类似差分的东西就好了。这个询问能传入长度为 $n$ 的数组，我们只用一个未免太奢侈了，对于这种问题需要考虑如何合并询问。我们如果维护处当前还未确定的深度区间 $[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$，对于每个区间我们只需要询问 $mid-1,mid$ 就可以得出距离是 $mid$ 的有哪些了。如果所有询问直接扔进去一块做会怎么样？那么很有可能 $mid-1$ 会超出边界，影响到上一个的选取，所以我们考虑排序后奇偶分组，这样就不会出现边界重复问题了，我们花了 $4$ 次操作能将问题规模减小一般，这一部分操作是 $4\lceil \log_2n \rceil$。求出每个点的父亲另一个 naive 的做法是对于一个深度为 $d$ 的点 $v$，我们枚举所有深度为 $d-1$ 的点 $u$，查询 $u$ 到距离为 $1$ 的点的集合，判断是否在里面。我们先想想能不能优化到对每一层能一起判断：考虑如果选择了多个点其实相当于是能确定某个点的父亲是否在这个集合内，于是我们考虑逐位确定：假设现在考虑所有点父节点编号二进制位第 $i$ 位是啥，我们把所有 $d-1$ 层二进制第 $i$ 位是 $1$ 的扔进去查询就好了。发现询问距离为 $1$ 的询问会影响上面和下面一层，于是考虑按层 $\bmod 3$ 分类，就不会有干扰的问题了。F你觉得我会神奇 $O(\frac{n^3}{\log n})$的 $3500$ 计数题？大概省选的时候会补。现在已经补了。这种没见过的题就是要找性质然后对性质dp，具体过程是（判定性问题 $\to $ 状态和转移 $\to $ 优化）判定性问题如果判定一个串是否是 $p$ 密度的呢？我们发现如果一个串是 $p$ 密度的，首先 $1 \ldots c$ 都要出现了，然后我们删掉 $1\ldots c$ 这一段的所有的数，剩下的应该是一个 $p-1$ 密度的串。设计状态有了这个东西就可以 dp 了：考虑设 $f_{i,j}$ 表示强制最后一次选的是 $i$，$j$ 密度串的个数，转移的时候只需要预处理 $g_{l,r}$ 表示区间 $[l,r]$ 的子序列数量，满足 $1 \ldots c$ 只出现了一次，并且选择 $a_r$ 后才满足 $1 \ldots c$ 都出现了一次（否则会算重）。这个可以先枚举右端点，然后扫左端点，维护一个出现次数的桶，相当于限制 $a_r$ 只能选一次，其他的只要至少选一个就行。时间复杂度 $O(n^3)$优化首先发现一个性质：$p$ 密度串的长度至少是 $cp$ 的。考虑判定过程每次至少删除 $c$ 个字符可得。那么发现 $f_{i,j}$ 中，$j \leq \frac{i}{c}$，复杂度降为了 $O(\frac{n^3}{c})$。但是还是不太行。我们考虑复杂度瓶颈主要在枚举下一个段是什么，但是枚举下一个段是为了防止算重的，如果不想算重就只能记录下当前还没填完的段已经选过哪些数了。于是考虑设 $f_{i,j,S}$ 表示考虑了前 $i$ 个数，最后一次选的是 $j$，当前这一个还没完整的段已经选过的数字集合是 $S$，我们只要在某次转移 $S=U$ 的时候直接将其强制转移到 $S'=0$，就和上面的方法是等价的了，这样的复杂度是 $O(\frac{n^2 2^c}{c})$，当 $c=\log_2 n$ 的时候两式的最小值取到最大值 $O(\frac{n^3}{\log_2 n})$ 。所以就当 $c \leq \log_2n$ 的时候用方法二（状压），否则用方法一，总复杂度 $O(\frac{n^3}{\log_2 n})$（代码里是反着写的）顺便一提时限 6s 我的代码是 5990ms 飘过的。。一些卡常技巧比如把能预先算的都放在最外层算有奇效。#include <bits/stdc++.h> #define fi first #define se second #define db double #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3000+5; const int ha = 998244353; int n,c,a[MAXN]; inline void add(int &x,int y){ x += y;if(x >= ha) x -= ha; } int ans[MAXN]; inline int qpow(int a,int n=ha-2){ int res = 1; while(n){ if(n & 1) res = 1ll*res*a%ha; a = 1ll*a*a%ha; n >>= 1; } return res; } namespace Subtask1{ // O(n^2/c * 2^c) int f[2][MAXN][(1<<10)+3],now; // 考虑了前i个数 凑了j个[1..c],当前段哪些还没凑 inline void Solve(){ int U = (1<<c)-1; f[now=0][0][0] = 1;FOR(i,1,n) --a[i]; FOR(i,1,n){ FOR(j,0,(i-1)/c) FOR(S,0,U-1) f[now^1][j][S] = f[now][j][S]; int t = (1<<a[i]); FOR(j,0,(i-1)/c){ FOR(S,0,U-1){ if(!f[now][j][S]) continue; int nS = S|t,nj = j; if(nS == U) nS = 0,nj = j+1; add(f[now^1][nj][nS],f[now][j][S]); } } now ^= 1; } FOR(S,0,(1<<c)-2) FOR(j,0,n/c) add(ans[j],f[now][j][S]); add(ans[0],ha-1);// 空 } } namespace Subtask2{ int f[MAXN][MAXN],g[MAXN][MAXN]; /* f[i][j]: 最后一次选的是i,搞出了j个段 转移需要预处理 g[i][j]: 最后一次选的是j,选出了一段 计算g只需要得到出现次数就行了 */ int cnt[MAXN],now,sm; int pw[MAXN],inv[MAXN]; inline void reset(){ FOR(i,1,c) cnt[i] = 0;now = 0;sm = 1; } inline void add(int x){ if(!cnt[x]){ ++cnt[x];++now; return; } sm = 1ll*sm*inv[cnt[x]]%ha; ++cnt[x]; sm = 1ll*sm*(pw[cnt[x]]+ha-1)%ha; } inline void Solve(){ pw[0] = 1;FOR(i,1,MAXN-1) pw[i] = 2ll*pw[i-1]%ha; FOR(i,0,MAXN-1) inv[i] = qpow((pw[i]+ha-1)%ha); FOR(r,1,n){ reset(); ROF(l,r,1){ add(a[l]); if(now != c) g[l][r] = 0; else g[l][r] = 1ll*sm*inv[cnt[a[r]]]%ha; } } f[0][0] = 1; FOR(i,0,n-1){ FOR(j,0,i/c){ if(!f[i][j]) continue; FOR(k,i+c,n){ ::add(f[k][j+1],1ll*f[i][j]*g[i+1][k]%ha); } } } // DEBUG(f[2][2]); // exit(0); FOR(j,0,n/c){ reset(); ROF(i,n,0){ if(!f[i][j]){ add(a[i]);continue; } int t=0; t = pw[n-i]; if(now == c) ::add(t,ha-sm); ::add(ans[j],1ll*f[i][j]*t%ha); add(a[i]); } } ::add(ans[0],ha-1); } } int main(){ scanf("%d%d",&n,&c); FOR(i,1,n) scanf("%d",a+i); if(c <= 10) Subtask1::Solve(); else Subtask2::Solve(); FOR(i,0,n) printf("%d ",ans[i]);puts(""); return 0; }
A发现操作相当于花费 $x$ 消掉一个 $0$ 的连续段，或者是花费 $y$ 将两个连续段拼起来，显然如果使用了拼接操作就会拼到只剩一个，所以直接判断即可。B打表发现在 $n$ 较大的时候是个等差数列，小范围暴力即可。一个比较有理有据的做法是首先考虑我们先将集合转化为 $\{0,4,9,49\}$ 考虑，然后我们为了保证不重，必须限制 $4$ 的个数 $\leq 8$ 个，并且如果取了 $4$，那么为了去重也只能取 $\leq 4$ 个 $9$，没有取 $4$ 就可以取 $\leq \gcd(49,9)=9$ 个。剩下的用 $0$ 和 $49$ 填充即可。通过整体平移让某一个出现 $0$ 是很不错的套路，可以直接少考虑一个维度。C必然是容斥原理。我们去枚举多少行多少列是相同颜色的，设 $f(i,j)$ 表示 $i$ 行 $j$ 列每行每列相同颜色的方案数，答案就是：$$ \sum_{i=0}^n \sum_{j=0}^n [i+j \neq 0](-1)^{i+j+1}\binom n i\binom n j f(i,j) $$其中：$$ \begin{aligned} f(i,j) = \begin{cases} 3^{n(n-j)} \times 3^j ,&i=0\\ 3^{(n-i)n} \times 3^i, &j=0\\ 3^{(n-i)(n-j)} \times 3,& \text{otherwise} \end{cases} \end{aligned} $$接下来考虑如何优化：首先 $i=0$ 和 $j=0$ 的情况比较平凡，我们只需要考虑算：$$ -3\sum_{i=1}^n (-1)^i\binom n i\sum_{j=1}^n (-1)^{j}\binom n j 3^{(n-i)(n-j)} $$对后面用二项式定理，后面的式子等价于 $(3^{n-i}-1)^n-3^{(n-i)n}$，就可以 $O(n \log n)$ 计算了。同时算多个 $n$ 的答案感觉可以卷积。。不错以后出了。D首先要直观理解一下在图上怎么走路的：你从 $(u,v)$ 可以走到 $(u,w)$满足树 $2$ 上有边 $(v,w)$，树 $1$ 同理。主要是要观察到一个性质：两棵树起点确定，长度为 $x,y$ 的环能组合出长度为 $x+y$ 的环，方案是 $\binom {x+y} x$。所以我们对树分开处理，只需要对于每棵树处理出长度 $=i$ 的环的个数就行了（在环上每个点都要贡献一次），如果我们现在求 $1$ 号点的环个数，可以将这个点设为根，然后设 $f_{i,j}$ 表示从 $i$ 开始的长度为 $j$ 的环的数量。考虑写出生成函数 $F_i = \sum_{j} f_{i,j}x^j$，考虑如何用生成函数的形式刻画转移：首先我们可以算出 $G_i$ 表示经过 $i$ 一次的情况，显然有 $G_i = x^2\sum{v \in son_i} F_{v}$，$x^2$ 是因为要走回来，那么就可以得到 $F_i = \sum_{j \geq 0} G_i^j = \frac{1}{1-G_i}$，所以多项式求逆就可以求出来了。但是因为要求出所有点的答案，所以我们要考虑换根：实际上就是去掉/加入一些子树，先修改 $G$ 再修改 $F$ 即可。这样复杂度是 $O(nk \log k)$ 的，但是由于 $k$ 很小并且 NTT 常数巨大跑不过 $O(nk^2)$ 的做法。官方题解给的做法是用那个 dp 套在点分治上，也是很妙的，对这种类似路径条数和连通块的问题我们可以考虑点分治每次只 dp 分治区域内所有的点。E先考虑如果全局询问怎么做：因为是排列，限制可以拆成 $r-l = mx-mn$，并且我们发现一定有 $r-l \leq mx-mn$，也就是 $r \leq mx-mn+l$，所以我们枚举右端点，线段树维护所有左端点的 $mx-mn+l$，每次如果存在合法的区间值一定是最小值 $r$，记录最小值个数即可，维护单调栈每次更新即可。这个题是要对一个子区间全部做，相当于要维护历史贡献信息：对于这种题我们线段树上记一个值专门用来存答案，每次更新完右端点的操作后我们在根打一个答案标记，答案标记下传到某个儿子当且仅当这个点儿子的最小值和父亲的最小值相等，并且一定要在加法下传后再下传（因为前面的加法标记都是应该加完后判断的），然后查询就区间查询和就好了。建议看代码意会一下。。这个东西感觉是可以扩展的，好多利用线段树枚举左端点维护右端点的题都可以改改做了。核心思想还是每次修改前肯定先处理完标记再下传，那么统计答案的标记优先级一定小于修改的标记。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; int mn[MAXN<<2],cnt[MAXN<<2],tag[MAXN<<2]; LL res[MAXN<<2],tag2[MAXN<<2]; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void pushup(int x){ mn[x] = std::min(mn[lc],mn[rc]);cnt[x] = 0; if(mn[x] == mn[lc]) cnt[x] += cnt[lc]; if(mn[x] == mn[rc]) cnt[x] += cnt[rc]; } inline void cover(int x,int d){ mn[x] += d;tag[x] += d; } inline void cover2(int x,int mn,int d){ if(::mn[x] != mn) return; res[x] += 1ll*cnt[x]*d;tag2[x] += d; }// 注意这个标记是后打的 所以最后pushdown这个标记 inline void pushdown(int x){ if(tag[x]){ cover(lc,tag[x]); cover(rc,tag[x]); tag[x] = 0; } if(tag2[x]){ cover2(lc,mn[x],tag2[x]); cover2(rc,mn[x],tag2[x]); tag2[x] = 0; } } inline void modify(int x,int l,int r,int L,int R,int d){ if(l == L && r == R){ cover(x,d);return; } int mid = (l + r) >> 1;pushdown(x); if(R <= mid) modify(lc,l,mid,L,R,d); else if(L > mid) modify(rc,mid+1,r,L,R,d); else modify(lc,l,mid,L,mid,d),modify(rc,mid+1,r,mid+1,R,d); pushup(x); } inline void build(int x,int l,int r){ if(l == r){ mn[x] = l;cnt[x] = 1; return; } int mid = (l + r) >> 1; build(lc,l,mid);build(rc,mid+1,r); pushup(x); } inline LL query(int x,int l,int r,int L,int R){ if(l == L && r == R) return res[x]; int mid = (l + r) >> 1;pushdown(x); if(R <= mid) return query(lc,l,mid,L,R); if(L > mid) return query(rc,mid+1,r,L,R); return query(lc,l,mid,L,mid)+query(rc,mid+1,r,mid+1,R); } int a[MAXN]; int n; int stk1[MAXN],stk2[MAXN],tp1,tp2; // 后缀加 std::vector G[MAXN]; LL ans[MAXN]; int main(){ scanf("%d",&n); FOR(i,1,n) scanf("%d",a+i); int q;scanf("%d",&q); FOR(i,1,q){ int l,r;scanf("%d%d",&l,&r); G[r].pb(MP(l,i)); } build(1,1,n); // 1=min,2 = max // r-l = mx-mn // r = mx-mn+l FOR(i,1,n){ while(tp1 && a[stk1[tp1]] <= a[i]){// max modify(1,1,n,stk1[tp1-1]+1,stk1[tp1],-a[stk1[tp1]]); --tp1; } while(tp2 && a[stk2[tp2]] >= a[i]){// min modify(1,1,n,stk2[tp2-1]+1,stk2[tp2],a[stk2[tp2]]); --tp2; } modify(1,1,n,stk1[tp1]+1,i,a[i]); modify(1,1,n,stk2[tp2]+1,i,-a[i]); stk1[++tp1] = i;stk2[++tp2] = i; cover2(1,mn[1],1); for(auto x:G[i]) ans[x.se] = query(1,1,n,x.fi,i); } FOR(i,1,q) printf("%lld\n",ans[i]); return 0; }
A贪心想法先把 $a$ 和 $b$ 拼成若干个 $ab$，然后如果有剩余的可以在对应的开头/结尾放，所以答案是 $c+\min(a,b)+[a \neq b]$。B枚举我们强制让这个人 $A \to B$ 选择那一班航班起飞（这样就相应 ban 掉了一些航班），然后双指针维护处对应的 $B \to C$ 最近能从哪里开始起飞，就是查一个第 $x$ 大的问题了。因为排好序了可以 $O(1)$ 直接求出。C我们只需要实现 $5$ 步内交换两个数的算法就好了：我们考虑交换 $(x,y)$ 的最一般的情况：$1 < x \leq \frac{n}{2} < y < n$，这样我们需要交换 $(x,n),(y,1),(1,n),(x,n),(y,1)$。需要额外判断一下 $x < y < \frac{n}{2}$，$\frac{n}{2} > x > y$，$x = 1,y = n$ 的各种情况，都能在五步内完成。然后直接每次将对应的值交换到正确的位置上就好了。D要看到能任意交换顺序这一点。不然就只会垃圾做法了。我们将 $a_i < b_i$ 和 $a_i > b_i$ 分成两组，发现两组内的数不能放在一起，于是可以分开处理。以解决 $a_i < b_i$ 为例：一个 sb 的想法是树状数组优化 dp，但是真的是这样么？我们考虑相邻的两个元素 $a_1 < b_1 > a_2 < b_2$，那么如果 $b$ 越小 $a$ 就越小，所以我们肯定按照 $b$ 从大到小排序，发现 $b_1 > b_2,a_2 < b_2 \Rightarrow b_1 > a_2$，这样就全满足了。另一组讨论是类似的。这个问题还是要好好读题，然后在草稿纸上画一画这些组，发现一些性质就好了。E又是可以随便排列顺序。。读题一定要仔细了。。那么我们肯定贪心从大到小排序然后考虑调整：如果一个位置想要减小，一定是找一个后面想要变大的匹配。所以我们记一下当前想要变小的位置和要变小多少，每次如果 $s_i > t_i$ 就把 $i$ 扔到集合内，否则就不断从集合头匹配即可。如果找不到前面的一个数匹配或者是最后没有匹配完就无解。感觉操作次数 $\leq 2n$ 啊不知道范围是个什么迷惑操作。。F考虑先使用归纳法证明一定有解：首先如果 bit 只有 $1$ 位一定有解：直接翻转即可。那么假设 bit 有 $k$ 位有解，接下来我们想证明 $k+1$ 位有解。发现当前翻转 $k+1$ 位上的若干位数不会影响最高位 $\leq k$ 的数，所以判断一下是否需要翻转即可。需要注意虽然我们每次决定是否翻转只是看最高位是 $k+1$ 的数，但是翻转的时候是要全部都翻转的。G好神仙啊。。。首先发现如果得到一个 $k$ 的好的集合，那么一定能得到 $\leq k$ 的好的集合。但是得到了大小为 $k$ 的不好的集合不代表你能得到 $\leq k$ 的好的集合。首先我们考虑 $O(n^2)$ 的暴力怎么做（小蒟蒻这个都不会）：如果 $k$ 是偶数：我们任意选出 $k$ 个数，每次先判断一下是不是组成一个团，如果组成直接输出，否则一定存在一对点之间没有边，删除这两个点，并且找这个点的两个相邻的点放入这个集合。如果操作 $\frac{k}{2}$ 次仍然无解，被删除的点的集合一定满足是不好的。如果 $k$ 是奇数：我们一开始找到三个点 $u,v,w$ 满足 $(u,v),(v,w)$ 边不存在，删去这三个点做子问题，可以得到一个偶数大小的不好集合，最后考虑是否要加入这三个点即可。选择三个点而不是一个点的原因是三个点可以自由决定是否加两个/三个，但是一个点加入之后你不知道是不是会破坏不好的性质。如果找不到这三个点，考虑这个图的补图，补图一定是森林，好的集合对应一个独立集，黑白染色可知一定存在 $\geq \frac{n}{2}$ 的独立集，只需要在一开始判掉有好集合的情况就好了。道理我都懂，但是正解怎么做呢？我们可以用一个复杂度 $O(2^8 n \log n)$ 的复杂度解决。首先可以将所有数的唯一分解后的形式的 $>0$ 的指数都改成 $1$，不难发现这样不影响图的形态。考虑整张图的形态显然是不行的，那么遇到这种问题一定先考虑某些特殊量是否能被算出：首先我们先考虑如何快速算一个点的度数，可以用 $f_i$ 记录包含因子 $i$ 的数的个数然后 $2^8$ 运用容斥原理算出。类似地我们选出三个点 $u,v,w$，满足 $(u,v),(v,w)$ 边不存在，并删去这三个点。我们对剩下的点，设和其他所有点都有连边的数量是 $b$，如果 $b \geq k$ 直接输出答案即可，否则剩下的 $n-3-b$ 个元素组成的集合是不好的。因为 $u,v,w$ 之间无边，所以可以全部加入到任意不好的集合内而不破坏性质。考虑有 $b < k \leq \frac{n}{2}$ ，所以 $n-3-b+3 = n-b > n-\frac{n}{2} = \frac{n}{2} \geq k$，所以一定存在一个大小 $\geq k$ 的不好的集合。现在我们就要考虑如何删除一些数而不破坏性质：我们设 $f(r)$ 表示 $[1\ldots r]$ 数能选出最大的不好的集合，通过二分找到第一个位置 $r$ 满足 $f(r) \geq k,f(r-1) < k$，观察一下可以发现这说明了有 $f(r)-f(r-1)-1$ 个点与前 $r-1$ 个点连边，但是与 $r$ 点不连边，并且 $r$ 点也是不好点。所以我们可以删除这些点而不影响性质（因为其他点都是连到这个点上的，不依赖于它而保持不好的性质），我们发现至多删除 $f(r)-f(r-1)-2$ 个点（因为如果全删了可能 $r$ 点就是好点了），所以经过删除后我们能得到大小为 $k$ 或者 $k+1$ 的集合，这时候我们一开始选出的三个点就派上用场了：我们可以选择保留两个点或三个点而不破坏性质（这些点之间没有连边），按照需求调整即可。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 1e5 + 5; const int MAXM = 1e7 + 5; bool p[MAXM]; int prime[MAXM],cnt; inline void prework(){ FOR(i,2,MAXM-1){ if(!p[i]) prime[++cnt] = i; for(int j = 1;j <= cnt && 1ll*i*prime[j] < MAXM;++j){ p[i*prime[j]] = 1; if(!(i%prime[j])) break; } } } int n,k; int a[MAXN]; std::vector<int> G[MAXN],v[MAXM]; inline void reduce(int i){ int x = a[i],q = std::sqrt(1.0*x); FOR(j,1,cnt){ int p = prime[j]; if(p > x || p > q) break; if(!(x%p)){ int c = 0;v[j].pb(i);G[i].pb(p); while(!(x%p)) ++c,x /= p; --c;while(c--) a[i] /= p; } } if(x != 1){ G[i].pb(x); int p = std::lower_bound(prime+1,prime+cnt+1,x)-prime; v[p].pb(i); } } int f[MAXM]; // 求有多少个和它不互质 枚举gcd容斥即可 int b[MAXN]; inline int deg(int i){ int sz = G[i].size(),res = 0; FOR(S,1,(1<<sz)-1){ int t = 1; FOR(j,0,sz-1){ if((S>>j)&1) t *= G[i][j]; } int gx = f[t]; if((__builtin_popcount(S)-1)&1) gx = -gx; res += gx; } return res-1; } inline void add(int i,int d){ int sz = G[i].size(); FOR(S,1,(1<<sz)-1){ int t = 1; FOR(j,0,sz-1){ if((S>>j)&1) t *= G[i][j]; } f[t] += d; } } int m; inline int chk(int x){ FOR(i,x+1,m) add(b[i],-1); int c = 0; FOR(i,1,x) c += (deg(b[i]) == x-1); FOR(i,x+1,m) add(b[i],1); return x-c+3; } bool vis[MAXN]; std::mt19937 g(19260); int tt[MAXN]; int main(){ prework(); scanf("%d%d",&n,&k); FOR(i,1,n) scanf("%d",a+i),tt[i] = a[i],reduce(i); FOR(i,1,cnt){ if(v[i].size() >= k){ FOR(j,0,k-1) printf("%d ",v[i][j]); puts(""); return 0; } } FOR(i,1,n) add(i,1); int u=-1,v=-1,w=-1; FOR(i,1,n){ if(n-1-deg(i) >= 2){ v = i; FOR(j,1,n){ if(j == i) continue; if(std::__gcd(a[i],a[j]) > 1) continue; if(u == -1) u = j; else w = j; } break; } } add(u,-1);add(v,-1);add(w,-1); if(k == 3){ printf("%d %d %d\n",u,v,w); return 0; } FOR(i,1,n){ if(i == u || i == v || i == w) continue; b[++m] = i; } int c = 0; FOR(i,1,m) if(deg(b[i]) == m-1) ++c; if(c >= k){ c = 0; FOR(i,1,m){ if(deg(b[i]) == m-1) ++c,printf("%d ",b[i]); if(c == k) break; } puts(""); return 0; } int l = 1,r = m,ans = -1; while(l <= r){ int mid = (l + r) >> 1; if(chk(mid) >= k) ans = mid,r = mid-1; else l = mid+1; } int _ = chk(ans),t = _-chk(ans-1)-2,d = _-k; FOR(i,ans+1,m) add(b[i],-1); FOR(i,1,ans) vis[i] = (deg(b[i]) != ans-1); FOR(i,1,ans-1){ if(!d) break; if(t <= 0) break; if(!vis[i]) continue; if(std::__gcd(a[b[i]],a[b[ans]]) != 1) continue; if(deg(b[i]) != ans-2) continue; --d;--t;vis[i] = 0; } FOR(i,1,ans) if(vis[i]) printf("%d ",b[i]); if(!d) printf("%d ",u); printf("%d %d\n",v,w); return 0; }H还在咕咕咕
感觉没有 ytq 哥哥之前的毒瘤画风了，很怪异。做的时候一直以为我做法假了爆零了，结果发现并不是这样？不过还是垫底了A考场做法：我们肯定贪心从小往大选，所以先按照 $a_i$ 排序。可以看成每个时间 $i$ 种钻石补充了 $b_i$ 个，我们肯定贪心从小往大选，我们每次需要找到第一个位置满足前缀和 $\geq c_i$，然后选这前面的宝石。可以用线段树维护一次函数和完成。还有一个做法：我们设 $c$ 的前缀和是 $sm_i$，那么求 $(i,sm_i)$ 的凸包，对于每条边对应的区间我们都买数量一样的宝石。正确性就是可以通过调整变得更好图一如果满足限制，图二一定也满足限制，并且注意到代价函数下凸，所以图二的代价一定比图一的小。我们就证明了要求凸包。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 2e5 + 5; LL sm1[MAXN<<2],sm2[MAXN<<2],coe1[MAXN<<2],coe2[MAXN<<2]; LL tag[MAXN<<2],clr[MAXN<<2]; LL c[MAXN]; P a[MAXN]; int n,m; #define lc ((x)<<1) #define rc ((x)<<1|1) inline void pushup(int x){ sm1[x] = sm1[lc]+sm1[rc]; sm2[x] = sm2[lc]+sm2[rc]; coe1[x] = coe1[lc]+coe1[rc]; coe2[x] = coe2[lc]+coe2[rc]; } inline void build(int x,int l,int r){ if(l == r){ sm1[x] = sm2[x] = 0; coe1[x] = a[l].se;coe2[x] = 1ll*a[l].fi*a[l].se; return; } int mid = (l + r) >> 1; build(lc,l,mid);build(rc,mid+1,r); pushup(x); } inline void cover(int x,LL d){ sm1[x] += coe1[x]*d; sm2[x] += coe2[x]*d; tag[x] += d; } inline void reset(int x){ sm1[x] = sm2[x] = tag[x] = 0;clr[x] = 1; } inline void pushdown(int x){ if(clr[x]){ reset(lc); reset(rc); clr[x] = 0; } if(tag[x]){ cover(lc,tag[x]); cover(rc,tag[x]); tag[x] = 0; } } inline void modify(int x,int l,int r,int L,int R){ if(L > R) return; if(l == L && r == R){ reset(x); return; } int mid = (l + r) >> 1;pushdown(x); if(R <= mid) modify(lc,l,mid,L,R); else if(L > mid) modify(rc,mid+1,r,L,R); else modify(lc,l,mid,L,mid),modify(rc,mid+1,r,mid+1,R); pushup(x); } inline LL query1(int x,int l,int r,int L,int R){ if(L > R) return 0; if(l == L && r == R) return sm1[x]; int mid = (l + r) >> 1;pushdown(x); if(R <= mid) return query1(lc,l,mid,L,R); if(L > mid) return query1(rc,mid+1,r,L,R); return query1(lc,l,mid,L,mid)+query1(rc,mid+1,r,mid+1,R); } inline LL query2(int x,int l,int r,int L,int R){ if(L > R) return 0; if(l == L && r == R) return sm2[x]; int mid = (l + r) >> 1;pushdown(x); if(R <= mid) return query2(lc,l,mid,L,R); if(L > mid) return query2(rc,mid+1,r,L,R); return query2(lc,l,mid,L,mid)+query2(rc,mid+1,r,mid+1,R); } inline int getpos(int x,int l,int r,int k){ if(l == r) return l; int mid = (l + r) >> 1; pushdown(x); LL ls = sm1[lc]; if(k <= ls) return getpos(lc,l,mid,k); else return getpos(rc,mid+1,r,k-ls); } inline void update(int x,int l,int r,int p,int d){ if(l == r){ sm1[x] += d; sm2[x] += 1ll*d*a[l].fi; return; } pushdown(x); int mid = (l + r) >> 1; if(p <= mid) update(lc,l,mid,p,d); else update(rc,mid+1,r,p,d); pushup(x); } int main(){ scanf("%d%d",&m,&n); FOR(i,1,m) scanf("%d",c+i); FOR(i,1,n) scanf("%d%d",&a[i].fi,&a[i].se); std::sort(a+1,a+n+1);n = 1; while(a[n].se != -1) ++n; if(n == 1){ LL ans = 0; FOR(i,1,m) ans += 1ll*c[i]*a[1].fi; printf("%lld\n",ans); return 0; } int N = n-1;build(1,1,N); LL ans = 0; FOR(i,1,m){ pushdown(1);cover(1,1); if(sm1[1] <= c[i]){ ans += 1ll*(c[i]-sm1[1])*a[n].fi; ans += sm2[1]; reset(1); } else{ int p = getpos(1,1,N,c[i]); LL r = c[i]-query1(1,1,N,1,p-1); ans += 1ll*query2(1,1,N,1,p-1)+1ll*r*a[p].fi; modify(1,1,N,1,p-1); update(1,1,N,p,-r); } } printf("%lld\n",ans); return 0; }B排序代码写成inline bool cmp(std::string a,std::string b){ return a+b < b+a; }感觉是经典题了。这里注意尽量不要用字符串加法（当然这个cmp可以，但是输出的时候不要用加号）#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl const int MAXN = 3e5 + 5; std::string s[MAXN]; inline bool cmp(std::string a,std::string b){ return a+b < b+a; } int main(){ std::ios::sync_with_stdio(false); int n;std::cin >> n; FOR(i,1,n) std::cin >> s[i]; std::sort(s+1,s+n+1,cmp); FOR(i,1,n) std::cout << s[i]; std::cout << '\n'; return 0; }C如果不考虑后手能选择一个集合，其实就是一个 K-Nim 游戏：K-Nim 游戏：每次可以选择 $k$ 堆，拿走任意个数的石子，无法操作者输结论：石子数二进制每一位的和如果都 $\bmod k+1=0$，那么先手必败，否则先手必胜。[collapse status="false" title="证明"]我们先证明必败态操作一步一定回到必胜态：首先显然至少有一位的 $1$ 个数变动了。最多操作 $k$ 个，每一位的 $1$ 的个数变动不会超过 $k$，一定不会是 $k+1$ 的倍数。再证明必胜态一定有一种操作到必败态：我们从高到低考虑所有为，假设存在一种方法改变了 $m$ 堆，使 $i$ 之前的所有位回到了 $k+1$ 的整数倍，现在要证明有一种方法让第 $i$ 位也恢复到 $k+1$ 整数倍。首先发现对于已经被改变的 $m$ 堆在第 $i$ 位可以自由选择。设除去已经更改的 $m$ 堆，剩下堆 $i$ 位上的 $1$ 的个数位 $sum$。$sum \leq k-m$，把剩下堆是 $1$ 的全变成 $0$ 即可，还是满足选取个数的$sum > k-m$，在之前改变的 $m$ 堆选择 $k+1-sum$ 堆设置成 $1$，其余设置成 $0$。发现 $k+1-sum < k+1-(k-m) < m+1$，$k+1-sum \leq m$，可以达到。[/collapse]那么加上后手可以选择一个集合就是要求不存在一个非空子集，三进制不进位加法结果 $=0$。我们发现每次加入两个这个限制就像是强行拼凑的一样，考虑三进制加法下 $2x=-x$。所以我们就可以去考虑线性基了（因为一个线性组合所需的所有系数我们都可以造出来了）所以必胜等价于这些数字在三进制不进位加法下线性无关。就可以用线性基维护了（每次如果插入的权值大于这个地方的权值就交换接着下去消）为了加快速度需要位运算优化，看一下代码理解就行了（其实本质就是把所有可能这一位是 1 的情况都写出来 ）（所以这个题是不是可以加强到 $k$ 进制啊）#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(int i = a;i <= b;++i) #define ROF(i,a,b) for(int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl struct Node{ LL v[2]; Node(LL x=0,LL y=0){ v[0] = x;v[1] = y; } inline LL& operator [] (const int &n){return v[n];} friend Node operator + (Node x,Node y){ return Node( (x[1]&y[1])|(x[0]&(~(y[0]|y[1])))|(y[0]&(~(x[0]|x[1]))), (x[0]&y[0])|(x[1]&(~(y[0]|y[1])))|(y[1]&(~(x[0]|x[1]))) ); } }b[60]; LL y[60],sm; inline void insert(Node x,LL v){ ROF(i,59,0){ if(((x[0]|x[1])>>i)&1){ if(!(((b[i][0]|b[i][1])>>i)&1)){ b[i] = x;y[i] = v;sm += v;return; } if(v > y[i]) sm += v-y[i],std::swap(v,y[i]),std::swap(x,b[i]); if(MP((x[0]>>i)&1,(x[1]>>i)&1) == MP((b[i][0]>>i)&1,(b[i][1]>>i)&1)){ x = x+b[i]+b[i]; } else{ x = x+b[i]; } } } } int main(){ int n;scanf("%d",&n); FOR(i,1,n){ LL x,y;scanf("%lld%lld",&x,&y); x ^= sm; insert(Node(x,0),y); printf("%lld\n",sm); } return 0; }
题目大意给定两个长度为 $n$ 的正整数序列 $\{a_i\}$与 $\{b_i\}$，序列的下标为 $1, 2, \cdots , n$。现在你需要分别对两个序列各指定恰好$K$ 个下标，要求至少有 $L$ 个下标在两个序列中都被指定，使得这 $2K$ 个下标在序列中对应的元素的总和最大。$n \leq 2\times 10^5,\sum _n \leq 10^6$题解模拟费用流真奇妙首先考虑这个题如何用网络流解决。然后在 $A \to B$ 上限制有多少对不一样就好了。发现只能有 $K-L$ 对不同。这样就能得到可能是 64 分的好成绩了。考虑我们如何去模拟这个费用流。如果当前 $A \to B$ 还有流量的话我们就可以从左边没选的选个最大的，右边没选的也选个最大的，组合起来。如果没有流量的话，就要分情况讨论：直接选能通过中间的边的一对（比如 $1$ 和 $4$）找到一个左边的没被选 但是对应右边被选的点 我们让左边被选上 那么为了保持流量平衡 右边需要从没被选的点中选一个。反过来同理注意都要更新是不是会导致 $A \to B$ 的流量增加。所以拿堆维护未被选左边/右边点的值，对应点被选的左边/右边的值，一对都没被选的值即可。细节有点多 还有点卡常 zbl#include<bits/stdc++.h> #define fi first #define se second #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back #define MP std::make_pair #define all(x) x.begin(),x.end() #define CLR(i,a) memset(i,a,sizeof(i)) #define FOR(i,a,b) for(register int i = a;i <= b;++i) #define ROF(i,a,b) for(register int i = a;i >= b;--i) #define DEBUG(x) std::cerr << #x << '=' << x << std::endl inline char nc(){ #define SIZE 1000000+3 static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE; if(p1 == p2){ p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin); if(p1 == p2) return -1; } return *p1++; #undef SIZE } template <typename T> inline void read(T &x){ x = 0;int flag = 0;char ch = nc(); while(!isdigit(ch)){ if(ch == '-') flag = 1; ch = nc(); } while(isdigit(ch)){ x = (x<<1) + (x<<3) + (ch^'0'); ch = nc(); } if(flag) x = -x; } const int MAXN = 2e5 + 5; int a[MAXN],b[MAXN],n,K,L; struct A{ int id; A(int id=0) : id(id) {} bool operator < (const A &t) const { return a[id] < a[t.id]; } }; struct B{ int id; B(int id=0) : id(id) {} bool operator < (const B &t) const { return b[id] < b[t.id]; } }; struct AB{ int id; AB(int id=0) : id(id) {} bool operator < (const AB &t) const { return a[id]+b[id] < a[t.id]+b[t.id]; } }; std::priority_queue q1,p1;//单纯 A | B 被占 std::priority_queue q2,p2;// 单纯 B | A 被占 std::priority_queue<AB> q;//一群 int flow,st[MAXN],id[MAXN];LL ans; inline void clear(){ while(!q1.empty()) q1.pop();while(!p1.empty()) p1.pop(); while(!q2.empty()) q2.pop();while(!p2.empty()) p2.pop(); while(!q.empty()) q.pop();flow = 0; FOR(i,1,n) st[i] = 0,id[i] = i;ans = 0; } inline void pop(){ while(!q1.empty() && (st[q1.top().id]&1)) q1.pop(); while(!q2.empty() && (st[q2.top().id]&2)) q2.pop(); while(!q.empty() && st[q.top().id]) q.pop(); while(!p1.empty() && st[p1.top().id] != 2) p1.pop(); while(!p2.empty() && st[p2.top().id] != 1) p2.pop(); } inline void gao1(){ flow--; int x = q1.top().id,y = q2.top().id; ans += a[x]+b[y]; st[x] |= 1;st[y] |= 2; if(st[x] == 1) p2.push(B(x)); if(st[y] == 2) p1.push(A(y)); if(x == y) flow++; else flow += (st[x]==3)+(st[y]==3); } inline void gao2(){ int t1=-2e9,t2=-2e9,t3=-2e9; if(!p1.empty() && !q2.empty()) t1 = a[p1.top().id]+b[q2.top().id]; if(!p2.empty() && !q1.empty()) t2 = b[p2.top().id]+a[q1.top().id]; if(!q.empty()) t3 = a[q.top().id]+b[q.top().id]; int mx = std::max(std::max(t1,t2),t3); if(mx == -2e9) return; ans += mx; if(mx == t1){ int x = p1.top().id,y = q2.top().id; st[x] |= 1;st[y] |= 2; if(st[y] == 3) flow++; else p1.push(A(y)); return; } if(mx == t2){ int x = q1.top().id,y = p2.top().id; st[x] |= 1;st[y] |= 2; if(st[x] == 3) flow++; else p2.push(B(x)); return; } if(mx == t3){ int x = q.top().id; st[x] |= 3;return; } } inline void Solve(){ read(n);read(K);read(L); FOR(i,1,n) read(a[i]);FOR(i,1,n) read(b[i]); clear(); std::sort(id+1,id+n+1,[](int x,int y){return a[x] > a[y];}); FOR(i,1,K-L) ans += a[id[i]],st[id[i]] |= 1; std::sort(id+1,id+n+1,[](int x,int y){return b[x] > b[y];}); FOR(i,1,K-L) ans += b[id[i]],st[id[i]] |= 2; FOR(i,1,n){ if(st[i] == 0) q1.push(A(i)),q2.push(B(i)),q.push(AB(i)); if(st[i] == 1) q2.push(B(i)),p2.push(B(i)); if(st[i] == 2) q1.push(A(i)),p1.push(A(i)); if(st[i] == 3) flow++; } while(L--){ pop(); if(flow) gao1(); else gao2(); } printf("%lld\n",ans); } int main(){ int T;read(T); while(T--) Solve(); return 0; }