Blog Detail

C20250053's blog
20260320杭电春季赛总结
C20250053 LV 8 @ 2026-3-21 8:50:37

闲话：做了不到 3h 就 AK 了，感觉没有什么难题，所以简略写写。

A

首先取石子游戏经典结论，当石头数是 $k+1$ 的倍数的时候后手胜，否则先手胜。

发现先手胜的情况很多，所以考虑用总方案减去后手胜的。

观察式子 $f(i,j,k)=a_i\cdot k^{a_i+a_j}+a_j$ ，在模 $k+1$ 意义下是 $a_i\cdot (-1)^{a_i+a_j}+a_j$ 。

看到 $-1$ 于是讨论 $a_i+a_j$ 的奇偶性：

$a_i+a_j$ 为奇数，那么 $-a_i+a_j\equiv 0\pmod {k+1}$ ，因为 $a_i,a_j\le k$ ，所以 $a_i=a_j$ ，此时 $a_i+a_j$ 为偶数，矛盾。
$a_i+a_j$ 为偶数，那么 $a_i+a_j\equiv 0\pmod {k+1}$ ，因为 $a_i,a_j\le {k}$ ，所以 $a_i+a_j=k+1$ ，此时要求 $k$ 是奇数。

因为 $k=\max_{x=l}^r a_x$ ，也就是区间最大值，于是我们枚举 $k=a_p$ ，然后用单调栈预处理 $k$ 作为最大值的区间 $[L_i,R_i]$ ，在 $[L_i,p)$ 和 $(p,R_i]$ 中挑小的一半区间枚举 $i$ 然后查询另一半区间值为 $k+1-a_i$ 的数的数量即可。

你发现一个数最多只会被枚举到 $\log n$ 次，因为每被枚举到 $1$ 次，所在枚举区间长度至少减半。

时间复杂度 $\mathcal{O}(n\log^2 n)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e5 + 10;
const int inf = 0x3f3f3f3f;

int n,idx=0;
ll ans;
int a[MAXN];
int st[MAXN],top=0;
int L[MAXN],R[MAXN];
vector<int>pos[MAXN];
map<int,int>id;

int Calc(int l,int r,int val){
	if(id.find(val)==id.end()) return 0;
	val=id[val];
	int L=lower_bound(pos[val].begin(),pos[val].end(),l)-pos[val].begin();
	int R=upper_bound(pos[val].begin(),pos[val].end(),r)-pos[val].begin()-1;
	return R-L+1;
}

int main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d",&n),ans=1ll*n*n,idx=0;
		id.clear();
		FL(i,1,n){
			scanf("%d",&a[i]);
			if(!id[a[i]]) id[a[i]]=++idx,pos[idx].clear();
			pos[id[a[i]]].push_back(i);
		}
		top=0;
		st[++top]=0,a[0]=inf;
		FL(i,1,n){
			while(top&&a[st[top]]<a[i]) top--;
			L[i]=st[top]+1;
			st[++top]=i;
		}
		top=0;
		st[++top]=n+1,a[n+1]=inf;
		FR(i,n,1){
			while(top&&a[st[top]]<=a[i]) top--;
			R[i]=st[top]-1;
			st[++top]=i;
		}
		FL(p,1,n){
			if(!(a[p]&1)) continue;
			if(p-L[p]<R[p]-p)
				FL(i,L[p],p-1) ans-=2*Calc(p+1,R[p],a[p]+1-a[i]);
			else
				FL(i,p+1,R[p]) ans-=2*Calc(L[p],p-1,a[p]+1-a[i]);
		}
		printf("%lld\n",ans);
	}
}

B

没有区间和是 $k$ 的倍数等价于每个前缀的和模 $k$ 的余数均不同，于是当 $n\ge k$ 时无解。

当 $n<k$ 时，假设当前枚举到第 $i$ 位，前 $i-1$ 位前缀和为 $sum$ ，因为要求严格递增，那么前 $i$ 位的前缀和至少为 $nw=sum+a_{i-1}+1$ ，找第一个 $\ge nw \bmod k$ 的还没被用过的余数即可，可以用并查集维护做到 $\mathcal{O}(\alpha(n))$ 。

时间复杂度 $\mathcal{O}(n\alpha(n))$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e5 + 10;

int n,K;
ll a[MAXN];
int fa[MAXN];

int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void Del(int r){
	fa[find(r)]=find((r+1)%K);
}

int main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d%d",&n,&K);
		if(n>=K){
			puts("-1");
			continue;
		}
		FL(i,0,K-1) fa[i]=i;
		Del(0);
		ll sum=0;
		a[0]=0;
		FL(i,1,n){
			ll nw=sum+a[i-1]+1,rem=find(nw%K);
			Del(rem);
			nw+=(rem>=nw%K?(rem-nw%K):(K-nw%K+rem));
			a[i]=nw-sum,sum=nw;
		}
		FL(i,1,n) printf("%lld ",a[i]);
		puts("");
	}
}

C

发现 $n$ 的数据范围是 $2000$ ，那不是 $n^2$ 随便做。

设我们从 $S$ 中取出的子串为 $A$ ，从 $T$ 中取出的子串为 $B$ 。我们要使 $A + B$ 成为一个回文串。

我们将 $T$ 进行翻转得到 $R$ ，取出对应子串 $C$ （为什么要翻转因为翻转后就相当于 $A$ 和 $C$ 有一段公共前缀，更好处理）。

讨论 $A,C$ 的长度大小关系：

当 $|A|>|C|$ ，那么要求 $|C|$ 是 $|A|$ 的前缀且 $A$ 剩下的后缀是非空回文串。
当 $|A|<|C|$ ，那么要求 $|A|$ 是 $|C|$ 的前缀且 $C$ 剩下的后缀是非空回文串。
当 $|A|=|C|$ ，那么要求 $A=C$ 。

于是我们枚举 $A$ 在 $S$ 中的起点 $i$ ，枚举 $C$ 在 $R$ 中的起点 $j$ ，假设它们的 $LCP$ 长度为 $L$ ，那么合法选取子串的方案数就是 $S$ 中起点在 $[i+1,i+L]$ 区间的回文串数量加上 $T$ 中起点在 $[j+1,j+L]$ 区间的回文串数量再加上 $L$ （也就是 $L$ 种相等的 $A,C$ ）。

起点在某个位置的子串可以 $\mathcal{O}(n^2)$ 求出，预处理前缀和可以 $\mathcal{O}(1)$ 查询。

$LCP$ 也可以 $\mathcal{O}(n^2)$ 求出，赛时我怕 MLE 把第一维压掉了，实质就是 dp， $lcp_{i,j}=[s_i=t_j](lcp_{i+1,j+1}+1)$ 。

注意最长公共前缀是从后往前转移！！！

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e3 + 10;

int n,m;
ll ans=0;
char S[MAXN],T[MAXN],R[MAXN];
int cntS[MAXN],cntR[MAXN];
int sS[MAXN],sR[MAXN];
int lcp[MAXN];

int main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%s%s",S+1,T+1),n=strlen(S+1),m=strlen(T+1),ans=0;
		FL(i,1,m) R[i]=T[m-i+1];
		FL(i,1,n+1) cntS[i]=0;
		FL(i,1,n){
			int l=i,r=i;
			while(l>=1&&r<=n&&S[l]==S[r]) cntS[l]++,l--,r++;
			l=i,r=i+1;
			while(l>=1&&r<=n&&S[l]==S[r]) cntS[l]++,l--,r++;
		}
		FL(i,1,n+1) sS[i]=sS[i-1]+cntS[i];
		FL(i,1,m+1) cntR[i]=0;
		FL(i,1,m){
			int l=i,r=i;
			while(l>=1&&r<=m&&R[l]==R[r]) cntR[l]++,l--,r++;
			l=i,r=i+1;
			while(l>=1&&r<=m&&R[l]==R[r]) cntR[l]++,l--,r++; 
		}
		FL(i,1,m+1) sR[i]=sR[i-1]+cntR[i];
		FL(j,1,m+1) lcp[j]=0;
		FR(i,n,1){
			FL(j,1,m){
				lcp[j]=(S[i]==R[j]?lcp[j+1]+1:0);
				ans+=(sS[i+lcp[j]]-sS[i]);
				ans+=(sR[j+lcp[j]]-sR[j]);
				ans+=lcp[j];
			}
		}
		printf("%lld\n",ans);
	}
}

D

要求区间乘积中指数为奇数的质因数的乘积，然后只需支持判断是否相等，于是想哈希，因为我们只关心奇偶性所以想异或哈希，于是我们给每一个质数赋一个随机权，预处理异或的前缀和。

那么相当于求两个前缀和异或起来等于 $hs_X$ 得方案数，直接枚举其中一个的值用 map 查找另一个的个数即可，时间复杂度 $\mathcal{O}(n\log n)$ 。

注意当 $hs_X=0$ 时要特判，相当于选两个相同的值的方案数。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e6 + 10;

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

int n,X;
ll ans=0;
int pri[MAXN],tot=0;
int mn[MAXN];
ull hs[MAXN];
int a[MAXN];
ull s[MAXN];
map<ull,int>cnt;
bool mk[MAXN];

int main(){
	scanf("%d%d",&n,&X);
	hs[1]=0;
	FL(i,2,MAXN-1){
		if(!mk[i])
			pri[++tot]=i,mn[i]=i,hs[i]=rnd();
		for(int j=1;j<=tot&&i*pri[j]<MAXN;j++){
			int k=i*pri[j];
			mk[k]=1,mn[k]=pri[j],hs[k]=hs[i]^hs[pri[j]];
			if(!(i%pri[j])) break;
		}
	}
	cnt[0]=1;
	FL(i,1,n) scanf("%d",&a[i]),s[i]=s[i-1]^hs[a[i]],cnt[s[i]]++;
	if(!hs[X])
		for(auto i:cnt)	
			ans+=1ll*i.second*(i.second-1)/2;
	else{
		for(auto i:cnt){
			ull val=hs[X]^i.first;
			if(i.first>val) continue;
			if(cnt.find(val)!=cnt.end()) ans+=1ll*i.second*cnt[val];
		}
	}
	printf("%lld\n",ans);
}

E

当 $K\ge 30$ 时答案只能是 $1$ ，因为 $2^{30}>10^9$ ，然后剩下的你直接枚举答案求出答案的 $K$ 次方和 $n$ 比较即可。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;

int main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		ll K,n;
		scanf("%lld%lld",&n,&K);
		if(K>=30) puts("1");
		else{
			FL(i,2,n){
				ll Mul=1;
				FL(j,1,K) Mul*=i;
				if(Mul>n){
					printf("%d\n",i-1);
					break;
				}
			}
		} 
	}
}

F

显然你直接按照起始时间排序然后累加即可。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e5 + 10;

int n;
ll tim=0;
PII a[MAXN];

int main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d",&n);
		FL(i,1,n) scanf("%d%d",&a[i].first,&a[i].second);
		sort(a+1,a+n+1); 
		ll tim=0;
		FL(i,1,n) tim=max(tim,(ll)a[i].first)+a[i].second;
		printf("%lld\n",tim); 
	}
}

G

令 $siz_u$ 表示 $u$ 子树的大小， $sum_u$ 表示 $u$ 子树内的沙粒总数，那么 $f_u=\min(\lfloor\frac{sum_u}{siz_u}\rfloor,\min_{v\in son(u)}f_v)$。

因为看不懂给的开大栈空间的指令于是写的 topo 序。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e6 + 10;

int n;
ll a[MAXN],f[MAXN];
int id[MAXN],tot=0;
int fa[MAXN],siz[MAXN];
ll sum[MAXN];
vector<int>G[MAXN];

int main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d",&n);
		FL(i,1,n) G[i].clear(); 
		FL(i,1,n) scanf("%lld",&a[i]);
		FL(i,1,n-1){
			int u,v;
			scanf("%d%d",&u,&v);
			G[u].push_back(v);
			G[v].push_back(u);
		}
		queue<int>q;
		tot=0;
		fa[1]=0,q.push(1);
		while(!q.empty()){
			int u=q.front();
			id[++tot]=u;
			q.pop();
			for(int v:G[u]){
				if(v!=fa[u]) fa[v]=u,q.push(v);
			}
		}
		FR(i,n,1){
			int u=id[i];
			siz[u]=1,sum[u]=a[u];
			for(int v:G[u])
				if(v!=fa[u]) 
					siz[u]+=siz[v],sum[u]+=sum[v];
			f[u]=sum[u]/siz[u];
			for(int v:G[u])
				if(v!=fa[u])
					f[u]=min(f[u],f[v]);
		}
		FL(i,1,n) printf("%lld ",f[i]);
		puts("");
	}
}

H

你会发现如果 $a_x,a_y$ 的最大公因数是 $g$ 那么 $a_x,a_y$ 都必须是 $g$ 的倍数，

发现 $g\le 30$ ，那么 $1\sim 30$ 的最小公倍数只到 $10^{12}$ 级别，

令 $mn_x$ 表示和 $x$ 有关的所有提示的 $g$ 的最小公倍数，显然 $a_x,a_y$ 最大公因数的下界就是 $\gcd(mn_x,mn_y)$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 2e5 + 10;

int n,m,q;
ll mn[MAXN];

ll lcm(ll x,ll y){
	return (x/__gcd(x,y))*y;
}

int main(){
	int Num;
	scanf("%d",&Num);
	while(Num--){
		scanf("%d%d%d",&n,&m,&q);
		FL(i,1,n) mn[i]=1;
		FL(i,1,m){
			int x,y,g;
			scanf("%d%d%d",&x,&y,&g);
			mn[x]=lcm(mn[x],g),mn[y]=lcm(mn[y],g);
		}
		while(q--){
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%lld\n",__gcd(mn[x],mn[y]));
		}
	}
}

I

显然是 bfs，然后猜结论说如果最后存在一种合法的方案，那么图中向量和的两维都不会超出 $[-2V,2V]$ 这个区间，这道题中 $V=200$ 。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 500 + 20;
const int C = 250 + 5;
const int inf = 0x3f3f3f3f;

int n,ans;
int dis[MAXN][MAXN];
vector<PII>V,us;
bool fg=0;

int main(){
	int Num;
	scanf("%d",&Num);
	FL(i,0,(C<<1)) FL(j,0,(C<<1)) dis[i][j]=inf;
	while(Num--){
		scanf("%d",&n),ans=-1,fg=0;
		V.clear(); 
		queue<PII>q; 
		FL(i,1,n){
			int x,y;
			scanf("%d%d",&x,&y);
			if(dis[x+C][y+C]==inf) 
				V.push_back({x,y}),us.push_back({x,y}),dis[x+C][y+C]=1,q.push({x,y});
		} 
		if(dis[C][C]!=inf){
			puts("1");
			for(PII i:us) dis[i.first+C][i.second+C]=inf;
			us.clear();
			continue; 
		}
		while(!q.empty()){
			int x=q.front().first,y=q.front().second;
			q.pop();
			for(PII i:V){
				int nx=x+i.first,ny=y+i.second; 
				if(!nx&&!ny){
					fg=1,ans=dis[x+C][y+C]+1;
					break;
				}
				if(nx<-C||nx>C||ny<-C||ny>C||dis[nx+C][ny+C]!=inf) continue;
				us.push_back({nx,ny}),dis[nx+C][ny+C]=dis[x+C][y+C]+1,q.push({nx,ny});
			}
			if(fg) break; 
		}
		printf("%d\n",ans);
		for(PII i:us) dis[i.first+C][i.second+C]=inf;
		us.clear();
	}
}

J

首先 $b_i=\mathrm{MEX}[i,n]$ 是严格不增的，所以判掉非法的情况，然后 $b_1\not =n$ 也是非法的。

否则我们可以强制添加 $b_1=n$ 这条限制， $b_i=k$ 这个条件等价于填在 $[1,i-1]$ 的数的最小值为 $k$ 。

我们把限制按 $x_i$ 排序，考虑相邻的两个限制 $i,i+1$ ，我们要给区间 $[x_{i},x_{i+1})$ 填数， $b_{x_i}=y_i,b_{x_{i+1}}=y_{i+1}$ 。

讨论 $y_i$ 和 $y_{i+1}$ 的大小关系：

若 $y_{i}\not=y_{i+1}$ ，否则我们要在这个区间内选一个位置放入 $y_{i+1}$ ，其余位置放 $>y_{i+1}$ 的数。

（显然我们在这之前填入的 $x_i-1$ 个数均 $>y_{i+1}$ ，所以是 $(n-1)-y_{i+1}$ 个减去 $x_i-1$ 个已经用过的）。
否则我么已经填入了 $y_{i+1}$ ，我们在所有位置填入 $> y_{i+1}$ 的数即可。

（注意前面填入的数有一个是 $y_{i+1}$ ，所以只有 $x_i-2$ 个 $>y_i$ 的数是用过的）。

最后剩下 $[x_m,n]$ ，直接全排列填数即可。

单组时间复杂度 $\mathcal{O}(m\log m)$ ，瓶颈是排序。

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;
const int MAXN = 1e5 + 10;
const int mod = 998244353;

int n,m,ans;
PII a[MAXN];
int fac[MAXN],inv[MAXN];

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}

int P(int n,int m){
	if(n<m||n<0||m<0) return 0;
	return 1ll*fac[n]*inv[n-m]%mod;
}

int main(){
	int Num;
	scanf("%d",&Num);
	fac[0]=1;
	FL(i,1,MAXN-1) fac[i]=1ll*fac[i-1]*i%mod;
	inv[MAXN-1]=qpow(fac[MAXN-1],mod-2);
	FR(i,MAXN-2,0) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	while(Num--){
		scanf("%d%d",&n,&m),ans=1;
		FL(i,1,m) scanf("%d%d",&a[i].first,&a[i].second);
		sort(a+1,a+m+1);
		if(a[1].first==1&&a[1].second!=n){
			puts("0");
			continue;
		}
		if(a[1].first!=1) a[++m]={1,n};
		sort(a+1,a+m+1);
		bool fg=1;
		FL(i,2,m)
			if(a[i].second>a[i-1].second) fg=0;
		if(!fg){
			puts("0");
			continue;
		}
		FL(i,2,m){
			if(a[i].second==a[i-1].second)
				ans=1ll*ans*P((n-1-a[i].second)-(a[i-1].first-2),a[i].first-a[i-1].first)%mod;
			else
				ans=1ll*ans*(a[i].first-a[i-1].first)%mod*P((n-1-a[i].second)-(a[i-1].first-1),a[i].first-a[i-1].first-1)%mod;		
		}
		ans=1ll*ans*fac[n-a[m].first+1]%mod;
		printf("%d\n",ans);
	}
}

20260320杭电春季赛总结

A

B

C

D

E

F

G

H

I

J

Status

Development

Support

About

20260320杭电春季赛总结

A

B

C

D

E

F

G

H

I

J

Status

Development

Support

About

SIGN IN