526互联

Codeforces Round 893 (Div. 2)

发布时间 2023-08-17 20:45:55作者: 空気力学の詩

Preface

最战俘的一场，B题写挂一发后整个人脑子就不清醒了，放着D不写去写E1，然后忘了可持久化栈有一个经典的倍增写法，最主要当时暑假前集训我还上去讲了这个东西然后比赛的时候还没想起来

后面目送徐神爆切5题成功完成两场从蓝上橙，狠狠地把我这个在紫卡了半年的废物羞辱了一波

不过确实说实话我们队比赛后期我也基本全程划水，真大腿还得看徐神的说

A. Buttons

签到题，每个人肯定优先按公用的按钮然后再按自己的

#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<functional>
#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;
int t,a,b,c;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d",&a,&b,&c);
		int sa=a+(c+1)/2,sb=b+c/2;
		puts(sa>sb?"First":"Second");
	}
	return 0;
}

B. The Walkway

最难读懂题目的一题，最后这题过的人比C少到不知道哪里去了

其实就是枚举删掉哪个点，每两个点之间的贡献也很好预处理出来，只不过细节比较多容易写挂

#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<functional>
#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,m,d,a[N],pfx[N],sfx[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%d",&n,&m,&d),i=1;i<=m;++i) scanf("%d",&a[i]);
		for (a[0]=1,pfx[0]=1,i=1;i<=m;++i)
		{
			if (a[i]==1) { pfx[i]=1; continue; }
			pfx[i]=pfx[i-1]+(a[i]-a[i-1]-1)/d+1;
		}
		for (a[m+1]=n+1,sfx[m+1]=0,i=m;i>=1;--i) sfx[i]=sfx[i+1]+(a[i+1]-a[i]-1)/d+1;
		int mi=2e9,num; for (i=1;i<=m;++i)
		{
			int tmp=pfx[i-1]+sfx[i+1]+(a[i+1]-a[i-1]-1)/d;
			if (tmp<mi) mi=tmp,num=1; else if (tmp==mi) ++num;
		}
		printf("%d %d\n",mi,num);
	}
	return 0;
}

C. Yet Another Permutation Problem

纯签到题，看一眼就会了的C还有什么出的必要吗

对于每个质数\(p_i\)，将范围内的\(2p_i,4p_i,8p_i\cdots\)都依次放在它后面即可

#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<functional>
#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; bool vis[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) vis[i]=0;
		vector <int> ans; ans.push_back(1); vis[1]=1;
		for (i=2;i<=n;++i) if (!vis[i])
		for (j=i;j<=n;j<<=1) if (!vis[j]) ans.push_back(j),vis[j]=1;
		for (int x:ans) printf("%d ",x); putchar('\n');
	}
	return 0;
}

D. Trees and Segments

比赛的时候心态崩了完全想不进去，其实不是很难的一个题

考虑我们可以枚举一段区间\([l,r]\)，将它全部变成\(0\)，然后以此作为我们最后的最长连续\(0\)的区间

然后对于\([1,l-1],[r+1,n]\)可以分别预处理出在分配了若干次修改后，可以得到的最长连续\(1\)的长度

可以用上面的信息求出当最长连续\(0\)的区间长为\(i\)时，最长连续\(1\)的区间长为\(len_i\)，最后我们枚举系数\(a\)更新答案即可

具体实现看代码，不难发现所有东西的处理都是\(O(n^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<functional>
#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=3005;
int t,n,k,a[N],pfx[N][2],pre[N][N],suf[N][N],len[N],ans[N]; char s[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%d%s",&n,&k,s+1),i=1;i<=n;++i)
		pfx[i][1]=pfx[i-1][1]+(s[i]=='1'),pfx[i][0]=pfx[i-1][0]+(s[i]=='0');
		auto calc=[&](CI l,CI r,CI tar)
		{
			return pfx[r][tar^1]-pfx[l-1][tar^1];
		};
		for (i=0;i<=n+1;++i) for (j=0;j<=n+1;++j) pre[i][j]=suf[i][j]=0;
		for (i=0;i<=n;++i) len[i]=ans[i]=-1;
		for (i=1;i<=n;++i) for (j=i;j<=n;++j)
		pre[j][calc(i,j,1)]=max(pre[j][calc(i,j,1)],j-i+1),
		suf[i][calc(i,j,1)]=max(suf[i][calc(i,j,1)],j-i+1);
		for (i=1;i<=n;++i) for (j=0;j<=n;++j) if (j) pre[i][j]=max(pre[i][j],pre[i][j-1]);
		for (j=0;j<=n;++j) for (i=1;i<=n;++i) pre[i][j]=max(pre[i][j],pre[i-1][j]);
		for (i=n;i>=1;--i) for (j=0;j<=n;++j) if (j) suf[i][j]=max(suf[i][j],suf[i][j-1]);
		for (j=0;j<=n;++j) for (i=n;i>=1;--i) suf[i][j]=max(suf[i][j],suf[i+1][j]);
		for (len[0]=pre[n][k],i=1;i<=n;++i) for (j=i;j<=n;++j)
		if (calc(i,j,0)<=k) len[j-i+1]=max(len[j-i+1],max(pre[i-1][k-calc(i,j,0)],suf[j+1][k-calc(i,j,0)]));
		for (i=1;i<=n;++i) for (j=0;j<=n;++j) if (~len[j]) ans[i]=max(ans[i],i*j+len[j]);
		for (i=0;i<=n+1;++i) for (j=0;j<=n+1;++j) pre[i][j]=suf[i][j]=0;
		for (i=0;i<=n;++i) len[i]=-1;
		for (i=1;i<=n;++i) for (j=i;j<=n;++j)
		pre[j][calc(i,j,0)]=max(pre[j][calc(i,j,0)],j-i+1),
		suf[i][calc(i,j,0)]=max(suf[i][calc(i,j,0)],j-i+1);
		for (i=1;i<=n;++i) for (j=0;j<=n;++j) if (j) pre[i][j]=max(pre[i][j],pre[i][j-1]);
		for (j=0;j<=n;++j) for (i=1;i<=n;++i) pre[i][j]=max(pre[i][j],pre[i-1][j]);
		for (i=n;i>=1;--i) for (j=0;j<=n;++j) if (j) suf[i][j]=max(suf[i][j],suf[i][j-1]);
		for (j=0;j<=n;++j) for (i=n;i>=1;--i) suf[i][j]=max(suf[i][j],suf[i+1][j]);
		for (len[0]=pre[n][k],i=1;i<=n;++i) for (j=i;j<=n;++j)
		if (calc(i,j,1)<=k) len[j-i+1]=max(len[j-i+1],max(pre[i-1][k-calc(i,j,1)],suf[j+1][k-calc(i,j,1)]));
		for (i=1;i<=n;++i) for (j=0;j<=n;++j) if (~len[j]) ans[i]=max(ans[i],j+i*len[j]);
		for (i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
	}
	return 0;
}

E1. Rollbacks (Easy Version)

想这种有回溯操作的题可以用经典套路在操作间连边建成一棵DFS树，每次在树上完成插入和撤销操作即可

但这题由于要实现弹出栈中元素的功能，直接暴力做肯定会T飞，因此需要用可持久化栈的思路

就是对于每个点倍增维护出向前弹出\(2^k\)个数的状态，然后遇到弹出操作直接把它接在对应的下面即可

总复杂度\(O(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<functional>
#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 q,x[N],tot,ans[N],stk[N],top,bkt[N],cur,anc[N][21]; char opt[10]; vector <int> v[N],ques[N];
inline void add(CI x)
{
	if (++bkt[x]==1) ++cur;
}
inline void del(CI x)
{
	if (--bkt[x]==0) --cur;
}
inline void DFS(CI now)
{
	if (now) add(x[now]); for (int id:ques[now]) ans[id]=cur;
	for (int to:v[now]) DFS(to); if (now) del(x[now]);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&q),i=1;i<=q;++i)
	{
		scanf("%s",opt); ans[i]=-1;
		switch (opt[0])
		{
			case '+':
			{
				int now=++tot; scanf("%d",&x[now]); anc[now][0]=stk[top]; v[stk[top]].push_back(now);
				for (j=0;j<20;++j) anc[now][j+1]=anc[anc[now][j]][j]; stk[++top]=now; break;
			}
			case '-':
			{
				int now=stk[top],k; scanf("%d",&k);
				for (j=0;j<21;++j) if ((k>>j)&1) now=anc[now][j]; stk[++top]=now; break;
			}
			case '!':
				--top; break;
			case '?':
				ques[stk[top]].push_back(i); break;
		}
	}
	//for (i=0;i<=q;++i) for (int x:v[i]) printf("%d -> %d\n",i,x);
	for (DFS(0),i=1;i<=q;++i) if (~ans[i]) printf("%d\n",ans[i]);
	return 0;
}

E2. Rollbacks (Hard Version)

听zzh说好像就是维护每种数第一次出现的位置即可，没太仔细想就先坑着了

Postscript

今晚还有CF，又要被虐杀了……