【做题记录】多校-dp

A. Multitest Generator

考虑一个长为 \(m(m\ge 2)\) 的序列 \(b\)，我们显然可以令 \(b_1=1,b_2=m-2\) 来使它变成 multitest。于是我们只需要判断能否使用 \(0\) 次或 \(1\) 次操作使其变成 multitest。

首先考虑 \(0\) 次，也就是它本身就是个 multitest。设 \(f_i\) 表示 \(i\sim n\) 这段后缀中有多少个 test，若不合法则 \(f_i=0\)，可以 DP 出来。于是 \(i\) 的答案为 \(0\) 的充要条件即为 \(a_i=f_{i+1}\)。

考虑 \(1\) 次。首先如果 \(f_{i+1}\ne0\)，那么我们可以直接修改 \(a_i\) 来满足要求。而如果 \(f_{i+1}=0\)，我们则希望通过一次修改将 \(i+1\sim n\) 这段后缀变成 \(a_i\) 个 test。考虑如果能变成 \(x\) 个 test，则一定可以变成 \(x-1\) 个 test，于是设 \(g_i\) 表示通过一次修改能使 \(i\sim n\) 最多变成多少个 test，则有：

\[g_i=\max(g_{i+a_i+1}+1,\max_{j=i+1}^{n}\{f_j\}+1) \]

也就是分别考虑是否修改 \(a_i\)。于是若 \(g_{i+1}\ge a_i\) 那么 \(i\) 的答案为 \(1\)，否则答案为 \(2\)。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int T,n,a[maxn],f[maxn],hp[maxn],g[maxn];
il void solve(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}f[n+1]=hp[n+1]=g[n+1]=0;for(int i=n;i;i--){f[i]=i+a[i]==n?1:i+a[i]>n||!f[i+a[i]+1]?0:f[i+a[i]+1]+1;hp[i]=max(hp[i+1],f[i]);g[i]=max(i+a[i]>n?0:g[i+a[i]+1]+1,hp[i+1]+1);}for(int i=1;i<n;i++){cout<<(a[i]==f[i+1]?0:f[i+1]||g[i+1]>=a[i]?1:2)<<' ';}cout<<'\n';
}
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>T;while(T--){solve();}return 0;
}
}
int main(){return asbt::main();}

B. Bitwise Slides

记 \(s_i\) 为前缀异或和数组。则对于每一时刻，都有三个数的异或和为 \(s_i\)。又因为有两个相等，所以必然有一个值为 \(s_i\)。

设 \(dp_{i,j}\) 表示进行完第 \(i\) 次操作后那两个相等的数值为 \(j\) 的方案数。于是有转移：

• \(j=s_{i-1}\)，\(dp_{i,j}\gets 3dp_{i-1,j}\)。

• \(j=s_i\)，\(\begin{cases}dp_{i,j}\gets dp_{i-1,j}\\dp_{i,s_{i-1}}\gets2dp_{i,j}\end{cases}\)。

• \(else\)，\(dp_{i,j}\gets dp_{i-1,j}\)。

发现每次 DP 值改变的只有 \(dp_{i,s_{i-1}}\)。用 map 维护即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pii pair<int,int>
#define fir first
#define sec second
using namespace std;
namespace asbt{
const int maxn=2e5+5,mod=1e9+7;
il int pls(int x,int y){return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){x=pls(x,y);
}
il int mns(int x,int y){return x<y?x-y+mod:x-y;
}
il void sub(int &x,int y){x=mns(x,y);
}
int T,n,a[maxn];
map<int,int> dp;
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>T;while(T--){cin>>n;dp.clear();dp[0]=1;for(int i=1,x;i<=n;i++){cin>>x;a[i]=a[i-1]^x;dp[a[i-1]]=(dp[a[i-1]]*3ll+dp[a[i]]*2ll)%mod;}int ans=0;for(pii i:dp){add(ans,i.sec);}cout<<ans<<'\n';}return 0;
}
}
int main(){return asbt::main();}