VP NOIP 2024 游寄
考了 3.5h,比正赛少 1h,得了 100+70+0+0,没有 1=。再考 1h 估计能上 200。
T1 edit
这题青在哪?简单小贪心,代码也不长(那些 多行的是怎么写出来的)。唯一称得上青的可能是贪心的严谨证明吧。
可以发现不能动的部分将整个字符串分成了好几段,每段的字符都可以自由排列顺序。代码里首先用了 idx 数组标记每个字符属于哪一段,以维护一整段的信息。对于两个字符串对应位置的字符,如果都不能动,那么就无计可施了。如果其中一个能动,我们可以在能动的字符所属的段中,找出一个可用的字符,把它移过来,以匹配另一个字符串对应位置的字符,尽量匹配即可。最终只剩下两边都能动的位置没有处理,我们找出这两个位置所处的段的共有字符,把共有字符移过来进行匹配,尽量匹配即可。
为什么这样做是对的?因为两个字符进行匹配,不管这两个字符所处的位置,在前面还是在后面,获得的价值都为 。所以只要尽量匹配,不用担心在前面匹配了,后面的价值就会减少,因为总价值是不变的。你可以分讨一下,模拟各种情况,发现这种贪心总是不劣的。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,idx1[N],idx2[N],cnt1[2][N],cnt2[2][N];
char s1[N],s2[N],t1[N],t2[N];
void solve(){
scanf("%d\n%s\n%s\n%s\n%s",&n,s1+1,s2+1,t1+1,t2+1);
memset(cnt1,0,sizeof cnt1);
memset(cnt2,0,sizeof cnt2);
for(int i=1;i<=n;i++){
if(t1[i]=='1'&&t1[i-1]!='1')idx1[i]=idx1[i-1]+1;
else idx1[i]=idx1[i-1];
if(t2[i]=='1'&&t2[i-1]!='1')idx2[i]=idx2[i-1]+1;
else idx2[i]=idx2[i-1];
if(t1[i]=='1')cnt1[s1[i]-'0'][idx1[i]]++;
if(t2[i]=='1')cnt2[s2[i]-'0'][idx2[i]]++;
}
int ans=0;
for(int i=1;i<=n;i++){
int v1=t1[i]-'0',v2=t2[i]-'0';
if(v1==0&&v2==0&&s1[i]==s2[i])ans++;
else if(v1==0&&v2==1){
if(cnt2[s1[i]-'0'][idx2[i]]>0)
cnt2[s1[i]-'0'][idx2[i]]--,ans++;
}
else if(v1==1&&v2==0){
if(cnt1[s2[i]-'0'][idx1[i]]>0)
cnt1[s2[i]-'0'][idx1[i]]--,ans++;
}
}
for(int i=1;i<=n;i++){
int v1=t1[i]-'0',v2=t2[i]-'0';
if(v1==0||v2==0)continue;
if(cnt1[0][idx1[i]]>0&&cnt2[0][idx2[i]]>0)
cnt1[0][idx1[i]]--,cnt2[0][idx2[i]]--,ans++;
else if(cnt1[1][idx1[i]]>0&&cnt2[1][idx2[i]]>0)
cnt1[1][idx1[i]]--,cnt2[1][idx2[i]]--,ans++;
else{
if(cnt1[0][idx1[i]]>0)cnt1[0][idx1[i]]--;
if(cnt1[1][idx1[i]]>0)cnt1[1][idx1[i]]--;
if(cnt2[0][idx2[i]]>0)cnt2[0][idx2[i]]--;
if(cnt2[1][idx2[i]]>0)cnt2[1][idx2[i]]--;
}
}
printf("%d\n",ans);
}
int main(){
// freopen("edit.in","r",stdin);
// freopen("edit.out","w",stdout);
scanf("%d",&T);
while(T--)solve();
return 0;
}
T2 assign
比 T1 难好几倍的题怎么才是绿?什么是组合数学?我不会呀,我只会 DP。第一眼看到这题:,这不就是何老师上次场切的矩阵快速幂优化 DP 吗?发现这题的线性做法有 分,并且矩阵快速幂也依赖线性做法,于是我就开始思考 DP 的方程式。也是挺神奇的,比赛结束前 5min 时我还没有调出来,大样例第一个点都没过。我在想可能 和 有重复计数的情况,于是一直在雷霆大思考,正确的转移方程式到底是什么,越想越错。我盯着我的方程式,又思考了它的定义,瞅出几个不对的地方改了,感觉其他很多地方也要改但实在找不出来了。于是随手测了一下样例,!?过了?!这能过?于是我就这样在比赛结束前极限拿下 70 分。
现在讲做法。
状态定义
对 , 表示处理完前 条二元限制后,第 条限制不强制 的方案数; 表示第 条限制会强制 的方案数。这里 中 仍有 种取值,和 是否有一元限制无关。方案数指的是 的方案数,而不是 的方案数。若一个位置存在多个不同值的一元限制,答案为 ,无需进行下列计算。
初始值
若 ,则 。
若 ,则 。
转移方程
若 ,则 。
若 ,则 。
讲解一下转移方程中的 是什么意思。前面的数可能会产生二元限制,规定位置 必须为 。 有不同的 种取值,只有取到 这一种情况,才有可能构造出合法的解,因此乘以 。
答案
若 ,题目没规定答案是多少,此处认为是 。
若 :
当 时,答案为 。
当 时,答案为 。
矩阵快速幂加速
注意到 ,。这题的 DP 转移方程显然可以用矩阵转移,从而使时间复杂度降至 。很可惜我做出线性做法时比赛刚好结束并且我也忘记矩阵乘法的规则了,赛后尝试把矩阵推了出来。 时的转移方程为:
然后就能做了。
代码
solve1() 和 solve2() 分别代表线性做法和矩阵做法。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,P=1e9+7,M=1e5+5;
int T,n,m,v,c[M],d[M],f[2][N],inv,x[N];
map<int,int>mp;
struct matrix{
int mat[2][2];
matrix(){
mat[0][0]=mat[1][1]=1;
mat[0][1]=mat[1][0]=0;
}
matrix(int a,int b,int c,int d){
mat[0][0]=a,mat[0][1]=b;
mat[1][0]=c,mat[1][1]=d;
}
matrix operator*(const matrix &x)const{
return matrix(
(mat[0][0]*x.mat[0][0]%P+mat[0][1]*x.mat[1][0]%P)%P,
(mat[0][0]*x.mat[0][1]%P+mat[0][1]*x.mat[1][1]%P)%P,
(mat[1][0]*x.mat[0][0]%P+mat[1][1]*x.mat[1][0]%P)%P,
(mat[1][0]*x.mat[0][1]%P+mat[1][1]*x.mat[1][1]%P)%P
);
}
};
int qpow(int x,int y){
int res=1;
while(y){
if(y&1)res=res*x%P;
x=x*x%P;
y>>=1;
}
return res;
}
matrix qpow(matrix x,int y){
matrix res;
while(y){
if(y&1)res=res*x;
x=x*x;
y>>=1;
}
return res;
}
void solve1(){
memset(x,0,sizeof x);
bool ok=1;
for(int i=1;i<=m;i++){
cin>>c[i]>>d[i];
if(x[c[i]]&&x[c[i]]!=d[i])ok=0;
x[c[i]]=d[i];
}
if(!ok){cout<<"0\n";return;}
if(x[1])f[0][1]=(v-1)*v%P,f[1][1]=v;
else f[0][1]=v*v%P,f[1][1]=0ll;
if(n==1){cout<<"1\n";return;}
for(int i=2;i<n;i++){
if(x[i]){
f[0][i]=(f[0][i-1]+f[1][i-1]*inv%P)*(v-1)%P*v%P;
f[1][i]=(f[0][i-1]+f[1][i-1]*inv%P)*v%P;
}
else{
f[0][i]=(f[1][i-1]*(v-1)%P+f[0][i-1]*v%P)*v%P;
f[1][i]=f[1][i-1]*v%P;
}
}
if(x[n])cout<<(f[0][n-1]+f[1][n-1]*inv%P)%P<<'\n';
else cout<<(f[0][n-1]+f[1][n-1])%P<<'\n';
}
void solve2(){
bool ok=1;
mp.clear();
for(int i=1,c,d;i<=m;i++){
cin>>c>>d;
if(mp.count(c)&&mp[c]!=d)ok=0;
mp[c]=d;
}
if(!ok){cout<<"0\n";return;}
if(n==1){cout<<"1\n";return;}
if(mp.count(1))f[0][1]=(v-1)*v%P,f[1][1]=v;
else f[0][1]=v*v%P,f[1][1]=0ll;
int pre=1,cur=0;
matrix mv(v*v%P,0,(v-1)*v%P,v);
for(auto [a,b]:mp){
if(a==n||a==1)continue;
matrix t=qpow(mv,a-pre-1);
f[0][cur]=(f[0][cur^1]*t.mat[0][0]%P+f[1][cur^1]*t.mat[1][0]%P)%P;
f[1][cur]=(f[0][cur^1]*t.mat[0][1]%P+f[1][cur^1]*t.mat[1][1]%P)%P;
cur^=1;
f[0][cur]=(f[0][cur^1]+f[1][cur^1]*inv%P)*(v-1)%P*v%P;
f[1][cur]=(f[0][cur^1]+f[1][cur^1]*inv%P)*v%P;
cur^=1,pre=a;
}
matrix t=qpow(mv,n-pre-1);
f[0][cur]=(f[0][cur^1]*t.mat[0][0]%P+f[1][cur^1]*t.mat[1][0]%P)%P;
f[1][cur]=(f[0][cur^1]*t.mat[0][1]%P+f[1][cur^1]*t.mat[1][1]%P)%P;
if(mp.count(n))cout<<(f[0][cur]+f[1][cur]*inv%P)%P<<'\n';
else cout<<(f[0][cur]+f[1][cur])%P<<'\n';
}
signed main(){
// freopen("assign.in","r",stdin);
// freopen("assign.out","w",stdout);
cin.tie(0)->sync_with_stdio(0);
cin>>T;
while(T--){
cin>>n>>m>>v;
inv=qpow(v,P-2);
/*if(n<N)solve1();
else */solve2();
}
return 0;
}
T3 和 T4 没做,题都没看。赛后补了,非常具有思维难度,至少比黑的 hub 难。
T3 traverse
首先这题的题面就很难读懂。
读懂题面之后,这题是说,有一棵树,把它的边看作节点(可以理解成图中边的中点),我们从一个边可以走到另一个相邻的边,然后呢把这两个边对应的节点连起来(对应图中的蓝边)。最终形成一棵新树(就是图中的蓝树)。求:只能从原树中标红的边出发,能形成多少种不同的蓝树。
如果对于每一个标红的起始边分别计算,显然会出现“从两个不同边出发,形成两棵同样的蓝树”的情况。换一种角度考虑,对于一种蓝树,考虑哪些边能够作为起始边。用图中这个树举例子,标红的所有边任取一条作为起点,都能形成这棵相同的蓝树。

这是整道题最关键的结论:
对于一棵已经生成的新树,所有能作为起点的原树边,恰好组成一条“从叶子到叶子”的链。
我们用前面的例子理解。
假设原树点 周围的边,在新树里形成了:
那么,当遍历从某个方向第一次到达这里时,进入边只能是 或 。
因为:
- 从 进入,可以按 访问;
- 从 进入,可以按 访问;
- 从中间的 或 进入,就无法生成原来的这条链。
所以,这条局部链的两个端点,是允许进入这里的两个方向。
从一个合法起始边出发,向它两侧延伸:
- 到达一个非叶子点时,沿当地链的另一个端点方向继续走;
- 到达叶子时停止。
最终得到一条叶子到叶子的路径。
如果把起点换成这条路径上的另一条边,各处仍然都是从局部链的端点进入,所以还能生成同一棵新树。
如果把起点放到路径外,就会在进入这条路径的位置,从某条局部链的中间进入,因此不合法。
这样,重复计数的问题就解决了:
不再按照起始边计数,而是按照这条路径的两个叶子端点计数。每棵新树只会属于一对叶子。
固定两个叶子作为红色起始边的链,如何计算出方案数?
设这两个叶子为 ,它们之间的路径为 。
对于不在 上的点 ,朝向 的那条边必须是局部链的一个端点,其余边任意排列,方案数是 。
对于 中间的点 ,两条路径边必须分别是局部链的两个端点,所以只能排列中间的其他边,方案数变成 。
使用树形 DP,选取一个非叶子节点作为根, 表示从 子树的叶子走到 的答案, 表示是否经过至少一条题目给定的关键边。这题的核心结论以及做法讲完了,具体式子自己推吧,总能推出来的。也可以参考以下代码:
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
const int N=1e5+5,P=1e9+7;
int c,T,n,k,u[N],v[N],e[N],d[N],rt;
ll inv[N],f[N][2],ans;
vector<pii>g[N];
void dfs(int u,int fa){
f[u][0]=f[u][1]=0;
ll val=0,x=inv[d[u]-1];
for(auto [v,w]:g[u]){
if(v==fa)continue;
dfs(v,u);
if(w)f[v][1]+=f[v][0],f[v][0]=0;
val=(val+f[v][1]*(f[u][0]+f[u][1])%P+f[v][0]*f[u][1]%P)%P;
f[u][0]=(f[u][0]+f[v][0])%P;
f[u][1]=(f[u][1]+f[v][1])%P;
}
if(d[u]==1)f[u][0]++;
ans=(ans+val*x%P)%P;
f[u][1]=f[u][1]*x%P;
f[u][0]=f[u][0]*x%P;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>c>>T;
inv[0]=inv[1]=1;
for(int i=2;i<N;i++)inv[i]=inv[P%i]*(P-P/i)%P;
while(T--){
cin>>n>>k;
for(int i=1;i<=n;i++)g[i].clear(),e[i]=0;
for(int i=1;i<n;i++)cin>>u[i]>>v[i];
for(int i=1,x;i<=k;i++)cin>>x,e[x]=1;
if(n==2){cout<<"1\n";continue;}
for(int i=1;i<n;i++)g[u[i]].push_back({v[i],e[i]});
for(int i=1;i<n;i++)g[v[i]].push_back({u[i],e[i]});
for(int i=1;i<=n;i++)d[i]=g[i].size();
for(int i=1;i<=n;i++)if(d[i]>1)rt=i;
dfs(rt,ans=0);
for(int i=1;i<=n;i++)
for(int j=1;j<d[i];j++)
ans=(ans*j)%P;
cout<<ans<<'\n';
}
return 0;
}
T4 query
记节点深度为 。有一个性质:一个区间 的 的深度为 。
记 ,题目要求的便是:。
接下来考虑如何解决这个问题。
题解是用笛卡尔树解决这个问题的,但是我并不知道是如何想到这个解法的,或许实力还不足吧。
对 数组建立小根笛卡尔树(如何建笛卡尔树见 OI-Wiki),笛卡尔树上的每一个点都代表一个区间,这个点的权值是这段区间的最小值。
看不懂的话,举个例子:

把上图中的树计算出的 数组建立一棵笛卡尔树,得到下图:

我们把所有查询离线下来,按照区间大小从大到小排序,然后依次处理。当处理一个查询 时,我们需要把笛卡尔树中所有管辖范围比 大的节点给激活,在所有激活的节点中查找 区间内的最大值,即为所求的答案。为什么是这样的?因为所有激活的节点管辖区间的长度都不小于 ,符合题目的要求。但是也有可能区间两端的两个节点,它们的管辖范围超出了查询区间,这时我们需处理这种特殊情况,直接使用 ST 表求 数组的区间最值即可。添加一个更小的节点时,我们需要把其父节点删掉,这是因为父节点的管辖范围是包含子节点的,添加了一个子节点,完全可以代替原来的父节点产生答案,因此父节点就不需要了。如何维护一个区间内所有激活节点的最大值?线段树动态维护即可。这题理解起来确实有点困难,尤其是那个笛卡尔树为什么能保证答案的正确性,我也没办法讲的非常通俗易懂,具体请结合代码与图片辅助理解吧。
#include<bits/stdc++.h>
#define mid ((L+R)>>1)
using namespace std;
const int N=5e5+5,M=1e6+5;
int n,q,up[20][N],dep[N],b[N],ans[N];
vector<int>g[N],points[N];
struct queries{
int l,r,id;
};
vector<queries>Q[N];
void dfs(int u,int fa){
up[0][u]=fa;
dep[u]=dep[fa]+1;
for(int v:g[u])
if(v!=fa)dfs(v,u);
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=19;i>=0;i--)
if(dep[up[i][x]]>=dep[y])
x=up[i][x];
if(x==y)return x;
for(int i=19;i>=0;i--)
if(up[i][x]!=up[i][y])
x=up[i][x],y=up[i][y];
return up[0][x];
}
int mx[N<<2],mxr[N<<2];
void update(int u,int L,int R,int x,int v,int r){
if(L==R){mx[u]=v,mxr[u]=r;return;}
if(x<=mid)update(u<<1,L,mid,x,v,r);
else update(u<<1|1,mid+1,R,x,v,r);
mx[u]=max(mx[u<<1],mx[u<<1|1]);
mxr[u]=max(mxr[u<<1],mxr[u<<1|1]);
}
int query(int u,int L,int R,int l,int r){
if(l<=L&&R<=r&&mxr[u]<=r)return mx[u];
if(L==R)return 0;
int res=0;
if(l<=mid)res=max(res,query(u<<1,L,mid,l,r));
if(r>mid)res=max(res,query(u<<1|1,mid+1,R,l,r));
return res;
}
int st[20][N];
int rmq(int l,int r){
if(l>r)return 0;
int lg=__lg(r-l+1);
return min(st[lg][l],st[lg][r-(1<<lg)+1]);
}
int lc[M],rc[M],L[M],R[M],stk[N],top,w[M],fa[M],rt;
bool active[M];
void dfs1(int u){
if(!lc[u])return;
if(lc[u])dfs1(lc[u]);
if(rc[u])dfs1(rc[u]);
L[u]=L[lc[u]],R[u]=R[rc[u]];
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<20;i++)
for(int j=1;j<=n;j++)
up[i][j]=up[i-1][up[i-1][j]];
for(int i=1;i<n;i++)b[i]=dep[lca(i,i+1)];
cin>>q;
for(int i=1,l,r,k;i<=q;i++){
cin>>l>>r>>k;
Q[k].push_back({l,r,i});
}
for(int i=1;i<n;i++)st[0][i]=b[i];
for(int i=1;i<20;i++)
for(int j=1;j+(1<<i)<=n;j++)
st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
for(int i=1;i<n;i++){
int k=top,u=n+i;
w[u]=b[i];
while(k&&w[stk[k]]>w[u])k--;
if(k)rc[stk[k]]=u;
if(k<top)lc[u]=stk[k+1];
stk[++k]=u,top=k;
}
rt=n==1?1:stk[1];
for(int i=1;i<=n;i++)L[i]=R[i]=i,w[i]=dep[i];
for(int i=1;i<n;i++){
int u=i+n;
if(!lc[u])lc[u]=i;
if(!rc[u])rc[u]=i+1;
fa[lc[u]]=fa[rc[u]]=u;
}
dfs1(rt);
for(int i=1;i<n+n;i++)points[R[i]-L[i]+1].push_back(i);
for(int k=n;k>=1;k--){
for(auto i:points[k]){
if(fa[i]&&active[fa[i]]){
update(1,1,n,L[fa[i]],0,0);
active[fa[i]]=0;
}
update(1,1,n,L[i],w[i],R[i]);
active[i]=1;
}
for(auto [l,r,id]:Q[k]){
int res=query(1,1,n,l,r);
res=max(res,rmq(l,l+k-2));
res=max(res,rmq(r-k+1,r-1));
ans[id]=res;
}
}
for(int i=1;i<=q;i++)
cout<<ans[i]<<'\n';
return 0;
}