Educational Codeforces Round 92 Summary

Educational Codeforces Round 92 Summary(2020-7-29 22:35-0:35)

xiaoh 2020-8-2

A-LCM Problem

题意

给定两个正整数$l,r$，求满足$l\leq x<y\leq r$且$l\leq lcm(x,y)\leq r$的任意一对$(x,y)$，或者判断其不存在。

数据范围

$1\leq t\leq 10^4,1\leq l<r\leq 10^9$

题解

因为$x\ne y$，所以$lcm(x,y)\geq 2x$。所以$r\ge 2l$时有解，否则无解。构造的话直接$(l,2l)$即可。每个数据常数复杂度。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
int main()
{
	int t;
	read(t);
	while(t--)
	{
		int l,r;
		read(l),read(r);
		if(l*2>r) printf("-1 -1\n");
		else printf("%d %d\n",l,l*2);
	}
	return 0;
}

B-Array Walk

题意

给定$n$个正整数$a_i$，从$a_1$开始，我们每次选择左移一步或者右移一步（但不能连续右移），每到达一个点就将答案加上这个数（包括起点）。现在一共要走$k$步，且至多能向左$z$步。求能获得的最大答案。

数据范围

$1\leq t\leq 10000,2\leq k<n\leq 10^5,0\leq z\leq \min(5,k),\sum n\leq 3\times 10^5$

题解

注意到每次向左即将答案加上连续两个数的贡献。从$0-z$枚举向左的步数，然后找出连续两个数的和最大的一对相邻的数，反复走$z$次能使答案最大。每个数据$O(nk)$。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=100010;
int n,k,z;
int a[MAXN];
int main()
{
	int t;
	read(t);
	while(t--)
	{
		read(n),read(k),read(z);
		for(int i=1;i<=n;++i) read(a[i]);
		int ans=0;
		for(int i=0;i<=z;++i)
		{
			int sum=0,maxn=0;
			for(int j=1;j<=k-2*i+1;++j) sum+=a[j],maxn=max(maxn,a[j]+a[j+1]);
			ans=max(ans,sum+maxn*i);
		}
		write(ans),putchar('\n');
	}
	return 0;
}

C-Good String

题意

给定一个数字串$s$，现在构造两个新串$s_ns_1s_2\dots s_{n-1}$和$s_2s_3\dots s_ns_1$。求最少在$s$中删去多少个数可以使这两个串相等。

数据范围

$1\leq t\leq 1000,2\leq |s|\leq \sum |s|\leq 2\times 10^5$

题解

根据代数方法我们发现原串要么为$aaaaa\dots$形式，要么为$abab\dots abab$形式。暴力枚举$a,b$并计算需要删除多少数位即可。时间复杂度$O(100|s|)$。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=200010;
int n;
int a[MAXN];
char ch[MAXN];
int cnt[20];
int main()
{
	int t;
	read(t);
	while(t--)
	{
		memset(cnt,0,sizeof(cnt));
		scanf("%s",ch+1);
		n=strlen(ch+1);
		for(int i=1;i<=n;++i) a[i]=ch[i]-'0';
		int maxn=0;
		for(int i=1;i<=n;++i) ++cnt[a[i]],maxn=max(maxn,cnt[a[i]]);
		int ans=n-maxn;
		for(int i=0;i<=9;++i)
		for(int j=0;j<=9;++j)
		{
			int ret=0,p=1,cur=i;
			while(p<=n)
			if(a[p]==cur)
			{
				if(cur==i) cur=j;
				else cur=i;
				++p;
			}
			else ++ret,++p;
			if((n-ret)%2!=0) ++ret;
			ans=min(ans,ret);
		}
		write(ans),putchar('\n');
	}
	return 0;
}

D-Segment Intersections

题意

有$2$组每组$n$条线段，第一组的每条线段都为$[l1,r1]$，记为$a_i$，第二组的则为$[l2,r2]$记为$b_i$。现在每次操作可以延长任何一条线段，求使$\sum_{i=0}^nintersect(a_i,b_i)\ge k$的最小操作次数。

数据范围

$1\leq t\leq 1000,1\leq n\leq \sum n\leq 2\times 10^9,1\leq l1,l2,r1,r2,k\leq 10^9$

题解

若两条线段本身相交，则延长任意一条即可使答案$+1$，显然最优。所以一直操作直至所有线段对等长，然后每两次操作使答案$+1$，直接统计即可。

否则两个需要延长一定次数后相交，期间对相交长度无贡献，然后每次延长答案$+1$直至两者等长，所有等长后$2$次操作使答案$+1$，遍历$1-n$枚举使几对线段相交即可。总的复杂度为线性。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
long long n,k,l1,r1,l2,r2;
int main()
{
	int t;
	read(t);
	while(t--)
	{
		read(n),read(k),read(l1),read(r1),read(l2),read(r2);
		if(max(l1,l2)<=min(r1,r2))
		{
			k-=n*(min(r1,r2)-max(l1,l2));
			long long tmp=n*(max(r1,r2)-min(l1,l2)-(min(r1,r2)-max(l1,l2)));
			if(k<=0) write(0),putchar('\n');
			else if(tmp>=k) write(k),putchar('\n');
			else write(tmp+(k-tmp)*2),putchar('\n');
		}
		else
		{
			long long dis=max(l1,l2)-min(r1,r2),project=max(r1,r2)-min(l1,l2);
			long long ans=1e18+7;
			for(long long i=1;i<=n;++i)
			if(project*i>=k) ans=min(ans,dis*i+k);
			else ans=min(ans,dis*i+project*i+(k-project*i)*2);
			write(ans),putchar('\n');
		}
	}
	return 0;
}

E-Calendar Ambiguity

题意

某纪年法中一年有$m$个月，每个月$d$天，且$w$天一个星期（$1$月$1$号为周一）。记$(x,y)$为第$x$个月第$y$天是星期几。求$(x,y)=(y,x)$且$x<y$的对数。

数据范围

$1\leq t\leq 1000,1\leq m,d,w\leq 10^9$

题解

我们取$w$的剩余系考虑。则$(x-1)d+y=(y-1)d+x$，变形得：$(x-y)(d-1)=0$。所以$(x-y)$为$\frac{w}{gcd(d-1,y)}$的倍数。因为$1\leq x,y\leq min(m,d)$，所以直接找规律然后用等差数列求和即可。常数复杂度

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
long long m,d,w;
long long gcd(long long a,long long b)
{
	return (b==0)? a:gcd(b,a%b);
}
int main()
{
	int t;
	read(t);
	while(t--)
	{
		read(m),read(d),read(w);
		long long k=min(m,d);
		if(d==1) printf("%lld\n",k*(k-1)/2);
		else
		{
			long long tmp=w/gcd(w,d-1);
			long long p=k/tmp;
			write((k-tmp+k-p*tmp)*p/2),putchar('\n');
		}
	}
	return 0;
}

F-Bicolored Segments

题意

有两种颜色的线段共$n$条，现在选择这些线段的一个子集，满足异色的线段无相交。

数据范围

$1\leq n\leq 2\times 10^5,1\leq l_i,r_i\leq 10^9$

题解

考虑线段树维护动态规划

首先，上面的做法显然是可行的，但是实在是太长了，所以采用官方提供的简单做法……

考虑建图，将异色相交的线段连边，显然原图为二分图，因此答案为$n-$最大匹配。

接下来考虑贪心求最大匹配。我们将一条线段$[l,r]$看做两个事件，从$l$开始线段出现，直至$r$消失。那么根据贪心，在一条线段消失时，在对面匹配一条$r$最小的未消失线段即可。用微扰法可证明这是最优的。用set维护即可。时间复杂度$O(n\log n)$。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=200010;
int n,n1,n2;
struct node{
	int l,r,t;
}a[MAXN];
int tot1,tot2;
struct node2{
	int pos,val,type;
	friend bool operator <(node2 x,node2 y)
	{
		if(x.val!=y.val) return x.val<y.val;
		else return x.pos<y.pos;
	}
};
set<node2> f[2];
vector<node2> g;
inline bool cmp(node2 x,node2 y)
{
	if(x.val!=y.val) return x.val<y.val;
	else if(x.type!=y.type) return x.type<y.type;
	else return x.pos<y.pos;
}
int main()
{
	read(n);
	for(int i=1;i<=n;++i) read(a[i].l),read(a[i].r),read(a[i].t),--a[i].t,g.push_back({i,a[i].l,0}),g.push_back({i,a[i].r,1});
	sort(g.begin(),g.end(),cmp);
	int ans=0;
	for(vector<node2>::iterator it=g.begin();it!=g.end();++it)
	{
		int op=a[it->pos].t,tmp=it->type;
		if(tmp==0) f[op].insert({it->pos,a[it->pos].r,0});
		else
		{
			if(f[op].count({it->pos,a[it->pos].r,0})&&!f[op^1].empty()) f[op^1].erase(f[op^1].begin()),++ans;
			if(f[op].count({it->pos,a[it->pos].r,0})) f[op].erase({it->pos,a[it->pos].r,0});
		}
	}
	write(n-ans),putchar('\n');
	return 0;
}

G-Directing Edges

题意

有一张$n$个点，$m$条边的无向连通图，有$k$个指定点$v1,v2,\dots,v_k$。对于每一条边，你可以选择给它指定一个方向，这不需要代价，或者使它保持双向，这需要$w_i$的代价。对于每个点，若从所有指定点出发都能到达这个点，则称这个点饱和的，则你可以获得$c_i$的代价。求对于$i\in [1,n]$当$i$饱和时可以获得的最大的代价。

数据范围

$2\leq n\leq 3\times 10^5,n-1\leq m\leq min(\frac{n(n-1)}{2},3\times 10^5),1\leq k\leq n,0\leq c_i,w_i\leq 10^9$

题解

个人认为出的超级好的一道题。

首先，注意到对于每一个边双，其中的所有点要么同时饱和，要么同时不饱和。因为对于每一个边双，必有一种定向方法使其成为一个强连通分量。所以用$Tarjan$缩点成一棵树。

接下来考虑进行树上$dp$。记$f_i$为当$i$饱和时，$i$所在的子树的最大代价。则当所有指定点都不在这棵子树中时，或所有指定点都在$i$的某一个儿子中时，可以给从$i$连向$son_i$的边定向，同时也能获得$f_{son_i}$的所有收益。前者可以通过从儿子连向爸爸，后者可以通过爸爸连向儿子满足。否则，只有不给这条边定向时，才能获得$f_{son_i}$的收益，即获得$max(0,f_{son_i}-edge(i,son_i))$的收益。直接$dp$即可。

根据上述做法，我们得到了一个$n^2$的做法。那么如何将其优化为$O(n)$呢？我们想到了”二次扫描与换根法“。我们在以$1$为根$dp$后，再次扫描整棵树，并计算出对于每个$i$，当$i$为根时的答案。显然，每次计算时受影响的只有$i$和$son_i$。所以直接深搜即可。具体的转换可以参考代码。

总的复杂度是一个（常数超级超级大的）线性。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=300010;
int n,m,k;
int c[MAXN],v[MAXN];
long long c2[MAXN];
int tot=2;
int edge[MAXN*2],nxt[MAXN*2],w[MAXN*2],hd[MAXN];
inline void add_edge(int u,int v)
{
	edge[tot]=v,nxt[tot]=hd[u],hd[u]=tot++;
}
int cnt=0;
int low[MAXN],dfn[MAXN];
bool bridge[MAXN*2];
void Tarjan(int p,int fa)
{
	dfn[p]=low[p]=++cnt;
	for(int i=hd[p];i;i=nxt[i])
	if(edge[i]!=fa)
	{
		int x=edge[i];
		if(dfn[x]) low[p]=min(low[p],dfn[x]);
		else
		{
			Tarjan(x,p);
			low[p]=min(low[p],low[x]);
			if(low[x]>dfn[p]) bridge[i]=bridge[i^1]=1;
		}
	}
}
int id[MAXN];
void dfs(int p)
{
	id[p]=cnt;
	for(int i=hd[p];i;i=nxt[i])
	if(!id[edge[i]]&&!bridge[i]) dfs(edge[i]);
}
struct graph{
	int tot=1;
	int edge[MAXN*2],nxt[MAXN*2],w[MAXN*2],hd[MAXN];
	inline void add_edge(int u,int v,int c)
	{
		edge[tot]=v,nxt[tot]=hd[u],w[tot]=c,hd[u]=tot++;
	}
}g;
int v2[MAXN],num[MAXN];
long long f[MAXN];
int dp(int p,int fa)
{
	int tmp=v2[p];
	f[p]=c2[p];
	for(int i=g.hd[p];i;i=g.nxt[i])
	if(g.edge[i]!=fa)
	{
		tmp+=dp(g.edge[i],p);
		if(num[g.edge[i]]==0||num[g.edge[i]]==k) f[p]+=f[g.edge[i]];
		else f[p]+=max(f[g.edge[i]]-g.w[i],0ll); 
	}
	num[p]=tmp;
	return tmp;
}
long long ans[MAXN];
void reroot(int p,int fa,long long cur,int e)
{
	long long tmp=f[p];
	if((num[p]!=0&&num[p]!=k)||fa==-1) cur-=max(0ll,tmp-e),tmp+=max(0ll,cur-e);
	else cur-=tmp,tmp+=cur;
	ans[p]=tmp;
	for(int i=g.hd[p];i;i=g.nxt[i])
	if(g.edge[i]!=fa) reroot(g.edge[i],p,tmp,g.w[i]);
}
int main()
{
	read(n),read(m),read(k);
	for(int i=1;i<=k;++i) read(v[i]);
	for(int i=1;i<=n;++i) read(c[i]);
	for(int i=1;i<=m;++i) read(w[i<<1]),w[i<<1|1]=w[i<<1];
	for(int i=1;i<=m;++i)
	{
		int u,v;
		read(u),read(v);
		add_edge(u,v),add_edge(v,u);
	}
	Tarjan(1,-1);
	cnt=0;
	for(int i=1;i<=n;++i)
	if(!id[i]) ++cnt,dfs(i);
	for(int i=1;i<=n;++i)
	for(int j=hd[i];j;j=nxt[j])
	if(id[i]!=id[edge[j]]) g.add_edge(id[i],id[edge[j]],w[j]);
	for(int i=1;i<=n;++i) c2[id[i]]+=c[i];
	for(int i=1;i<=k;++i) ++v2[id[v[i]]];
	dp(1,-1);
	reroot(1,-1,0,0);
	for(int i=1;i<=n;++i) write(ans[id[i]]),putchar(' ');putchar('\n');
	return 0;
}