博客详情 - oirush

wyh 的博客
9.21 %你赛
wyh LV 9 @ 2026-9-21 18:33:14

9.21 %你赛

比赛数据

分数 $\color{#D0F000}260/440$ 。
各题分数（赛时/总分）：
T1 $\color{#00F000}100/100$
T2 $\color{#00F000}100/100$
T3 $\color{#F07000}31/120$
T4 $\color{#F09000}30/100$
排名 $\color{#C08050}3/7$ （符合预期）。

T1 link $\color{#00E0A0}(4.00)$

吸取昨天教训，看到 $n,q \leq 5000$ 直接往DP想。
令 $dp_{i,j}$ 为第 $i$ 次操作后删除前缀长度至多为 $j$ 时至少需要删除的后缀长度。
对于一次操作，对于每一个后缀算出至少需要再删除多长的后缀才能完成操作是 $O(n)$ 的，
对于每一个前缀算出至少需要再删除多长的前缀才能完成操作也是 $O(n)$ 的。
如果对所有 $0 \leq j \leq n$ 均有 $dp_{i,j}+j > n$ 则第 $i$ 次操作无法完成。

时间复杂度 $O(n\min(n,q))$ 。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[5007],b[5007],c[5007],mn[15][5007],g[5007],x[5007],y[5007],dpa[5007],dpb[5007];
int MN(int l,int r){
	int w=r-l+1;
	return min(mn[g[w]][l],mn[g[w]][r-(1<<g[w])+1]);
}
int main(){
	cin>>n>>m;
	g[0]=-1;
	for(int i=1;i<=n;i++){
		g[i]=g[i/2]+1;
		cin>>a[i];
		mn[0][i]=a[i];
	}
	for(int i=1;i<15;i++){
		for(int j=1;j+(1<<i)<=n+1;j++){
			mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<=n+1;j++) dpb[j]=11751;
		cin>>b[i]>>c[i];
		for(int j=n+1;j>n-b[i];j--) x[j]=11751;
		for(int j=n-b[i];j>=0;j--){
			if(MN(j+1,j+b[i])>=c[i]) x[j]=j+b[i];
			else x[j]=x[j+1];
		}
		for(int j=0;j<b[i];j++) y[n-j]=11751;
		for(int j=b[i];j<=n+1;j++){
			if(MN(j-b[i]+1,j)>=c[i]) y[n-j]=n-j+b[i];
			else y[n-j]=y[n-j+1];
		}
		for(int j=0;j<=n;j++){
			if(j) dpb[j]=min(dpb[j],dpb[j-1]);
			if(dpa[j]!=11751) dpb[j]=min(dpb[j],y[dpa[j]]);
			if(x[j]!=11751) dpb[x[j]]=min(dpb[j],dpa[j]);
		}
		int f=0;
		for(int j=0;j<=n;j++){
			dpa[j]=dpb[j];
			if(dpa[j]+j<=n) f=1;
		}
		if(!f){
			cout<<i-1;
			return 0;
		}
	}
	cout<<m;
	return 0;
}

T2 link $\color{#00E0C0}(4.25)$

神秘状态压缩矩阵快速幂。

发现 $\text{Subtask 1}$ 是快速幂，又 $n \leq 10$ ，线索明显指向矩阵快速幂。
但是，乍一看，状态数高达 $10^{10}$ ，似乎不行。
不过又发现很多本质相同的状态可以合并。
如果将颜色置换及重排后相等的状态视为本质相同的，那到底有多少本质不同的状态呢？
似乎有几百个，但实际用DFS搜一下就发现：**的就只有 $42$ 个！
再把各状态间的转移概率暴力算一下就可以用矩阵快速幂秒掉这题了。

记状态数为 $S(n)$ ，则时间复杂度为 $O\left(S(n)^2n^3+S(n)^3\log(t)\right)$ 。
由状态意义得 $S(n) \in O(2^n)$ 。
事后发现状态数即为知名的分拆数，由DP结果估计

$$S(n) \in o\left(\epsilon^n\right)(\epsilon > 1),S(n) \in \omega(n^{x})(x>1)$$

代码：（真**长啊）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
int n,m,w,s[12],st[1007][12],sz[1007],ct;
ll k,tmpa[47][47],tmpb[47][47],p[47][47],a[64][47][47],ans;
priority_queue<int>pq;
void DFS(int p){
	if(!w){
		ct++;
		sz[ct]=p-1;
		for(int i=1;i<p;i++) st[ct][i]=s[i];
		return;
	}
	for(int i=1;i<=s[p-1];i++){
		if(i>w) break;
		w-=i;
		s[p]=i;
		DFS(p+1);
		w+=i;
		s[p]=0;
	}
}
ll QP(ll b,ll e){
	ll tmp=b,res=1;
	while(e){
		if(e&1) res=(res*tmp)%mod;
		tmp=(tmp*tmp)%mod;
		e>>=1;
	}
	return res;
}
void MUL(int r,int s,int t,ll x[47][47],ll y[47][47],ll (&res)[47][47]){
	for(int i=1;i<=r;i++) for(int j=1;j<=s;j++) tmpa[i][j]=x[i][j];
	for(int i=1;i<=s;i++) for(int j=1;j<=t;j++) tmpb[i][j]=y[i][j];
	for(int i=1;i<=r;i++) for(int j=1;j<=s;j++) res[i][j]=0;
	for(int i=1;i<=r;i++) for(int j=1;j<=t;j++) for(int k=1;k<=s;k++) res[i][j]=(res[i][j]+tmpa[i][k]*tmpb[k][j])%mod;
}
int main(){
	cin>>n>>k>>m;
	s[0]=w=n;
	DFS(1);
	for(int i=1;i<=ct;i++) for(int j=1;j<=sz[i];j++) for(int k=1;k<=sz[i];k++){
		for(int l=1;l<=sz[i];l++) if(st[i][l]+(l==k)-(l==j)) pq.push(st[i][l]+(l==k)-(l==j));
		for(int l=1;l<=sz[i];l++){
			if(pq.empty()) break;
			s[l]=pq.top();
			pq.pop();
		}
		for(int l=1;l<=ct;l++){
			for(int o=1;o<=sz[l];o++){
				if(st[l][o]!=s[o]) break;
				if(o==sz[l]) a[0][i][l]=(a[0][i][l]+QP(n*n,mod-2)*st[i][j]*st[i][k])%mod;
			}
		}
	}
	p[1][1]=1;
	for(int i=0;i<=60;i++){
		if(k&(1ll<<i)) MUL(1,ct,ct,p,a[i],p);
		MUL(ct,ct,ct,a[i],a[i],a[i+1]);
	}
	for(int i=1;i<=ct;i++) if(sz[i]>=m) ans=(ans+p[1][i])%mod;
	cout<<ans;
	return 0;
}

T3 link $\color{#00E0E0}(4.50)$

是谁在场上写了树链剖分并反复卡常无果我不说。

我唐完了，赛时下面这么简便的方法没想到，反倒写了一堆假做法，喜提 $31$ 分。

这 $10^6$ 的数据范围显然不是给 $O\left(n\log(n)^2\right)$ 的东西乱草的。
注意到操作完后再查询，所以可以离线。
如果反转顺序操作，那么一条边被染色后就不该再被染一次。
于是可以让操作的A和B不断跳至其父亲直到跳到二者重合（此时A,B均在刚开始A,B的LCA）。
这里我们让深度大的先跳，免得跳过头。
但是如果每次都暴力跳父亲，那肯定T到飞起。
假如知道某个点只经过有色边能到达的最远祖先，不就可以限制跳祖先的次数在一个合理范围内了吗？
发现上述信息可以用并查集维护，当将一条边染色时将其直接相连的两个节点合并即可，
注意是后代向祖先合并。
你可能想问，跳过LCA了怎么办？
没事，大不了A和B在LCA的某个祖先会合，由于跳过的都是有色边，所以不影响正确性。

时间复杂度为并查集复杂度，这里认为是 $O(n\log(n))$ ，反正够快。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000007;
int n,m,x[N],y[N],a[N],b[N],d[N],u[N],z[N],f[N],ans[N];
vector<int>v[N];
vector<int>w[N];
int F(int p){
	if(f[p]==p) return p;
	f[p]=F(f[p]);
	return f[p];
}
void DFS(int p,int fa){
	d[p]=d[fa]+1;
	for(int i=0;i<v[p].size();i++){
		if(v[p][i]==fa) continue;
		u[v[p][i]]=p;
		z[v[p][i]]=w[p][i];
		DFS(v[p][i],p);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<n;i++){
		cin>>x[i]>>y[i];
		v[x[i]].push_back(y[i]);
		v[y[i]].push_back(x[i]);
		w[x[i]].push_back(i);
		w[y[i]].push_back(i);
	}
	DFS(1,0);
	for(int i=1;i<=m;i++){
		cin>>a[i]>>b[i];
	}
	for(int i=m;i>=1;i--){
		a[i]=F(a[i]);
		b[i]=F(b[i]);
		while(a[i]!=b[i]){
			if(d[a[i]]>d[b[i]]){
				f[a[i]]=F(u[a[i]]);
				ans[z[a[i]]]=i;
				a[i]=F(a[i]);
			}
			else{
				f[b[i]]=F(u[b[i]]);
				ans[z[b[i]]]=i;
				b[i]=F(b[i]);
			}
		}
	}
	for(int i=1;i<n;i++) cout<<ans[i]<<' ';
	return 0;
}

T4 link $\color{#00A0FF}(5.25)$

题解说是线段树分治DP。
分治没问题，但懒标记都不用，叫个毛线的“线段树分治”！

注意到 $c \leq 20$ ，可以对 $c$ 的值域做文章。
设 $dp_{\left[l,r\right],i}$ 为 $\left[l,r\right]$ 的人中有 $i$ 人购买彩色画的情况数,
则如果知道 $dp_{\left[l_1,r_1\right],i}\,(0 \leq i \leq r_1-l_1+1)$ 及 $dp_{\left[l_2,r_2\right],j}\,(0 \leq i \leq r_2-l_2+1)$，（注意 $l_2-r_1=1$ ）
则可 $O((r_1-l_1+1)(r_2-l_2+2))$ 地计算 $dp_{[l_1,r_2],k}\,(0 \leq k \leq r_2-l_1+1)$ 。
由于题目只关心 $k \geq c$ 的情况数总和，所以可以像 CSP-J 2025 T4 一样将 $k \geq c$ 的情况压在一起，
使单次转移复杂度降至 $O\left(c^2\right)$ 。
这可以递归进行，基础情况为 $dp_{[i,i],0}=b_i,dp_{[i,i],1}=a_i(1 \leq i \leq n)$ 。

这个分治确实不好想，幸好赛时至少写了暴力。

时间复杂度 $O\left(nc^2+qc^2\log(n)\right)$ 。

代码：（意外地短）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=10007;
const int D=17;
const int N=1<<D;
int n,q,k,p,w,a[N],b[N],dp[2*N][21];
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
		dp[i+N][1]=a[i]%mod;
	}
	for(int i=0;i<n;i++){
		cin>>b[i];
		dp[i+N][0]=b[i]%mod;
	}
	for(int i=n;i<N;i++) dp[i+N][0]=1;
	for(int i=D-1;i>=0;i--){
		for(int j=0;j<(1<<i);j++){
			for(int x=0;x<=k;x++){
				for(int y=0;y<=k;y++){
					w=(1<<i)+j;
					dp[w][min(x+y,k)]=(dp[w][min(x+y,k)]+dp[w*2][x]*dp[w*2+1][y])%mod;
				}
			}
		}
	}
	cin>>q;
	while(q--){
		cin>>p;
		p--;
		cin>>a[p]>>b[p];
		dp[p+N][1]=a[p]%mod;
		dp[p+N][0]=b[p]%mod;
		for(int i=1;i<=D;i++){
			w=(p+N)>>i;
			for(int j=0;j<=k;j++) dp[w][j]=0;
			for(int x=0;x<=k;x++){
				for(int y=0;y<=k;y++){
					dp[w][min(x+y,k)]=(dp[w][min(x+y,k)]+dp[w*2][x]*dp[w*2+1][y])%mod;
				}
			}
		}
		cout<<dp[1][k]<<endl;
	}
    return 0;
}

总结与反思

看来这个部分真的挺有用，没有再在T1想半天的假贪心。

今天从比赛角度发挥还行，没有大失误。

学到 $2$ 个新 trick。

发现自己得学多点新板子了，不然初三都干不过，可以原地 AFO 了。

9.21 %你赛

9.21 %你赛

比赛数据

T1 link $\color{#00E0A0}(4.00)$

T2 link $\color{#00E0C0}(4.25)$

T3 link $\color{#00E0E0}(4.50)$

T4 link $\color{#00A0FF}(5.25)$

总结与反思

状态

开发

支持

关于

9.21 %你赛

9.21 %你赛

比赛数据

T1 link (4.00)\color{#00E0A0}(4.00)(4.00)

T2 link (4.25)\color{#00E0C0}(4.25)(4.25)

T3 link (4.50)\color{#00E0E0}(4.50)(4.50)

T4 link (5.25)\color{#00A0FF}(5.25)(5.25)

总结与反思

状态

开发

支持

关于

还没有账户？

登录

T1 link $\color{#00E0A0}(4.00)$

T2 link $\color{#00E0C0}(4.25)$

T3 link $\color{#00E0E0}(4.50)$

T4 link $\color{#00A0FF}(5.25)$