首页 > 其他分享 >Codeforces Round 934 (Div. 1)

Codeforces Round 934 (Div. 1)

时间：2024-03-17 16:34:41浏览次数：20  
标签：typedef const int Codeforces long 934 Div include define

Preface

真是一场酣畅淋漓的掉分啊，一场回到解放前了属于是

这把虽然有不可抗力的原因（电脑半路蓝屏了），但不知道为什么状态就特别差

A刚开始没清空干净WA了2发后就心态崩了，然后加上头疼难耐B题也没看出关键trick直接写了个不仅错还巨难写的东西

不过yysy这场Guess的成分是否有点太高了，感觉和这场的出题人没啥相性，BCD一个猜不出来怎么回事呢

A. MEX Game 1

傻逼题，感觉白天VP的时候刚遇到这种弱智的清空没清干净的情况，然后晚上又发病了

对于那些出现次数\(\ge 2\)的数，不管怎么样Alice总能取到它们

而由于先手的缘故，Alice可以保证将一个出现次数为\(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,x,c[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=0;i<=n;++i) c[i]=0;
		for (i=1;i<=n;++i) scanf("%d",&x),++c[x];
		bool fir_turn=1; for (i=0;i<=n;++i)
		{
			if (c[i]==0) { printf("%d\n",i); break; }
			if (c[i]==1)
			{
				if (!fir_turn) { printf("%d\n",i); break; }
				else fir_turn=0;
			}
		}
	}
	return 0;
}

B. Non-Palindromic Substring

唉看不出结论被狠狠吊打力，以下选自赛后徐神的指点

你想想

如果 k 小于区间长度又大于一

所有长度为 k 的子串还得是回文串

这是很难的

手玩一下不难发现如果k是偶数

那么这个字符串一定只能只包含一种字符

如果k是奇数则奇数位为同一种字符，偶数位为同一种字符

因此本题本质上极其傻逼，在特判掉\(k=r-l+1\)的情况后（随便拿个Hash维护一下），对于\(k\in[2,r-l+1)\)的所有情况：

  • \(k\)为偶数时，不合法的充要条件为区间内所有字符都相同
  • \(k\)为奇数时，不合法的充要条件为区间内奇数位置上所有字符都相同，偶数位置上所有字符都相同

这两种情况都可以很容易地维护

#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,q,l,r,nxt[N],pnxt[N]; char s[N];
const int mod1=998244353,mod2=1e9+7;
struct Hasher
{
	int x,y;
	inline Hasher(CI X=0,CI Y=0)
	{
		x=X; y=Y;
	}
	inline LL get_val(void)
	{
		return ((1LL*x)<<31LL)|(1LL*y);
	}
	friend inline bool operator == (const Hasher& A,const Hasher& B)
	{
		return A.x==B.x&&A.y==B.y;
	}
	friend inline Hasher operator + (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x+B.x)%mod1,(A.y+B.y)%mod2);
	}
	friend inline Hasher operator - (const Hasher& A,const Hasher& B)
	{
		return Hasher((A.x-B.x+mod1)%mod1,(A.y-B.y+mod2)%mod2);
	}
	friend inline Hasher operator * (const Hasher& A,const Hasher& B)
	{
		return Hasher(1LL*A.x*B.x%mod1,1LL*A.y*B.y%mod2);
	}
}pw[N],H[N],R[N];
const Hasher seed=Hasher(31,131);
inline Hasher geth(CI l,CI r)
{
	return H[r]-H[l-1]*pw[r-l+1];
}
inline Hasher getr(CI l,CI r)
{
	return R[l]-R[r+1]*pw[r-l+1];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%d%s",&n,&q,s+1);
		for (pw[0]=Hasher(1,1),i=1;i<=n;++i) pw[i]=pw[i-1]*seed;
		for (H[0]=Hasher(),i=1;i<=n;++i) H[i]=H[i-1]*seed+Hasher(s[i],s[i]);
		for (R[n+1]=Hasher(),i=n;i>=1;--i) R[i]=R[i+1]*seed+Hasher(s[i],s[i]);
		for (nxt[n]=n+1,i=n-1;i>=1;--i)
		if (s[i]!=s[i+1]) nxt[i]=i+1; else nxt[i]=nxt[i+1];
		for (pnxt[n]=pnxt[n-1]=n+1,i=n-2;i>=1;--i)
		if (s[i]!=s[i+2]) pnxt[i]=i+2; else pnxt[i]=pnxt[i+2];
		for (i=1;i<=q;++i)
		{
			scanf("%d%d",&l,&r);
			if (nxt[l]>r) { puts("0"); continue; }
			int k=(r-l+1)/2; LL ans=1LL*(2+2*k)*k/2;;
			if (pnxt[l]<=r||pnxt[l+1]<=r)
			{
				k=(r-l)/2; ans+=1LL*(3+2*k+1)*k/2;
				if (geth(l,r)==getr(l,r)) ans-=r-l+1;
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}

C. Tree Compass

这题当时等电脑修的时候感觉就等价于把直径染色，但因为前面的题都没出就也没去写，赛后发现真是这样

首先考虑找出图中的一条直径，设其长度为\(len\)

根据直径的性质我们感觉只要合理安排把直径上的点都染色其余的点基本都能染上

对于直径长度为奇数的情况，显然直接对中间的拿个点进行\(0\sim \frac{len-1}{2}\)操作即可

而当\(len\bmod 4=2\)的情况也类似，在中间的两个点中任选一个进行\(0\sim \frac{len}{2}\)操作即可

但是对于\(4\mid len\)的情况就有点特殊了，比如当\(len=4\)时（设四个点编号依次为\(1,2,3,4\)），操作\((2,1),(3,1)\)即可完成染色

手玩一下此时我们可以对中间的两个点，每个点分别进行\(1\sim \frac{len}{2}\)操作（且染色距离为奇数）即可

#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,x,y,dis[N],pre[N]; vector <int> v[N];
inline void DFS(CI now,CI fa=0)
{
	pre[now]=fa; for (auto to:v[now]) if (to!=fa) dis[to]=dis[now]+1,DFS(to,now);
}
int 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) v[i].clear();
		for (i=1;i<n;++i) scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
		for (dis[1]=0,DFS(1),x=i=1;i<=n;++i) if (dis[i]>dis[x]) x=i;
		for (dis[x]=0,DFS(x),y=i=1;i<=n;++i) if (dis[i]>dis[y]) y=i;
		vector <int> path; for (;y!=x;y=pre[y]) path.push_back(y); path.push_back(x);
		if (path.size()%2==1)
		{
			printf("%d\n",path.size()/2+1);
			for (i=0;i<path.size()/2+1;++i) printf("%d %d\n",path[path.size()/2],i);
		} else
		{
			if (path.size()%4==2)
			{
				printf("%d\n",path.size()/2+1);
				for (i=0;i<path.size()/2+1;++i) printf("%d %d\n",path[path.size()/2],i);
			} else
			{
				printf("%d\n",path.size()/2);
				for (i=1;i<=path.size()/2;i+=2)
				printf("%d %d\n",path[path.size()/2],i),printf("%d %d\n",path[path.size()/2-1],i);
			}
		}
	}
	return 0;
}

D1. Counting Is Fun (Easy Version)

唉Counting，但是得先猜结论

不妨令\(a_0=a_{n+1}=0\)，则手玩一波我们发现一个序列合法的充要条件等价于\(\forall i\in[1,n],a_{i-1}+a_{i+1}\ge a_i\)

证明的话感觉可以通过分解把所有长度大的操作区间分解为长度为\(2\)或\(3\)的区间，感性理解一下会发现上面的相当于是个必要条件，但充分性还是不会证，到时候看看官方题解吧

知道了这点后这题就很简单了，大力DP设\(f_{i,j,k}\)表示处理了前\(i\)个数，且\(a_{i-1}=j,a_{i}=k\)的方案数，拿个前缀和优化一下转移即可做到\(O(n^3)\)

#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=405;
int t,n,m,mod,f[N][N][N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j,k; scanf("%d%d%d",&n,&m,&mod);
		for (i=0;i<=n+1;++i) for (j=0;j<=m;++j) for (k=0;k<=m;++k) f[i][j][k]=0;
		for (f[1][0][0]=i=1;i<=n;++i) for (j=0;j<=m;++j)
		{
			for (k=1;k<=m;++k) (f[i][j][k]+=f[i][j][k-1])%=mod;
			for (k=0;k<=m;++k) if (f[i][j][k])
			(f[i+1][k][max(0,k-j)]+=f[i][j][k])%=mod;
		}
		int ans=0; for (i=0;i<=m;++i) (ans+=f[n+1][i][0])%=mod;
		printf("%d\n",ans);
	}
	return 0;
}

Postscript

好好好正愁没号打Div2了，这下好了又可以回到熟悉的地方了

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

相关文章

  • 每日一题 第七期 Codeforces Round 929 (Div. 3) Editorial
    TurtleTenacity:ContinualModsD.TurtleTenacity:ContinualModstimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputGivenanarraya......
  • Codeforces Round 934 (Div. 2)
    CodeforcesRound934(Div.2)A-DestroyingBridges解题思路:完全图每个点的连边数为\(n-1\)。\(k<n-1\)：都可到达。\(k\geqn-1\)：将点\(1\)的边删完，只能呆在点\(1\)。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=......
  • codeforce Round 934 div2 个人题解（A~C）
    A.DestroyingBridges时间限制:1秒内存限制:256兆输入:标准输入输出:标准输出有$n$个岛屿，编号为$1,2,…,n$。最初，每对岛屿都由一座桥连接。因此，一共有$\frac{n(n-1)}{2}$座桥。Everule住在岛屿$1$上，喜欢利用桥梁访问其他岛屿。Dominater有能力摧毁最多$k$座......
  • 5 分钟小工具：使用 dive 分析 docker 镜像
    需求拿到一个镜像之后，我想知道：分层查看镜像里都有哪些文件各层使用了什么命令构建的这个镜像镜像里比较大的文件有哪些（可能需要优化）dive工具介绍dive工具可以做这些分析。dive的github地址是 wagoodman/dive，小巧玲珑，MIT开源协议，42.9k的star。它的介绍是这么一......
  • Codeforces Round 908 (Div. 2)
    CodeforcesRound908(Div.2)A-SecretSport解题思路:有一说一，没看很懂，感觉最后赢的就是赢了。。。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingpiii=pair<ll,pa......
  • Codeforces 1948G MST with Matching
    因为贡献是两个之和，考虑固定下一个，求解另一个的最优。\(\text{MST}\)似乎找不到什么好的办法固定，便考虑固定下最大匹配。对于树的最大匹配，考虑到因为树也是二分图，所以树的最大匹配\(=\)最小点覆盖。考虑如果知道了最小点覆盖内的点，那就说明如果一条边两个端点都不在点集中，是......
  • Educational Codeforces Round 163 A-E
    A.SpecialCharacters构造。形如\(A\)和\(B\)这类单个字符构成的字符串对答案的贡献为\(0\)，而\(AA\)和\(AAAA\)这类多个相同字符构成的字符串对答案的贡献固定为\(2\)​，则无法构造出奇数值，由第二类字符串拼接即可构造出偶数值。时间复杂度：\(O(n)\)。#include<bit......
  • Codeforces 1948E Clique Partition
    考虑到有\(|i-j|\)，所以肯定是让相邻的一部分在一个团里。考虑构造出一个最长长度的，后面类似复制几遍即可。考虑到\(|k-1|=k-1\)，且因为\(a_i\)为一个排列，差的绝对值至少为\(1\)，所以只考虑两端最长长度也只可能为\(k\)。不妨先假设最长长度为\(k\)来构造。那么......
  • Codeforces-1005C
    https://codeforces.com/problemset/problem/1005/C一、代码目录#include<bits/stdc++.h>usingnamespacestd;voidsolve(){inta[122222],n,ans=0;map<int,int>m;scanf("%d",&n);for(inti=0;i<n;i++){......
  • Educational Codeforces Round 163 (Rated for Div. 2)
    EducationalCodeforcesRound163(RatedforDiv.2)A-SpecialCharacters解题思路:一个相同的连续段会贡献两个特殊字符，所以答案一定是偶数，找个不同的数分隔开即可。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99