专栏文章

【抽象】2025 sm的NOIP模拟赛 第三篇

FFenki_lo
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min17by6
此快照首次捕获于
2025/12/01 18:53
3 个月前
此快照最后确认于
2025/12/01 18:53
3 个月前
查看原文
不写题意了，没什么用。

R46 T3

AT_agc019_d [AGC019D] Shift and Flip

思路

首先把 AA 的循环位移变为 BB 的循环位移，可以把 BB 复制三遍变为左右位移。
考虑枚举 AA 最终对齐复制后的 BB 的哪一个长度为 nn 的区间，那么显然 AA 与最终对齐的位置不同的是需要变化的，并且这个变化次数是固定的，现在我们只需要考虑左右位移步数的最优情况。
贪心地想，方案一定是先向左走一段再向右走一段然后走到对其位置。
设 lil_i 表示 AA 中第 ii 个位置使得这个位置碰到 BB 中的 11 需要移动的最少步数，rir_i 同理。
那么对于一次对齐方式，我们考虑分别对 AA 与 BB 不同的位置做两次处理，一次按 lil_i 升序排序，一次按 rir_i 排序。两种处理类似，只说按 ll 的。
排序后只需要枚举选到一段后缀使用 ll，一段前缀使用 rr，设当前缀 max⁡\max 的 rr 为 RR，后缀 max⁡\max 的 ll 为 LL，那么我们只要判定选择先向左边走 LL 步，走回原点再向右走 RR 步还是先右再左更好即可。
每次处理特判全选 ll 或全选 rr 的情况。

代码

CPP
#pragma GCC optimize(1,2,3,"Ofast","inline")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const int N=5e3+10,inf=1e9+10;
int n;
char a[N],b[N];
char t[N<<2];
int l[N<<1],r[N<<1];
struct node{
	int L,R,id;
}d[N];
bool cmp(node a,node b){
	return a.R>b.R||a.R==b.R&&a.L<b.L;
}
bool cmp1(node a,node b){
	return a.L>b.L||a.L==b.L&&a.R<b.R;
}
bool vis[N];
void solve(){
	scanf("%s",a+1);
	scanf("%s",b+1);
	n=strlen(a+1);
	for(int i=1;i<=n*3;i++) l[i]=r[i]=0;
	bool fl1=0,fl2=1;
	for(int i=1;i<=n;i++) fl1|=(a[i]=='1'),fl2&=(b[i]=='0');
	if(fl1&&fl2){
		puts("-1");
		return ;
	}
	for(int i=1;i<=n;i++) t[i]=t[i+n]=t[i+n*2]=b[i];
	int lst=-inf;
	for(int i=1;i<=n*3;i++){
		if(t[i]=='1') lst=i;
		l[i]=lst;
	}
	int nxt=inf;
	for(int i=n*3;i>=1;i--){
		if(t[i]=='1') nxt=i;
		r[i]=nxt;
	}
	for(int i=1;i<=n;i++){
		d[i].L=i+n-l[i+n];
		d[i].R=r[i+n]-(i+n);
		d[i].id=i;
	}
//	for(int i=1;i<=n*3;i++) cout<<t[i]<<" ";
//	cout<<"\n";
//	for(int i=1;i<=n*3;i++) cout<<l[i]<<" ";
//	cout<<"\n";
//	for(int i=1;i<=n*3;i++) cout<<r[i]<<" ";
//	cout<<"\n";
//	for(int i=1;i<=n;i++) cout<<d[i].L<<" "<<d[i].R<<"\n";
	int ans=inf;
	sort(d+1,d+n+1,cmp);
	for(int i=1;i<=n*2+1;i++){
		for(int j=1;j<=n;j++) vis[j]=0;
		int sum=0;
		for(int j=1;j<=n;j++) if(a[j]!=t[i+j-1]) vis[j]=1,sum++;
		if(sum==0){
			ans=min(ans,abs(n+1-i));
			continue;
		} 
		int pre=-1;
		for(int j=1;j<=n;j++){
			if(!vis[d[j].id]) continue;
			if(pre==-1) ans=min(ans,d[j].R+abs(n+1+d[j].R-i)+sum);
			else ans=min(ans,min(d[j].R*2+pre+abs(n+1-pre-i),pre*2+d[j].R+abs(n+1+d[j].R-i))+sum);
			pre=max(pre,d[j].L);
//			cout<<d[j].L<<" "<<d[j].R<<"\n";
		}
		ans=min(ans,pre+abs(n+1-pre-i)+sum);
//		cout<<ans<<"\n\n";
	}
//	cout<<ans<<"\n"; 
//	cout<<"\n";
	sort(d+1,d+n+1,cmp1);
	for(int i=1;i<=n*2+1;i++){
		for(int j=1;j<=n;j++) vis[j]=0;
		int sum=0;
		for(int j=1;j<=n;j++) if(a[j]!=t[i+j-1]) vis[j]=1,sum++;
		if(sum==0){
			ans=min(ans,abs(n+1-i));
			continue;
		} 
		int pre=-1;
		for(int j=1;j<=n;j++){
			if(!vis[d[j].id]) continue;
			if(pre==-1) ans=min(ans,d[j].L+abs(n+1-d[j].L-i)+sum);
			else ans=min(ans,min(d[j].L*2+pre+abs(n+1+pre-i),pre*2+d[j].L+abs(n+1-d[j].L-i))+sum);
			pre=max(pre,d[j].R);
		}
		ans=min(ans,pre+abs(n+1+pre-i)+sum);
//		cout<<ans<<"\n";
	}
//	cout<<"\n";
	write(ans);
	putchar('\n');
}
int main(){
	freopen("ring.in","r",stdin);
	freopen("ring.out","w",stdout);
	int T=1;
	read(T);
	while(T--) solve();
	return 0;
}
/*
最多左右移动 n 次

最劣情况下一直往左或者右移动即可

然后这个东西很阴间

对于一个态，它可以向左右两边走

并且一个态最多达到两次

有点像图论

如果能够dp说明没有环

那么考虑结论

对于每次移动，只有可能是 

2
1010
1100
1
0

小了 

*/

R46 T4

AT_arc083_d [ARC083F] Collecting Balls

思路

首先每个球要么被 xx 轴对应的机器人清掉，要么是 yy 轴上的。并且每个球分别被不同的机器人清掉。
考虑对于一个球 (x,y)(x,y)，连无向边 (x,y)(x,y)，那么我们就获得了一个 2n2n 个点 2n2n 条边的图，这让我们联想到基环树。
事实证明，它确实是一个基环树森林。问题可以转换为在这个基环树森林中每一条边归分别一个不同点管理的合法方案数。
再转换一下，可以转换为给每一条边定向的合法方案数。
显然当存在不是基环树的结构时，答案为 00，因为这样会导致某一条边无法被管理，这意味着这个球无法被收集。
同时为了满足题目条件，我们需要满足对于一个球 (x,y)(x,y)，如果让 AA 类机器人收集，那么 ∀y′∈[1,y)\forall y'\in[1,y)，都要让 BB 类机器人把球 (x,y′)(x,y') 收走（如果有的话）。
那么题目再次转换为球满足上述拓扑关系的排列个数。
现在我们考虑对一棵基环树如何统计方案。首先环边一定要归环上的点管理，剩下的边从上到下分配给下端的点，并且剩下的边是唯一分配的。于是我们只要暴力枚举环上的边的是正向还是反向即可。
在给一棵基环树的边定向后，它会产生许多先决条件，即某个机器人应该在某个机器人前出动，我们根据这些先决条件连边，由于每个机器人最多只可能成为一个另外一个机器人的先决条件，因此连出来的是一个内向数森林。
对于一个内向数森林 SS，我们有其拓扑序个数公式
∣S∣!∏x∈Ssizx\frac{\lvert S\rvert!}{\prod_{x\in S}siz_x}
其中 sizxsiz_x 表示以 xx 为根的子树大小。具体证明考虑dp转移式即可。
最后把每棵基环树的方案数乘起来在搞点排列数就行了。
复杂度 O(n)\Omicron(n)。

代码

CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const ll N=2e5+10,mod=1e9+7;
struct edge{
	ll v,next;
}e[N<<2];
ll head[N],id;
void add(ll u,ll v){
	e[++id]=(edge){v,head[u]},head[u]=id;
}
vector<ll>v[N];
ll n;
ll fac[N],inv[N],ivc[N];
void init(){
	fac[0]=fac[1]=inv[0]=inv[1]=ivc[0]=ivc[1]=1;
	for(int i=2;i<=n;i++){
		fac[i]=1ll*fac[i-1]*i%mod;
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
		ivc[i]=1ll*ivc[i-1]*inv[i]%mod;
	}
}
bool vis[N];
ll pt[N],cnt,eds,cir1,cir2;
ll pre[N];
void dfs(ll u,ll fa){
//	cout<<u<<" ";
	pt[++cnt]=u,vis[u]=1;
	for(int p : v[u]){
		eds++;
		if(p==fa) continue;
		if(vis[p]) cir1=u,cir2=p;
		else dfs(p,u);
	}
}
void cpos(ll u,ll fa){
	for(int p : v[u]){
		if(p==fa) continue;
		if(p!=cir1&&p!=fa){
			pre[p]=u;
			cpos(p,u);
		}
	}
}
ll in[N],siz[N];
void sol(ll u,ll fa){
	siz[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(v==fa) continue;
		sol(v,u);
		siz[u]+=siz[v];
	}
}
ll solve(){
	id=0;
	for(int i=1;i<=cnt;i++) head[pt[i]]=0,siz[pt[i]]=0,in[pt[i]]=0,pre[pt[i]]=0;
	pre[cir1]=cir2;
	cpos(cir1,cir2);
	for(int i=1;i<=cnt;i++){
		for(int p : v[pt[i]]){
			if(p<pre[pt[i]]) add(pt[i],p),in[p]++;
		}
	}
	ll res=fac[cnt];
	for(int i=1;i<=cnt;i++){
		if(!in[pt[i]]) sol(pt[i],0);
	}
	for(int i=1;i<=cnt;i++) res=res*inv[siz[pt[i]]]%mod;
	return res;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n);
	for(int i=1;i<=(n<<1);i++){
		ll x,y;
		read(x),read(y);
		v[x].emplace_back(y+n),v[y+n].emplace_back(x);
	}
	n<<=1;
	init();
	ll ans=fac[n];
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			cnt=eds=0;
			dfs(i,0);
			if((cnt<<1)!=eds){
				puts("0");
				return 0;
			}
//			cout<<"\n";
//			for(int j=1;j<=cnt;j++) cout<<pt[j]<<" ";
//			cout<<"\n";
//			cout<<cir1<<" "<<cir2<<"\n"; 
			ans=ans*ivc[cnt]%mod;
//			cout<<ans<<"\n";
			ll res=0;
			res=(res+solve())%mod;
			swap(cir1,cir2);
			res=(res+solve())%mod;
			ans=ans*res%mod;
		}
	}
	write(ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...