526互联

Educational Codeforces Round 153 (Rated for Div. 2)

发布时间 2023-08-21 20:16:00作者: 空気力学の詩

Preface

最近CF状态烂得一批，已经连续两场被D题腐乳了，再这样下去就真成抱队友大腿的混子了

但没想到因为D题比赛时贪心过的人太多了，后面一波叉掉了比赛时过的\(\frac{1}{3}\)的人导致竟然还能上分我是没想到的

没抓住暑假大好的上分机会，等开学后再想冲分就难咯

A. Not a Substring

妈的开局被A腐乳了，想了5min结论是不会做，赶紧先去把BC写了

后面徐神说直接随机一个合法括号序列再检验就行，但实际上我们只要判断两种情况，(((())))和()()()()之类的即可

#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=105;
int T,n; char s[N],t[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&T),srand(time(0));T;--T)
	{
		RI i,j; scanf("%s",s+1); n=strlen(s+1); bool has_sol=0;
		for (RI TIM=100;TIM;--TIM)
		{
			int cur=0,num=0; for (i=1;i<=2*n;++i)
			{
				if (cur==0) { t[i]='('; ++cur; ++num; continue; }
				if (num==n) { t[i]=')'; --cur; continue; }
				if (rand()&1) t[i]='(',++cur,++num; else t[i]=')',--cur;
			}
			bool flag=1; for (i=1;i<=n+1&&flag;++i)
			{
				bool sign=1; for (j=1;j<=n&&sign;++j)
				if (s[j]!=t[i+j-1]) sign=0;
				if (sign) flag=0;
			}
			if (flag)
			{
				puts("YES");
				for (i=1;i<=2*n;++i) putchar(t[i]); putchar('\n');
				has_sol=1; break;
			}
		}
		if (!has_sol) puts("NO");
	}
	return 0;
}

B. Fancy Coins

这东西一眼可三分，直接做就完事了，后面发现是个分类讨论题来着

#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 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;
int t,m,k,a1,ak;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		scanf("%lld%lld%lld%lld",&m,&k,&a1,&ak);
		auto calc=[&](CI x)
		{
			return max(x-ak,0LL)+max(m-x*k-a1,0LL);
		};
		int l=0,r=m/k; while (r-l>2)
		{
			int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
			if (calc(lmid)<=calc(rmid)) r=rmid; else l=lmid;
		}
		int ret=calc(l); for (RI i=l+1;i<=r;++i) ret=min(ret,calc(i));
		printf("%lld\n",ret);
	}
	return 0;
}

C. Game on Permutation

傻逼博弈题，考虑检验一个状态是否为必败态，首先如果这个点之前没有小于它的点则按题意是必败

否则如果所有小于它的点都是必胜态的话这个点也是必败，这个用树状数组维护下即可

#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=300005;
int t,n,a[N],f[N];
class Tree_Array
{
	private:
		int bit[N];
	public:
		#define lowbit(x) (x&-x)
		inline void init(CI n)
		{
			for (RI i=1;i<=n;++i) bit[i]=0;
		}
		inline int get(RI x,int ret=0)
		{
			for (;x;x-=lowbit(x)) ret+=bit[x]; return ret;
		}
		inline void add(RI x,CI y)
		{
			for (;x<=n;x+=lowbit(x)) bit[x]+=y;
		}
		#undef lowbit
}A,B;
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) scanf("%d",&a[i]);
		for (A.init(n),B.init(n),i=1;i<=n;++i)
		{
			int less=A.get(a[i]);
			if (!less) f[i]=0; else f[i]=less==B.get(a[i]);
			A.add(a[i],1); if (!f[i]) B.add(a[i],1);
		}
		int ret=0; for (i=1;i<=n;++i) ret+=f[i];
		printf("%d\n",ret);
	}
	return 0;
}

D. Balanced String

这题其实比赛的时候想到很大一部分了，但就是最后一步写糙了，后面仔细一想马上就过了

首先考虑求出初始状态时\(01\)的对数\(st\)，同时我们很容易算出最后目标状态中\(01\)的对数\(tar\)

考虑交换的时候有一些性质，首先我们总是交换不同的字符，其次一个位置只会被交换一次

然后还有一个很关键的性质就是如果我们交换位置\(x,y(x<y)\)，若\(s_x=1\and s_y=0\)，则\(01\)的对数会增加\(y-x\)个，反之若\(s_x=0\and s_y=1\)则\(01\)的对数会减少\(y-x\)个

但如果只是这样的话还是不好求解，我们再多观察一步会发现如果一个\(s_x=1\)参与交换，则它的贡献永远是\(-x\)，反之如果一个\(s_x=0\)参与交换，则它的贡献永远是\(x\)

那么我们就很好DP了，设\(f_{i,j,k}\)表示处理了前\(i\)个位置，其中交换的\(0,1\)个数的差值为\(j\)，\(01\)的对数为\(k\)的最少操作数

初始条件为\(f_{0,0,st}=0\)，最后的答案就是\(f_{n,0,tar}\)，转移的话很显然，注意负数下标的问题

#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=105,S=10000,INF=1e9;
int n,f[2][N*2][N*N*2],lim; char s[N];
inline void chkmin(int& x,CI y)
{
	if (y<x) x=y;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	auto C2=[&](CI x)
	{
		return x*(x-1)/2;
	};
	RI i,j,k; scanf("%s",s+1); n=strlen(s+1); int c[2]={0,0};
	for (i=1;i<=n;++i) ++c[s[i]-'0']; lim=C2(n);
	int tar=(C2(n)-C2(c[0])-C2(c[1]))/2;
	int ret=0,num=0; for (i=1;i<=n;++i)
	{
		if (s[i]=='1') ret+=num; num+=s[i]=='0';
	}
	for (i=-(n+1);i<=(n+1);++i) for (j=-(lim+n);j<=(lim+n);++j) f[0][i+N][j+S]=INF;
	for (f[0][N][ret+S]=0,i=1;i<=n;++i)
	{
		int now=i&1,lst=now^1;
		for (j=-(n+1);j<=(n+1);++j) for (k=-(lim+n);k<=(lim+n);++k) f[now][j+N][k+S]=INF;
		for (j=-n;j<=n;++j) for (k=-lim;k<=lim;++k)
		{
			chkmin(f[now][j+N][k+S],f[lst][j+N][k+S]);
			if (s[i]=='1') chkmin(f[now][j+N][k+S],f[lst][j-1+N][k+i+S]+1);
			else chkmin(f[now][j+N][k+S],f[lst][j+1+N][k-i+S]+1);
			//if (f[now][j+N][k+S]!=INF) printf("f[%d][%d][%d] = %d\n",i,j,k,f[now][j+N][k+S]);
		}
	}
	return printf("%d",f[n&1][N][tar+S]/2),0;
}

E. Fast Travel Text Editor

这题其实不难，但比赛的时候都没来得及看，实在是太弱了的说

首先最优的走法其实只有两种，一种是直接从\(f\)走到\(t\)，这种情况的代价就是\(|f-t|\)

令一种就是先从\(f\)移动到某个\((x,y)\)处，然后通过这个\((x,y)\)走到\(t\)

先考虑从某个\((x,y)\)走到每个点的最短路，这部分可以很套路地建图

首先把所有相邻的点之间连边权为\(1\)的边，然后每个位置\(i\)向对应的\((s_i,s_{i+1})\)连边权为\(1\)的边，最后所有\((s_i,s_{i+1})\)向\(i\)连边权为\(0\)的边

不难发现由于边权只有\(0/1\)，因此用双端队列可以做到\(O(n)\)求解单源最短路

然后我们再预处理一下每个位置往前/往后到的第一个\((x,y)\)的距离，然后再扫一遍询问更新答案即可

总复杂度\(O(26^2\times (|S|+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<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=50005+26*26,INF=1e9;
int n,m,l[N],r[N],tot,pre[N],nxt[N],dis[N],ans[N]; char s[N]; vector <pi> v[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	auto trs=[&](const char& x,const char& y)
	{
		return n+(x-'a')*26+(y-'a');
	};
	RI i,j,k; for (scanf("%s",s+1),n=strlen(s+1),i=1;i<n;++i)
	v[i].push_back(pi(trs(s[i],s[i+1]),1)),v[trs(s[i],s[i+1])].push_back(pi(i,0));
	for (tot=trs('z','z'),i=1;i<n;++i)
	{
		if (i-1>=1) v[i].push_back(pi(i-1,1));
		if (i+1<n) v[i].push_back(pi(i+1,1));
	}
	for (scanf("%d",&m),i=1;i<=m;++i)
	scanf("%d%d",&l[i],&r[i]),ans[i]=abs(r[i]-l[i]);
	for (j=0;j<26;++j) for (k=0;k<26;++k)
	{
		for (pre[0]=-INF,i=1;i<n;++i)
		if (pre[i]=pre[i-1],s[i]==j+'a'&&s[i+1]==k+'a') pre[i]=i;
		for (nxt[n]=INF,i=n-1;i>=1;--i)
		if (nxt[i]=nxt[i+1],s[i]==j+'a'&&s[i+1]==k+'a') nxt[i]=i;
		for (i=1;i<=tot;++i) dis[i]=INF;
		deque <int> q; q.push_front(n+j*26+k); dis[n+j*26+k]=0;
		while (!q.empty())
		{
			int now=q.front(); q.pop_front();
			for (auto [to,w]:v[now]) if (dis[to]>dis[now]+w)
			{
				dis[to]=dis[now]+w;
				if (w) q.push_back(to); else q.push_front(to);
			}
		}
		for (i=1;i<=m;++i)
		{
			int tmp=min(l[i]-pre[l[i]],nxt[l[i]]-l[i]);
			ans[i]=min(ans[i],tmp+1+dis[r[i]]);
		}
	}
	for (i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}

Postscript

暑假集训总算是结束了，这两天闲着会尽量把之前欠下的一些博客补一补，当然前提是我没有玩云顶玩入魔qwq