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

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

2023-07-11,,

目录
Codeforces 1009
A.Game Shopping
B.Minimum Ternary String
C.Annoying Present
D.Relatively Prime Graph
E.Intercity Travelling(递推)
$Description$
$Solution$
F.Dominant Indices(启发式合并)
G.Allowed Letters(Hall定理 位运算)
$Description$
$Solution$

Codeforces 1009

比赛链接

hack好给力啊233

A.Game Shopping

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

const int N=1e3+5;

int n,m,cost[N],A[N];

inline int read()

{

	register 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();

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

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

	int now=1,ans=0;

	for(int i=1; i<=n && now<=m; ++i)

		if(cost[i]<=A[now]) ++ans, ++now;

	printf("%d\n",ans);

	return 0;

}

B.Minimum Ternary String

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

const int N=1e5+7;

int n;

char s[N],ans[N];

int main()

{

	scanf("%s",s+1), n=strlen(s+1);

	int cnt[5],now;

	cnt[0]=cnt[1]=cnt[2]=0;

	for(now=1; now<=n; ++now)

		if(s[now]!='2') ++cnt[s[now]-'0'];

		else break;

	for(int i=1; i<=cnt[0]; ++i) ans[i]='0';

	for(int i=cnt[0]+1; i<=cnt[0]+cnt[1]; ++i) ans[i]='1';

	cnt[0]=cnt[1]=cnt[2]=0;

	for(int i=now; i<=n; ++i) ++cnt[s[i]-'0'];

	for(int i=now; i<now+cnt[1]; ++i) ans[i]='1';

	s[n+1]='3';

	for(int i=now+cnt[1]; i<=n; ++i)

	{

		while(s[now]=='1') ++now;

		ans[i]=s[now++];

	}

	puts(ans+1);

	return 0;

}/*

102012012

*/

C.Annoying Present

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

#define eps 1e-8

typedef long long LL;

const int N=1e5+7;

inline int read()

{

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

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

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

	return now*f;

}

int main()

{

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

	LL sum=0, sumX=0, C1, C2=1ll*n*(n-1)>>1;//n/2写成n>>1略显乱

	if(n&1) C1=1ll*(n>>1)*((n>>1)+1);

	else C1=1ll*(n>>1)*((n>>1)+1)-1ll*(n>>1);

	LL x,d;

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

	{

		x=read(), d=read(), sumX+=x;

		if(d>0) sum+=C2*d;

		else if(d<0) sum+=C1*d;

	}

	printf("%.8lf",1.0*(sum+1ll*n*sumX)/n);

	return 0;

}

D.Relatively Prime Graph

靠 欺负我读英文题目不仔细吗 图必须连通。。

于是WA*3。看了数据才A。。

这破题 rank1000+了啊啊啊

而且这题n^2纯暴力都能过 太没意思了吧

#include <cmath>

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

#define pr std::pair<int,int>

#define mp std::make_pair

const int N=1e5+7;

int n,m,cnt,P[N],fac[N],sum;

pr A[3000005];

bool not_P[N];

int gcd(int x,int y){

	return y?gcd(y,x%y):x;

}

void Pre(int n)

{

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

	{

		if(!not_P[i]) P[++cnt]=i;

		for(int j=1; j<=cnt&&i*P[j]<=n; ++j)

		{

			not_P[i*P[j]]=1;

			if(!(i%P[j])) break;

		}

	}

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

		if(!not_P[i]) fac[i]=i;

		else{

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

				if(!(i%j)) {fac[i]=j; break;}

		}

}

int main()

{

	scanf("%d%d",&n,&m);// printf("%d\n",m);

	if(m<n-1) return puts("Impossible"),0;//...

	Pre(n);

	for(int i=2; i<=n && sum<m; ++i) A[++sum]=mp(1,i);

	for(int x=1; x<=cnt && sum<m; ++x)

	{

		int i=P[x];

		for(int j=i+1; j<=n && sum<m; )

		{

			int k=std::min(j+fac[i]-1,n+1);//n+1!

			for(int l=j; l<k && sum<m; ++l) A[++sum]=mp(i,l);

			j=k+1;

		}

	}

	for(int i=4; i<=n && sum<m; ++i)

	{

		if(!not_P[i]) continue;

		for(int j=i+1; j<=n && sum<m; )

		{

			int k=std::min(j+fac[i]-1,n+1);

			for(int l=j; l<k && sum<m; ++l)

				if(gcd(i,l)==1) A[++sum]=mp(i,l);

			j=k+1;

		}

	}

	if(sum<m) puts("Impossible");

	else

	{

		puts("Possible");

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

			printf("%d %d\n",A[i].first,A[i].second);

	}

	return 0;

}

比赛结束后

E.Intercity Travelling(递推)

\(Description\)

　　Leha从0出发前往n。给定数组\(a[]\)。路上可能会有一些休息点，Leha会在这些地方停下休息。如果当前所在休息点\(i\)，而上一个休息点是\(j\)，那他会得到\(a_{i-j}\)的困难值（包括在n点停下也要计算，路程上所有累加）。休息点一共有\(2^{n-1}\)种可能分布，求所有可能中整段路程所得到的困难值的期望\(e\times 2^{n-1}\mod\ 998244353\)。

\(Solution\)

　　要求一个线性做法，我们尝试递推求它。

　　对每一个位置\(i\)，我们可以写出它作为休息点时得到困难值的期望：\(e_i=\frac{a_1}{2}+\frac{a_2}{2^2}+\ldots+\frac{a_{i-1}}{2^{i-1}}+\frac{a_i}{2^{i-1}}\)。最后一项的概率是\(2^{i-1}\)，因为是从0号点出发。

　　那么就可以得到\(e_1=a_1，e_{i+1}=e_i-\frac{a_i}{2^i}+\frac{a_{i+1}}{2^i}\)。

//93ms	7700KB

#include <cstdio>

#include <cctype>

#define gc() getchar()

#define mod (998244353)

const int N=1e6+5;

int n,A[N],pw[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();

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

	pw[0]=1;

	for(int i=1; i<=n; ++i) pw[i]=pw[i-1]<<1, pw[i]>=mod&&(pw[i]-=mod);

	long long now=1ll*A[1]*pw[n-1]%mod, ans=now;

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

	{

		now=(now-1ll*A[i]*pw[n-1-i]%mod+1ll*A[i+1]*pw[n-1-i]%mod+mod)%mod,

		ans+=now;

	}

	printf("%I64d\n",ans%mod);

	return 0;

}

F.Dominant Indices(启发式合并)

显然对于\(d_{x,i}\)，我们有\(d_{x,i}=\sum_{v=son[x]}d_{v,i-1}\)

Dominant Indices就是最大的\(d_{x,i}\)中下标最小的\(i\)。我们可以利用启发式合并求\(d_x\)。启发式合并一般的复杂度是\(O(n\log n)\)的，但在本题中，复杂度只与深度较小的点的深度有关，而不是点数。所以复杂度是\(O(n)\)的。

我们还需要将数组整体右移，以便插入一个\(d_{x,0}=1\)。可以用map(\(O(n\log n)\))，也可以用vector倒序存储，这样就是\(O(n)\)的了。

也可以直接用个大点的(\(O(n)\)其实就够了)数组，每个点维护在数组中的位置。

[Update]这就是dsu on tree或者长链剖分啊。

//546ms	89700KB

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

const int N=1e6+5;

int n,Enum,H[N],nxt[N<<1],to[N<<1],Ans[N],A[N],pos[N],len[N],mx[N],mxpos[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 Merge(int x,int y)//x<-y

{

	if(len[x]<len[y])

	{

		std::swap(pos[x],pos[y]), std::swap(len[x],len[y]),

		std::swap(mx[x],mx[y]), std::swap(mxpos[x],mxpos[y]);

	}

	for(int i=0,ly=len[y],px=pos[x],py=pos[y]; i<ly; ++i)

	{

		A[px+i]+=A[py+i]; //A[px+i+1]+=A[py+i];

		if(A[px+i]>mx[x]) mx[x]=A[px+i], mxpos[x]=i;

		else if(A[px+i]==mx[x] && i<mxpos[x]) mxpos[x]=i;

	}

}

void DFS(int x,int f)

{

	A[pos[x]]=1, len[x]=1, mx[x]=1, mxpos[x]=0;

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

		if((v=to[i])!=f)

		{

			pos[v]=pos[x]+len[x]+1, DFS(v,x);//给v腾出一位，合并前将v右移一位。否则len[x]==len[v]时会重叠。。

			A[--pos[v]]=0, ++len[v], ++mxpos[v], Merge(x,v);

		}

	Ans[x]=mxpos[x];

}

int main()

{

	n=read();

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

	pos[1]=1, DFS(1,1);

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

	return 0;

}

G.Allowed Letters(Hall定理 位运算)

\(Description\)

给定长为n、由小写字母a~f组成的字符串s。有m个限制，每个限制为：在\(pos_i\)处只能是某些字母(\(pos_i\)两两不同)。

你可以任意交换原串两个字母的位置，问是否能得到满足限制的串，若能，输出满足限制的最小字典序的字符串。

\(Solution\)

有n个字符，每个字符可以放在某些位置，要求这些字符全部放置->完备匹配。

可以跑网络流，检查最大流是否等于n，连边比较好想。然后假设想要让i位置放字符c，如果原最大流不需要c->i这条边，那么可以；否则让这条边退流，容量-1，再检查最大流是否等于n。

如果决定了位置i放字符c，那么要使c->i这条边的容量-1.

没写，万一调不出来有点。。Tutorial里说复杂度\(O(n*2^A*A^2)\)(A为字符集大小)，不知道\(2^A\)是为什么。。（好像也是判子集合法？）

可以考虑Hall定理。对于任意一个字符的子集，其中字符个数要<=能够匹配其中字符的位置个数。

这样的话对于同一种字符，显然只需要检验包含它最多的子集（位置数不会变）。所以我们要检查的子集只有\(2^A=64\)个(A为字符集大小)。

任意子集包含字符的个数sum可以\(O(A*2^A)\)或\(O(2^A)\)算。对于(只要)能够匹配某子集s中任意字符 的位置数我们可以去算：位置总数-只能匹配除s中字符外的位置数。

除s中字符外的子集可以表示为2^A-1-s，预处理其包含的所有子集的位置数即可，记为f[]。

如果现在要确定i位置放什么，那要先减掉i对f的贡献，即枚举所有包括 位置i可放字符子集 的子集，依次-1。要放某字符首先要能放，然后数量-1，再Check就行了。

//62ms	400KB

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

#define lb(i) (i&-i)

const int N=1e5+7;

int n,num[7],can[N],sum[69],f[69],bit[69];

char s[N],tmp[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;

}

bool Check()

{

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

	{

		sum[i]=sum[i^lb(i)]+num[bit[lb(i)]];

		if(sum[i]>f[63]/*not n，or n也-1*/-f[63-i]) return 0;

	}

	return 1;

}

int main()

{

	scanf("%s",s+1), n=strlen(s+1);

	for(int i=1; i<=n; ++i) can[i]=63, ++num[s[i]-'a'];

	for(int m=read(),p; m--; )

	{

		can[p=read()]=0, scanf("%s",tmp+1);

		for(int j=1,l=strlen(tmp+1); j<=l; ++j)

			can[p]|=1<<tmp[j]-'a';

	}

	for(int i=1; i<=n; ++i) ++f[can[i]];

	for(int i=0; i<6; ++i)//求其包含的所有子集 先枚举i！

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

			if(j>>i & 1)

				f[j]+=f[j^(1<<i)];

	for(int i=0; i<6; ++i) bit[1<<i]=i;

	if(!Check()) return puts("Impossible"),0;

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

	{

		for(int s=can[i]; s<=63; s=(s+1)|can[i]) --f[s];

		for(int j=0; j<6; ++j)

		{

			if(!(can[i]>>j&1)) continue;

			--num[j];

			if(Check()) {putchar(j+'a'); break;}

			++num[j];

		}

	}

	return 0;

}

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

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

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

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