首页 > 其他分享 >Educational Codeforces Round 153 (Rated for Div. 2)

Educational Codeforces Round 153 (Rated for Div. 2)

时间：2023-08-21 20:12:09浏览次数：37  
标签：Educational Rated const int typedef long Codeforces include define

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

标签：Educational,Rated,const,int,typedef,long,Codeforces,include,define
From： https://www.cnblogs.com/cjjsb/p/17646958.html

相关文章

  • Codeforces Round 893 (Div. 2) A-C题解
    CF893(Div.2)A.Buttons签到题。两人会优先选择c中的按钮来，避免自己的按钮消耗同时减少对方可选择的按钮。所以c%2==1等价于a的按钮数+1，c%2==0时相当于c按钮不存在，比较ab按钮的数量来得出答案即可。#include<iostream>usingnamespacestd;typedeflonglong......
  • Codeforces EduRound153 Editorial
    A如果有\(()\)那么肯定是不合法的有两种很简单的构造，()()()()...()和((((...))))，如果一个串是第一种构造的子串那么一定不是第二种构造的子串，反之亦然。使用python取之B把\(m\%k\)的余数补齐，再把多出来的\(1\)价格regularcoins\(m\)个一组f使用python取之C......
  • Educational Codeforces Round 153 (Rated for Div. 2)
    EducationalCodeforcesRound153(RatedforDiv.2)A-NotaSubstring思路：找到串中最大的层数，若层数为1，构造层数大于1的即可；若层数大于1，构造层数为1的即可#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128#definedoublel......
  • Educational Codeforces Round 153 (Rated for Div. 2)
    EducationalCodeforcesRound153(RatedforDiv.2)这次的div2有点难度，当时b题思路对了，但是没有写好A题传送门A题意：给你一个只包含'('和')'的字符串，要求你将他的长度扩大一倍，并且使得所有括号匹配且组成的序列当中不能存在原序列的子序列A思路：这道题一开始写的时候没有注......
  • Codeforces Round 881 (Div. 3)
    比赛链接：https://codeforces.com/contest/1843A.SashaandArrayColoring题意：一个数组，可以任意分成任意组，每组的贡献是组最大值减最小值，求最大总贡献思路：一组内只有最大值和最小值有用，所以每组只由两个数组成即可，用贪心的思路，依次取出原数组的最大和最小值成组即可B.LongL......
  • Codeforces Round 893 (Div. 2)
    Preface最战俘的一场，B题写挂一发后整个人脑子就不清醒了，放着D不写去写E1，然后忘了可持久化栈有一个经典的倍增写法，最主要当时暑假前集训我还上去讲了这个东西然后比赛的时候还没想起来后面目送徐神爆切5题成功完成两场从蓝上橙，狠狠地把我这个在紫卡了半年的废物羞辱了一波不过确......
  • Educational Codeforces Round 109 (Rated for Div. 2)
    EducationalCodeforcesRound109(RatedforDiv.2)A-Potion-making思路：求最小操作数即药水最简比#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128#definedoublelongdoubletypedefpair<int,int>PII;typedefpair......
  • Codeforces Round 883 (Div. 3)
    比赛链接：https://codeforces.com/contest/1846A.RudolphandCuttheRope题意：给n条绳子，知道一端所在高度坐标和各自绳长，他们另一端都连到一个糖果上，问至少剪掉多少绳子糖果能碰到地面思路：显然只有坐标小于绳长的才能让糖果触地，去掉其他的即可B.RudolphandTic-Tac-Toe题......
  • Codeforces Round 892 (Div. 2)
    CodeforcesRound892(Div.2)目录CodeforcesRound892(Div.2)AUnitedWeStandBOlyaandGamewithArraysCAnotherPermutationProblemDAndreyandEscapefromCapygradEMaximumMonogonosityAUnitedWeStand给定长度为\(n\)的数组a，可以将a中元素添加到空数组b......
  • 2023.08.12 codeforces round 893 div2
    年轻人的第四场div2rank:8217solved:2ratingchange:+31newrating:1354A.Buttons题意：给定a,b,c三种按钮的数量，a按钮只能被Anna按，b按钮只能被Katie按，两个人都可以按c按钮，最后没有按钮可以按的人输，Anna先手，问谁是赢家；两个人肯定优先按c按钮，且Anna是先手，只需比较两人能按的按......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99