【比賽記錄】2025 暑假集訓模擬賽合集Ⅱ

塊長為 $5$。

2025CSP-S模擬賽35

A	B	C	D	Sum	Rank
100	40	40	-	180	3/19

A. 114514

分別考慮 $b$ 的每一位可以填什么。因為 $a$ 是字典序最小的，所以對于每一位 $a$ 不能有更小的選擇，于是 $b_i\le a_i$ 且要求 $[b_i,a_i]$ 在 $a_i$ 及之前都出現過。用鏈表可以做到線性復雜度。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=4e6+5,mod=1e9+7;
int n,a[maxn],pre[maxn],nxt[maxn];
int main(){
	freopen("trans.in","r",stdin);
	freopen("trans.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=0;i<=4e6;i++){
		nxt[i]=i+1,pre[i+1]=i;
	}
	int ans=1;
	for(int i=1;i<=n;i++){
		ans=ans*1ll*(a[i]-pre[a[i]])%mod;
		nxt[pre[a[i]]]=nxt[a[i]];
		pre[nxt[a[i]]]=pre[a[i]];
	}
	cout<<ans;
	return 0;
}
}
int main(){return asbt::main();}

B. 沉默樂團

容易發現，我們只需判斷不交的前后綴即可。考慮前綴和后綴都是嚴格單增的，于是考慮將它們歸并起來，考察臨項是否相等。考慮 DP，設 $f_{i,j,k}$ 表示考慮到了 $i$ 的前綴，$j$ 的后綴，后綴 $-$ 前綴 $=k$ 的方案數，于是有轉移：

\[f_{i,j,k}\to f_{i+1,j,k-x}\quad x\in[l_{i+1},r_{i+1}]\land k>0\\ f_{i,j,k}\to f_{i,j-1,k+x}\quad x\in[l_{j-1},r_{j-1}]\land k\le0 \]

注意 $k\ne0$，初始值 $f_{0,n+1,0}=1$。答案即為 $\sum_{i=0}^{n}f_{i,i+1,k}$。差分優化，時間復雜度 $O(n^2m)$。

Code

#include<bits/stdc++.h>
#define il inline
using namespace std;
namespace asbt{
const int V=2e3+5,mod=1e9+7;
il int pls(int x,int y){
	return x+y<mod?x+y:x+y-mod;
}
il int sub(int x,int y){
	return x<y?x-y+mod:x-y;
}
il void add(int &x,int y){
	x=pls(x,y);
}
il void mns(int &x,int y){
	x=sub(x,y);
}
int n,ll[55],rr[55],f[55][55][V<<1];
il void upd(int *f,int l,int r,int v){
	add(f[l+V],v),mns(f[r+V+1],v);
}
int main(){
	freopen("orchestra.in","r",stdin);
	freopen("orchestra.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ll[i]>>rr[i];
	}
	upd(f[0][n+1],0,0,1);
	for(int len=n+2;len>=2;len--){
		for(int i=0,j=len-1;j<=n+1;i++,j++){
			for(int k=-2000;k<=2000;k++){
				add(f[i][j][k+V],f[i][j][k+V-1]);
				if(k>0){
					int l=k-rr[i+1],r=k-ll[i+1];
					if(l>0||r<0){
						upd(f[i+1][j],l,r,f[i][j][k+V]);
					}
					else{
						upd(f[i+1][j],l,-1,f[i][j][k+V]);
						upd(f[i+1][j],1,r,f[i][j][k+V]);
					}
				}
				else{
					int l=k+ll[j-1],r=k+rr[j-1];
					if(l>0||r<0){
						upd(f[i][j-1],l,r,f[i][j][k+V]);
					}
					else{
						upd(f[i][j-1],l,-1,f[i][j][k+V]);
						upd(f[i][j-1],1,r,f[i][j][k+V]);
					}
				}
			}
		}
	}
	int ans=0;
	for(int i=0;i<=n;i++){
		for(int j=-2000;j<=2000;j++){
			add(ans,f[i][i+1][j+V]);
		}
	}
	cout<<ans;
	return 0;
}
}
int main(){return asbt::main();}

C. 深黯「軍團」

考慮將逆序對拆成每一位的貢獻，即每一位計算它后面有多少 $<a_i$。打個表出來長這樣：

打表

1 2 3 4 |0 0 0 0
1 2 4 3 |0 0 1 0
1 3 2 4 |0 1 0 0
1 3 4 2 |0 1 1 0
1 4 2 3 |0 2 0 0
1 4 3 2 |0 2 1 0
2 1 3 4 |1 0 0 0
2 1 4 3 |1 0 1 0
2 3 1 4 |1 1 0 0
2 3 4 1 |1 1 1 0
2 4 1 3 |1 2 0 0
2 4 3 1 |1 2 1 0
3 1 2 4 |2 0 0 0
3 1 4 2 |2 0 1 0
3 2 1 4 |2 1 0 0
3 2 4 1 |2 1 1 0
3 4 1 2 |2 2 0 0
3 4 2 1 |2 2 1 0
4 1 2 3 |3 0 0 0
4 1 3 2 |3 0 1 0
4 2 1 3 |3 1 0 0
4 2 3 1 |3 1 1 0
4 3 1 2 |3 2 0 0
4 3 2 1 |3 2 1 0

發現每一列都在以 $(n-i+1)!$ 為循環周期循環，且第 $i+1$ 列經過一個循環周期后第 $i$ 列答案加一。具體的證明：后 $n-i$ 位全排列一次過程中 $i$ 的答案不會變，而將 $i$ 和后面某個位置交換一定會使逆序對加一。

于是我們考慮對于每一列單獨計算。以下將相同的數組成的段叫一塊。首先是一個散塊，我們可以通過第 $i+1$ 列第一個循環節的開頭位置算出它的長度。然后是幾個整塊，它們和前面那個散塊組成一個散循環節，這些整塊直接暴力枚舉算出。然后是幾個整循環節，直接等差數列求和即可 $O(1)$ 算出。后面又是一個散循環節，暴力算即可。

考慮時間復雜度，$20!>10^{18}$，于是 $n-i\ge19$ 后沒有整循環節，$n-i\ge20$ 后沒有整塊。所以時間復雜度就是 $O(n\log n)$。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e5+5,inf=2e18;
int n,m,mod,a[maxn],fac[maxn];
struct{
	#define lowbit(x) (x&-x)
	int tr[maxn];
	il void add(int p,int v){
		for(;p<=n;p+=lowbit(p)){
			tr[p]+=v;
		}
	}
	il int query(int p){
		int res=0;
		for(;p;p-=lowbit(p)){
			res+=tr[p];
		}
		return res;
	}
	#undef lowbit
}F;
int main(){
	freopen("army.in","r",stdin);
	freopen("army.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>mod;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	fac[0]=1;
	for(int i=1;i<=19;i++){
		fac[i]=fac[i-1]*i;
//		cout<<fac[i]<<" ";
	}
//	cout<<"\n";
	for(int i=20;i<=n;i++){
		fac[i]=inf;
	}
	int ans=0;
	for(int i=n,lst0=1,chu,len;i;i--){
//		cout<<lst0<<"\n";
		chu=F.query(a[i]);
		if(lst0>m){
			(ans+=m%mod*chu)%=mod;
			goto togo;
		}
		(ans+=(lst0-1)%mod*chu)%=mod;
		if(lst0>1){
			chu++;
		}
		for(;chu<=n-i;chu++){
			if(lst0+fac[n-i]-1>m){
				(ans+=(m-lst0+1)%mod*chu)%=mod;
				lst0=inf;
				goto togo;
			}
			(ans+=fac[n-i]%mod*chu)%=mod;
			lst0+=fac[n-i];
		}
		(ans+=(m-lst0+1)/fac[n-i+1]%mod*(fac[n-i]%mod)%mod*((n-i+1)*(n-i)/2%mod))%=mod;
		len=(m-lst0+1)%fac[n-i+1];
		for(int j=0;;j++){
			if(len<fac[n-i]){
				(ans+=len%mod*j)%=mod;
				break;
			}
			(ans+=fac[n-i]%mod*j)%=mod;
			len-=fac[n-i];
		}
		togo:;
		F.add(a[i],1);
//		cout<<ans<<"\n";
	}
	cout<<ans;
	return 0;
}
}
signed main(){return asbt::main();}
/*
10 6 998244353
10 6 2 9 8 3 7 1 5 4 
*/

D. 終末螺旋

2025CSP-S模擬賽36

A	B	C	D	Sum	Rank
40	10	20	12	82	21/23

A. 購買飲料

首先判斷 $-1$ 情況：如果能買得起 $a$ 瓶，并且 $b$ 塊錢也能買得起 $a$ 瓶，那么輸出 $-1$。然后我們就不斷地買 $a$ 瓶并換錢直到買不起 $a$ 瓶即可。時間復雜度 $O(T)$。

Code

#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
int T,n,m,a,b;
int main(){
	freopen("buy.in","r",stdin);
	freopen("buy.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m>>a>>b;
		if(n<a*m){
			cout<<n/m<<'\n';
		}
		else if(b>=a*m){
			cout<<-1<<'\n';
		}
		else{
			int t=(n-a*m)/(a*m-b)+1,ans=t*a;
			n-=t*(a*m-b),ans+=n/m;
			cout<<ans<<'\n';
		}
	}
	return 0;
}
}
signed main(){return asbt::main();}

B. 多邊形

首先判斷是否有一種顏色只有一個點，如果有，那么將這個點和其他所有點相連即可。否則，一定有相鄰的三個顏色不同的點，將它們分成一個小三角形，遞歸下去即可。可以發現按照這樣的構造一定有解。需要鏈表和棧。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e6+5;
int n,pre[maxn],nxt[maxn],_1=1,c1,c2,c3;
bool ban[maxn];
string s;
stack<int> stk,R,G,B;
il bool chk(int x){
	char hp[3]={s[pre[x]],s[x],s[nxt[x]]};
	sort(hp,hp+3);
	return hp[0]=='B'&&hp[1]=='G'&&hp[2]=='R';
}
int main(){
//	freopen("B4.in","r",stdin);
	freopen("polygon.in","r",stdin);
	freopen("polygon.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>s;
	s=" "+s;
	for(int i=1;i<=n;i++){
		pre[i]=i==1?n:i-1;
		nxt[i]=i==n?1:i+1;
		if(chk(i)){
			stk.push(i);
//			cout<<i<<'\n';
		}
		switch(s[i]){
		case 'R':{
			R.push(i),c1++;
			break;
		}
		case 'G':{
			G.push(i),c2++;
			break;
		}
		default:{
			B.push(i),c3++;
			break;
		}
	}
	}
	while(n>3){
		if(c1==1){
			while(ban[R.top()]){
				R.pop();
			}
			_1=R.top();
		}
		else if(c2==1){
			while(ban[G.top()]){
				G.pop();
			}
			_1=G.top();
		}
		else if(c3==1){
			while(ban[B.top()]){
				B.pop();
			}
			_1=B.top();
		}
		else{
			goto togo;
		}
		for(int i=nxt[nxt[_1]];;i=nxt[i]){
			cout<<i<<' '<<_1<<'\n';
			if(i==pre[pre[_1]]){
				break;
			}
		}
		break;
		togo:;
		while(stk.size()){
			int x=stk.top();
			stk.pop();
			if(ban[x]||!chk(x)){
				continue;
			}
			cout<<pre[x]<<' '<<nxt[x]<<'\n';
			n--,ban[x]=1;
			switch(s[x]){
				case 'R':{
					c1--;
					break;
				}
				case 'G':{
					c2--;
					break;
				}
				default:{
					c3--;
					break;
				}
			}
			if(x==_1){
				_1=nxt[x];
			}
//			cout<<"a "<<s[x]<<' '<<s[pre[x]]<<' '<<s[nxt[x]]<<'\n';
			nxt[pre[x]]=nxt[x];
			pre[nxt[x]]=pre[x];
			if(chk(pre[x])){
				stk.push(pre[x]);
			}
			if(chk(nxt[x])){
				stk.push(nxt[x]);
			}
			break;
		}
//		cout<<'\n';
//		cout<<n<<' '<<c1<<' '<<c2<<' '<<c3<<'\n';
	}
	return 0;
}
}
int main(){return asbt::main();}

C. 二分圖最大權匹配

原，神秘網絡流。

D. 飛毯

原，神秘構造。

2025CSP-S模擬賽37

A	B	C	D	Sum	Rank
100	-	25	-	125	19/25

A. 新的階乘

我們需要一個線性做法，因此暴力枚舉每個數的每一個質因子是無法接受的，考慮用歐拉篩找出每個數的最小質因子 $\operatorname{mpf}(x)$，將 $x$ 的冪次下放給 $\operatorname{mpf}(x)$ 和 $\frac{x}{\operatorname{mpf}(x)}$ 即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e7+5;
int n,prn,prm[maxn],mpf[maxn];
ll fac[maxn];
bool npr[maxn];
il void euler(int n=1e7){
	for(int i=2;i<=n;i++){
		if(!npr[i]){
			prm[++prn]=i;
			mpf[i]=i;
		}
		for(int j=1;j<=prn&&i*1ll*prm[j]<=n;j++){
			npr[i*prm[j]]=1;
			mpf[i*prm[j]]=prm[j];
			if(i%prm[j]==0){
				break;
			}
		}
	}
}
int main(){
//	freopen("my.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	euler();
	cin>>n;
	for(int i=2;i<=n;i++){
		fac[i]=n-i+1;
	}
	for(int i=n;i>1;i--){
//		cout<<mpf[i]<<" ";
		if(npr[i]){
			fac[mpf[i]]+=fac[i];
			fac[i/mpf[i]]+=fac[i];
		}
	}
	bool flag=0;
	for(int i=1;i<=prn;i++){
		if(fac[prm[i]]){
			if(!flag){
				cout<<"f("<<n<<")=";
				flag=1;
			}
			else{
				cout<<'*';
			}
			cout<<prm[i];
			if(fac[prm[i]]>1){
				cout<<'^'<<fac[prm[i]];
			}
		}
	}
	return 0;
}
}
int main(){return asbt::main();}

B. 博弈樹

首先可以發現如果先手在直徑端點上那么必勝。接下來雙方一定不能走到直徑端點上，否則對方再走到另一個端點就輸了。因此我們可以直接將所有直徑端點刪掉。那么在刪后的這棵樹上，雙方一定還是不能走到直徑端點上，否則另一方走到另一個端點上后自己將不得不走到原樹直徑端點上。那么一層層刪點，如果最后剩下一個點了那么先手必敗，否則必勝。考慮這個條件等價于什么，發現就是如果起始點在直徑中點那么先手必敗，否則先手必勝，dfs 預處理即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,d1,d2,ans,dep[maxn],mxd[maxn],des[maxn];
vector<int> e[maxn];
il void dfs1(int u,int fa){
	mxd[u]=dep[u]=dep[fa]+1,des[u]=u;
	for(int v:e[u]){
		if(v==fa){
			continue;
		}
		dfs1(v,u);
		if(mxd[v]>mxd[u]){
			mxd[u]=mxd[v],des[u]=des[v];
		}
	}
}
il void dfs2(int u,int fa){
	des[dep[u]]=u;
	if(u==d2){
		ans=des[(dep[u]+1)>>1];
	}
	for(int v:e[u]){
		if(v==fa){
			continue;
		}
		dfs2(v,u);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		e[u].pb(v),e[v].pb(u);
	}
	dfs1(1,0),d1=des[1];
	dfs1(d1,0),d2=des[d1];
	if(dep[d2]&1){
		dfs2(d1,0);
	}
	while(m--){
		int u;
		cin>>u;
		cout<<(u==ans?"Bob":"Alice")<<'\n';
	}
	return 0;
}
}
int main(){return asbt::main();}

C. 劃分

發現我們的劃分一定是一段長為 $n-k+1$ 的和 $k-1$ 段長為 $1$ 的。考慮每個數對應的位權，那么我們一定是要找到最大的一段 $n-k+1$，哈希加二分求出 LCP 即可比較大小。考慮方案數，發現因為 $1$ 的數量是固定的，所以最后一位是 $0$ 還是 $1$ 都是無所謂的，所以找到有多少個長為 $n-k+1$ 的段與最優段的前 $n-k$ 位相同即可。注意 $n=k$ 時方案數為 $1$。但是還有一個問題，如果這個最優段有前導零，那么方案數是會變多的，換句話說如果前 $k-1$ 位都是 $0$ 那么一定是在前導零中隨便分 $\ge k-1$ 次，組合數計算即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define ull unsigned ll
using namespace std;
namespace asbt{
const int maxn=2e6+5,mod=998244353;
const ull bas1=131;
const ll bas2=233,mod2=1e9+7;
int n,m,fac[maxn],inv[maxn];
ull ha1[maxn],pw1[maxn];
ll ha2[maxn],pw2[maxn];
string s;
il int qpow(int x,int y=mod-2){
	int res=1;
	while(y){
		if(y&1){
			res=res*1ll*x%mod;
		}
		x=x*1ll*x%mod,y>>=1;
	}
	return res;
}
il int C(int x,int y){
	if(x<y||y<0){
		return 0;
	}
	return fac[x]*1ll*inv[y]%mod*inv[x-y]%mod;
}
il void chk(){
	if(n==m){
		int ans=0;
		for(int i=1;i<=n;i++){
			ans+=s[i]^48;
		}
		cout<<ans<<' '<<1;
		exit(0);
	}
	for(int i=1;i<m;i++){
		if(s[i]=='1'){
			return ;
		}
	}
	int ans=0,pos=n;
	for(int i=1;i<=n;i++){
		ans=(ans*2+(s[i]^48))%mod;
		if(pos==n&&s[i]=='1'){
			pos=i;
		}
	}
	fac[0]=1;
	for(int i=1;i<=n;i++){
		fac[i]=fac[i-1]*1ll*i%mod;
	}
	inv[n]=qpow(fac[n]);
	for(int i=n;i;i--){
		inv[i-1]=inv[i]*1ll*i%mod;
	}
	int res=0;
	for(int i=m-1;i<pos;i++){
		(res+=C(pos-1,i))%=mod;
	}
	cout<<ans<<' '<<res;
	exit(0);
}
il ull Ha1(int l,int r){
	return ha1[r]-ha1[l-1]*pw1[r-l+1];
}
il ll Ha2(int l,int r){
	return (ha2[r]-ha2[l-1]*pw2[r-l+1]%mod2+mod2)%mod2;
}
il bool Eq(int l1,int r1,int l2,int r2){
	return Ha1(l1,r1)==Ha1(l2,r2)&&Ha2(l1,r1)==Ha2(l2,r2);
}
il int lcp(int p,int q){
	int l=0,r=n-m+1;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(Eq(p,p+mid-1,q,q+mid-1)){
			l=mid;
		}
		else{
			r=mid-1;
		}
	}
	return l;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>s;
	s=" "+s;
	chk();
	pw1[0]=pw2[0]=1;
	for(int i=1;i<=n;i++){
		pw1[i]=pw1[i-1]*bas1;
		pw2[i]=pw2[i-1]*bas2%mod2;
		ha1[i]=ha1[i-1]*bas1+s[i];
		ha2[i]=(ha2[i-1]*bas2+s[i])%mod2;
	}
	int p=1;
	for(int i=2;i<=m;i++){
		int t=lcp(p,i);
		if(t<n-m+1&&s[p+t]<s[i+t]){
			p=i;
		}
	}
	int ans=0,cnt=0;
	for(int i=p,j=1;j<=n-m+1;i++,j++){
		ans=(ans*2+(s[i]^48))%mod;
	}
	for(int i=1;i<p;i++){
		ans+=s[i]^48;
	}
	for(int i=p+n-m+1;i<=n;i++){
		ans+=s[i]^48;
	}
	ans%=mod;
	for(int i=1;i<=m;i++){
		if(Eq(i,i+n-m-1,p,p+n-m-1)){
			cnt++;
		}
	}
	cout<<ans<<' '<<cnt;
	return 0;
}
}
int main(){return asbt::main();}

D. 燈籠

原

考慮 DP。設 $f_{l,r}$ 表示可以到達的高度區間為 $[l,r]$ 的最小花費，每次枚舉出發點 $i$ 進行一次 DP，時間復雜度 $O(nk^3)$。

考慮去掉枚舉 $i$ 的操作，考慮轉換定義與轉移順序（轉置）。設 $f_{i,l,r}$ 表示當前在 $i$，高度區間為 $[l,r]$，將 $[1,n]$ 走遍的最小花費，考慮優化狀態，容易發現 $[l,r]$ 其實是 $[a_u,b_v]$，這樣就可以不用記錄 $i$，于是設 $f_{u,v}$ 表示合法海拔區間為 $[a_u,b_v]$，且區間經過了 $u$ 和 $v$，將 $[1,n]$ 走遍的最小花費，于是有轉移：

$f_{u,v}\leftarrow f_{u,p}+c_p$
$f_{u,v}\leftarrow f_{p,v}+c_p$
$f_{u,v}\leftarrow f_{p,p}+c_p$

此時的時間復雜度為 $O(nk^2)$，考慮優化轉移。我們顯然要按照 $a$ 升序的順序枚舉 $u$，$b$ 降序的順序枚舉 $v$，那么對于 $v'<v$，如果 $f_{u,p}$ 不能向 $f_{u,v}$ 轉移，那么一定不能向 $f_{u,v'}$ 轉移。于是用小根堆對每個 $u$ 維護合法的 $f_{u,p}+c_p$ 即可。對于第三個轉移，將其分步成 $f_{p,p}\to f_{u,p}/f_{p,v}\to f_{u,v}$，特判即可。時間復雜度 $O(k^2\log k)$。

Code

#include<bits/stdc++.h>
#define il inline
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;
namespace asbt{
const int maxn=2e3+5,inf=0x7f7f7f7f;
int n,m,h[maxn],p[maxn],c[maxn],a[maxn],b[maxn];
int I[maxn],J[maxn],ll[maxn][2],rr[maxn][2],f[maxn][maxn];
priority_queue<pii> q1[maxn],q2[maxn];
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=1;i<=m;i++){
		cin>>p[i]>>c[i]>>a[i]>>b[i];
		I[i]=J[i]=i;
	}
	sort(I+1,I+m+1,[](int x,int y){return a[x]<a[y];});
	sort(J+1,J+m+1,[](int x,int y){return b[x]>b[y];});
	for(int i=1;i<=m;i++){
		ll[i][0]=ll[i][1]=rr[i][0]=rr[i][1]=p[i];
		while(ll[i][0]>1&&h[ll[i][0]-1]>=a[i]){
			ll[i][0]--;
		}
		while(rr[i][0]<n&&h[rr[i][0]+1]>=a[i]){
			rr[i][0]++;
		}
		while(ll[i][1]>1&&h[ll[i][1]-1]<=b[i]){
			ll[i][1]--;
		}
		while(rr[i][1]<n&&h[rr[i][1]+1]<=b[i]){
			rr[i][1]++;
		}
	}
	memset(f,0x7f,sizeof(f));
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			int x=I[i],y=J[j];
			if(p[x]<ll[y][1]||p[x]>rr[y][1]||p[y]<ll[x][0]||p[y]>rr[x][0]){
				continue;
			}
			if(a[y]<a[x]&&b[x]>b[y]){
				continue;
			}
			int l=max(ll[x][0],ll[y][1]),r=min(rr[x][0],rr[y][1]);
			if(l==1&&r==n){
				f[x][y]=0;
			}
			else if(a[y]<a[x]){
				f[x][y]=f[y][y];
			}
			else if(b[x]>b[y]){
				f[x][y]=f[x][x];
			}
			else{
				while(q1[x].size()){
					int t=q1[x].top().sec;
					if(p[t]<l||p[t]>r||b[t]<a[x]||a[t]>b[y]){
						q1[x].pop();
					}
					else{
						break;
					}
				}
				if(q1[x].size()){
					f[x][y]=min(f[x][y],-q1[x].top().fir);
				}
				while(q2[y].size()){
					int t=q2[y].top().sec;
					if(p[t]<l||p[t]>r||b[t]<a[x]||a[t]>b[y]){
						q2[y].pop();
					}
					else{
						break;
					}
				}
				if(q2[y].size()){
					f[x][y]=min(f[x][y],-q2[y].top().fir);
				}
			}
			if(f[x][y]<inf){
				q1[x].push(mp(-f[x][y]-c[y],y));
				q2[y].push(mp(-f[x][y]-c[x],x));
			}
		}
	}
	for(int i=1;i<=m;i++){
		if(h[p[i]]<a[i]||h[p[i]]>b[i]||f[i][i]>=inf){
			cout<<-1<<'\n';
		}
		else{
			cout<<f[i][i]+c[i]<<'\n';
		}
	}
	return 0;
}
}
int main(){return asbt::main();}

2025CSP-S模擬賽38

A	B	C	D	Sum	Rank
80	20	10	-	110	9/21

A. 黑暗料理

~~原（bushi~~

原

首先可以發現所有的 $1$ 只能留一個。然后我們考慮將和為質數的 $x$ 和 $y$ 連邊，此時 $x+y$ 一定為奇數，也就是 $x$ 和 $y$ 奇偶性不同，于是沒有奇環。此時我們要求最大獨立集，跑匈牙利即可。需要 Miller-Rabin。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int prm[]={2,3,5,7,11};
int T,n,m,a[755],mch[755];
bool vis[755];
vector<int> e[755];
il int qpow(int x,int y,int p){
	int res=1;
	while(y){
		if(y&1){
			res=res*1ll*x%p;
		}
		x=x*1ll*x%p,y>>=1;
	}
	return res;
}
il bool mlrb(int x){
	if(x<=11){
		for(int i:prm){
			if(x==i){
				return 1;
			}
		}
		return 0;
	}
	int t=x-1,k=0;
	while(t%2==0){
		t>>=1,k++;
	}
	for(int i:prm){
		int a=qpow(i,t,x);
		for(int j=1;j<=k;j++){
			int b=a*1ll*a%x;
			if(b==1&&a!=1&&a!=x-1){
				return 0;
			}
			a=b;
		}
		if(a!=1){
			return 0;
		}
	}
	return 1;
}
il bool dfs(int u){
	for(int v:e[u]){
		if(vis[v]){
			continue;
		}
		vis[v]=1;
		if(mch[v]==-1||dfs(mch[v])){
			mch[v]=u;
			return 1;
		}
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n,m=0;
		bool flag=0;
		for(int i=1,x;i<=n;i++){
			cin>>x;
			if(x>1){
				a[++m]=x;
			}
			else if(!flag){
				flag=1,a[++m]=x;
			}
		}
		for(int i=1;i<=m;i++){
			for(int j=i+1;j<=m;j++){
				if(mlrb(a[i]+a[j])){
					e[i].pb(j),e[j].pb(i);
//					cout<<i<<' '<<j<<'\n';
				}
			}
		}
		int ans=0;
		for(int i=1;i<=m;i++){
			mch[i]=-1;
		}
		for(int i=1;i<=m;i++){
			for(int j=1;j<=m;j++){
				vis[j]=0;
			}
			ans+=dfs(i);
		}
		cout<<m-ans/2<<'\n';
		for(int i=1;i<=m;i++){
			e[i].clear();
		}
	}
	return 0;
}
}
int main(){return asbt::main();}

B. 爆炸

原

如果一個炸彈是被橫著引爆的，那么貪心地想，它一定要豎著炸。于是對每一行和每一列設點，對于一個炸彈 $(x,y)$，將第 $x$ 行和第 $y$ 列連邊，于是獲得了若干連通塊。考慮如果連通塊內有環，那么隨便引爆環上一個點，一定是能把這個連通塊炸完的，直接計算答案即可。如果沒有環，那么這一定是一棵樹，我們要選擇一條邊，只保留它的一邊，另一邊舍去。顯然舍去一個葉子節點是最優的，暴力枚舉葉子即可。時間復雜度 $O(nm)$。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=6e3+5;
int n,m,a,b,cnt,lfn,ans,fa[maxn],f[maxn][maxn],hp[maxn],lf[maxn];
bool tag[maxn],vis[maxn];
string s[maxn];
vector<int> e[maxn];
il int find(int x){
	return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void dfs1(int u){
	if(vis[u]){
		return;
	}
	hp[++cnt]=u;
	vis[u]=1;
	if(u<=n){
		for(int i=1;i<=m;i++){
			if(s[u][i]=='k'&&++f[u][i]==1){
				ans++;
			}
		}
	}
	else{
		for(int i=1;i<=n;i++){
			if(s[i][u-n]=='k'&&++f[i][u-n]==1){
				ans++;
			}
		}
	}
	for(int v:e[u]){
		dfs1(v);
	}
}
il void dfs2(int u,int fa){
	hp[++cnt]=u;
	if(e[u].size()==1){
		lf[++lfn]=u;
	}
	if(u<=n){
		for(int i=1;i<=m;i++){
			if(s[u][i]=='k'&&++f[u][i]==1){
				ans++;
			}
		}
	}
	else{
		for(int i=1;i<=n;i++){
			if(s[i][u-n]=='k'&&++f[i][u-n]==1){
				ans++;
			}
		}
	}
	for(int v:e[u]){
		if(v==fa){
			continue;
		}
		dfs2(v,u);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>a>>b;
	for(int i=1;i<=n+m;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>s[i];
		s[i]=" "+s[i];
		for(int j=1;j<=m;j++){
			if(s[i][j]=='b'){
//				cout<<i<<' '<<n+j<<'\n';
				e[i].pb(n+j),e[n+j].pb(i);
				int u=find(i),v=find(n+j);
				if(u==v){
					tag[u]=1;
				}
				else{
					fa[u]=v,tag[v]|=tag[u];
				}
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		cout<<s[i]<<'\n';
//	}
	int Ans=0;
	for(int i=1;i<=n+m;i++){
		if(find(i)==i&&e[i].size()){
//			cout<<i<<'\n';
			if(tag[i]){
				cnt=ans=0;
				dfs1(i);
				Ans=max(Ans,ans);
			}
			else{
				cnt=lfn=ans=0;
				dfs2(i,0);
				for(int j=1;j<=lfn;j++){
					int u=lf[j];
					if(u<=n){
						for(int i=1;i<=m;i++){
							if(s[u][i]=='k'&&f[u][i]--==1){
								ans--;
							}
						}
					}
					else{
						for(int i=1;i<=n;i++){
							if(s[i][u-n]=='k'&&f[i][u-n]--==1){
								ans--;
							}
						}
					}
					Ans=max(Ans,ans);
					if(u<=n){
						for(int i=1;i<=m;i++){
							if(s[u][i]=='k'&&++f[u][i]==1){
								ans++;
							}
						}
					}
					else{
						for(int i=1;i<=n;i++){
							if(s[i][u-n]=='k'&&++f[i][u-n]==1){
								ans++;
							}
						}
					}
				}
			}
			for(int j=1;j<=cnt;j++){
				int u=hp[j];
				if(u<=n){
					for(int i=1;i<=m;i++){
						f[u][i]=0;
					}
				}
				else{
					for(int i=1;i<=n;i++){
						f[i][u-n]=0;
					}
				}
			}
		}
	}
	cout<<Ans;
	return 0;
}
}
int main(){return asbt::main();}

C. 游戲

發現每個棋子是獨立的，考慮算出 $sg_{i,j}$ 表示棋子初始在 $(i,j)$ 時的 $SG$ 值，將所有棋子的 $SG$ 值異或起來就是總的 $SG$ 值。

發現 $sg_{i+1,j}$ 不受 $sg_{i,j}$ 影響，于是倒序枚舉每一行。然后對每一行進行分類討論。記行號為 $t$。

本行中有障礙

這一行被這些障礙分成了若干段。于是對于一個位置 $(t,i)$，它只有三種狀態：

從 $(t-1,i)$ 下來，可以往左、往右或往下走。
從 $(t,i-1)$ 過來，可以往右或往下走。
從 $(t,i+1)$ 過來，可以往左或往下走。

于是我們考慮預處理出 $f_{0,i}$ 表示當前只可以往左或往下走時 $(t,i)$ 的 $SG$ 值，$f_{1,i}$ 表示當前可以往右或往下走時 $(t,i)$ 的 $SG$ 值，于是 $sg_{t,i}=\operatorname{mex}(f_{0,i-1},f_{1,i+1},sg_{t+1,i})$。

本行中沒有障礙

考慮棋子初始在 $(t,i)$，如果第一步先往左走到了 $(t,i-1)$，那么就不能再往右走了，于是 $(t,i-1)$ 的 $SG$ 值需要 $(t,i-2)$ 的 $SG$ 值，進一步需要 $(t,i-3)$ 的 $SG$ 值……以此類推，我們最終需要的是 $(t,i+1)$ 的 $SG$ 值，此時只能往下走了，是顯然的。但是這樣我們單次求的時間復雜度是 $O(m)$ 的，考慮優化。考慮從 $i-1$ 一路走到 $i+1$ 的過程，大概是這個樣子：

而 $sg_{i,j}$ 的取值范圍是 $[0,3]$，于是我們可以預處理出圖中打勾的兩個部分。

具體地，定義數組 $g_{0/1/2/3,j,i}$：

$g_{0,j,i}$ 表示 $(t,1)$ 的 $SG$ 值為 $j$，棋子從 $i$ 移動到 $1$，$(t,i)$ 的 $SG$ 值。
$g_{1,j,i}$ 表示 $(t,m)$ 的 $SG$ 值為 $j$，棋子從 $i$ 移動到 $m$，$(t,i)$ 的 $SG$ 值。
$g_{2,j,i}$ 表示 $(t,i)$ 的 $SG$ 值為 $j$，棋子從 $1$ 移動到 $i$，$(t,1)$ 的 $SG$ 值。
$g_{3,j,i}$ 表示 $(t,i)$ 的 $SG$ 值為 $j$，棋子從 $m$ 移動到 $i$，$(t,m)$ 的 $SG$ 值。

于是就可以對每個點進行 $O(1)$ 計算了。總時間復雜度 $O(\sum nm)$。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e3+5;
int T,n,m,sg[maxn][maxn],f[2][maxn],g[4][4][maxn];
string s[maxn];
il int mex(int a=-1,int b=-1,int c=-1){
	for(int i=0;;i++){
		if(i!=a&&i!=b&&i!=c){
			return i;
		}
	}
}
il void solve1(int t){
	#define gt(i) ((i)>m?(i)-m:(i))
	memset(f,-1,sizeof(f));
	int _1=1;
	while(s[t][_1]!='#'){
		_1++;
	}
	for(int l=_1,r;l<m+_1;l=r){
		r=l+1;
		while(s[t][r]!='#'){
			r++;
		}
		if(r==l+1){
			continue;
		}
		f[0][l+1]=mex(sg[t+1][gt(l+1)]);
		for(int i=l+2;i<r;i++){
			f[0][i]=mex(f[0][i-1],sg[t+1][gt(i)]);
		}
		f[1][r-1]=mex(sg[t+1][gt(r-1)]);
		for(int i=r-2;i>l;i--){
			f[1][i]=mex(f[1][i+1],sg[t+1][gt(i)]);
		}
		for(int i=l+1;i<r;i++){
			sg[t][gt(i)]=mex(f[0][i-1],f[1][i+1],sg[t+1][gt(i)]);
		}
	}
	#undef gt
}
il void solve2(int t){
	if(m==1){
		sg[t][1]=mex(sg[t+1][1]);
		return ;
	}
	for(int i:{0,1,2,3}){
		g[0][i][1]=g[1][i][m]=g[2][i][1]=g[3][i][m]=i;
	}
	for(int i=2;i<=m;i++){
		for(int j:{0,1,2,3}){
			g[0][j][i]=mex(g[0][j][i-1],sg[t+1][i]);
		}
	}
	for(int i=m-1;i;i--){
		for(int j:{0,1,2,3}){
			g[1][j][i]=mex(g[1][j][i+1],sg[t+1][i]);
		}
	}
	for(int i=2;i<=m;i++){
		for(int j:{0,1,2,3}){
			g[2][j][i]=g[2][mex(j,sg[t+1][i-1])][i-1];
		}
	}
	for(int i=m-1;i;i--){
		for(int j:{0,1,2,3}){
			g[3][j][i]=g[3][mex(j,sg[t+1][i+1])][i+1];
		}
	}
	for(int i=1;i<=m;i++){
		int l,r;
		if(i<m){
			int tmp=g[3][mex(sg[t+1][i+1])][i+1];
			if(i==1){
				l=tmp;
			}
			else{
				l=g[0][mex(tmp,sg[t+1][1])][i-1];
			}
		}
		else{
			l=g[0][mex(sg[t+1][1])][i-1];
		}
		if(i>1){
			int tmp=g[2][mex(sg[t+1][i-1])][i-1];
			if(i==m){
				r=tmp;
			}
			else{
				r=g[1][mex(tmp,sg[t+1][m])][i+1];
			}
		}
		else{
			r=g[1][mex(sg[t+1][m])][i+1];
		}
		sg[t][i]=mex(l,r,sg[t+1][i]);
	}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>s[i];
			s[i]=" "+s[i]+s[i];
		}
		for(int i=1;i<=n+1;i++){
			for(int j=1;j<=m;j++){
				sg[i][j]=-1;
			}
		}
		for(int i=n;i;i--){
			for(int j=1;j<=m;j++){
				if(s[i][j]=='#'){
					solve1(i);
					goto togo;
				}
			}
			solve2(i);
			togo:;
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(s[i][j]=='B'){
					ans^=sg[i][j];
				}
			}
		}
		cout<<(ans?'A':'B')<<'\n';
	}
	return 0;
}
}
int main(){return asbt::main();}

D. 公司

2025CSP-S模擬賽39

A	B	C	D	Sum	Rank
100	0	30	20	150	10/19

A. poohfrog

直接 bfs 即可，時間復雜度 $O(nmk)$。

Code

#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=6e6+5,inf=1e9;
const int dx[]={-1,1,0,0,0,0};
const int dy[]={0,0,-1,1,0,0};
const int dz[]={0,0,0,0,-1,1};
int n,m,kk,xx,yy,zz,hd=1,tl=0,dep[185][185][185];
bool vis[185][185][185];
char s[185][185][185];
struct node{
	int x,y,z;
	node(int x=0,int y=0,int z=0):x(x),y(y),z(z){}
}q[maxn];
int main(){
//	freopen("ex_poohfrog.in","r",stdin);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>kk>>xx>>yy>>zz;
	for(int k=1;k<=kk;k++){
		for(int i=1;i<=n;i++){
			cin>>s[k][i]+1;
		}
	}
	memset(dep,0x3f,sizeof(dep));
	vis[xx][yy][zz]=1,dep[xx][yy][zz]=0;
	q[++tl]=node(xx,yy,zz);
	while(hd<=tl){
		node u=q[hd++];
		int x=u.x,y=u.y,z=u.z;
//		cout<<x<<' '<<y<<' '<<z<<'\n';
		for(int i=0;i<=5;i++){
			int nx=x+dx[i],ny=y+dy[i],nz=z+dz[i];
			if(nx&&nx<=n&&ny&&ny<=m&&nz&&nz<=kk&&!vis[nx][ny][nz]&&s[nz][nx][ny]=='.'){
				vis[nx][ny][nz]=1,dep[nx][ny][nz]=dep[x][y][z]+1;
				q[++tl]=node(nx,ny,nz);
			}
		}
	}
	int ans=inf;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ans=min(ans,dep[i][j][kk]);
		}
	}
	cout<<ans*2;
//	cerr<<'\n'<<clock()*1.0;
	return 0;
}
}
int main(){return asbt::main();}

B. 數學題

C. 貨物運輸

D. 士兵游戲

posted @ 2025-08-15 17:07 zhangxy__hp 閱讀(55) 評論(0) 收藏舉報

刷新頁面返回頂部

zhangxyhp

【比賽記錄】2025 暑假集訓模擬賽合集Ⅱ

2025CSP-S模擬賽35

A. 114514

B. 沉默樂團

C. 深黯「軍團」

D. 終末螺旋

2025CSP-S模擬賽36

A. 購買飲料

B. 多邊形

C. 二分圖最大權匹配

D. 飛毯

2025CSP-S模擬賽37

A. 新的階乘

B. 博弈樹

C. 劃分

D. 燈籠

2025CSP-S模擬賽38

A. 黑暗料理

B. 爆炸

C. 游戲

本行中有障礙

本行中沒有障礙

D. 公司

2025CSP-S模擬賽39

A. poohfrog

B. 數學題

C. 貨物運輸

D. 士兵游戲