首页 > 其他分享 >Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)

Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)

时间：2024-07-21 19:53:37浏览次数：13  
标签：959 typedef now int Codeforces long Div include define

Preface

这场比赛的时候 CF 一直抽风，快 10min 的时候才登上去，然后中间交题也一直在人机验证

50min 左右过了前 5 题后，F 没想到生成树当场趋势了，赛后发现原来是原题大战可海星

A. Diverse Game

将每个数循环移位变为下一个数即可，注意特判 \(n=m=1\) 的情形

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=15;
int t,n,m,a[N][N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d%d",&n,&m); int all=n*m;
		for (i=1;i<=n;++i) for (j=1;j<=m;++j) scanf("%d",&a[i][j]),a[i][j]=a[i][j]%all+1;
		if (n*m==1) { puts("-1"); continue; }
		for (i=1;i<=n;++i) for (j=1;j<=m;++j) printf("%d%c",a[i][j]," \n"[j==m]);
	}
	return 0;
}

B. Fun Game

手玩一下发现只要前面存在一个 \(1\)，那么后面任意位置都可以任意取值

因此这个题实际上就是比较两个串第一个 \(1\) 出现的位置

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n; char a[N],b[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%s%s",&n,a+1,b+1);
		auto fst=[&](char *s)
		{
			for (RI i=1;i<=n;++i) if (s[i]=='1') return i;
			return n+1;
		};
		puts(fst(a)<=fst(b)?"YES":"NO");
	}
	return 0;
}

C. Hungry Games

考虑倒着递推，令 \(f_i\) 表示以 \(i\) 为左端点的合法区间数量

转移的话考虑找到最靠前的 \(j\)，使得 \(\sum_{k=i}^j a_k>x\)，这个可以预处理前缀和数组然后二分求解

根据定义显然有 \(f_i=f_{j+1}+1\)，注意特判 \(j\) 不存在的情况

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,m,x,pfx[N],f[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld%lld",&n,&m),i=1;i<=n;++i)
		scanf("%lld",&x),pfx[i]=pfx[i-1]+x; int ans=0;
		for (f[n+1]=0,i=n;i>=1;--i)
		{
			int pos=upper_bound(pfx+i,pfx+n+1,m+pfx[i-1])-pfx;
			if (pos<=n) f[i]=f[pos+1]+1; else f[i]=0;
			ans+=f[i];
		}
		printf("%lld\n",n*(n+1)/2-ans);
	}
	return 0;
}

D. Funny Game

感觉是本场最有意思的一个题了

不难发现边权越小的边可供连接的点对越多，因此我们从点对较少的边权大的边开始处理

考虑连接边权为 \(n-1\) 的边时，我们可以将所有点按照点权对 \(n-1\) 的余数分为 \(n-1\) 类，根据鸽笼原理，总是存在两个及以上的点在一类中

任意选出这样的两个点后，再它们之间连上边，然后随便删掉一个点，不难发现问题被规约为更小规模的原问题，因此可以一直往前做到边权为 \(1\)

我比赛的时候抽风了没有直接把点删了而是用并查集合并起来，每次要找两个在不同联通块的点连边，相比之下比较麻烦

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=2005;
int t,n,a[N],fa[N],lst_fa[N],num[N]; vector <int> vec[N];
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
		scanf("%d",&a[i]),fa[i]=i;
		vector <pi> ans;
		for (i=n-1;i>=1;--i)
		{
			for (j=0;j<i;++j) lst_fa[j]=num[j]=-1;
			for (j=1;j<=n;++j) 
			{
				int pos=a[j]%i;
				if (lst_fa[pos]==-1)
				{
					lst_fa[pos]=getfa(j);
					num[pos]=j; continue;
				}
				if (lst_fa[pos]!=getfa(j))
				{
					ans.push_back(pi(num[pos],j));
					fa[getfa(num[pos])]=getfa(j); break;
				}
			}
		}
		puts("YES"); reverse(ans.begin(),ans.end());
		for (auto [x,y]:ans) printf("%d %d\n",x,y);
	}
	return 0;
}

E. Wooden Game

究极丁真题，不难发现点数最大的那棵树显然全部删去是最优的，现在我们只需要考虑尽可能地将它二进制下为 \(0\) 的那些位变成 \(1\) 即可

考虑对于一棵 \(x\) 个点的树，由于我们总可以删去某个叶子使得其大小减 \(1\)，因此实际上它能贡献 \([1,x]\) 中的任意一个值

故而这题的树的形态就是花椒粉（徐神语：即诈骗用的），直接贪心处理即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1e6+5;
int t,n,a[N],x;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
		for (scanf("%d",&a[i]),j=1;j<a[i];++j) scanf("%d",&x);
		sort(a+1,a+n+1); int ans=a[n]; vector <int> ufd;
		int hb=0; for (i=0;i<20;++i) if ((ans>>i)&1) hb=i;
		for (i=hb;i>=0;--i) if (((ans>>i)&1)==0) ufd.push_back(i);
		for (i=n-1;i>=1;--i)
		{
			vector <int> tmp;
			for (auto x:ufd) if (a[i]>=(1<<x)) a[i]-=(1<<x),ans|=(1<<x);
			else tmp.push_back(x); ufd=tmp;
		}
		printf("%d\n",ans);
	}
	return 0;
}

F. Stardew Valley

ORZ 徐神一眼秒杀此题，但不会写欧拉回路板子可海星

首先题目就是要找经过所有有 NPC 的边（以下称为关键边）的欧拉回路，由于题目中已经保证依靠关键边可以将图连通，因此我们只需要用没有 NPC 的边（以下称为非关键边）把每个点的度数补为偶数即可

考虑将仅考虑关键边时，度数为奇数的点称为关键点，现在删去图中所有关键边，仅考虑非关键边，显然每个联通块独立

发现若一个联通块内有奇数个关键点则显然无解，因为此时需要奇数次度数变化，而一条边带来的度数变化是偶数，因此必然无解

否则有偶数个关键点时我们总有如下的构造方案，即先对该联通块求出任一生成树，再将所有关键点任意两两配对，将配对的两点间树上路径的选择关系取反，最后将要选择的边加入跑欧拉回路即可

上述做法的正确性在于树上一条路径端点被边 cover 一次，中间其余的点被边 cover 两次，因此满足度数要求

实现时不需要真的维护树上路径，只需要根据子树内关键点的数量决定该点的父边是否要选即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=500005;
int t,n,m,x[N],y[N],c[N],d[N],deg[N],vis[N],used[N]; vector <pi> v[N],tr[N],nv[N];
inline void DFS1(vector <int>& odd,CI now,CI fa=0)
{
	if (deg[now]%2==1) odd.push_back(now); vis[now]=1;
	for (auto [to,id]:v[now]) if (to!=fa&&!vis[to])
	tr[now].push_back(pi(to,id)),DFS1(odd,to,now);
}
inline void DFS2(CI now,CI fa=0,CI lst=0)
{
	for (auto [to,id]:tr[now]) if (to!=fa) DFS2(to,now,id),d[now]^=d[to];
	if (d[now]) nv[now].push_back(pi(fa,lst)),nv[fa].push_back(pi(now,lst));
}
inline void Euler(vector <int>& path,CI now=1)
{
	while (!nv[now].empty())
	{
		auto [to,id]=nv[now].back(); nv[now].pop_back();
		if (used[id]) continue; used[id]=1; Euler(path,to);
	}
	path.push_back(now);
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
		{
			scanf("%d%d%d",&x[i],&y[i],&c[i]); used[i]=0;
			if (c[i]==0)
			{
				v[x[i]].push_back(pi(y[i],i));
				v[y[i]].push_back(pi(x[i],i));
			} else
			{
				++deg[x[i]]; ++deg[y[i]];
				nv[x[i]].push_back(pi(y[i],i));
				nv[y[i]].push_back(pi(x[i],i));
			}
		}
		bool flag=1; for (i=1;i<=n;++i) if (!vis[i])
		{
			vector <int> odd; DFS1(odd,i);
			if (odd.size()%2==1) { flag=0; break; }
			for (auto x:odd) d[x]^=1; DFS2(i);
		}
		if (!flag) puts("NO"); else
		{
			puts("YES"); vector <int> path;
			Euler(path); reverse(path.begin(),path.end());
			printf("%d\n",path.size()-1);
			for (auto x:path) printf("%d ",x); putchar('\n');
		}
		for (i=1;i<=n;++i) deg[i]=d[i]=vis[i]=0,v[i].clear(),tr[i].clear(),nv[i].clear();
	}
	return 0;
}

G. Minecraft

也是个丁真题，没想到这么煞笔的题放在这个位置

考虑从低位向高位 DP，令 \(f_{i,j}\) 表示处理了前 \(i\) 位，此时从低位来的进位为 \(j\) 的局面是否存在

注意到假设所有低位全为 \(1\)，进位也不会超过 \(\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\dots=n\)，因此第二位的上界为 \(n\)

每位的决策只有两种，即 \(x\) 这一位取 \(0/1\)，分别讨论一下即可，复杂度 \(O(nk)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=2e6+5;
int t,n,k; char str[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d%d",&n,&k);
		vector <int> cnt(k),s(k);
		for (scanf("%s",str),i=0;i<k;++i) s[k-1-i]=str[i]-'0';
		for (i=0;i<n;++i)
		for (scanf("%s",str),j=0;j<k;++j) cnt[k-1-j]+=str[j]-'0';
		vector <vector <int>> f(k+1,vector <int>(n+1));
		vector <vector <pi>> pre(k+1,vector <pi>(n+1));
		for (f[0][0]=1,i=0;i<k;++i) for (j=0;j<=n;++j)
		{
			if (!f[i][j]) continue;
			if ((cnt[i]+j)%2==s[i])
			{
				f[i+1][(cnt[i]+j)/2]=1;
				pre[i+1][(cnt[i]+j)/2]={0,j};
			}
			if ((n-cnt[i]+j)%2==s[i])
			{
				f[i+1][(n-cnt[i]+j)/2]=1;
				pre[i+1][(n-cnt[i]+j)/2]={1,j};
			}
		}
		if (!f[k][0]) { puts("-1"); continue; }
		for (int cur=k,lst=0;cur>=1;--cur)
		putchar(pre[cur][lst].fi+'0'),lst=pre[cur][lst].se;
		putchar('\n');
	}
	return 0;
}

Postscript

这场题好抽象啊，难度感觉被 Random_Shuffle 了一样，打得人好难受

标签：959,typedef,now,int,Codeforces,long,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/18314879

相关文章

  • Codeforces Round 958 (Div. 2)
    A.SplittheMultisetForexample, {2,2,4} isamultiset.Youhaveamultiset ......
  • Codeforces Round 960 (Div. 2)(A - D)
    CodeforcesRound960(Div.2)(A-D)A-SubmissionBait解题思路:假设直接选最大数，如果最大数有奇数个，\(Alice\)必胜，反之必败。根据这个思路，从大到小看数字，找到第一个出现奇数次的数，从它开始选，就能保证每次\(Alice\)选的时候还剩奇数个选项。代码:#include<bits/stdc++.......
  • Codeforces Round 960 (Div. 2)
    Preface周日开始补之前欠下的CF博客，这周一共有三场就按照从后往前的顺序补吧这场经典前期唐完了，前4题上来每题WA一发也是神人了，最后做到E的时候只有50min了结果还把题看错了以为树的形态都是不确定的，怀疑人生了好久感觉这个题完全没法做，后面看了眼样例才发现树的形态......
  • Codeforces Round 960(Div.2）
    CodeforcesRound960(Div.2)A从大到小去判断数字个数的奇偶性，只要出现过奇数，先手必赢，如果不出现奇数，后手必赢#include<iostream>#include<queue>#include<map>#include<set>usingnamespacestd;constintN=55;inta[N];voidsolve(){ intn; cin>>n; ma......
  • 题解：Codeforces Round 960 (Div. 2) D
    D.GridPuzzletimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouaregivenanarray\(a\)ofsize\(n\).Thereisan\(n\timesn\)grid.Inthe\(i\)-throw,thefirst\(a_i\)......
  • 题解：Codeforces Round 960 (Div. 2) C
    C.MadMADSumtimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputWedefinethe\(\operatorname{MAD}\)(MaximumAppearingDuplicate)inanarrayasthelargestnumberthatappearsatleast......
  • Codeforces
    Round959A给定\(n*m\)数组\(a\)，$1\lea_i\len*m$并且两两不同，问是否存在数组\(b\)，也使用这些元素，并且每个位置的值都与\(a\)不同。\(1*1\)数组特判，其他循环移位。B给定01串s和t，可以对s任意次执行以下操作：选择l,r，将l，r异或等长前缀，问s和t是否能相等对于s和t第一个......
  • Codeforces Round 960 (Div. 2) A - D
    link好图好图qwq这次也是终于装上插件codeforcesbetter!了，妈妈再也不用担心我的英语啦A-SubmissionBaitA先手，B后手，优先往奇偶性的方向想一开始我只是单纯考虑A总是选最大值的数的奇偶性，样例过了？交上去发现wa2然后恼...瞎搞了个33344，发现A可以先选3......
  • 题解：Codeforces Round 960 (Div. 2) B
    B.ArrayCrafttimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputForanarray\(b\)ofsize\(m\),wedefine:themaximumprefixpositionof\(b\)isthesmallestindex\(i\)thatsat......
  • Codeforces Round 960 (Div.2) 补题
    A非常容易观察到性质，注意Alice为先手，发现当\(a_{\max}\)的个数为奇数时显然能win，但如果\(a_{\max}\)的个数为偶数且有一个数具有奇数个可以作为跳板，那么也能win，否则就lose。B结论：\(presum_x\geq2+presum_{y-1}\geq2+\min{presum_i}\geq1+\max{presum_i}......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99