sm2025 模拟赛24 (2025.10.20)

T1 超级集合

link
思路
由于删数的实际作用是减小剩下数的排名，所以最后答案排名为 $1$ 。
考虑时光倒流。在第 $k$ 轮结束后，答案排名为 $x=1$。考虑第 $k-1$ 轮答案的排名 $x^{\prime }$ 。找到最大的 $i$ 满足 $a_i+1\le x+i$ ，即 $a_i-i+1\le x$ ，此时 $x^{\prime }\leftarrow x+i$ 。这样一轮轮枚举的复杂度为 $O(k)$ 。发现随着 $x$ 的增大，$i$ 也会增大。那么从小到大枚举 $i$ ，计算出有多少轮的 $x$ 的决策点在 $i$ ，复杂度 $O(n)$ 。

反思
好像之前模拟赛2出过类似思路的题？
所以对于这种删数的是不是可以考虑倒着做然后加数。
虽然但是找规律也有 75pts .

代码

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
ll a[maxn];
int main(){
	freopen("superset.in","r",stdin);
	freopen("superset.out","w",stdout);
	int id,t; cin>>id>>t;
	while(t--){
		ll n,k; cin>>n>>k;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		if(a[1]>1){
			cout<<"1\n";
			continue;
		}
		ll x=1;
		for(int i=1;i<n;i++){
			ll tmp=(a[i+1]-x-1)/i;
			if(tmp>k){
				x+=k*i;
				break;
			}
			x+=tmp*i; k-=tmp;
		}
		cout<<x+n*k<<"\n";
	}
	return 0;
}

T2 宝可梦

link
思路
首先每只怪物的每种属性只会被改一次。考虑建图，直接暴力建边为 $O(n^{2}m)$ 。考虑优化建图。
首先带着点权 $c_i$ 操作不方便，将一个点拆成入点和出点。然后由于每个属性值只会从小变化到大，所以对于每种属性，将怪物排序后用一条链连起来即可，边权为相邻两值的差。总共会连 $O(4nm)$ 条边。跑一次最短路即可。

代码

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
#define pir pair<ll,int>
using namespace std;
const int maxn=4e5+5,INF=1e18;

int idx,head[maxn];
struct EDGE{ int v,next; ll w; }e[maxn*2];
void Insert(int u,int v,ll w){
	e[++idx]={v,head[u],w};
	head[u]=idx;
}

int n,m;
ll dis[maxn];
priority_queue<pir,vector<pir>,greater<pir> >q; 
void Dij(){
	for(int i=1;i<=n*m+n;i++){
		dis[i]=INF;
	}
	while(!q.empty()) q.pop();
	dis[n*m+1]=0; q.push({0,n*m+1});
	while(!q.empty()){
		int x=q.top().second; ll y=q.top().first; q.pop();
		if(dis[x]<y) continue;
		for(int i=head[x];i;i=e[i].next){
			int v=e[i].v;
			if(dis[v]>dis[x]+e[i].w){
				dis[v]=dis[x]+e[i].w;
				q.push({dis[v],v});
			}
		}
	}
}

struct NODE{
	ll w; int id; 
	bool operator < (const NODE a)const{
		return a.w>w;
	}
};
vector<NODE>a[maxn];
int main(){
	freopen("pokemon.in","r",stdin);
	freopen("pokemon.out","w",stdout);
	int id,t; scanf("%d%d",&id,&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=1,x;i<=n;i++){
			scanf("%d",&x);
			for(int j=1;j<=m;j++)
				Insert((i-1)*m+j,n*m+i,x),Insert(n*m+i,(i-1)*m+j,0);
		}
		for(int i=1;i<=n;i++)
			for(int j=1,x;j<=m;j++){
				scanf("%d",&x);
				a[j].push_back({x,i});
			}
		for(int i=1;i<=m;i++){
			sort(a[i].begin(),a[i].end());
			for(int j=1;j<n;j++){
				Insert((a[i][j].id-1)*m+i,(a[i][j-1].id-1)*m+i,a[i][j].w-a[i][j-1].w),
				Insert((a[i][j-1].id-1)*m+i,(a[i][j].id-1)*m+i,0);
			}
		}
		Dij();
		printf("%lld\n",dis[n*m+n]);
		for(int i=1;i<=m;i++)
			a[i].clear();
		memset(head,0,sizeof(head));
		idx=0;
	}
	return 0;
}

T3 城市地铁

link
思路
首先我们希望对于每个询问 $(x,y)$ ，让 $x,y$ 都跳到他们的 lca ，此时的换乘数量之和 $-$ 跳到 lca 时最后是否乘到同一个地铁就是答案。发现一步步跳很慢，考虑倍增。记 $f_{i,j}$ 表示从 $i$ 号点换乘 $2^j$ 次能跳到的最高的点。
实际上判断 $x,y$ 跳到 lca 时最后是否乘到同一个地铁可以将询问离线下来，即在 $x,y$ 都跳到 lca 的下一层时要判断是否有一条地铁能从 $x^{\prime }$ 的子树出发到达 $y^{\prime }$ 的子树，这可以将子树通过 $dfn$ 转化为一段连续的区间，类似二位数点判断即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;

int idx,head[maxn];
struct EDGE{ int v,next; }e[maxn*2];
void Insert(int u,int v){
	e[++idx]={v,head[u]};
	head[u]=idx;
}

int dep[maxn],fatr[maxn][23],dfn[maxn],ed[maxn],tim;
void Dfs(int x,int fa){
	dep[x]=dep[fa]+1; fatr[x][0]=fa; dfn[x]=++tim;
	for(int i=0;i<20;i++)
		fatr[x][i+1]=fatr[fatr[x][i]][i];
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].v;
		if(v!=fa) Dfs(v,x);
	}
	ed[x]=tim;
}

int Get_lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--)
		if(dep[fatr[x][i]]>=dep[y]) x=fatr[x][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--)
		if(fatr[x][i]!=fatr[y][i]) x=fatr[x][i],y=fatr[y][i];
	return fatr[x][0];
}

int f[maxn][23];
vector<int>pos[maxn];
int Dfs2(int x,int fa){
	int mi=x;
	for(auto i:pos[x])
		if(dep[i]<dep[mi]) mi=i;
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].v;
		if(v!=fa){
			int tmp=Dfs2(v,x);
			if(dep[tmp]<dep[mi]) mi=tmp;
		}
	}
	return f[x][0]=mi;
}

void Dfs3(int x,int fa){
	for(int i=0;i<20;i++)
		f[x][i+1]=f[f[x][i]][i];
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].v;
		if(v!=fa) Dfs3(v,x);
	}
}

int Jump_(int &x,int d){
	int s=0;
	for(int i=20;i>=0;i--)
		if(dep[f[x][i]]>d) x=f[x][i],s+=(1<<i);
	return s;
}

int n,tree[maxn];
void Add(int x){
	while(x<=n) tree[x]++,x+=x&(-x);
}
int Ask(int x){
	int s=0;
	while(x) s+=tree[x],x-=x&(-x);
	return s;
}

int ans[maxn],ok[maxn];
struct SUY{ int x,y; }sw[maxn];
struct QUE{ int x,ql,qr,id,op; }ct[maxn*2];
int main(){
	freopen("metro.in","r",stdin);
	freopen("metro.out","w",stdout);
	int id; cin>>id>>n;
	for(int i=1;i<n;i++){
		int x,y; cin>>x>>y;
		Insert(x,y),Insert(y,x);
	}
	Dfs(1,0);
	int m; cin>>m;
	for(int i=1;i<=m;i++){
		int x,y; cin>>x>>y;
		int lca=Get_lca(x,y);
		pos[x].push_back(lca); pos[y].push_back(lca);
		if(dfn[x]>dfn[y]) swap(x,y);
		sw[i]={dfn[x],dfn[y]};
	}
	Dfs2(1,0),Dfs3(1,0);
	int q; cin>>q; int tot=0;
	for(int i=1;i<=q;i++){
		int x,y; cin>>x>>y;
		if(x==y){ ans[i]=0; continue; }
		int lca=Get_lca(x,y); 
		if(dep[x]>dep[y]) swap(x,y);
		if(x==lca){
			ans[i]=Jump_(y,dep[lca]);
			if(dep[f[y][0]]<=dep[lca]) ans[i]++;
			else ans[i]=-1;
		}
		else{
			ans[i]=Jump_(x,dep[lca])+Jump_(y,dep[lca]);
			if(dep[f[x][0]]<=dep[lca]&&dep[f[y][0]]<=dep[lca]){
				ans[i]+=2;
				if(dfn[x]>dfn[y]) swap(x,y);
				ct[++tot]={dfn[x]-1,dfn[y],ed[y],i,-1};
				ct[++tot]={ed[x],dfn[y],ed[y],i,1};
			}
			else ans[i]=-1;
		}
	}
	sort(sw+1,sw+m+1,[](SUY a,SUY b){ return a.x<b.x; });
	sort(ct+1,ct+tot+1,[](QUE a,QUE b){ return a.x<b.x; });
	for(int i=1,j=1;i<=tot;i++){
		while(j<=m&&sw[j].x<=ct[i].x) Add(sw[j++].y);
		ok[ct[i].id]+=ct[i].op*(Ask(ct[i].qr)-Ask(ct[i].ql-1));
	}
	for(int i=1;i<=q;i++){
		if(ans[i]==-1) cout<<"-1\n";
		else{
			if(ok[i]) ans[i]--;
			cout<<ans[i]<<"\n";
		}
	}
	return 0;
}

T4 寿司晚宴

link
思路
首先如果确定了排列 $A,B,C$ ，那么每个人吃的顺序是固定的。到某一轮三人分别选择 $x,y,z$ 的寿司时，此时前面的寿司已经被选完，那么如果 C 有贡献当且仅当 $x,y$ 都在 $z$ 的后面。所以从后往前推，如果已经确定 $c$ 吃了哪些寿司，考虑将不是 c 吃的那部分寿司插入 c 吃的排列中，那么对应的排列数为 $\prod _{i=1}^{\frac{n}{3}}(3\times i-1)(3\times i-2)$ 。
那么现在只需要知道 $c$ 吃了哪些寿司即可。考虑计数的限制条件。

• a,b,c 各自吃的寿司不会有重复；
• a 吃了的寿司不会被 b,c 选择，b,c 同理。
• a,b,c 每一轮都要吃；

所以说到第 $t$ 轮，c 能选择的数为 3 × t − ∣ { a i 1 , a i 2 , … , a i t } ∪ { b i 1 , b i 2 , … , b i t } ∣ 3\times t-|\{a_{i_1},a_{i_2},\dots,a_{i_t}\}\cup \{b_{i_1},b_{i_2},\dots ,b_{i_t}\}| 3×t−∣{ai1​​,ai2​​,…,ait​​}∪{bi1​​,bi2​​,…,bit​​}∣ 。设 $f_{t,i,j}$ 表示考虑到第 $t$ 轮，a 吃了 $i$ ，b 吃了 $j$ ，c 的选择数。转移为： f t , i , j = ∑ i ′ < i , j ′ < j f t − 1 , i ′ , j ′ × ( 3 × t − ∣ { a i 1 , a i 2 , … , a i t } ∪ { b i 1 , b i 2 , … , b i t } ∣ ) f_{t,i,j}=\sum\limits_{i'\lt i,j'\lt j} f_{t-1,i',j'}\times (3\times t-|\{a_{i_1},a_{i_2},\dots,a_{i_t}\}\cup \{b_{i_1},b_{i_2},\dots ,b_{i_t}\}|) ft,i,j​=i′<i,j′<j∑​ft−1,i′,j′​×(3×t−∣{ai1​​,ai2​​,…,ait​​}∪{bi1​​,bi2​​,…,bit​​}∣)
前缀和优化一下，复杂度为 $O(n^3)$ 。

反思

计数的通常方式是列出限制条件，再根据限制条件解决 。

代码

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=405,maxt=140,mod=1e9+7;
int a[maxn],b[maxn];
ll f[maxt][maxn][maxn],g[maxn][maxn];
bool vis[maxn],oka[maxn][maxn],okb[maxn][maxn];
int main(){
	freopen("sushi.in","r",stdin);
	freopen("sushi.out","w",stdout);
	int id,t; cin>>id>>t;
	while(t--){
		int n; cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=1;i<=n;i++)
			cin>>b[i];
		for(int i=1;i<=n;i++){
			vis[a[i]]=1;
			g[i][0]=i;
			for(int j=1;j<=n;j++){
				g[i][j]=g[i][j-1];
				if(!vis[b[j]]) g[i][j]++;
			}
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=i;j++)
				okb[i][b[j]]=1,oka[i][a[j]]=1;
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				f[0][i][j]=1;
		for(int i=1;i<=n/3;i++)
			for(int j=1;j<=i*3;j++)
				for(int k=1;k<=i*3;k++){
					if(!okb[k][a[j]]&&!oka[j][b[k]]) (f[i][j][k]+=f[i-1][j-1][k-1]*(3*i-g[j][k])%mod)%=mod;
					(f[i][j][k]+=((f[i][j-1][k]+f[i][j][k-1])%mod-f[i][j-1][k-1]+mod)%mod)%=mod;
				}
		ll ans=f[n/3][n][n];
		for(int i=1;i<=n/3;i++)
			(ans*=(3*i-1)%mod*(3*i-2)%mod)%=mod;
		cout<<ans<<"\n";
		for(int i=1;i<=n/3;i++)
			for(int j=1;j<=n;j++){
				vis[j]=0;
				for(int k=1;k<=n;k++)
					f[i][j][k]=0,g[j][k]=0,oka[j][k]=okb[j][k]=0;
			}
	}
	return 0;
}