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

Codeforces Round 968 (Div. 2)

时间：2024-09-05 20:03:09浏览次数：16  
标签：typedef int 968 Codeforces long Div include RI define

Preface

今天课比较少，就抽点时间补一下之前欠的 CF

这场总体来说题还算简单，E1 之前的题基本都是一眼，不过 E2 没往转化到区间不交的情况想，F 更是完全没想到 color coding，只能说太菜太菜

A. Turtle and Good Strings

不难发现只要比较开头和结尾的字符是否相同即可

#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; char s[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%s",&n,s+1);
		puts(s[1]!=s[n]?"YES":"NO");
	}
	return 0;
}

B. Turtle and Piggy Are Playing a Game 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=100005;
int t,n,a[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d",&n);
		for (RI i=1;i<=n;++i) scanf("%d",&a[i]);
		sort(a+1,a+n+1); printf("%d\n",a[n/2+1]);
	}
	return 0;
}

C. Turtle and Good Pairs

首先不难发现一个串不合法的充要条件为其形如 \(aaa\cdots bbb\cdots\)，即由两段相同的字符构成

要最大化合法的区间，只需要最小化不合法的区间，手玩后发现贪心地交错着放最优

具体地，从前往后每次放当前出现次数最多的字符即可，总复杂度 \(O(26\times n)\)

#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,c[30]; char s[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%s",&n,s+1);
		for (RI i=1;i<=n;++i) ++c[s[i]-'a'];
		for (RI i=1;i<=n;++i)
		{
			int mx=-1,ch;
			for (RI j=0;j<26;++j) if (c[j]>mx) mx=c[j],ch=j;
			--c[ch]; putchar(ch+'a');
		}
		putchar('\n');
	}
	return 0;
}

D1. Turtle and a MEX Problem (Easy Version)

经典套路 MEX，属于是看一眼就会了

对于一个序列 \(a_1,\dots,a_{l_i}\)，我们令 \(x=\operatorname{mex}(a_1,\dots,a_{l_i}),y=\operatorname{mex}(x,a_1,\dots,a_{l_i})\)

此时这个序列相当于可以将 \(x\) 变为 \(y\)；同时将非 \(x\) 的所有值变为 \(x\)

不难发现将所有的 \(y\) 求出最大值 \(S\) 后，所有 \(\le S\) 的数一定都能变为 \(S\)，因此就很好计算答案了

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

D2. Turtle and a MEX Problem (Hard Version)

D1 我们之所以能这么做是因为一个序列可以被用多次，而这里不行

考虑对于每个序列连边 \(x\to y\)，即可得到一个 DAG，很容易想到用类似拓扑排序的方法求出从每个数开始能走到的最大的数

但这样只考虑了顺着边走的情况，考虑把重置的情况加入

若某个点 \(i\) 只有一条出边，则任何数都可以变为 \(i\)，对于所有这类数取 \(\max\) 用以更新贡献

若某个点 \(i\) 有超过一条出边，则任何数都可以先变为 \(i\)，然后沿着 \(i\) 的有向边向后走到最大的数，对于所有这类数也取 \(\max\) 用以更新贡献

最后综合起来讨论一下即可

#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,m,l,a[N],vis[N],out[N],f[N]; vector <int> v[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d",&n,&m); int base=0,idx=0;
		for (RI i=1;i<=n;++i)
		{
			scanf("%d",&l);
			for (RI j=1;j<=l;++j)
			{
				scanf("%d",&a[j]);
				if (a[j]<=l+2) vis[a[j]]=1;
			}
			int mex=0; while (vis[mex]) ++mex;
			int smex=mex+1; while (vis[smex]) ++smex;
			++out[mex]; v[smex].push_back(mex);
			base=max(base,mex); idx=max(idx,smex);
			for (RI j=1;j<=l;++j)
			if (a[j]<=l+2) vis[a[j]]=0;
		}
		for (RI i=0;i<=idx;++i) f[i]=i;
		for (RI i=idx;i>=0;--i)
		for (auto j:v[i]) f[j]=max(f[j],f[i]);
		int mx=0; for (RI i=0;i<=idx;++i)
		if (out[i]>1) mx=max(mx,f[i]);
		LL ans=0; for (RI i=0;i<=min(idx,m);++i) ans+=max({f[i],mx,base});
		if (idx<m) ans+=1LL*(idx+1+m)*(m-idx)/2LL;
		printf("%lld\n",ans);
		for (RI i=0;i<=idx;++i) out[i]=0,v[i].clear();
	}
	return 0;
}

E1. Turtle and Inversions (Easy Version) && E2. Turtle and Inversions (Hard Version)

这两题思路差不太多，就放在一起讲了

首先要想到 E1 的做法，整体来看可以把数分为小数（用 \(0\) 表示）和大数（用 \(1\) 表示），此时每一个区间一定是由若干个 \(0\) 加上若干个 \(1\) 构成

定下一种 01 序列后考虑计算其贡献，首先所有的 01 之间都降序排列一定最优，而剩下的贡献只和该序列中 \(10\) 的对出现次数有关

考虑 DP，令 \(f_{i,j}\) 表示处理了前 \(i\) 个位置，此时前 \(i\) 个位置共有 \(j\) 个 \(1\) 时，序列中 \(10\) 的对的出现次数

转移分要求的区间以及没被 cover 的位置两种情况讨论下即可，根据定义还是非常直观的

现在的问题就是 E2 中区间不一定相离，其实也很好处理，考虑将其转化为相离的情况

若存在区间 \([l_1,r_1],[l_2,r_2](l_1\le l_2)\) 相交，则显然 \([l_1,l_2-1]\) 一定全为 \(0\)，\([r_1+1,r_2]\) 一定全为 \(1\)，此时只要考虑 \([l_2,r_1]\) 的情况即可

用此法可以将原来的限制转化为若干不相交的区间，以及一些以及确定了 01 的位置，再做上面的 DP 即可

总复杂度 \(O(n^2+m\log m)\)

#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,INF=1e9;
int t,n,m,pos[N],tp[N],f[N][N]; pi a[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d",&n,&m);
		for (RI i=1;i<=m;++i) scanf("%d%d",&a[i].fi,&a[i].se);
		if (!m) { printf("%d\n",n*(n-1)/2); continue; }
		for (RI i=1;i<=n;++i) pos[i]=tp[i]=-1;
		sort(a+1,a+m+1); int mnl,mxl,mnr,mxr;
		mnl=mxl=a[1].fi; mnr=mxr=a[1].se;
		bool flag=1;
		for (RI i=2;i<=m+1;++i)
		if (i==m+1||mxr<a[i].fi)
		{
			if (mnr<=mxl) { flag=0; break; }
			for (RI j=mnl;j<mxl;++j) tp[j]=0;
			for (RI j=mnr+1;j<=mxr;++j) tp[j]=1;
			pos[mxl]=mnr;
			mnl=mxl=a[i].fi; mnr=mxr=a[i].se;
		} else
		{
			mnl=min(mnl,a[i].fi); mxl=max(mxl,a[i].fi);
			mnr=min(mnr,a[i].se); mxr=max(mxr,a[i].se);
		}
		if (!flag) { puts("-1"); continue; }
		for (RI i=0;i<=n;++i) for (RI j=0;j<=n;++j) f[i][j]=-INF;
		f[0][0]=0; for (RI i=1;i<=n;++i)
		if (pos[i]!=-1)
		{
			for (RI j=0;j<i;++j)
			for (RI k=1;k<pos[i]-i+1;++k)
			f[pos[i]][j+k]=max(f[pos[i]][j+k],f[i-1][j]+(pos[i]-i+1-k)*j);
			i=pos[i];
		} else
		{
			if (tp[i]==1)
			{
				for (RI j=1;j<=i;++j)
				f[i][j]=max(f[i][j],f[i-1][j-1]);
			} else if (tp[i]==0)
			{
				for (RI j=0;j<i;++j)
				f[i][j]=max(f[i][j],f[i-1][j]+j);
			} else
			{
				for (RI j=0;j<=i;++j)
				f[i][j]=max(j>0?f[i-1][j-1]:-INF,f[i-1][j]+j);
			}
		}
		int ans=-1;
		for (RI i=0;i<=n;++i) ans=max(ans,f[n][i]+i*(i-1)/2+(n-i)*(n-i-1)/2);
		printf("%d\n",ans);
	}
	return 0;
}

F. Turtle and Three Sequences

好经典的 color coding 啊，有人明明知道这个东西却没想到，怎么回事呢

假设 \(b_i\) 的取值范围很小，则可以进行状压 DP，令 \(f_{i,j,mask}\) 表示已经处理了前 \(i\) 个位置，上一个选的 \(a\) 的值为 \(j\)，且选取的 \(b_i\) 对应的状压状态为 \(mask\) 对应的贡献最大值

不难发现在枚举 \(mask\) 的情况下这个 DP 和求 LIS 的基本一致，可以用树状数组优化

显然问题是 \(b_i\) 的取值范围太大了，但其实我们只要取 \(m\) 个数，\(m\) 的级别是很小的

因此考虑用 color coding，将每个 \([1,n]\) 的数随机映射到 \([0,m-1]\) 的一个数，映射之后再跑上面的状压 DP

考虑这样做一次得到正解的概率为 \(\frac{m!}{m^m}\)，跑足够多的次数后可以得到正确性很高的算法

令 color coding 的次数为 \(T\)，总复杂度 \(O(T\times 2^m\times n\log n)\)

#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=3005,T=300,INF=1e9;
int n,m,a[N],b[N],c[N],r[N];
class Tree_Array
{
	private:
		int bit[N];
	public:
		#define lowbit(x) (x&-x)
		inline void clear(void)
		{
			for (RI i=1;i<=n+1;++i) bit[i]=-INF;
		}
		inline void add(RI x,CI y)
		{
			for (++x;x<=n+1;x+=lowbit(x)) bit[x]=max(bit[x],y);
		}
		inline int get(RI x,int ret=-INF)
		{
			for (++x;x;x-=lowbit(x)) ret=max(ret,bit[x]); return ret;
		}
		#undef lowbit
}BIT[1<<5];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	srand(time(0)); scanf("%d%d",&n,&m);
	for (RI i=1;i<=n;++i) scanf("%d",&a[i]);
	for (RI i=1;i<=n;++i) scanf("%d",&b[i]);
	for (RI i=1;i<=n;++i) scanf("%d",&c[i]);
	int ans=-1; for (RI t=1;t<=T;++t)
	{
		for (RI i=1;i<=n;++i) r[i]=rand()%m;
		for (RI i=0;i<(1<<m);++i) BIT[i].clear();
		BIT[0].add(0,0);
		for (RI i=1;i<=n;++i)
		for (RI mask=0;mask<(1<<m);++mask)
		{
			int x=r[b[i]];
			if (!((mask>>x)&1)) continue;
			int cur=BIT[mask^(1<<x)].get(a[i])+c[i];
			if (mask==(1<<m)-1)
			{
				ans=max(ans,cur);
			}
			BIT[mask].add(a[i],cur);
		}
	}
	return printf("%d",ans),0;
}

Postscript

感觉我好像已经很久没有现场打 CF 了，真是越来越怠惰了

标签：typedef,int,968,Codeforces,long,Div,include,RI,define
From： https://www.cnblogs.com/cjjsb/p/18399166

相关文章

  • 《魔兽世界》divxdecoder.dll丢失怎么办？轻松解决指南
    在深入艾泽拉斯大陆的冒险旅途中，每一位玩家都希望拥有流畅且无碍的游戏体验。然而，技术问题偶尔会像突如其来的部落突袭一样打断我们的探索。其中，“divxdecoder.dll丢失”错误便是不少玩家可能遇到的一个小障碍。别担心，本文将为您提供一套简单易行的解决方案。divxdecoder.dll......
  • Codeforces Round 947 (Div. 1 + Div. 2) VP记录
    CodeforcesRound947(Div.1+Div.2)VP记录我是唐诗，我是唐诗，我是唐。场切：ABCE。笑点解析D是我不在场的GJ模拟赛的T1签到题。A找\(a_i<a_{i-1}\)然后按数量分讨即可。B最小值要取，不能被最小值表示出来的数的最小值要取，暴力即可。C先对相邻两个值的较小......
  • Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)
    A.ColourtheFlag题意：给定一个棋盘，一些格子已经染上黑白色，判断能否将剩下的格子染色，使得相邻格子不同色。输出构造。思路：考虑一个棋盘的合法染色方案只有两种，分别比较一下即可。提交记录B.HistogramUgliness题意：一个柱状图，权值定义为操作次数加上竖直方向的周长。一次......
  • 2024 Xiangtan University Summer Camp-Div.2
    A.二度树上的染色游戏因为题目保证了是二叉树，所以每次至多只需要选择一个子节点染成红色。所以可以贪心的选择红色权值小的子树即可。#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;usingldb=longdouble;consti32inf......
  • Codeforces Round 971 (Div. 4) ABCD题详细题解(C++,Python)
    前言:    本文为CodeforcesRound971(Div.4)ABCD题的题解，包含C++,Python语言描述，觉得有帮助或者写的不错可以点个赞    比赛打了没一半突然unrated了就不是很想继续写了,早起写个题解    (之前的div3也没复盘，哎真菜)目录题A:题目大意和解题......
  • Codeforces Round 969 (Div. 1)
    Preface暑假最后几天疑似有点摆过头了，训练也没咋训，CF也没咋打这周末就是网络赛了，虽然名额早就满了，但还是得写写题找下手感不然要被学弟暴打了这场由于是Div.1/2分场，补题就只写Div.1的题了A.IrisandGameontheTree首先考虑快速计算一个01串的贡献，不难发现一段相......
  • Codeforces Round 971 (Div. 4) E 题解析
    #E题Klee'sSUPERDUPERLARGEArray!!!题目描述思路：对于这道题，首先观察到题目求的是最小可能值，而且数据的范围是1e9范围，所以首先可以考虑的方法就是O(logn)的方法，而适合求最值的方法无疑就是二分搜索，可以通过二分来不断缩小答案的区间......
  • Codeforces Round 969 (Div. 1 + 2)
    A将序列转化为\(01\)串，奇数为\(1\)，偶数为\(0\)。容易发现两个\(0\)不能分在同一组，于是答案的上限取决于奇数的个数，并且容易构造方案达到这个上界，随便做做就行。B将序列排序后，发现不管怎么加，大小顺序不变，记录下最大值按题意模拟。C根据基本数论知识可得，操作等价于加上......
  • Codeforces Round 971 (Div. 4)
    A-Minimize!inlinevoidsolve(){ inta,b; cin>>a>>b; cout<<b-a<<'\n';}B-osu!maniainlinevoidsolve(){ intn; cin>>n; vector<string>a(n); for(auto&x:a){ cin>>x......
  • Codeforces Round 971 (Div. 4) A-G1
    Ab-a#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;mt19937rnd(time(0));#defineintlonglongtypedeftuple<int,int,int>tp;#definexfirst#defineysecondtypedefpair<int,int>pii;typedefpair<double,double......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99