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

Codeforces Round 862 (Div. 2)

时间：2023-04-14 21:58:22浏览次数：57  
标签：CI include int 862 Codeforces fa Div now define

Preface

补题ing

这场思路挺顺的，早上上课的时候口胡了前5题下午都一发写过了

然后想了30min的F1也Rush出来了，不过F2还是有点仙的做不动

A. We Need the Zero

SB题，首先判断是否所有数的异或和等于\(0\)

若不为\(0\)且\(n\)为偶数则无解，否则答案就是这个异或和本身

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n,x,ret;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),ret=0,i=1;i<=n;++i) scanf("%d",&x),ret^=x;
		if (ret&&n%2==0) puts("-1"); else printf("%d\n",ret);
	}
	return 0;
}

B. The String Has a Target

SB题，我们找到标号最小的那个字符出现的最后一个位置，然后把它换到最前面即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,mi,pos; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%s",&n,s+1),mi=1e9,i=1;i<=n;++i)
		if (s[i]<=mi) mi=s[i],pos=i;
		for (putchar(s[pos]),i=1;i<=n;++i)
		if (i!=pos) putchar(s[i]); putchar('\n');
	}
	return 0;
}

C. Place for a Selfie

怎么我不打的场的C题都是傻逼题啊恼

显然根据判别式\((b-k)^2-4ac<0\)，我们只要找到距离每个\(b\)最近的\(k\)来最小化左边即可，即找出\(b\)在\(k\)数组中的前驱和后继

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,INF=1e9;
int t,n,m,slp[N],a,b,c;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&slp[i]);
		for (sort(slp+1,slp+n+1),slp[0]=-INF,slp[n+1]=INF,i=1;i<=m;++i)
		{
			scanf("%d%d%d",&a,&b,&c);
			int pre=slp[upper_bound(slp+1,slp+n+1,b)-slp-1];
			int nxt=slp[lower_bound(slp+1,slp+n+1,b)-slp];
			auto sqr=[&](CI x) { return 1LL*x*x; };
			if (pre!=-INF&&sqr(b-pre)-4LL*a*c<0) { printf("YES\n%d\n",pre); continue; }
			if (nxt!=-INF&&sqr(b-nxt)-4LL*a*c<0) { printf("YES\n%d\n",nxt); continue; }
			puts("NO");
		}
	}
	return 0;
}

D. A Wide, Wide Graph

刚开始手玩样例玩错了给第一眼的做法弃掉了，后来再验证了一遍发现我是个脑瘫（因为没带草稿纸上课纯靠脑中建图想）

首先我们很容易想到我们枚举每个点\(x\)，考虑这个点在\(k\)等于多少时才是独立的

很显然我们设距\(x\)最远的点到\(x\)的距离为\(dis_x\)，则当\(k\le dis_x\)时这个点的贡献就要被消去，因此很容易统计答案

那现在问题就是要算出每个点的\(dis_x\)了，很显然可以用换根DP，记录一下每个点在子树内最远和次远的可达点

然后在换根是讨论一下子树外传进去的部分是哪条链即可，总复杂度\(O(n)\)

PS：好像有两遍BFS找出答案的做法，但是我没仔细看原理的说

#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,INF=1e9;
int n,x,y,mx[N],smx[N],c[N],ans[N],sfx; vector <int> v[N];
inline void DFS1(CI now=1,CI fa=0)
{
	for (int to:v[now]) if (to!=fa)
	{
		if (DFS1(to,now),mx[to]+1>mx[now])
		smx[now]=mx[now],mx[now]=mx[to]+1; else
		if (mx[to]+1>smx[now]) smx[now]=mx[to]+1;
	}
}
inline void DFS2(CI now=1,CI fa=0,CI outer=0)
{
	++c[max(outer,mx[now])];
	for (int to:v[now]) if (to!=fa)
	{
		if (mx[to]+1==mx[now]) DFS2(to,now,max(outer,smx[now])+1);
		else DFS2(to,now,max(outer,mx[now])+1);
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<n;++i)
	scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
	for (DFS1(),DFS2(),i=n;i;--i) sfx+=c[i],ans[i]=min(n,n-sfx+1);
	for (i=1;i<=n;++i) printf("%d ",ans[i]);
	return 0;
}

E. There Should Be a Lot of Maximums

woc后悔啊早知道早点打这场比赛了，如果复习了Dsu on Tree的板子上周蓝桥杯的E就随便切了

感觉这题用Dsu on Tree做可以说是毫无思维含量了（额话说这个算法本来好像就和莫队一样被叫做“优雅的暴力”来着）

用桶统计下子树内和子树外每个颜色出现的次数，然后把出现次数大于等于\(2\)的扔到multiset里维护即可

总复杂度是\(O(n\log^2n)\)的，好像可以优化到一个\(\log\)但没太大必要的说

PS：Tutorial的做法挺有意思的，首先我们发现当一个颜色出现次数大于等于\(3\)时不管怎么分它一定能造成贡献

那我们只要处理所有的出现次数等于\(2\)的颜色对即可，不难发现就是个判断某条边在哪些路径上的问题，经典树上差分即可

这里懒了只贴上面的做法了的代码了

#include<cstdio>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<utility>
#define RI register int
#define CI const int&
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair <int,int> pi;
const int N=100005;
int n,x,y,a[N],ans[N],sz[N],son[N]; map <pi,int> hsh; vector <int> v[N];
class Color_Counter
{
	private:
		map <int,int> bkt; multiset <int> s;
	public:
		inline void add(CI x)
		{
			if (++bkt[x]==2) s.insert(x);
		}
		inline void del(CI x)
		{
			if (--bkt[x]==1) s.erase(s.find(x));
		}
		inline int get(void)
		{
			return s.empty()?0:*(--s.end());
		}
}T[2];
inline void DFS(CI now=1,CI fa=0)
{
	sz[now]=1; for (int to:v[now]) if (to!=fa)
	if (DFS(to,now),sz[now]+=sz[to],sz[to]>sz[son[now]]) son[now]=to;
}
inline void travel(CI now,CI fa,CI tp)
{
	T[tp].add(a[now]); T[tp^1].del(a[now]);
	for (int to:v[now]) if (to!=fa) travel(to,now,tp);
}
inline void DSU(CI now=1,CI fa=0,CI flag=1)
{
	for (int to:v[now]) if (to!=fa&&to!=son[now]) DSU(to,now,0);
	if (son[now]) DSU(son[now],now,1);
	for (int to:v[now]) if (to!=fa&&to!=son[now]) travel(to,now,1);
	T[0].del(a[now]); T[1].add(a[now]); ans[hsh[mp(now,fa)]]=max(T[0].get(),T[1].get());
	if (!flag) travel(now,fa,0);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<n;++i)
	scanf("%d%d",&x,&y),v[x].pb(y),v[y].pb(x),hsh[mp(x,y)]=hsh[mp(y,x)]=i;
	for (i=1;i<=n;++i) scanf("%d",&a[i]),T[0].add(a[i]);
	for (DFS(),DSU(),i=1;i<n;++i) printf("%d\n",ans[i]);
	return 0;
}

F1. Survival of the Weakest (easy version)

很有意思的一个题，暴力本身都比较有意思的说

一个显而易见的事情是如果暴力计算数字的范围会大爆炸，考虑怎么把它们搞到可存储的范围内

我们发现每次操作选取的依据仅仅为每个数之间的相对大小，同时最后的答案是有原来序列中的多少个数组成的也是确定的

因此我们不妨把序列中所有数都减去最小的那个，然后把最小的那个的贡献单独先算上去，系数就是\(2\)的若干次幂

但是如果直接暴力搞是\(O(n^3)\)的，考虑每次\(F\)的计算次数怎么减少

由于这是个在\(O(n^2)\)级别的方案中选出\(O(n)\)种，同时由于方案间存在着严格的偏序关系

如下图所示，当我们选择了某个方案\(a_x+a_y\)时，则所有\(a_i+a_j(i\le x\and j\le y)\)的方案都一定也入选了

放在图上就会发现，如果我们选了第\(i\)行的某个\(a_i\)，则它能选取的\(a_j\)必须有\(j\le \lceil \frac{n}{i}\rceil\)，不然我们把上面的点都算上去一定是超过\(n\)个了

因此我们可以把枚举方案这部分复杂度优化成\(O(n\log n)\)，因此总复杂度就是\(O(n^2\log n)\)的

#include<cstdio>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<utility>
#define RI register int
#define CI const int&
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair <int,int> pi;
const int N=100005;
int n,x,y,a[N],ans[N],sz[N],son[N]; map <pi,int> hsh; vector <int> v[N];
class Color_Counter
{
	private:
		map <int,int> bkt; multiset <int> s;
	public:
		inline void add(CI x)
		{
			if (++bkt[x]==2) s.insert(x);
		}
		inline void del(CI x)
		{
			if (--bkt[x]==1) s.erase(s.find(x));
		}
		inline int get(void)
		{
			return s.empty()?0:*(--s.end());
		}
}T[2];
inline void DFS(CI now=1,CI fa=0)
{
	sz[now]=1; for (int to:v[now]) if (to!=fa)
	if (DFS(to,now),sz[now]+=sz[to],sz[to]>sz[son[now]]) son[now]=to;
}
inline void travel(CI now,CI fa,CI tp)
{
	T[tp].add(a[now]); T[tp^1].del(a[now]);
	for (int to:v[now]) if (to!=fa) travel(to,now,tp);
}
inline void DSU(CI now=1,CI fa=0,CI flag=1)
{
	for (int to:v[now]) if (to!=fa&&to!=son[now]) DSU(to,now,0);
	if (son[now]) DSU(son[now],now,1);
	for (int to:v[now]) if (to!=fa&&to!=son[now]) travel(to,now,1);
	T[0].del(a[now]); T[1].add(a[now]); ans[hsh[mp(now,fa)]]=max(T[0].get(),T[1].get());
	if (!flag) travel(now,fa,0);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<n;++i)
	scanf("%d%d",&x,&y),v[x].pb(y),v[y].pb(x),hsh[mp(x,y)]=hsh[mp(y,x)]=i;
	for (i=1;i<=n;++i) scanf("%d",&a[i]),T[0].add(a[i]);
	for (DFS(),DSU(),i=1;i<n;++i) printf("%d\n",ans[i]);
	return 0;
}

F2. Survival of the Weakest (hard version)

正解的证明很有意思也很好懂，这里建议直接看官方的Tutorial，还是很好理解的

大致思路就是通过讨论在前面补一个\(0\)是否会改变答案来分类讨论，最后得出数组中最大的元素每两次操作就会减半

因此在\(K=2\times \log a_n=64\)次操作后所有数都会衰减到\(0\)，因此可以直接搞了

不过注意这里操作的次数是指会让最大的数发生实质变化的操作，因此还要对原来暴力的做法稍作修改，具体看代码

总复杂度\(O(n\times k\log k)\)

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=1e9+7,K=64;
int n,x,ans,pw[N]; vector <int> a,b;
inline void resolve(vector <int>& v)
{
	int mi=v[0]; (ans+=1LL*mi*pw[n-1]%mod)%=mod; for (int &x:v) x-=mi;
}
inline void solve(vector <int>& v,CI tp)
{
	--n; vector <int> t; int len=v.size(); RI i,j;
	for (i=0;i<len;++i) for (j=i+1;j<min(len,len/(i+1)+1);++j) t.push_back(v[i]+v[j]);
	sort(t.begin(),t.end()); vector <int> nv;
	for (i=0;i<len-tp;++i) nv.push_back(t[i]);
	resolve(nv); v=nv;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&x),a.push_back(x);
	for (sort(a.begin(),a.end()),pw[0]=i=1;i<=n;++i) pw[i]=2LL*pw[i-1]%mod;
	for (i=0;i<min(n,K);++i) b.push_back(a[i]); resolve(b);
	while (b.size()<n)
	{
		if (b[1]+b[2]>b.back()) solve(b,1),solve(b,1); else solve(b,0);
	}
	while (n>1) solve(b,1); (ans+=b[0])%=mod;
	return printf("%d\n",ans),0;
}

Postscript

感觉验证了一个定理，只要我现场打的比赛就会挂的很惨，补题的比赛怎么写都是1A

有点难顶的说

标签：CI,include,int,862,Codeforces,fa,Div,now,define
From： https://www.cnblogs.com/cjjsb/p/17320048.html

相关文章

  • [Educational Codeforces Round 118 (Rated for Div. 2)]题解
    A题意：给定两个数，每一个数有两个属性，第一个属性是p1,第二个属性是p2.表示这个数有p2个后缀0.这个数本身等于p1后面加p2个0.问给你两个这种数，判断大小。思路：赛场上想到的：如果最终的长度不一样，可以直接根据长度判断。如果相等，就把后缀0加上直接比较大小就可以（比较字典序的大小），但......
  • Educational Codeforces Round 110 (Rated for Div. 2) C. Unstable String（状态机）
    https://codeforces.com/contest/1535/problem/C题目大意：给定一个字符串s，由10？组成：？每次都可以任意替换成0或者1问我们这个子字符串中，能够组成010101这样两两互不相等的字符串的数量最大是多少？input30?10????10??1100output8625#include<bits/stdc++.h>usin......
  • Educational Codeforces Round 120 (Rated for Div. 2)
    题目链接C核心思路这是一个很好的二分的题目，首先我们判断题目可不可二分，很显然是可以的把。因为假设我们x是可以的话，x+1...肯定也是可以的，但是x-1,x-2....这些又是不可以的。好，接下来思考二分刚开始的左右边界，左边届很好想，关键是右边界。这个其实也不难。因为我们最坏肯定是全......
  • CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)
    CodeTONRound2(Div.1+Div.2,Rated,Prizes!)A.Two0-1Sequencesvoidsolve(){intn=read(),m=read(),ans=1;strings,t;cin>>s>>t;//cout<<s<<t<<endl;for(inti=t.size()-1,j=s.size()-1;i>=1&......
  • Codefroces Round #863(div.3)---E
    题目：Problem-E-Codeforces题意：有一个序列a，a中的每个元素的每一位都不为4，问序列中第k个数字是多少。分析：可以用数位dp查询出1-r中有多少个满足条件的数字，通过二分r找到结果。代码：#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineendl'\n'u......
  • Codeforces Round #289 Div. 2 解题报告 A.B.C.E
    A-MaximuminTable纯递推。代码如下：#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>#include<set>#include<stdio.h>usingn......
  • Codeforces Round #290 (Div. 2) 解题报告 A.B.C.D.
    A-FoxAndSnake模拟。代码如下：#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>#include<set>#include<stdio.h>usingnames......
  • Codeforces Round #287 (Div. 2) 解题报告 A.B.C.D.E
    这次的CF挺水的，当时B题犯了一个很SB的错误，浪费了好多时间，所以D和E也没来得及看。sad，。。A-AmrandMusic水题，从小的开始选。代码如下：#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>......
  • Codeforces Round #286 (Div. 2) C题 Mr. Kitayuta, the Treasure Hunter （DFS+记忆化D
    题目地址：http://codeforces.com/contest/505/problem/C从d点开始，每个点都有三个方向，形成了一棵树，那么就从跟结点开始进行dfs查找，dp数组记录当前的点和长度，当这两个条件相同的时候，显然，后面的子树是完全相同的，于是用记忆化来优化。代码如下：#include<iostream>#include<string.h>#......
  • codeforces #185 A Plant（矩阵快速幂+递推）
    题目地址：http://codeforces.com/problemset/problem/185/A通过这个题终于找回了点找递推公式的信心。。TAT。。不过真心感觉CF的题目质量都真不错。。。首先，第n个图形的上方，左下方，右下方的三个大三角形是跟第n-1个是一模一样的，所以是3*f(n-1)。然后只剩下中间一个倒着的大三角形了，......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99