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

Codeforces Round 912 (Div. 2)

时间：2023-12-06 19:47:17浏览次数：31  
标签：typedef now int Codeforces long Div include 912 define

Preface

这场题莫名很对我胃口，因为F是个究极套路题，还是我最拿手的2-SAT，想+写不到半小时就搞定了

然后E的核心思想和上周末VP的一场省赛的题一样，因此看一眼就会了

唯一抽象的是D2要用对超集的sosdp，由于之前没写过就不知道还能这么搞

A. Halloumi Boxes

当\(k\ge 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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=105;
int t,n,k,a[N];
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,&k),i=1;i<=n;++i) scanf("%d",&a[i]);
		bool flag=1; for (i=1;i<n;++i) if (a[i]>a[i+1]) flag=0;
		puts(flag||k>=2?"YES":"NO");
	}
	return 0;
}

B. StORage room

设\(a_i=\operatorname{AND}_{j\ne i} M_{i,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 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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1005;
int t,n,a[N],b[N][N];
int 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 (j=1;j<=n;++j) scanf("%d",&b[i][j]);
		for (i=1;i<=n;++i) for (a[i]=(1<<30)-1,j=1;j<=n;++j)
		if (i!=j) a[i]&=b[i][j]; bool flag=1;
		for (i=1;i<=n&&flag;++i) for (j=1;j<=n&&flag;++j)
		if (i!=j&&(a[i]|a[j])!=b[i][j]) flag=0;
		if (!flag) { puts("NO"); continue; }
		for (puts("YES"),i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
	}
	return 0;
}

C. Theofanis' Nightmare

刚开始没想到关键点还卡了一会，太菜太菜

不妨给贡献的计算方式换个形式，设\(b_i\)表示数\(i\)前面的分隔符的数量，则答案为\(\sum_{i=1}^n a_i\times b_i\)

考虑是否在\(i\)的前面插入分隔符，带来的影响其实就是\([i,n]\)中所有数的和

因此不难发现所有后缀和\(\ge 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 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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,a[N],b[N],sfx[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]),b[i]=0;
		for (sfx[n]=a[n],i=n-1;i>=1;--i) sfx[i]=sfx[i+1]+a[i];
		for (i=1;i<=n;++i) if (sfx[i]>=0) b[i]=1;
		int ans=0; for (b[1]=1,i=1;i<=n;++i) b[i]+=b[i-1],ans+=a[i]*b[i];
		printf("%lld\n",ans);
	}
	return 0;
}

D1. Maximum And Queries (easy version)

D1就是想一个很trivial的贪心思路

首先发现若\(k+\sum a_i\ge 2^{20}\times n\)，则答案为\(\lfloor\frac{k+\sum a_i}{n}\rfloor\)，否则考虑从高位到低位确定答案的每一位

若当前枚举的是第\(k\)位，若\(a_i\)该位为\(1\)则无需操作，否则需要将\(a_i\)的低位全部清\(0\)，补足到第\(k\)位的进位

D1的话只要\(O(nq\times \log a_i)\)模拟这个过程即可，代码略

D2. Maximum And Queries (hard version)

这题比EF都难的说……

考虑保留D1做法中从高位到低位枚举的过程，考虑怎么优化统计贡献的部分

若当前枚举的是第\(k\)位，首先考虑那些在之前更高的位就进行过操作导致后面的位被清空的数，这些数一定要付出\(2^k\)的代价

那么怎么样的数字满足上述性质呢？手玩一下会发现设当前答案为\(ans\)，那么那些不包含\(ans\)作为子集的数会有贡献，即不是\(ans\)的超集的数会有贡献

这部分可以sosdp处理，只要把原来求子集的转移从\(0\to 1\)改成从\(1\to 0\)即可

对于剩下的数字，如果它是\(ans|(2^k)\)的超集，则不需要额外操作，否则某个数需要操作的数量就是\(2^k\)减去\(k\)以下位的和

同理我们可以用sosdp求出在某一位以下的是某个数超集的数的贡献，具体实现可以看代码

总复杂度\(O((n+q)\times \log^2 a_i)\)

#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1e6+5;
int n,q,a[N],k,sum,g[1<<20],f[20][1<<20];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%lld%lld",&n,&q),i=1;i<=n;++i)
	scanf("%lld",&a[i]),sum+=a[i],++g[a[i]];
	for (i=0;i<20;++i) for (j=0;j<(1<<20);++j)
	if ((j>>i)&1) g[j^(1<<i)]+=g[j];
	for (k=0;k<20;++k)
	{
		int S=(1<<k+1)-1;
		for (i=1;i<=n;++i) f[k][a[i]]+=(a[i]&S);
		for (i=0;i<20;++i) for (j=0;j<(1<<20);++j)
		if ((j>>i)&1) f[k][j^(1<<i)]+=f[k][j];
	}
	while (q--)
	{
		if (scanf("%lld",&k),(k+sum)/n>=(1<<20))
		{
			printf("%lld\n",(k+sum)/n); continue;
		}
		int ans=0; for (i=19;i>=0;--i)
		{
			int c1=g[ans],c2=g[ans|(1<<i)];
			int tmp=(n-c1)*(1<<i)+(c1-c2)*(1<<i)-(f[i][ans]-f[i][ans|(1<<i)]);
			if (tmp<=k) k-=tmp,ans|=(1<<i);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

E. Geo Game

这题思路啥的都很顺畅

首先不难发现其实每个点的贡献只和其\((x\&1)\oplus (y\&1)\)的值有关，因此实际上只有两种点，我们根据它上面的值将其分为\(0/1\)类点

现在问题抽象为，给定一个开头确定的\(01\)串，现在要把若干个\(0/1\)放在后面，而最后答案的奇偶性只和这个\(01\)串相邻元素中不同的pair个数的奇偶性有关

然后这个问题有个经典的结论就是一个\(01\)串相邻元素中不同的pair个数的奇偶性只和这个串的开头和结尾的字符有关，若两个字符相同最后的pair就是偶数，反之亦然

知道了这个我们就很好设计策略了，只要想办法把序列的结尾控制成我们想要的即可

设\(n\)个点中\(0\)类点的个数为\(x\)，\(1\)类点的个数为\(y\)，简单分类讨论下：

  • 若\(x\ne y\)，则无论我们先手还是后手，只要一直拿初始数量较少的那类点，即可保证结尾的是哪类点，根据起点终点是否相同判断拿先手还是后手即可
  • 若\(x=y\)，手玩一下发现可以选先手，每次拿和起点类型不同的那类点，即可保证最后结尾的点类型和起始点相同

用set模拟一下即可

#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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int t,n,x,y;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; scanf("%d%d%d",&n,&x,&y); int s=(x&1)^(y&1);
		set <int> p[2]; for (i=1;i<=n;++i)
		scanf("%d%d",&x,&y),p[(x&1)^(y&1)].insert(i);
		auto output=[&](CI id)
		{
			printf("%d\n",*p[id].begin()); fflush(stdout); p[id].erase(p[id].begin());
		};
		auto remove=[&](CI x)
		{
			for (RI i=0;i<2;++i) if (p[i].count(x)) p[i].erase(x);
		};
		if (p[0].size()==p[1].size())
		{
			printf("First\n"); fflush(stdout);
			while (!p[0].empty()||!p[1].empty())
			{
				if (!p[s^1].empty()) output(s^1); else output(s);
				scanf("%d",&x); remove(x);
			}
		} else
		{
			int cs=p[0].size()<p[1].size()?0:1;
			if ((cs^1)==s)
			{
				printf("First\n"); fflush(stdout);
				while (!p[0].empty()||!p[1].empty())
				{
					if (!p[cs].empty()) output(cs); else output(cs^1);
					if (p[0].empty()&&p[1].empty()) break;
					scanf("%d",&x); remove(x);
				}
			} else
			{
				printf("Second\n"); fflush(stdout);
				while (!p[0].empty()||!p[1].empty())
				{
					scanf("%d",&x); remove(x);
					if (p[0].empty()&&p[1].empty()) break;
					if (!p[cs].empty()) output(cs); else output(cs^1);
				}
			}
		}
	}
	return 0;
}

F. Babysitting

最套路的一集

首先最小值最大一眼二分答案，考虑如何check(k)

图上的点覆盖，而且还不要求点集大小最少，那么一眼转化成2-SAT模型，即一条边的两个点中至少有一个在解集中

然后我们就顺理成章地发现此时还有个限制就是\(i\)和\([i-k+1,i-1]\cup[i+1,i+k-1]\)不能同时选，用线段树优化下建图即可

总复杂度\(O((n+m)\times \log^2 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 __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1e6+5;
int t,n,m,x[N],y[N],tot; vector <int> v[N]; vector <pi> edges;
inline int ID(CI x,CI tp)
{
	return x+tp*n;
}
class Segment_Tree
{
	private:
		int id[200005<<2];
		inline void addedge(CI x,CI y)
		{
			edges.push_back(pi(x,y));
		}
	public:
		#define TN CI now=1,CI l=1,CI r=n
		#define LS now<<1,l,mid
		#define RS now<<1|1,mid+1,r
		inline void build(TN)
		{
			if (l==r) return (void)(id[now]=ID(l,0)); int mid=l+r>>1;
			id[now]=++tot; build(LS); build(RS);
			addedge(id[now],id[now<<1]); addedge(id[now],id[now<<1|1]);
		}
		inline void link(CI beg,CI end,CI st,TN)
		{
			if (beg<=l&&r<=end) return v[st].push_back(id[now]); int mid=l+r>>1;
			if (beg<=mid) link(beg,end,st,LS); if (end>mid) link(beg,end,st,RS);
		}
		#undef TN
		#undef LS
		#undef RS
}SEG;
int dfn[N],low[N],stk[N],vis[N],col[N],idx,top,cnt;
inline void Tarjan(CI now)
{
	dfn[now]=low[now]=++idx; stk[++top]=now; vis[now]=1;
	for (int to:v[now]) if (!dfn[to]) Tarjan(to),low[now]=min(low[now],low[to]);
	else if (vis[to]) low[now]=min(low[now],dfn[to]);
	if (low[now]==dfn[now])
	{
		col[now]=++cnt; vis[now]=0; while (stk[top]!=now)
		col[stk[top]]=cnt,vis[stk[top--]]=0; --top;
	}
}
inline bool check(CI lim)
{
	RI i; for (i=1;i<=tot;++i) v[i].clear(),dfn[i]=0; idx=cnt=0;
	for (auto [x,y]:edges) v[x].push_back(y);
	for (i=1;i<=m;++i) v[ID(x[i],0)].push_back(ID(y[i],1)),v[ID(y[i],0)].push_back(ID(x[i],1));
	for (i=1;i<=n;++i)
	{
		if (max(i-lim+1,1)<=i-1) SEG.link(max(i-lim+1,1),i-1,ID(i,1));
		if (i+1<=min(i+lim-1,n)) SEG.link(i+1,min(i+lim-1,n),ID(i,1));
	}
	for (i=1;i<=tot;++i) if (!dfn[i]) Tarjan(i);
	for (i=1;i<=n;++i) if (col[ID(i,0)]==col[ID(i,1)]) return 0;
	return 1;
}
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<=m;++i) scanf("%d%d",&x[i],&y[i]);
		edges.clear(); tot=2*n; SEG.build();
		int l=1,r=n,mid,ret; while (l<=r)
		if (check(mid=l+r>>1)) ret=mid,l=mid+1; else r=mid-1;
		printf("%d\n",ret);
	}
	return 0;
}

Postscript

还有好多场CF没补啊苦露西

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

相关文章

  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    Preface补题，经典不会F，看了会题解发现看不懂，索性直接开摆A.JaggedSwaps判断\(a_1\)是否为\(1\)即可#include<cstdio>#include<iostream>#include<utility>#include<vector>#include<cstring>#include<cmath>#include<cstdlib>#include<al......
  • CodeForces 1497E2 Square-free division (hard version)
    洛谷传送门CF传送门感觉和CF1889C2Doremy'sDryingPlan(HardVersion)有异曲同工之妙。显然去除每个数的平方因子后，两个数相乘为完全平方数当且仅当它们相等。考虑若确定了分段方案，那么修改次数就是，每一段重复出现的数的个数。那么我们设\(f_{i,j}\)为\([1,i]\)......
  • Codeforces Round 805 (Div. 3)
    CodeforcesRound805(Div.3)基本情况A、B、C题秒了。D题一开始读错题了，以为是DP，后面发现是简单贪心，拖了点时间才AC。不过无所谓，因为E题没思路了。但是总感觉C做的太不优雅。C.TrainandQueries我的做法就纯用STL无脑模拟。跑了\(701ms\)#include<iostream>#inclu......
  • [Codeforces Round 855 (Div. 3)](https://codeforces.com/contest/1800)
    CodeforcesRound855(Div.3)A.IsItaCat?为什么这个A这么麻烦#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){intn;strings;cin>>n>>s;s=""+s;......
  • Educational Codeforces Round 159 总结
    最失败的一集。C开题顺序搞错，不小心先开了C，以为是A。还好C不难。题意大概是在给定的数组最后添一个数（所有数两两不同），再自定义一个数\(k\)，数组中每个数可以加上若干个\(k\)，最后使得所有数字相等。要求加\(k\)的次数最少。如果不加最后一个数，那么显然把所有的数加到与最大......
  • [ARC141D] Non-divisible Set 题解
    题目链接点击打开链接题目解法很思维的题，需要用好所有的特殊性质暴力的做法是建出图，然后求包含点\(i\)的最长反链，但这明显过不了上面的做法没用到\(a_i<2m\)的性质如何用？把\(a_i\)拆分成\(q\times2^k\;(k\)为奇数\()\)的形式，那么对于同一个\(q\)，只能在其中选一个......
  • [CF1902] Educational Codeforces Round 159 A~E 题解
    [CF1902]EducationalCodeforcesRound159A~E题解A.BinaryImbalance很快观察到如果有不同的相邻元素，那么一定有解，意味着如果全是1无解，其他有解B.GettingPoints题面很长，可以发现，最好的偷懒方式一定是把所有的课都拖到最后几天上（真实），可以简单调整证明这样是不劣的，最后......
  • Codeforces Beta Round 18 (Div. 2 Only) E
    111感觉写的好多都是2000分dp+路径这个dp很明显发现只和行相关然后我们发现每行最多俩个那么肯定就是ababab这种交叉dpiab就是我们第i行选了ab交叉的min转移也是26*26预处理costiab作为每行的转移代价即可最后要注意就是m==1的情况然后初始化一定要把所......
  • [Educational Codeforces Round 159 (Rated for Div. 2)](https://codeforces.com/con
    EducationalCodeforcesRound159(RatedforDiv.2)好困，差点没打A-BinaryImbalance#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;voidsolve(){ strings; intn; cin>>n; cin>>s; if(n==......
  • Codeforces Round 800 (Div. 2)
    CodeforcesRound800(Div.2)基本情况A题秒了。B题写了个递推，但是T了，这种构造题还是得多练。B.ParanoidString我的解法#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingll=longlong;constintN=2e5+10;intt,n;char......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99