首页 > 其他分享 >Codeforces Round 960 (Div. 2)

Codeforces Round 960 (Div. 2)

时间：2024-07-21 17:07:41浏览次数：13  
标签：typedef 960 int Codeforces long const Div include define

Preface

周日开始补之前欠下的 CF 博客，这周一共有三场就按照从后往前的顺序补吧

这场经典前期唐完了，前 4 题上来每题 WA 一发也是神人了，最后做到 E 的时候只有 50min 了

结果还把题看错了以为树的形态都是不确定的，怀疑人生了好久感觉这个题完全没法做，后面看了眼样例才发现树的形态给了

但由于时间所剩无几也没去写找重心的做法了，随便写了个在子树内随机选点的东西结果会超询问上限，后面补题的时候写了下找重心发现还是很好写的

A. Submission Bait

很有迷惑性的签，要根据归纳法，从大往小考虑每个数

如果当前数出现了奇数则先手取之则必胜，因为此时后面的数每个都有偶数个，先手可以镜像操作

因此先手必败的情况当且仅当所有数出现次数为偶数

#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=105;
int t,n,a[N],c[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) c[i]=0;
		for (i=1;i<=n;++i) scanf("%d",&a[i]),++c[a[i]];
		bool flag=0; for (i=1;i<=n;++i) if (c[i]%2==1) flag=1;
		puts(flag?"YES":"NO");
	}
	return 0;
}

B. Array Craft

注意到 \(y<x\)，同时不难发现将 \([y,x]\) 内的所有位置都填上 \(1\) 一定不劣

剩下的就是用 \(-1/1\) 交错地填上 \([1,y-1],[x+1,n]\) 了，特别注意 \(y-1,x+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=100005;
int t,n,x,y,a[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d%d",&n,&x,&y),i=y;i<=x;++i) a[i]=1;
		for (i=1;i<y;++i) a[i]=(y-i)&1?-1:1;
		for (i=x+1;i<=n;++i) a[i]=(i-x)&1?-1:1;
		for (i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
	}
	return 0;
}

C. Mad MAD Sum

一个重要的观察是在操作两次后，序列会变成单调不降，且除了最后一段外每一段中的数出现次数都 \(\ge 2\)

此时手玩一下后就能发现一次操作等价于将序列的最后一个元素删除并在前面加入一个 \(0\)，因此很好统计贡献

#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,a[N],c[N]; 
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; LL sum=0; for (scanf("%d",&n),i=1;i<=n;++i)
		scanf("%d",&a[i]),sum+=a[i],c[i]=0;
		int mx=0; for (i=1;i<=n;++i)
		{
			if (++c[a[i]]>=2) mx=max(mx,a[i]);
			a[i]=mx; sum+=a[i];
		}
		for (mx=0,i=1;i<=n;++i) c[i]=0;
		for (i=1;i<=n;++i)
		{
			if (++c[a[i]]>=2) mx=max(mx,a[i]);
			a[i]=mx; sum+=1LL*a[i]*(n-i+1);
		}
		printf("%lld\n",sum);
	}
	return 0;
}

D. Grid Puzzle

由于 \(2\times 2\) 的操作只能对两个相邻行进行，同时不难发现对于行 \((i,i+1)\)，至多只会进行一次 \(2\times 2\) 的操作，否则直接将两列覆盖一定不会更劣

那么考虑 DP 求解，令 \(f_{i,0/1/2}\) 表示覆盖了前 \(i\) 行，且第 \(i\) 行利用 \(2\times 2\) 的格子覆盖了第 \(i+1\) 行的零个格子/ \(1\sim 2\) 个格子/ \(3\sim 4\) 个格子的最小操作数，转移显然

#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,a[N],f[N][3];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j,k; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		for (i=0;i<=n;++i) f[i][0]=f[i][1]=f[i][2]=n;
		for (f[0][0]=i=0;i<n;++i) for (j=0;j<3;++j)
		{
			int c[6]={0,0,0,0,0,0};
			for (k=1;k<=min(5,a[i+1]);++k) c[k]=1;
			if (j==1) c[1]=c[2]=0; else if (j==2) c[3]=c[4]=0;
			auto calc=[&](void)
			{
				int sum=0; for (RI i=1;i<=5;++i) sum+=c[i];
				return min(sum,1);
			};
			f[i+1][0]=min(f[i+1][0],f[i][j]+calc());
			if (j!=1)
			{
				int t1=c[1],t2=c[2]; c[1]=c[2]=0;
				f[i+1][1]=min(f[i+1][1],f[i][j]+1+calc());
				c[1]=t1; c[2]=t2;
			}
			if (j!=2)
			{
				int t3=c[3],t4=c[4]; c[3]=c[4]=0;
				f[i+1][2]=min(f[i+1][2],f[i][j]+1+calc());
				c[3]=t3; c[4]=t4;
			}
		}
		//for (i=1;i<=n;++i) for (j=0;j<3;++j) printf("f[%d][%d] = %d\n",i,j,f[i][j]);
		printf("%d\n",min({f[n][0],f[n][1],f[n][2]}));
	}
	return 0;
}

E1. Catch the Mole(Easy Version) && E2. Catch the Mole(Hard Version)

很有意思的智慧题，比较考验直觉

一般这类问题第一个想到的就是二分，但在树上要进行二分就不太容易，因为不知道要在哪条链或者哪个子树询问

但树上有一个比较有二分性质的就是重心，我们每次找出当前询问点子树的重心，这样就能一次排除尽量多的点

不过话又说回来如果出题人有意构造数据，像菊花图之类的是找不到一个较为平衡的点的

但这题好在有一个将点往上跳的过程，要卡掉上述过程的图恰好需要满足点的分布较为均衡，那么此时子树的深度一定不大，很容易将目标点直接跳到根节点

因此我们有了一个大致的思路，先在子树内每次选择重心缩小范围，最后留出一部分询问在当前点到根的路径上确定点的位置即可（因为可能这个点之前还在我们确定的子树里，几次操作后又跑到外面去了，因此要最后确定一下位置）

由于这部分是一条链，因此可以二分处理，实测可以在 \(160\) 的限制内通过此题

#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=5005;
int t,n,x,y,anc[N],del[N],sz[N],len[N],cnt,cnt0; vector <int> v[N];
inline int ask(CI x)
{
	int r; printf("? %d\n",x); fflush(stdout);
	++cnt; scanf("%d",&r); cnt0+=(r==0); return r;
}
inline void answer(CI x)
{
	printf("! %d\n",x); fflush(stdout);
}
inline void DFS1(CI now=1,CI fa=0)
{
	len[now]=0; for (auto to:v[now]) if (to!=fa)
	anc[to]=now,DFS1(to,now),len[now]=max(len[now],len[to]+1);
}
inline void DFS2(vector <int>& vec,CI now)
{
	if (del[now]||len[now]<cnt0) return (void)(sz[now]=0);
	vec.push_back(now); sz[now]=1;
	for (auto to:v[now]) if (to!=anc[now]) DFS2(vec,to),sz[now]+=sz[to];
}
inline void DFS3(CI now)
{
	if (del[now]||len[now]<cnt0) return;
	del[now]=1; for (auto to:v[now]) if (to!=anc[now]) DFS3(to);
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),cnt=cnt0=0,i=1;i<=n;++i) v[i].clear(),del[i]=0;
		for (i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
		DFS1(); anc[1]=1; int cur=1;
		while (cnt<180-20)
		{
			vector <int> sbt; DFS2(sbt,cur);
			if (sz[cur]==1) break;
			int mn=1e9,pos=-1; for (auto x:sbt)
			{
				int tmp=max(sz[x],sz[cur]-sz[x]);
				if (tmp<mn) mn=tmp,pos=x;
			}
			if (ask(pos)) cur=pos; else DFS3(pos);
		}
		vector <int> path; path.push_back(cur);
		while (cur!=1) path.push_back(cur=anc[cur]);
		int l=0,r=path.size()-1;
		while (l<r-1)
		{
			int mid=l+r>>1;
			if (ask(path[mid])) r=mid;
			else l=mid+1,r=min((int)path.size()-1,r+1);
		}
		int lst=path[r]; bool flag=0;
		for (RI i=r-1;i>=l;--i)
		if (ask(path[i])==0) { answer(anc[lst]); flag=1; break; } else lst=path[i];
		if (!flag) answer(lst);
	}
	return 0;
}

Postscript

感觉最近 CF 打的好唐，每场都是前期狂出假算法，后期没时间暴毙了

标签：typedef,960,int,Codeforces,long,const,Div,include,define
From： https://www.cnblogs.com/cjjsb/p/18314685

相关文章

  • 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}......
  • 题解：Codeforces Round 960 (Div. 2) A
    A.SubmissionBaittimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputAliceandBobareplayingagameinanarray\(a\)ofsize\(n\).Theytaketurnstodooperations,withAlicestarting......
  • Codeforces Round 960 (Div. 2) 补题记录（A~D）
    打的稀烂，但是还是上分了（A考虑对值域做一个后缀和。若某一个后缀和的值是奇数那么先手就可以获胜。否则就不可以获胜。（我才不会告诉你我这题吃了一次罚时的）#pragmaGCCoptimize(3)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intmysqrt(intx){......
  • 使用牛顿法近似整数的 sqrt，ZeroDivisionError
    Sqrt(x)给定一个非负整数x，返回x的平方根，向下舍入到最接近的整数。返回的整数也应该是非负数。不得使用任何内置指数函数或运算符。例如，不要在c++中使用pow(x,0.5)或在c++中使用x**0.5python.示例1:输入：x=4输出：2解释：4的平方根是2，所......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99