CF补题题解2023.5
说明：CF题直接去luogu看翻译，AT题会附上简要题意
CF1821E
先考虑如何高速计算权值
一个显而易见的贪心是尽量在右边取括号消除，设右括号为 1，左括号为 -1
那么我们每一次消除的括号 \(i,i+1\) 都满足了 \(i+1\) 的右边剩下的全部是右括号，代价就是往右数的个数
更进一步来说，对于右括号 \(i\) 的代价，就是其右边的未匹配的右括号个数，换而言之就是 \([i+1,n]\) 的右括号个数减去左括号个数
考虑设 \(s_i=\sum_{k=i}^n a_i\)，则代价为 \(\sum_{i=1}^n[a_i=1]s_{i+1}\)
接着看 \(k\) 是怎么用的
对于一次移动而言，容易发现无论是左括号移到右括号旁边，还是右括号移到左括号旁边，其代价是一样的
我们可以使用栈求出最终状态下括号是如何匹配的
如果我们强行将两个原本不是一起的括号匹配在一起，是一定不优秀的(因为其会增加代价)，则我们预处理出每对括号的位置 \(l_i,r_i\)，设 \(c_i=\sum_{k=1}^i[a_i=1]\)
设移动左括号\(l\) 到右括号 \(r\)，则可以对 \([l+1,r]\) 的所有 \(s\) 值全部减一，那么其贡献为 \(c_{r_i-1}-c_{l_i}\)
将贡献排序，选前 \(k\) 大减掉即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
#define N 505050
#define int long long
int s[N],n,k,h[N],num,ans,t1,t2,l[N],r[N],c[N];
char a[N];
signed main(){
int t;cin>>t;
while(t--){
cin>>k;ans=0;num=0;int tot=0;t1=t2=0;
cin>>a+1;n=strlen(a+1);s[n+1]=0;
for(int i=1;i<=n;i++)s[i]=(a[i]==')'?1:-1);
for(int i=n;i;--i)s[i]+=s[i+1];
for(int i=1;i<=n;i++)c[i]=c[i-1]+(a[i]==')');
for(int i=1;i<=n;i++){
if(a[i]==')'){
ans+=s[i+1];
}
}
stack<int>q;
for(int i=1;i<=n;i++){
if(a[i]=='(')l[++t1]=i,q.push(t1);
else r[q.top()]=i,q.pop();
}
for(int i=1;i<=n/2;i++)h[i]=c[r[i]-1]-c[l[i]];
sort(h+1,h+n/2+1);reverse(h+1,h+n/2+1);
for(int i=1;i<=min(k,n/2);i++)ans-=h[i];
cout<<ans<<"\n";
}
}
CF1831D
对于此类有限制的计数问题，首先考虑值域
注意到 \(b_i\le n\)，那么 \(a_ia_j=b_i+b_j\le 2n\implies \min(a_i,a_j)\le \sqrt{2n}\)
看到 \(n\le 2\times 10^5\implies O(n\sqrt n)\)
像这样对数对计数，考虑枚举较大数，然后统计较小数的贡献
我们考虑将相同的点合并为一个，并记录大小。
将所有点按 \(a_i\) 排序，自大到小枚举
设 \(s=\sqrt{2n}\)，则较小数的范围只有可能是 \([1,\min(s,a_i)]\)，我们考虑设 \(cnt[i,j]\) 为 \(a_k=i,b_k=j\) 的数的个数，显然第一维只需要开到 \(\sqrt{400000}+2\) 差不多 \(636\)，统计 \(cnt\) 的过程显然是 \(O(1)\) 的，那么我们就可以在 \(O(\sqrt n)\) 的时间内统计出 \(i\) 的贡献（记得乘个数），复杂度 \(O(n\sqrt n)\)
这里有两个特殊情况
- \(\forall i,j\in[1,n],a_i=a_j,a_ia_j=b_i+b_j\)，注意这在上述过程中会算重，考虑直接单独拿出来算
- \(a_i^2=2b_i\)，且出现次数 \(>1\)，设出现次数为 \(t_i\)，则贡献为 \(t_i(t_i-1)/2\)。
int n,m,pp,cnt[636][200001];
struct node{
int a,b,t;
bool operator<(const node c){
return a==c.a?b<c.b:a<c.a;
}
}in[N],a[N];
signed main(){
ios::sync_with_stdio(false);
int t;read(t);
while(t--){
read(n);pp=n;int s=sqrt(n<<1)+1;s=min(s,n);
for(int i=1;i<=n;i++){
read(in[i].a);
}
for(int i=1;i<=n;i++){
read(in[i].b);
in[i].t=1;
}
sort(in+1,in+n+1);m=0;
a[++m]=in[1];
for(int i=2;i<=n;i++){
if(a[m].a==in[i].a&&a[m].b==in[i].b)a[m].t++;
else a[++m]=in[i];
}
n=m;
for(int i=1;i<=n;i++){
if(a[i].a<=s)cnt[a[i].a][a[i].b]+=a[i].t;
}
ll ans=0;
for(int i=1;i<=n;i++){
int ed=min(a[i].a,s+1);
for(int j=ed-1;j;--j)if(j*a[i].a-a[i].b>0&&j*a[i].a-a[i].b<=pp)ans+=1ll*a[i].t*cnt[j][j*a[i].a-a[i].b];
}
ll s1=0;
for(int i=1;i<=n;i++){
if(a[i].a>s)continue;
if(a[i].a*a[i].a==a[i].b+a[i].b){
s1+=1ll*a[i].t*(a[i].t-1);continue;
}
if(a[i].a*a[i].a-a[i].b>pp)continue;
if(a[i].a*a[i].a-a[i].b>0)s1+=1ll*a[i].t*cnt[a[i].a][a[i].a*a[i].a-a[i].b];
}
for(int i=1;i<=n;i++){
if(a[i].a<=s)cnt[a[i].a][a[i].b]-=a[i].t;
}
cout<<ans+s1/2ll<<"\n";
}
}
注意时空卡得很紧很紧，如果改用 map 或者 unordered_map，会被出题人针对然后死亡（赛上就这么死掉的）
记得开 long long
第二个做法，用时间换空间 (我也不知道这玩意 \(O(n\sqrt n \log n)\) 是怎么过 2e5 的)。
1749D
对于操作类问题，经常从极端情况入手。注意到 \(\gcd(a,1)=1\)，那么每个数列都会有一种方案，就是在开头不断移除
那么只要某一时刻，除位置1之外有一个位置合法，就说明挂掉了
接着就容易得到长为 \(n\) 且有且仅有一种方案的序列的充要条件是：
\(\forall i\in[2,n],j\in[2,i],\gcd(a_i,j)\neq 1\)
换言之即为 \(a_i\) 含有 \([2,i]\) 范围中的所有质因子才能满足条件，设 \(g_i=lcd(1,2,3,4……,i),f_i\) 为长为 \(i\) 的序列中有且仅有一种移除方案的序列个数
则显然有 \(f_i=f_{i-1}\times \lfloor\frac{m}{g_i}\rfloor\)
正难则反，容斥一下就可以得到最终结果
ll n,m,f[N],g[N],v[N];
int main(){
scanf("%lld%lld",&n,&m);
for(int i=2;i<=n;i++)if(!v[i])for(int j=i+i;j<=n;j+=i)v[j]=true;
f[1]=m%p,g[1]=1;
ll tmp=m%p,ans=0;
for(int i=2;i<=n;i++){
g[i]=v[i]?g[i-1]:g[i-1]*i;
if(g[i]>m)g[i]=m+1;
f[i]=f[i-1]*((m/g[i])%p)%p;
tmp=tmp*(m%p)%p;
ans+=tmp-f[i];
ans%=p;
}
ans=(ans%p+p)%p;
printf("%lld\n",ans);
}
1837D
这个题告诉我们，有时候，暴力的复杂度，其实是很低的，只是你想不到而已
考虑一个贪心的想法：每次选最长的合法序列染色，这个可以在 \(O(n)\) 算出
然后每一次都这样暴力染色，到最后直接输出答案即可
What???这么简单吗??
考虑证明时间复杂度：
只要合法，每一次选走最长的，就会导致同一类型的括号被选完……，一共两种类型，则肯定最多跑两组……
事实上，括号序列问题的套路是：将左括号视作1，右括号视作-1，求前缀和
#include<bits/stdc++.h>
using namespace std;
int n,k,t,f[505050],g[505050],c[505050],h[505050],w[505050];
char a[1000050];
void calc(){
g[n+1]=f[n+1]=f[0]=g[0]=h[0]=w[0]=h[n+1]=w[n+1]=0;
for(int i=1;i<=n;i++)f[i]=f[i-1]+(a[i]=='('&&c[i]==0);
for(int i=n;i;--i)g[i]=g[i+1]+(a[i]==')'&&c[i]==0);
for(int i=1;i<=n;i++)h[i]=h[i-1]+(a[i]==')'&&c[i]==0);
for(int i=n;i;--i)w[i]=w[i+1]+(a[i]=='('&&c[i]==0);
}
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<=n+1;i++)c[i]=0;
cin>>a+1;
int cnt=0,num=0,tag=0;
while(1){
calc();
if(f[n]!=g[1]){
cout<<"-1\n";
tag=1;
break;
}
if(f[n]==0)break;
int mx=0,nx=0,cnt=0;++num;
for(int i=1;i<=n;i++){//正：mx
if(c[i])continue;
if(a[i]=='('&&cnt+1<=g[i])++cnt;
if(a[i]==')'&&cnt)--cnt,nx+=2;
}
cnt=0;
for(int i=1;i<=n;i++){//正：mx
if(c[i])continue;
if(a[i]==')'&&cnt+1<=w[i])++cnt;
if(a[i]=='('&&cnt)--cnt,mx+=2;
}
if(mx>nx){
for(int i=1;i<=n;i++){//正：mx
if(c[i])continue;
if(a[i]==')'&&cnt+1<=w[i])c[i]=num,++cnt;
if(a[i]=='('&&cnt)c[i]=num,--cnt;
}
}
else {
for(int i=1;i<=n;i++){//正：mx
if(c[i])continue;
if(a[i]=='('&&cnt+1<=g[i])c[i]=num,++cnt;
if(a[i]==')'&&cnt)--cnt,c[i]=num;
}
}
// for(int i=1;i<=n;i++)cout<<c[i]<<" ";
// cout<<"\n";
}
if(tag)continue;
cout<<num<<"\n";
for(int i=1;i<=n;i++)cout<<c[i]<<" ";
cout<<"\n";
}
}
1775E
真的很好的一道题！
一个重要的思路是：序列全0=差分数组全0=前缀和数组全0
重要应用是：单点操作通过计算前缀和时候就会变成整体的区间操作，而区间操作在差分后又会变成朴素的单点操作
如果我们把原序列转化为前缀和的话，我们进行的单项操作就变成区间操作
那么选出两个数，等价于是给一段区间+1/-1
选出三个数呢？设为 \(a,b,c\)，设为加一的情况，则\([1,a]+1,[1,b]-1,[1,c]+1=[1,a]+1,[1,a]-1,[a+1,b]-1,[1,a]+1,[a+1,b]+1,[b+1,c]+1=[1,a]+1,[b+1,c]+1\)
那么多个数的情况，如出一辙
我们选出一个子序列事实上就变为了抽出若干段，将这些段整体+/- 1
那么就有最小操作数为前缀和数组的最大最小值绝对值之和(如果只有正负数就是其中之一)
signed main(){
ios::sync_with_stdio(false);
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)a[i]+=a[i-1];
int mx=0,mn=1e18;
for(int i=1;i<=n;i++){
if(a[i]>0)mx=max(a[i],mx);
if(a[i]<0)mn=min(a[i],mn);
}
if(mn==1e18)mn=0;
cout<<mx-mn<<"\n";
}
}
1788D
首先考虑计算
显然，两个点相撞之后在相互作用力下不会再移动。
一维的直线运动问题，显然在速度相同的情况下讨论运动方向。
引理：运动方向始终不变
证明：
设向左为 \(0\),向右为 \(1\)
我们讨论当前点为 \(1\) 的情况，为 \(0\) 的情况根据对称性显然成立
考虑分类讨论与其最近的点的运动状况
- 运动状况是 \(0\)，双向奔赴，显然在速度相同的情况下是一定会撞上然后不动的
- 运动状况是 \(1\)，那么其前面的第一个运动状况为 \(0\) 的点(显然存在，也即最后一个点及其之前 )会使得所有为 \(1\) 的点全部撞上停止运动
综上，两种情况均满足，引理得证
我们考虑计算方案
显然，如果我们将运动方向抽象为一个 \(01\) 序列 \(a\) ，那么我们实质上 \(f(S)=\sum_{i=1}^{|S|-1}[a_i=1][a_{i+1}=0]\)
那么我们考虑统计贡献。
统计贡献的方法是看每一个单一贡献的组成部分，将组成部分单独抽离进行计算求和
那么这题贡献显然是一个数对。
接着我们计算数对 \((i,j)\) 的贡献，显然此时 \(i+1\sim j-1\) 应该已经删完。
设 \(pos1(pos1<i),pos2(pos2>j)\) 分别为满足： \(x_i-x_{pos1}>x_j-x_i,x_{pos2}-x_j>x_j-x_i\) 的最大/最小值。
那么则 \([1,pos1],[pos2,n]\) 的数可选可不选，其他数必选，那么贡献为： \(2^{pos1+n-pos2+1}\)
显然 \(pos1,pos2\) 可以使用二分查找求出，然后计算贡献即可。
\(O(n^2\log n)\)
#include<iostream>
#include<algorithm>
using namespace std;
const int p=1e9+7;
#define N 3050
int a[N],n,ans,pw[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
pw[0]=1;
for(int i=1;i<=n;i++)pw[i]=pw[i-1]*2ll%p;
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
int pos1=lower_bound(a+1,a+n+1,a[i]+a[i]-a[j])-a-1;
int pos2=lower_bound(a+1,a+n+1,-a[i]+a[j]+a[j])-a;
ans=(ans+pw[pos1+(n-pos2+1)])%p;
}
}
cout<<ans<<"\n";
}
1778D
纪念一下我正式独立做出的期望题，这里体现了 优化DP状态设计的思想
由于概率均等，我们只关心有多少位不匹配
设 \(g_i\) 表示还有 \(i\) 位没匹配好的期望次数，设有 \(x\) 位不匹配
发现这玩意很难搞，但 \(g_0=0\)，我们可以用作差法优化DP状态，也即设 \(f_i=g_{i}-g_{i-1}\)，求出 \(f\) 后就可以递推出 \(g\)
那么 \(f_i\) 的意义即为在有 \(i\) 个不匹配的情况下，找到翻好一个位置的期望，这就变得简单了
显然一次有 \(\frac{i}{n}\) 的概率翻对，有 \(\frac{n-i}{n}\) 的概率挂掉，这时候问题变为求 \(f_{i+1}\) 变回原来状态，然后再使用 \(f_i\) 次翻好一个位置
则有 \(f_i=\frac{i}{n}+\frac{n-i}{n}(1+f_{i+1}+f_i)\implies f_i=\frac{n+(n-i)f_{i+1}}{i}\)
显然有 \(f_n=1\)
最后答案即为 \(\sum_{i=1}^xf_i\)
void solve(){
for(int i=1;i<=n;i++)f[i]=0;
cin>>n;
f[n]=1;
for(int i=n-1;i;--i){
f[i]=power(i,p-2)*(n+(n-i)*f[i+1]%p)%p;
}
cin>>a+1;cin>>b+1;
cnt=0;
for(int i=1;i<=n;i++)cnt+=(a[i]!=b[i]);
int ans=0;
for(int i=cnt;i;i--)ans=(ans+f[i])%p;
cout<<ans<<"\n";
}
*2100的期望题……
632D
挺有意思的一道题
注意到 \(m\le 10^6\)，**转化角度，考虑枚举最小公倍数 \(x\) **，显然如果 \(a_i\ge m\) 直接舍掉，值域变成 \(10^6\)
利用公倍数的性质：
设 \(x=lcm(a_1,a_2……a_n),p=kx\)，那么 \(p\) 有 \(x\) 的所有因数
那么我们可以使用倍数法，求出每一个值 \(i,(i\in [1,m])\)，其包含了 \(a_i\) 中的因数的个数
然后从小到大扫最大值，注意严格大于才能更新(这是因为可能后面的答案就不是lcm而是一个普通公倍数了)
找到值之后，枚举 \(a_i\) 判断能否整除即可
#define N 1005050
vector<int>p[N];
int cnt[N],n,m,ans[N],s,a[N];
inline void solve(){
for(int i=1;i<=m;i++){
for(int j=i;j<=m;j+=i)ans[j]+=cnt[i],p[j].push_back(i);
}
for(int i=1;i<=m;i++)s=max(s,ans[i]);
for(int i=1;i<=m;i++){
if(s==ans[i]){
cout<<i<<" "<<s<<"\n";
for(int j=1;j<=n;j++){
if(i%a[j]==0)cout<<j<<" ";
}
break;
}
}
return ;
}
int main(){
read(n);read(m);
for(int i=1;i<=n;i++){
int x;read(x);if(x<=m)cnt[x]++;
a[i]=x;
}
solve();
return 0;
}
trick:
转化角度，从序列选数到数选序列，*2100的题
600E
首先，这题问的就是树上众数
树上莫队法
显然我们可以将树用DFS序拍成序列，记录下每个点对应的子树区间，问题就变成了裸的序列众数问题
常见的序列众数，我们会使用莫队。
普通的莫队如果要维护区间众数，显然需要线段树等结构的嵌套，这使复杂度多了一个 \(\log\) ，显然是不优的
那么还有两种方法可以保证 \(O(n\sqrt n)\) 的复杂度
第一种是回滚莫队法：其原因是众数在只加不删时是容易维护的
简单来说，我们将问题分为两类，第一类是区间长度 \(\le \sqrt n\) 的问题，我们直接暴力统计
那么剩下的所有区间长度都 \(\ge \sqrt n\)
考虑将所有问题按左端点所在块排序，块内右端点递增排序
我们将问题整块整块的处理
- 初始化：记录当前指针 \(l=R+1,r=R\)，其中 \(R\) 是当前块的终点（这里注意不存在一个询问的右端点小于 \(R\))
- 扫描询问，以如下形式操作：
- 移动右端点，不断加入新的数(注意需要两个变量：众数次数和众数编号和，维护是简单的，这里略去)
- 记录下当前统计的答案，然后左移左端点，只增不删
- 将答案记录，然后还原答案变量，并且将左端点移回 \(R\) 只改动 \(cnt\) 数组
但200ms 的时间，加上巨大的常数，是难以卡过的
第二种做法：普通莫队+值域分块
注意到移动的复杂度必须要求 \(O(1)\) 但查询的复杂度只需要在 \(O(\sqrt n)\) 范围内即可
那么记录三个量： \(cnt[i]\) 表示颜色 \(i\) 的出现次数，\(cn[i]\) 记录出现次数为 \(i\) 的颜色编号和，\(sum[i]\) 记录出现次数在第 \(i\) 块内的颜色编号和
正常增删维护
void add(int x){ x=dfn[x];//序列x位置的颜色 sum[pos[cnt[x]]]--; cn[cnt[x]]-=x; ++cnt[x]; sum[pos[cnt[x]]]++; cn[cnt[x]]+=x; } void del(int x){ x=dfn[x]; sum[pos[cnt[x]]]--; cn[cnt[x]]-=x; --cnt[x]; sum[pos[cnt[x]]]++; cn[cnt[x]]+=x; }然后将查询分为 \(\sqrt n\) 范围内的大查询，然后在块内查询
int get(){ for(int i=pos[n];i>=0;--i){ if(sum[i]){ int r=min(i*bl,num); for(int j=r;pos[j]==i;--j){ if(cn[j])return cn[j]; } } } return 0; }
当然，这道题也让我们想起了雨天的尾巴，简单地说，就是对于每个节点开一个线段树(动态开点)，在线段树合并中求众数
还有一个更加优秀的做法：
考虑朴素的树上做法
开一个计数数组 \(cnt\)，在树上深度优先遍历时，暴力地在子树扫描统计，然后清空，显然复杂度 \(O(n^2)\)
考虑进行优化：
显然每棵子树DFS完之后有一个儿子是不需要清空的，那么我们将这个儿子设为点最多的，不清空这玩意。
复杂度 \(O(n\log n)\)
1832E
差量分析思想
考虑设 \(f_{i,j}=\sum_{k=1}^i{i-k+1\choose j}\)，则 \(b_i=f_{i,k},f_{i,j}=f_{i-1,j}+f_{i,j-1}+a_i\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
#define p 998244353
#define N 10505050
int a[N],b[N][6],inv[N],jc[N],c[N];
int t,n,k,x,y,m;
void init(){
jc[1] = inv[1] = jc[0]=inv[0]=1;
for (int i = 2; i <= n; i++) {
jc[i] = jc[i - 1] * i % p;
inv[i] = p - (p / i * inv[p % i] % p) % p;
}
for(int i=2;i<=n;i++)inv[i]=inv[i-1]*inv[i]%p;
}
int C(int n,int m){
if(n<m)return 0;
return jc[n]*inv[m]%p*inv[n-m]%p;
}
signed main(){
cin>>n>>a[1]>>x>>y>>m>>k;
init();
for(int i=2;i<=n;i++){
a[i]=(a[i-1]*x%m+y)%m;
}
for(int j=0;j<=k;j++){
for(int i=1;i<=n;i++){
if(j==0)b[i][j]=b[i-1][j]+a[i];
else {
b[i][j]=(b[i-1][j]+b[i-1][j-1])%p+C(1,j)*a[i]%p;
}
b[i][j]%=p;
}
}
int ans=0;
for(int i=1;i<=n;i++)ans^=(b[i][k]*i);
cout<<ans<<"\n";
}
就这TM2200
1826D
有意思的带限制DP题
遇到这种思维题，我们一般考虑比较在一定相同条件下的决策的优劣，从而得到优化方案
在这个题中体现为：如果两个区间的前三大值相同，则区间长度小的更优
进一步得到推论：一个区间，其两端一定属于前三大值
那么我们得到一个朴素做法：枚举区间，预处理其最大值
这里又有一个优化手段：对于最优化的选择区间问题，我们可以将枚举区间转化为枚举区间中的某个数，再计算其向左向右扩展的代价，也可以理解为两端区间的拼凑，这是“3”化“2”的重要套路
设 \(f_i=\max_{k<i}\lbrace val_i+val_k-(i-k)\rbrace=val_i-i+\max(val_k+k),g_i=val_i+i+\max_{k>i}(val_k-k)\)
递推进行计算，答案即为 \(\max_{1\le i\le n} \lbrace f_{i-1}+g_{i+1}+val_{i}-1\rbrace\)
为什么，如何保证 \(val_i\) 是最大值呢？
事实上，\(f,g\) 里的决策也是呈段状的，那么我们枚举 \(i\) 的过程实际上也是在给可能的区间枚举最大值
1594E2
有意思的树上计数题，推荐先去看 E1
首先考虑设 \(g_i\) 表示高度为 \(i\) 的完全二叉树，根节点颜色确定，没有任何限制情况下的答案。
显然有 \(g[1]=1,g[n]=16g_{n-1}^2\)
然后考虑怎么处理这个带限制的问题
遇到此类很小部分点带限制，其余部分一样的问题，一般考虑将特殊部分单独拿出计算，与一般部分进行答案的合并
显然，树高是很低的，而 \(n\le 2000\)，也即子树中有带限制的点的点的个数是 \(O(nk)\) 的，考虑把每一个特殊点到根节点的链单独拿出，然后将其合并成一颗树进行计算
由于原树是完全二叉树，则我们抽离的这颗虚树中每个节点也不会有超过2个儿子。注意由于点的编号很大，可以用 map 映射新的点号
考虑进行DP计算，设 \(f[i,j]\) 表示在以 \(i\) 为根，\(j\) 根节点颜色为 \(j\) 时的方案数，那么我们根据儿子个数分类讨论，计算 \(f[u,j]\)，用 \(vis[i,j]\) 表示节点 \(i\) 能否取颜色 \(j\)，用 \(vaild(i,j)\) 表示颜色 \(i,j\) 能否相邻
-
没儿子
此时这个节点的子树是一般的，则 \(f[u,j]=g[k-dep[u]+1][vis[u,j]]\)
-
有一个儿子 \(v\)
此时另一个一般的儿子是4种颜色随便取，方案数是 \(4g[k-dep[u]]\)
\(f[u,j]=vis[u,j]\sum_{vaild(j,a)}4f[v,a]g[k-dep[u]]\)
-
有两个儿子 \(v_1,v_2\)
类比有一个儿子的情况，有：
\(f[u,j]=vis[u,j]\sum_{vaild(j,a)}\sum_{valid(j,b)}f[v_1,a]f[v_2,b]\)
#include<bits/stdc++.h>
using namespace std;
#define N 505050
#define int long long
const int p=1e9+7;
int head[N],ver[N],nxt[N],tot,num,n,m,k,f[N][6],g[65],c[N],lim[N],dep[N];
map<int,int>H;
/*
H:虚树编号的映射
co:映射时颜色限制
f:dp数组，f[i,j]表示点i子树中i染为j的方案数(注意先处理根节点)，注意若有限制除限制外其他几个变成0
g:辅助数组，g[i]表示没有限制下高为i的子树方案数
lim:初始深度
*/
void init(){//预处理g数组
g[1]=1;memset(c,-1,sizeof c);
for(int i=2;i<=k;i++)g[i]=g[i-1]*g[i-1]%p*16ll%p;
}
void add(int u,int v){
nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
int get(char a){//返回颜色
if(a=='r')return 0;
if(a=='o')return 1;
if(a=='w')return 2;
if(a=='y')return 3;
if(a=='g')return 4;
if(a=='b')return 5;
}
bool check(int a,int b){//返回两色是否矛盾
if(a==-1||b==-1)return true;
if(a/2==b/2)return false;
else return true;
}
void build(int x,char a){//处理出根到i的链，并初始化属性
if(H[x]==0)H[x]=++num;
else {
c[H[x]]=get(a);return ;
}
c[H[x]]=get(a);
while(x>1){
int p=x;
x/=2;
if(H[x]==0){
H[x]=++num;add(H[x],H[p]);add(H[p],H[x]);
}
else{
add(H[x],H[p]);add(H[p],H[x]);break;
}
}
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
int cnt=0,s1,s2;
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(v==fa)continue;
dfs(v,u);
++cnt;
if(cnt==1)s1=v;
if(cnt==2)s2=v;
}
if(cnt==0){
if(c[u]!=-1)f[u][c[u]]=g[k-dep[u]];
else for(int i=0;i<6;i++)f[u][i]=g[k-dep[u]];
}
else if(cnt==1){
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
if(check(i,j)){
f[u][i]=(f[u][i]+4ll*f[s1][j]*g[k-dep[s1]]%p)%p;
}
}
}
}
else {
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
for(int a=0;a<6;a++){
if(check(i,j)&&check(i,a))f[u][i]=(f[u][i]+f[s1][j]*f[s2][a]%p)%p;
}
}
}
}
if(c[u]!=-1){
for(int i=0;i<6;i++)if(i!=c[u])f[u][i]=0;
}
}
signed main(){
char ch[15];
cin>>k>>n;k++;
init();H[1]=++num;
for(int i=1;i<=n;i++){
int x;cin>>x>>ch+1;
build(x,ch[1]);
}
dfs(1,0);
int ans=0;for(int i=0;i<6;i++)ans+=f[1][i];
cout<<(ans%p+p)%p<<"\n";
}
1594F
简要题意：
给定 \(s,n,k\) ，构造一个长度为 \(n\) 的序列，序列最小值大于 \(0\)，序列和为 \(s\)，使得不存在任意连续子序列和为 \(k\)
如果存在符合条件的序列，输出 "YES"'，否则 "NO"
对于静态的有关连续子序列的和的问题，我们一般考虑使用前缀和进行操作
那么原问题等价于：有 \(n+1\) 个数满足 \(0=s_0<s_1<s_2<…<s_n=s\)，从中两两做差不为 \(k\)
首先我们只需要考虑长度 \(\le k\) 的子序列
那么容易想到我们可以将一个子序列隔开，两边将其“堵上“，使其不能外扩
详细地说就是，考虑这样一种构造方案：
放 \(k-1\) 个1，然后放一个 \(k+1\)，这显然满足条件
在最后的时候，如果剩余的值大于了剩余的位置，那么向值为 \(k+1\) 的格子上填即可，如果小于则无解
cin>>t;
while(t--){
cin>>s>>n>>k;
if(s==k)cout<<"Yes\n";
else if(s<n)cout<<"No\n";
else {
if(k*(s/(k<<1))+min(k,s%(k<<1)+1/*后半截全填1，找起始位置*/)<=n)cout<<"Yes\n";
else cout<<"No\n";
}
}
abc303F
简要题意：有一个怪物血量为 \(h\)，以及 \(n\) 张卡片，每张卡片有属性 \(t,d\)，进行回合制游戏
如果在回合 \(i\) 选择使用卡片 \(j\)，那么卡片 \(j\) 会在回合 \(i\sim i+t_j-1\) 持续造成 \(d_j\) 的伤害，求杀死怪物的最小回合数 \((h\le 0)\)
注意卡片可以重复使用，答案显然具有可二分性
考虑二分答案，转为判定
问题化为在 \(tim\) 的时间求出最大的贡献
显然的一种做法是枚举每一个时刻，再枚举每一个卡片，求最大值，这显然需要优化
我们发现，在任意时刻 \(i\)，所有卡片可以分为两种：
- \(t_j+i\le tim\)
- \(t_j+i>tim\)
不妨设二者分属于集合 \(S,T\)，则 \(i\) 时刻的最大贡献为：
所求即为：
这个式子显然可以分段计算，然后两个集合取较大值
注意到集合的归属与 \(t\) 有关，不妨先按 \(t\) 递增排序，然后考虑优化掉这个式子
下面我们把时间倒着看，也即以下的时刻 \(i\) 表示之前的时刻 \(tim-i+1\)
容易发现，在时间段 \([0,t_1-1],[t_1,t_2-1],[t_2,t_3-1]……[t_{n-1},t_n-1],[t_n,\inf]\)，\(S,T\) 的集合是不同的，换言之答案就可能会发生变化
不妨设时间段 \(l_i\) 表示 \([t_{i-1},t_i-1]\)，\((l_{n=1}=[t_n,\inf])\)，则在时刻 \(i\in l_j\)，\(S=[1,j-1],T=[j,n]\)
其中不同时间段的 \(S,T\) 最值显然可以预处理出来
这里注意一个点，如果存在两个卡片 \(i,j\) 满足 \(t_i=t_j,d_i\ge d_j\)，则 \(j\) 无用，直接删去
read(n);read(h);P=(h<<1)+10;
for(int i=1;i<=n;i++)read(a[i].t),read(a[i].d);
sort(a+1,a+n+1);
b[++m]=a[1];
for(int i=2;i<=n;i++){
if(b[m].t!=a[i].t)b[++m]=a[i];
}
for(int i=1;i<=m;i++)a[i]=b[i];n=m;
for(int i=1;i<=n;i++)mxl[i]=max(mxl[i-1],a[i].t*a[i].d);//S
for(int i=n;i;--i)mxr[i]=max(mxr[i+1],a[i].d);//T
那么我们考虑分时间段计算，下面设计算时间段 \(i\) 的贡献
\(S\) 所提供的答案设为 \(x_1\)，\(T\) 的答案设为 \(x_2\)
由于 \(x_2\) 的特殊性，我们考虑计算其答案
设在时刻 \([a_1,a_2]\) 放了 \(x_2\)，则其答案在到终末时刻的时候构成了一个等差数列：\((a_1x_2,(a_1+1)x_2……,a_2x_2)\)，求和即为 \(x_2\frac{(a_2-a_1+1)(a_1+a_2)}{2}\)
而 \(x_1\) 就是 \((a_2-a_1+1)x_1\)
我们需要知道到底选哪一个是更优的
显然随着时刻的减小，\(x_1\)的贡献在不断减小，而 \(x_2\) 的贡献在变大，究竟分界点在哪里呢？
考虑比较时刻 \(k\) 时两者的贡献，则可以列出不等式 \(x_1\le x_2k\implies k\ge \frac{x_1}{x_2}\)
显然我们可以将时间段 \(i\) 分为 \([t_{i-1},k-1],[k,t_i-1]\)，前一段用 \(x_1\)，后一段用 \(x_2\)
需要注意两个点 \(i=1\)，此时只能用 \(x_2\)
\(i=n+1\),只能用 \(x_1\)
int check(int tim){
int res=0;
for(int i=1;i<=n+1;i++){
int l=a[i-1].t,r=a[i].t-1;
if(r>tim||i==n+1)r=tim;
if(l<=r){
if(i==1){
res+=s(l,r)*mxr[i];
}
else if(i==n+1){
res+=(r-l+1)*mxl[i-1];
}
else {
int cut=mxl[i-1]/mxr[i];//这里是下取整，变成[l,cut],[cut+1,r]
if(l<=cut){
res+=mxl[i-1]*(min(cut,r)-l+1);
}
if(cut<r){
res+=s(max(cut+1,l),r)*mxr[i];//等差数列求和
}
}
}
if(res>=h)return 1;
}
return res>=h;
}
注意精度，推荐使用__int128
trick:
- 在此类与结束时间有关的问题中，将时间倒过来看是一个不错的方法
- 重要的分段计数思想
- 分类讨论不同类的决策，并考虑高效划分集合范围
- 预处理一个集合在不同阶段的答案，注意到随着阶段增长，直增不删正推，只删不增倒推
- 比较决策思想