526互联

CF1162 Codeforces Round 557 (Div. 2) [based on Forethought Future Cup - Final Round]

发布时间 2023-09-27 22:23:27作者: Zhou_JK

CF1162A Zoning Restrictions Again

每个位置越高越好，暴力模拟即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=55;
int n,h,m;
int a[N];
int main()
{
	scanf("%d%d%d",&n,&h,&m);
	for(int i=1;i<=n;i++)
		a[i]=h;
	for(int i=1;i<=m;i++)
	{
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		for(int j=l;j<=r;j++)
			a[j]=min(a[j],x);
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
		ans+=1LL*a[i]*a[i];
	printf("%lld",ans);
	return 0;
}

CF1162B Double Matrix

可以发现，最后两个矩阵的 \((i,j)\) 的数分别为 \(\min(a_{i,j},b_{i,j})\)，\(\max(a_{i,j},b_{i,j})\) 会尽可能优，其他情况不会比这种情况更优，判断一下是否合法即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=55;
int n,m;
int a[N][N],b[N][N];
int c[N][N],d[N][N];
bool check(int s[N][N])
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j]<=s[i-1][j]||s[i][j]<=s[i][j-1]) return false;
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&b[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			c[i][j]=min(a[i][j],b[i][j]),d[i][j]=max(a[i][j],b[i][j]);
	if(check(c)&&check(d)) printf("Possible");
	else printf("Impossible");
	return 0;
}

CF1162C Hide and Seek

枚举代币在哪个位置，判一下向左移，不动，向右移是否合法即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
int n,k;
int a[N];
int Max[N],Min[N];
int main()
{
	scanf("%d%d",&n,&k);
	memset(Min,63,sizeof(Min));
	for(int i=1;i<=k;i++)
	{
		scanf("%d",&a[i]);
		Max[a[i]]=max(Max[a[i]],i);
		Min[a[i]]=min(Min[a[i]],i);
	}	
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(i-1>=1&&Min[i]>Max[i-1]) ans++;
		if(i+1<=n&&Min[i]>Max[i+1]) ans++;
		if(Min[i]>Max[i]) ans++;
	}
	printf("%d",ans);
	return 0;
}

CF1162D Chladni Figure

枚举 \(n\) 的因子 \(d\)，判断 \(k=d\) 的时候是否合法即可。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200005;
int n,m;
pair<int,int>seg[N];
pair<int,int>b[N];
int tot;
bool check(int k)
{
	tot=0;
	for(int i=1;i<=m;i++)
	{
		pair<int,int>nxt={(seg[i].first+k)%n==0?n:(seg[i].first+k)%n,(seg[i].second+k)%n==0?n:(seg[i].second+k)%n};
		if(nxt.first>nxt.second) swap(nxt.first,nxt.second);
		b[++tot]=nxt;
	}
	sort(b+1,b+tot+1);
	for(int i=1;i<=m;i++)
		if(seg[i]!=b[i]) return false;
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		if(a>b) swap(a,b);
		seg[i]={a,b};
	}
	sort(seg+1,seg+m+1);
	if(check(1))
	{
		printf("Yes");
		return 0;
	}
	for(int i=2;i<=sqrt(n);i++)
		if(n%i==0)
		{
			if(check(i)||check(n/i))
			{
				printf("Yes");
				return 0;
			}
		}
	printf("No");
	return 0;
}

CF1162E Thanos Nim

最后的获胜条件等价于 \(0\) 的堆数要 \(> \frac{2}{n}\)。

如果最小堆的数量 \(> \frac{2}{n}\)，先手一定会取到某个最小堆，最小堆的数量会 \(\leq \frac{2}{n}\)，后手可以将最小堆的数量 \(> \frac{2}{n}\)，一直循环直到后手将 \(0\) 的堆数 \(> \frac{2}{n}\)。

那么可以推出：

如果最小堆的数量 \(\leq \frac{n}{2}\)，则先手必胜，否则后手必胜。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=55;
int n;
int a[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int m=*min_element(a+1,a+n+1);
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(a[i]==m) cnt++;
	if(cnt>n/2) printf("Bob");
	else printf("Alice");
	return 0;
}

CF1162F Palindrome XOR

可以发现，\(b\) 的二进制位数一定等于 \(m\)，考虑枚举 \(a\) 的位数 \(n\)。

问题可以转化成一些限制，表示某些位置要和某些位置的数相等或不同。

考虑建图，边权为 \(1\) 的边表示这两个点的权值不同，边权为 \(0\) 的边表示这两个点的权值相同。方案数即为原图的染色方案。

对于一个二进制位，我们可以将其拆成两个点，表示这个点取 \(0\) 或 \(1\)。再用两个点 \(0,1\) 表示取 \(0\) 和 \(1\) 的点，在这两个点之间连一条权值为 \(1\) 的边。

对于某个位置 \(i\)，它的权值已经确定，就将它连向它的权值一条权值为 \(0\) 的边。

对于 \(s_i=1\)，可以在 \(a_i\) 和 \(b_i\) 之间连权值为 \(1\) 的边；\(s_i=0\) 可以在 \(a_i\) 和 \(b_i\) 之间连权值为 \(0\) 的边。

回文的限制也连一下权值为 \(0\) 的边。

可以将权值为 \(0\) 的边缩起来，然后二分图染色判断一下是否合法。如果合法，令 \(cnt\) 为图中的联通块数，这种情况下的答案为 \(2^{cnt-1}\)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2005;
const int MOD=998244353;
long long pw[N];
int n;
char s[N];
int fa[N];
int getf(int v)
{
	if(v==fa[v]) return v;
	else return fa[v]=getf(fa[v]);
}
void merge(int u,int v)
{
	int f1=getf(u),f2=getf(v);
	if(f1!=f2) fa[f2]=f1;
	return;
}
int ida[N],idb[N];
int id[2],tot;
vector<int>G[N];
int col[N];
bool flag;
void dfs(int u)
{
	for(int v:G[u])
	{
		if(col[v]!=-1)
		{
			if(col[v]==col[u])
			{
				flag=true;
				return;
			}
			else continue;
		}
		col[v]=col[u]^1;
		dfs(v);
		if(flag) return;
	}
	return;
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	id[0]=++tot;
	id[1]=++tot;
	for(int i=1;i<=n;i++)
		ida[i]=++tot,idb[i]=++tot;
	pw[0]=1;
	for(int i=1;i<=tot;i++)
		pw[i]=pw[i-1]*2%MOD;
	long long ans=0;
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i<=tot;i++)
			fa[i]=i,col[i]=-1,G[i].clear();
		merge(ida[len],id[1]);
		merge(idb[1],id[1]);
		for(int i=1;i<len;i++)
			merge(ida[i],id[0]);
		for(int i=len;i<=n;i++)
			merge(ida[i],ida[n-(i-len+1)+1]);
		for(int i=1;i<=n;i++)
		{
			merge(idb[i],idb[n-i+1]);
			if(s[i]=='0') merge(ida[i],idb[i]);
		}
		G[getf(id[0])].emplace_back(getf(id[1])),G[getf(id[1])].emplace_back(getf(id[0]));
		for(int i=1;i<=n;i++)
			if(s[i]=='1') G[getf(ida[i])].emplace_back(getf(idb[i])),G[getf(idb[i])].emplace_back(getf(ida[i]));
		flag=false;
		int num=0;
		for(int i=1;i<=tot;i++)
			if(getf(i)==i&&col[i]==-1)
			{
				col[i]=0;
				dfs(i);
				if(flag) break;
				num++;
			}
		if(flag) continue;
		ans=(ans+pw[num-1])%MOD;
	}
	printf("%lld",ans);
	return 0;
}