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

目录

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
",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
",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
",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 imes 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
",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(nlog n))的，但在本题中，复杂度只与深度较小的点的深度有关，而不是点数。所以复杂度是(O(n))的。
我们还需要将数组整体右移，以便插入一个(d_{x,0}=1)。可以用map((O(nlog 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
",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;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/SovietPower/p/9311498.html