RainAir's Blog - 贪心
type: channel
link: http://blog.aor.sd.cn/tag/贪心
items: Edu 106 题解
items: CF 1455 题解
items: qbxt 10 月模拟赛 Day7
items: qbxt 10 月模拟赛 Day5
items: CF 521 题解
items: CF 1158 题解
items: CF 997 题解
items: CF 1148 题解
items: ZR2020 提高十联测 day2
items: 「NOI2019」序列

Edu 106 题解
type: item
date: 2021-03-19T22:15:00+08:00
description: 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$ 是…

CF 1455 题解
type: item
date: 2020-12-08T20:53:12+08:00
description: 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_pai…

qbxt 10 月模拟赛 Day7
type: item
date: 2020-10-07T20:02:00+08:00
description: 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 思路（（虽然代码…

qbxt 10 月模拟赛 Day5
type: item
date: 2020-10-05T21:35:29+08:00
description: 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 优化。#…

CF 521 题解
type: item
date: 2020-09-29T21:43:00+08:00
description: 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$。

CF 1158 题解
type: item
date: 2020-09-21T21:21:00+08:00
description: 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$ 都出现了一次（否则会算重）。这个可以…

CF 997 题解
type: item
date: 2020-09-17T21:15:00+08:00
description: 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 #def…

CF 1148 题解
type: item
date: 2020-09-17T07:26:00+08:00
description: 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$ 之间无边，所以可以全部加入到任意不好的集合内而不破…

ZR2020 提高十联测 day2
type: item
date: 2020-09-06T19:04:00+08:00
description: 感觉没有 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)…

「NOI2019」序列
type: item
date: 2020-05-15T08:21:00+08:00
description: 题目大意给定两个长度为 $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(); wh…