Codeforces Round #557 Div. 1 based on Forethought Future Cup - Final Round

2024-03-13 16:35:33

　　A：开场就读错题。读对了之后也没啥好说的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,m,a[N],cnt[N],tot;
vector<int> pos[N];
ll ans;
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	m=read(),n=read();
	for (int i=1;i<=n;i++) a[i]=read(),pos[a[i]].push_back(i);
	for (int i=1;i<=m;i++)
	{
		if (i>1)
		{
			if (pos[i].empty()) ans++;
			else
			{
				int x=pos[i][0];
				if (pos[i-1].empty()||pos[i-1][pos[i-1].size()-1]<x) ans++;
			}
		}
		if (pos[i].empty()) ans++;
		if (i<m)
		{
			if (pos[i].empty()) ans++;
			else
			{
				int x=pos[i][0];
				if (pos[i+1].empty()||pos[i+1][pos[i+1].size()-1]<x) ans++;
			}
		}
	}
	cout<<ans;
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　B：swap(1B,1D)。花了1h+仍然没有比暴力更好的做法，于是信仰交了暴力神tmpp了，最后居然似乎是因为用了map或者randomshuffle而fst，更加纯粹的暴力反而过了。无法想到的结论是，如果有解，一定存在某个解k是n的因子。考虑反证，如果只存在不是n因子的k的话，选择某条边一直往后跳k，最后会需要所有与其差为gcd(n,k)的边都存在，于是如果k合法，gcd(n,k)也一定合法。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 100010
#define M 200010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,m,t;
map<int,int> f[N];
struct data{int x,y;
}a[M<<1];
int dis(int x,int y){return x<y?y-x:n-x+y;}
int nxt(int x,int y){x+=y;if (x>n) x-=n;return x;}
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read(),m=read();srand(time(0));
	for (int i=1;i<=m;i++)
	{
		a[i].x=read(),a[i].y=read();
		f[a[i].x][a[i].y]=f[a[i].y][a[i].x]=1;
	}
	random_shuffle(a+1,a+m+1);
	for (int i=1;i<n;i++)
	if (n%i==0)
	{
		bool flag=1;
		for (int j=1;j<=m;j++)
		if (!f[nxt(a[j].x,i)][nxt(a[j].y,i)]) {flag=0;break;}
		if (flag) {cout<<"Yes";return 0;}
	}
	cout<<"No";
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　C：场上最后5min的时候猜了一个一个石子的堆数<=n/2时Alice赢，wa4。然后正解就是最少石子的堆数<=n/2时Alice赢。注意到有人*拿完一堆石子就输了，进一步有人*减少所有石子中的最小值就输了，因为另一方此时一定可以不减小最小值。而是否*就取决于上面的条件。在这个条件下必胜态一定可以转移到必败态，必败态只能转移到必胜态。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 55
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,a[N];
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read();
	for (int i=1;i<=n;i++) a[i]=read();
	int x=100;for (int i=1;i<=n;i++) x=min(x,a[i]);
	int cnt=0;
	for (int i=1;i<=n;i++) if (a[i]==x) cnt++;
	if (cnt<=n/2) cout<<"Alice";else cout<<"Bob";
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　D：要是我放弃希望死磕B大约能掉回紫（）枚举b串长度，a串每一位和b串每一位都视作一个点，并查集将要求数字相同的位合并，要求不同的位连边，并且对于某些位的强制设为1/0，也当做两个点加入这张图中进行合并。然后跑一个二分图染色，不是二分图显然没有贡献，跑完看一下1的颜色和0的颜色是否相同，若相同也显然没有贡献。然后贡献就是2^{不含01的连通块个数}。丝毫看不出来为什么放在D。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 4010
#define P 998244353
#define ida(x) (x)
#define idb(x) (n+(x))
#define S0 (n+m+1)
#define S1 (n+m+2)
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
char s[N];
int n,t,T,fa[N],a[N],p[N],color[N];
bool flag;
ll ans;
struct data{int x,y;}e[N];
struct data2{int to,nxt;
}edge[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){fa[find(x)]=find(y);}
int ksm(int a,int k)
{
	int s=1;
	for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;
	return s;
}
void addedge(int x,int y){T++;edge[T].to=y,edge[T].nxt=p[x],p[x]=T;}
void paint(int k,int c)
{
	color[k]=c;
	for (int i=p[k];i;i=edge[i].nxt)
	if (color[edge[i].to]==-1) paint(edge[i].to,c^1);
	else if (color[edge[i].to]==c) flag=0;
}
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("d.in","r",stdin);
	freopen("d.out","w",stdout);
#endif
	scanf("%s",s+1);
	n=strlen(s+1);reverse(s+1,s+n+1);
	for (int m=n-1;m>=1;m--)
	{
		for (int i=1;i<=n+m+2;i++) fa[i]=i;t=0;T=0;
		for (int i=1;i<=n;i++) merge(ida(i),ida(n-i+1));
		for (int i=1;i<=m;i++) merge(idb(i),idb(m-i+1));
		for (int i=n;i>m;i--)
		{
			if (s[i]=='0') merge(ida(i),S0);
			if (s[i]=='1') merge(ida(i),S1);
		}
		merge(idb(m),S1);
		for (int i=m;i>=1;i--)
		{
			if (s[i]=='0') merge(ida(i),idb(i));
			if (s[i]=='1') t++,e[t].x=ida(i),e[t].y=idb(i);
		}
		memset(p,0,sizeof(p));
		for (int i=1;i<=t;i++)
		{
			addedge(find(e[i].x),find(e[i].y));
			addedge(find(e[i].y),find(e[i].x));
		}
		memset(color,255,sizeof(color));
		flag=1;
		for (int i=1;i<=n+m+2;i++) if (color[i]==-1) paint(i,0);
		if (!flag) continue;
		int u=color[find(S0)],v=color[find(S1)];
		for (int i=1;i<=t;i++) merge(e[i].x,e[i].y);
		if (find(S0)==find(S1)&&u==v) continue;
		int cnt=0;
		for (int i=1;i<=n+m+2;i++)
		if (find(i)==i) cnt++;
		cnt--;if (find(S0)!=find(S1)) cnt--; 
		ans=(ans+ksm(2,cnt))%P;
	}
	cout<<ans;
	return 0;
	//NOTICE LONG LONG!!!!!
}

　　E：待会补.jpg怎么是个交互算了不补了。

　　结论题乃一生之敌。昨天晚上agc也被两个博弈卡死最后都没敢交题。

　　想起来这位上次的比赛也是D比EFGH都难（当然也是结论题），下次得格外小心。不对退役前肯定没有了担心个啥

　　You should stop creating problems

　　result：rank 287 rating -81 小号刚好变成小小号惹。

码农公寓

相关文章