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

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

2023-07-11,,

目录
Codeforces 1000
A.Codehorses T-shirts
B.Light It Up
C.Covered Points Count(差分)
D.Yet Another Problem On a Subsequence(DP)
E.We Need More Bosses(圆方树)
$Description$
$Solution$
F.One Occurrence(线段树)
$Description$
$Solution$
G.Two-Paths(树形DP)
$Description$
$Solution$

Codeforces 1000

比赛链接

CF的第1000场比赛。。

在学校熬到12点半打CF而不是看他们打联盟真是。。rating差点掉真是难受啊。

A.Codehorses T-shirts

因为长度固定，所以看着分就好了...

当然其实只需要map<string,int>。

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

const int N=105;

int n,have[4][3],sum[4][3],ref[2333];//x:0~3 S/L

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(); char s[233];

	ref['S']=0, ref['L']=1, ref['M']=2;

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

	{

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

		++have[l-1][ref[s[l]]];

	}

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

	{

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

		++sum[l-1][ref[s[l]]];

	}

	int res=0;

	for(int i=0; i<=3; ++i)

	{

		int tmp=0;

		for(int j=0; j<=2; ++j) tmp+=std::abs(have[i][j]-sum[i][j]);

		res+=tmp>>1;

	}

	printf("%d",res);

	return 0;

}

B.Light It Up

对于要开的和要灭的要放的最优位置是确定的，有不同的贡献。枚举一下放在哪就行了。

漏了一个-A[i-1]还过了4个点 WA了三遍。。aaaaaa

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

typedef long long LL;

const int N=1e5+7;

LL n,m,A[N],sum[N],suf[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(),m=read();

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

	for(int i=1; i<=n; i+=2) sum[i+1]=sum[i]=sum[i-1]+A[i]-A[i-1];

	if(n&1){

		for(int i=n-1; i>0; i-=2) suf[i-1]=suf[i]=suf[i+1]+A[i+1]-A[i];

	}

	else{

		A[n+1]=m;

		for(int i=n; i>0; i-=2) suf[i-1]=suf[i]=suf[i+1]+A[i+1]-A[i];

	}

//	for(int i=1; i<=n; ++i) printf("%d:pre:%I64d suf:%I64d\n",i,sum[i],suf[i]);

	LL ans=sum[n];

	if(!(n&1)) ans+=m-A[n];

	if(n&1) A[++n]=m;

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

		if(A[i]-A[i-1]>1){

			if(i&1) ans=std::max(ans,sum[i-1]+A[i]-A[i-1]-1+m-A[i]-suf[i]);

			else ans=std::max(ans,sum[i-1]+A[i]-A[i-1]-1+m-A[i]-suf[i]);

		}

	printf("%I64d",ans);

	return 0;

}

C.Covered Points Count(差分)

离散化，差分。每个区间拆成4个点，即在修改前计算一遍。

Ans原本开的longlong，但是WA了一次发现，我怎么用%d输出longlong了？遂改int Ans[]。。

数据范围好像有问题啊mmp

好像没问题。。那为什么我N=2e5+7会RE啊

噢 val也是4N。。

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

typedef long long LL;

const int N=2e5+7;

int n,cnt,val[N*4];

LL ref[N*4],L[N],R[N],Ans[N];

inline LL read()

{

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

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

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

	return now;

}

inline int Find(LL x)

{

	int l=1, r=cnt, mid;

	while(l<r)

		if(ref[mid=l+r>>1]>=x) r=mid;

		else l=mid+1;

	return l;

}

int main()

{

	n=read(); int tot=0;

	for(int i=1; i<=n; ++i) L[i]=ref[++tot]=read(), ref[++tot]=L[i]-1, R[i]=ref[++tot]=read(), ref[++tot]=R[i]+1;

	std::sort(ref+1,ref+1+tot), cnt=1;

	for(int i=2; i<=tot; ++i) if(ref[i]!=ref[i-1]) ref[++cnt]=ref[i];

	for(int i=1; i<=n; ++i) ++val[Find(L[i])], --val[Find(R[i]+1)];

	ref[0]=ref[1]-1;

	for(int now=0,i=1; i<=cnt; ++i)

	{

		now+=val[i];

		Ans[now]+=ref[i]-ref[i-1];

	}

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

	return 0;

}

比赛结束后

D.Yet Another Problem On a Subsequence(DP)

Good Sequence是可以拼接的吧。于是考虑倒着\(O(n^2)\)dp。

枚举要接在i后面的子序列j(\(i<j\)，\(A[i]>0\))。A[i]已知 i这个子序列就已知，且有\(C_{j-i-1}^{A[i]+1-1}\)种构成i的方案(并不需要它连续)。

i单独成一个也可以，要加上自己构成的\(C_{n-i}^{A[i]}\)种。可以令f[n+1]=1，j枚举到n+1。

//31ms	3800KB

#include <cstdio>

#include <cctype>

#define gc() getchar()

#define mod (998244353)

typedef long long LL;

const int N=1005;

int n,C[N][N],A[N],f[N];

inline int read()

{

	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;

}

void Init()

{

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

	{

		C[i][0]=C[i][i]=1;

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

			C[i][j]=C[i-1][j]+C[i-1][j-1], (C[i][j]>=mod)&&(C[i][j]-=mod);

	}

}

int main()

{

	n=read(), Init();

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

	f[n+1]=1;

	for(int i=n; i; --i)

	{

		if(A[i]<=0) continue;

		LL tmp=0;

		for(int j=i+1+A[i]; j<=n+1; ++j) tmp+=1ll*C[j-i-1][A[i]]*f[j]%mod;

		f[i]=(int)(tmp%mod);

	}

	LL ans=0;

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

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

	return 0;

}

略一优化：C()可以预处理阶乘和阶乘逆元线性求，可以省个\(n^2\)。但时间没变就空间优化了。。

以前真是闲。。

//31ms	0KB

int n,A[N],f[N],sum[N],inv[N];

inline int FP(LL x,int k)

{

	LL t=1;

	for(; k; k>>=1, x=x*x%mod)

		if(k&1) t=t*x%mod;

	return t;

}

inline int C(int n,int m){

	return 1ll*sum[n]*inv[m]%mod*inv[n-m]%mod;

}

int main()

{

	n=read(), inv[0]=sum[0]=1;

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

	for(int i=1; i<=n; ++i) sum[i]=1ll*sum[i-1]*i%mod, inv[i]=1ll*inv[i-1]*FP(i,mod-2)%mod;

	f[n+1]=1;

	for(int i=n; i; --i)

	{

		if(A[i]<=0) continue;

		LL tmp=0;

		for(int j=i+1+A[i]; j<=n+1; ++j) tmp+=1ll*C(j-i-1,A[i])*f[j]%mod;

		f[i]=(int)(tmp%mod);

	}

	LL ans=0;

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

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

	return 0;

}

E.We Need More Bosses(圆方树)

\(Description\)

给定一张无向图。你可以任选两个点S,T(S≠T)作为起点终点，记v为S->T必须经过的边的数量，求最大的v。

(such that连用时such就是个代词啊 学到了)

\(Solution\)

圆方树缩环，方点与圆点之间的边边权为0，圆点之间的边边权为1，求直径。

不想在圆点间再建方点。。

官方题解：与答案有关的边一定是桥。把所有之间没有桥的点合并为1个点，建出一棵新树。求这棵树的直径。反正就这样了。

圆方树还跑了个Rank1 233

//93ms	38500KB

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

const int N=3e5+5;

int n,m,tot,Index,dfn[N],low[N],Max,V,top,sk[N];

struct Edge

{

	int Enum,H[N<<1],nxt[N<<2],to[N<<2],val[N<<2];//Square point...

	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;

	}

	inline void AddTreeEdge(int u,int v,int w)

	{

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

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

	}

}G,T;

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;

}

void Tarjan(int x,int f)

{

	low[x]=dfn[x]=++Index, sk[++top]=x;

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

		if(!dfn[v=G.to[i]])

		{

			Tarjan(v,x), low[x]=std::min(low[x],low[v]);

			if(dfn[x]==low[v])

			{

				T.AddTreeEdge(x,++tot,0);

				do{

					T.AddTreeEdge(tot,sk[top--],0);

				}while(sk[top+1]!=v);

			}

			else if(dfn[x]<low[v]) T.AddTreeEdge(x,v,1), --top;//出栈！

		}

		else if(v!=f) low[x]=std::min(low[x],dfn[v]);

}

void DFS(int x,int f,int d)

{

	if(d>Max) Max=d, V=x;

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

		if(T.to[i]!=f) DFS(T.to[i],x,d+T.val[i]);

}

int main()

{

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

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

	Tarjan(1,1);

	DFS(1,1,0), DFS(V,V,0);

	printf("%d",Max);

	return 0;

}

F.One Occurrence(线段树)

\(Description\)

给定一个长为n的序列，多次询问[l,r]中只出现一次的数，输出任意一个即可(没有输出0)。

\(Solution\)

记\(las[i],nxt[i]\)分别为\(A[i]\)上一次、下一次出现的位置，则会对区间\([l,r]\)产生贡献当且仅当\(las[i]<l\ \&\&\ r<nxt[i]\)，也就是\(A[i]\)会对\([las[i]+1,nxt[i]-1]\)产生贡献。这应该可以用线段树区间修改。

将询问离线，按右端点排序，枚举当前点\(i\)作为右端点，用线段树维护\([1,i]\)上\(las[p]\)最小的位置\(p\)。

那么如果\(\min\{las[p]\}<l\)，则\(p\)为所求解之一；否则无解。

当前\(A[i]\)的出现会消除\(1\)(\(las[las[i]])\sim las[i]\)上\(las[i]\)的贡献，直接将线段树上\(las[i]\)的值(\(las[las[i]]\))改为INF即可。

不知道直接莫队+set能不能过。不过看过了的莫队(套权值分块/vector)感觉set应该没问题。

有个加强版的题见这儿。

//421ms	29184KB(Rank1了233)

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

const int N=5e5+5,INF=10000000;

int n,Q,A[N],pre[N],las[N],Ans[N];

struct Ques{

	int l,r,id;

	inline bool operator <(const Ques &x)const{

		return r<x.r;

	}

}q[N];

struct Segment_Tree

{

	#define lson rt<<1

	#define rson rt<<1|1

	#define ToL l,m,rt<<1

	#define ToR m+1,r,rt<<1|1

	int n,Min,Val,mn[N<<2],val[N<<2];

	inline void Update(int rt)

	{

		if(mn[lson]<mn[rson]) mn[rt]=mn[lson], val[rt]=val[lson];

		else mn[rt]=mn[rson], val[rt]=val[rson];

	}

	void Build(int l,int r,int rt)

	{

		if(l==r) mn[rt]=las[l], val[rt]=A[l];

		else

		{

			int m=l+r>>1;

			Build(ToL), Build(ToR);

			Update(rt);

		}

	}

	void Modify(int l,int r,int rt,int p)//Modify t[p] to INF

	{

		if(l==r) mn[rt]=INF;

		else

		{

			int m=l+r>>1;

			if(p<=m) Modify(ToL,p);

			else Modify(ToR,p);

			Update(rt);

		}

	}

	void Query(int l,int r,int rt,int L,int R)

	{

		if(L<=l && r<=R){

			if(mn[rt]<Min) Min=mn[rt], Val=val[rt];

		}

		else

		{

			int m=l+r>>1;

			if(L<=m) Query(ToL,L,R);

			if(m<R) Query(ToR,L,R);

		}

	}

	int Get_Ans(int l,int r)

	{

		Min=INF, Query(1,n,1,l,r);

		return Min<l?Val:0;

	}

}T;

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

{

	T.n=n=read();

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

	T.Build(1,n,1);

	Q=read();

	for(int i=1; i<=Q; ++i) q[i].l=read(), q[i].r=read(), q[i].id=i;

	std::sort(q+1,q+1+Q), q[Q+1].r=n+1;

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

	{

		if(las[i]) T.Modify(1,n,1,las[i]);

		while(/*now<=Q &&*/q[now].r==i) Ans[q[now].id]=T.Get_Ans(q[now].l,i), ++now;

	}

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

	return 0;

}

G.Two-Paths(树形DP)

\(Description\)

给定一棵带边权的树。多次询问，每次给出两个点s,t，求从S到T可获得的最大权值和。权值定义为经过的点权(只计算一次)减去经过的边权(多次叠加计算)，且每条边最多只能走两次。

\(Solution\)

ps:随便走指按最优方案走。

对于询问u->v，令\(w=LCA(u,v)\)，我们分别求u->w和w->v的答案。

可以想到，令\(sub[x]\)表示从\(x\)出发在\(x\)的子树中随便走可得到的最大权值和，则$$sub[fa[x]]=∑max(0,sub[son[x]]-2val[x\rightarrow son[x]])$$

对于u->w，简单路径上的边只能走一次，上面点的\(sub[]\)可以累加。于是考虑前缀和，求个 从根节点到达当前节点前，可以在任意节点的子树中随便走，得到的最大权值和\(sum\)。

则$$sum[x]=sum[fa[x]]+sub[fa[x]]-(x对sub[fa[x]]的贡献)-(val[fa[x]\rightarrow x])$$

\(x\)对\(sub[fa[x]]\)的贡献即\(max(0,sub[x]-2*val[fa[x]\rightarrow x])\)，为方便可以令$$fe[x]=val[fa[x]\rightarrow x],f[x]=max(0,sub[x]-2val[fa[x]\rightarrow x])$$。则$$sum[x]=sum[fa[x]]+sub[fa[x]]-f[x]-fe[x]$$

还可以在\(w\)的上面随便走，所以令\(up[x]\)表示由\(x\)向上随便走得到的最大权值和，$$up[x]=max(0,up[fa[x]]+sub[fa[x]]-f[x]-2*fe[x])$$

则\(Ans(u,v)=sum[u]+sum[v]-2*sum[w]+sub[u]+sub[v]+up[w]\)？

设u1,v1分别为w->u,w->v路径上要到的第一个点。\(sum[w]\)还没有计算\(w\)的子树，但\(sum[u1],sum[v1]\)都计算了，且分别少个\(u1,v1\)对\(sum[w]\)的贡献，那就正好算重了一个\(sum[w]\)。减掉就行了。

Rank1（现在是Rank2了）的代码真是没谁了。。不过还是感谢他的思路，题解啥的怎么都那么长。

//545ms	33600KB

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

typedef long long LL;

const int N=3e5+5;

int n,Q,A[N],Enum,H[N],to[N<<1],nxt[N<<1],val[N<<1],sz[N],son[N],fa[N],dep[N],top[N];

LL f[N],fe[N],sub[N],sum[N],up[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 w,int u,int v)

{

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

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

}

inline int LCA(int u,int v)

{

	while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];

	return dep[u]>dep[v]?v:u;

}

void DFS1(int x)

{

	int mx=0; sz[x]=1, sub[x]=A[x];

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

		if((v=to[i])!=fa[x])

		{

			fa[v]=x, dep[v]=dep[x]+1, fe[v]=val[i], DFS1(v), sz[x]+=sz[v], sub[x]+=f[v];

			if(sz[v]>mx) mx=sz[v], son[x]=v;

		}

	f[x]=std::max(0ll,sub[x]-2ll*fe[x]);

}

void DFS2(int x,int tp)

{

	top[x]=tp;

	sum[x]=sub[fa[x]]-f[x]-fe[x];

	up[x]=std::max(0ll,up[fa[x]]+sum[x]-fe[x]);//up[fa[x]]+sub[fa[x]]-f[x]-2*fe[x]

	sum[x]+=sum[fa[x]];

	if(son[x])

	{

		DFS2(son[x],tp);

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

			if(to[i]!=fa[x]&&to[i]!=son[x]) DFS2(to[i],to[i]);

	}

}

int main()

{

	n=read(), Q=read();

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

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

	DFS1(1), DFS2(1,1);

	for(int u,v,w,i=1; i<=Q; ++i)

		u=read(), v=read(), w=LCA(u,v), printf("%I64d\n",sum[u]+sum[v]-(sum[w]<<1)+sub[u]+sub[v]-sub[w]+up[w]);

	return 0;

}

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

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

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

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