技术教程 编程代码 Educational Codeforces Round 45 (Div 2) (A~G) 正文

Educational Codeforces Round 45 (Div 2) (A~G)

2023-07-11,,

目录
Codeforces 990
A.Commentary Boxes
B.Micro-World
C.Bracket Sequences Concatenation Problem
D.Graph And Its Complement(思路 构造)
E.Post Lamps(贪心)
F.Flow Control(思路)
G.GCD Counting(思路)

Codeforces 990

比赛链接

真特么菜啊 后一个多小时无所事事。。

要多做CF的题啊，也许没有那么难但是就是容易想不到，代码也不难写。

A.Commentary Boxes

//15ms	0KB

//整除一下就行，但是第一次把n,m弄反了。。3次看错题mmp，还写了个二分。

#include <cmath>

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

typedef long long LL;

LL n,m,A,B;

int main()

{

	scanf("%I64d%I64d%I64d%I64d",&n,&m,&A,&B);

	LL l=0,r=n/m+1,mid,res=1;

	while(l<=r)

		if((mid=l+r>>1)<=(double)n/m) res=mid,l=mid+1;

		else r=mid-1;

	LL ans=std::min(B*(n-res*m),A*((res+1)*m-n));

	printf("%I64d",ans);

	return 0;

}

B.Micro-World

//31ms	1376KB

//注意重复就好了

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

const int N=2e5+5;

int n,K,A[N],val[N];

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

int main()

{

	n=read(), K=read();

	int res=n;

	for(int i=1; i<=n; ++i) A[i]=read();//,++val[A[i]];

	std::sort(A+1,A+1+n);

	int cnt=1; val[1]=1;

	for(int i=2; i<=n; ++i)

		if(A[i]!=A[i-1]) A[++cnt]=A[i], val[cnt]=1;

		else ++val[cnt];

	for(int i=2; i<=cnt; ++i)

		if(A[i]<=A[i-1]+K) res-=val[i-1];

	printf("%d",res);

	return 0;

}

C.Bracket Sequences Concatenation Problem

//46ms	2472KB

//注意一下非法情况。

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

const int N=3e5+5;

int n,val[N],rval[N];

char s[N];

bool Check1(int l)

{

	int n=0;

	for(int i=1; i<=l&&n>=0; ++i)

		if(s[i]=='(') ++n;

		else --n;

	return n>=0;

}

bool Check2(int l)

{

	int n=0;

	for(int i=l; ~i&&n>=0; --i)//这我为什么写的~i?还没WA...

		if(s[i]==')') ++n;

		else --n;

	return n>=0;

}

int main()

{

	scanf("%d",&n);

	long long res=0;

	for(int i=1; i<=n; ++i)

	{

		scanf("%s",s+1);

		int l=strlen(s+1), cnt=0;

		for(int j=1; j<=l; ++j)

			if(s[j]=='(') ++cnt;

			else --cnt;

		if(cnt==0)

			if(Check1(l)) res+=val[0]*2+1, ++val[0];

			else ;

		else if(cnt>0)

			if(Check1(l)) res+=rval[cnt], ++val[cnt];

			else ;

		else if(Check2(l)) res+=val[-cnt], ++rval[-cnt];

	}

	printf("%I64d",res);

	return 0;

}

赛后

D.Graph And Its Complement(思路 构造)

首先要画出图发现a,b必有一个为1。。

假设当前图只有n个点，没有边，即a=n，b=1，那么想要让b≠1，即补集中至少有一个点孤立出来，那么这个点要在原图中与其它所有点连边。

好现在b=2，a=1了。

或者这样想，原图有a个连通块，肯定先让每个连通块中的点两两有边。这样在补集中每个点一定与所有不在同一连通块的点有边。

这样所有点又连起来了，即a=a，b=1。

这样每次找俩当前不连通的点就可以使a+1；若是b≠1反过来就行了。

注意在n=2/3时a,b不能同时为1，否则一定可以构造出合法解。

//31ms	800KB

#include <cstdio>

#include <algorithm>

const int N=1005;

int n,A,B;

char mp[N][N];

int main()

{

	scanf("%d%d%d",&n,&A,&B);

	if(A!=1&&B!=1) return puts("NO"),0;

	if((n==2||n==3)&&A==1&&B==1) return puts("NO"),0;

	puts("YES");

	const char a=A==1?'0':'1', b=a=='1'?'0':'1';//注意b是与a相对！(A=B=1的情况)

	for(int i=1; i<=n; ++i)

		for(int j=i; j<=n; ++j)

			if(i!=j) mp[i][j]=mp[j][i]=b;

			else mp[i][j]='0';

	for(int i=1, lim=n-std::max(A,B); i<=lim; ++i)

		mp[i][i+1]=mp[i+1][i]=a;

	for(int i=1; i<=n; ++i) mp[i][n+1]='\0', puts(mp[i]+1);

	return 0;

}

E.Post Lamps(贪心)

假设已知要选择哪种灯i。那么从0开始走，每次走i，如果i可放置，那么一定会在i放置而不回去；否则要退回到最近的可放置位置。这其实显然啊。。

\(n/1+n/2+n/3+...+n/n≈O(n\ln n)\)，复杂度没问题啊。

//280ms	9600KB

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 1000000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

const int N=1e6+5;

const long long INF=1e17;

int n,m,K,A[N],move[N];

bool block[N];

char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

int main()

{

	n=read(),m=read(),K=read();

	int delta=0;

	for(int p,i=1; i<=m; ++i)

	{

		block[p=read()]=1;

		move[p]=move[p-1]+1;

		delta=std::max(delta,move[p]);

	}

	if(delta>=K||block[0]) {puts("-1"); return 0;}

	for(int i=1; i<=K; ++i) A[i]=read();

	long long res=INF;

	for(int i=delta+1; i<=K; ++i)

	{

		int now=0; long long sum=0;

		while(now<n)

			if(block[now]) now-=move[now];

			else now+=i, sum+=A[i];

		res=std::min(res,sum);

	}

	printf("%I64d",res==INF?-1ll:res);

	return 0;

}

F.Flow Control(思路)

题目相当于：给定一张图，每个点有一个权值，每条边可以传递任意权值，问能否使每个点的权值为0，并输出边上传递的权值。

无解的情况显然是点权和不为0。否则一定有解。

权值是可以传递的啊！只要从随便一个点开始DFS，不重复走(走出一棵树)，如果它的某子树下还有多余的权值，那么这些一定能补到另一棵子树去；某棵不够也能由其它子树补充。

其它边0就行了。

//

#include <cstdio>

#include <cctype>

#define gc() getchar()

const int N=2e5+5;

int n,m,Enum,H[N],nxt[N<<1],to[N<<1],val[N],Ans[N<<1];//Ans:2N!

bool vis[N];

inline int read()

{

	int now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=gc()) if(c=='-') f=-1;

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now*f;

}

inline void AddEdge(int u,int v)

{

	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;

	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;

}

int DFS(int x)

{

	vis[x]=1;

	int sum=val[x];

	for(int v,i=H[x]; i; i=nxt[i])

		if(!vis[to[i]])

		{

			v=DFS(to[i]), sum+=v;

			if(i&1) Ans[i^1]=-v;

			else Ans[i]=v;

		}

	return sum;

}

int main()

{

	n=read();

	int sum=0;

	for(int i=1; i<=n; ++i) sum+=(val[i]=read());

	if(sum) return puts("Impossible"),0;

	m=read(), Enum=1;

	for(int u,i=1; i<=m; ++i) u=read(),AddEdge(u,read());

	DFS(1), puts("Possible");//连通。否则可以用并查集判sum。

	for(int i=1; i<=m; ++i) printf("%d\n",Ans[i<<1]);

	return 0;

}

G.GCD Counting(思路)

一条gcd=g的路径，其上所有点的权值都至少是g的倍数，即它们是连续的。这样，一个大小为x的连通块且其中点权都为g的倍数，其对Ans[g]的贡献为C(x,2)+x。

这显然算多了。对于2x,3x,...x都会统计，枚举倍数都减掉就可以了。

我们可以对每个点点权分解约数，在其约数的vector中存下它们。然后枚举每个约数g，把每个可行连通块DFS一遍分别统计答案。

或者在点权的vector中存点，在枚举约数时弄出是其倍数的点。

这样复杂度会有问题？反正能过。复杂度O(n*约数个数)，2e5内的数的最大约数个数也就100+。

Rank1是用并查集代替了DFS吧。。不过好像也是一样的。

//3400ms	16100KB

#include <cstdio>

#include <cctype>

#include <vector>

#include <algorithm>

#define gc() getchar()

const int N=2e5+3;

int n,tot,A[N],Enum,H[N],nxt[N<<1],to[N<<1];

long long ans[N];

bool ok[N];

std::vector<int> pt[N];

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline void AddEdge(int u,int v)

{

	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;

	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;

}

void DFS(int x)

{

	ok[x]=0, ++tot;

	for(int i=H[x]; i; i=nxt[i])

		if(ok[to[i]]) DFS(to[i]);

}

int main()

{

	n=read();

	int mx=0;

	for(int v,i=1; i<=n; ++i) pt[v=read()].push_back(i), mx=std::max(mx,v);

	for(int i=1; i<n; ++i) AddEdge(read(),read());

	for(int i=1; i<=mx; ++i)

	{

		int t=0;

		for(int j=i; j<=mx; j+=i)

			for(int k=0,v,lim=pt[j].size(); k<lim; ++k)

				v=pt[j][k], ok[v]=1, A[++t]=v;

		for(int j=1; j<=t; ++j)

			if(ok[A[j]])

			{

				tot=0, DFS(A[j]);

				ans[i]+=(1ll*tot*(tot-1)>>1)+tot;

			}

	}

	for(int i=mx-1; i; --i)

		if(ans[i])

			for(int j=i+i; j<=mx; j+=i) ans[i]-=ans[j];

	for(int i=1; i<=mx; ++i)

		if(ans[i]) printf("%d %I64d\n",i,ans[i]);

	return 0;

}

Educational Codeforces Round 45 (Div 2) (A~G)的相关教程结束。

《Educational Codeforces Round 45 (Div 2) (A~G).doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!