526互联

Codeforces Round 912 (Div. 2)

发布时间 2023-12-06 19:37:00作者: 空気力学の詩

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没补啊苦露西