AtCoder Grand Contest 034-526互联

Kenken Race

可以分成两种情况：

当 \(A\leq B\leq C\leq D\) 时，先让 \(B\) 到 \(D\)，在让 \(A\) 到 \(C\)；
当 \(A\leq B\leq D\leq C\) 时，判断一下 \(B\to D\) 是否有三个连续的 .。

然后判断一下 \(A\to C,B\to D\) 是否有两个连续的 # 即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=200005;
int n,a,b,c,d;
char s[N];
int main()
{
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d); //a->c b->d
	scanf("%s",s+1);
	if(a<b&&c>d)
	{
		bool flag=false;
		for(int i=b;i<=d;i++)
			if(s[i-1]=='.'&&s[i]=='.'&&s[i+1]=='.')
			{
				flag=true;
				break;
			}
		if(!flag)
		{
			printf("No");
			return 0;
		}
		for(int i=a+1;i<=c;i++)
			if(s[i-1]=='#'&&s[i]=='#')
			{
				printf("No");
				return 0;
			}
		printf("Yes");
		return 0;
	}
	else
	{
		for(int i=b+1;i<=d;i++)
			if(s[i-1]=='#'&&s[i]=='#')
			{
				printf("No");
				return 0;
			}
		for(int i=a+1;i<=c;i++)
			if(s[i-1]=='#'&&s[i]=='#')
			{
				printf("No");
				return 0;
			}
		printf("Yes");
		return 0;
	}
	return 0;
}

B - ABC

分成 BC 和 A，每个 BC 都可以跟它前面的相邻 A 匹配，记录一下前面连续的 A 的数量，遇到单个的 B，C 清空即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200005;
int n;
char s[N];
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	int A=0;
	long long ans=0;
	for(int i=1;i<=n;i++)
		if(s[i]=='B'&&s[i+1]=='C') ans+=A,i++;
		else if(s[i]=='A') A++;
		else if(s[i]=='B'||s[i]=='C') A=0;
	printf("%lld",ans);
	return 0;
}

C - Tests

可以发现，重要度只可能为 \(u_i\) 和 \(l_i\) 中的一个，如果 \(a_i\ge b_i\) 选 \(u_i\)，\(a_i< b_i\) 选 \(l_i\)。

可以二分一个 \(mid\)，判断学习 \(mid\) 后能否合法。可以发现，我们肯定是将一个前缀 \(a_i\) 置为 \(X\)，一个后缀 \(a_i\) 置为 \(0\)，中间有一个 \(0\sim X\) 的 \(a_i\)。

我们肯定贪心的使收益最大的在前面。但是选 \(u_i\) 和 \(l_i\) 时 Aoki 的得分是不同的，不妨将 \(\le l_i\) 的部分将两个人都看做 \(l_i\) 的贡献。那么对 \(i\) 门科目，对于 \(a_i\ge b_i\) 的贡献为 \((a_i-b_i)u_i+b_il_i\)，\(a_i< b_i\) 的贡献为 \(a_il_i\)。

将所有科目按照 \((X-b_i)u_i+b_il_i\) 排序，枚举取 \(0\sim X\) 的 \(a_i\) 的位置 \(i\)，然后贪心的填即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n,X;
struct Node
{
	int b,l,u;
	long long v;
}a[N];
long long sum[N];
long long A,B;
bool check(long long x)
{
	int t=min(x/X,(long long)n),ret=x%X;
	for(int i=1;i<=t;i++)
	{
		long long add=0;
		if(ret>a[i].b) add=1LL*(ret-a[i].b)*a[i].u+1LL*a[i].b*a[i].l;
		else add=1LL*ret*a[i].l;
		if(sum[min(t+1,n)]-a[i].v+add>=B) return true;
	}
	for(int i=t+1;i<=n;i++)
	{
		long long add=0;
		if(ret>a[i].b) add=1LL*(ret-a[i].b)*a[i].u+1LL*a[i].b*a[i].l;
		else add=1LL*ret*a[i].l;
		if(sum[t]+add>=B) return true;
	}
	return sum[t]>=B;
}
int main()
{
	scanf("%d%d",&n,&X);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i].b,&a[i].l,&a[i].u);
		a[i].v=1LL*(X-a[i].b)*a[i].u+1LL*a[i].b*a[i].l;
	}
	sort(a+1,a+n+1,[=](const Node &x,const Node &y){return x.v>y.v;});
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+a[i].v;
	for(int i=1;i<=n;i++)
		B+=1LL*a[i].b*a[i].l;
	long long l=0,r=1e10,ans=-1;
	while(l<=r)
	{
		long long mid=(l+r)/2;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld",ans);
	return 0;
}

D - Manhattan Max Matching

直接连边的话边数有 \(n^2\) 条，无法通过。

将绝对值拆开：

\[|x_1-x_2|+|y_1-y_2|=\max\{ x_1-x_2+y_1-y_2, x_1-x_2-y_1+y_2, -x_1+x_2+y_1-y_2, -x_1+x_2-y_1+y_2 \} \]

可以发现两个点是独立的：

\[|x_1-x_2|+|y_1-y_2|=\max\{ (x_1+y_1)+(-x_2-y_2), (x_1-y_1)+(-x_2+y_2), (-x_1+y_1)+(x_2-y_2), (-x_1-y_1)+(x_2+y_2) \} \]

中间建四个点，分别表示四种情况，分别连边然后跑最大费用最大流即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=2010;
const int INF=1061109567;
const long long LINF=4557430888798830399;
int n;
int rx[N],ry[N],rc[N];
int bx[N],by[N],bc[N];
struct Edge
{
	int to,next;
	long long flow,cost;
}edge[N*10];
int head[N],cur[N],cnt=1;
void add_edge(int u,int v,int c,int f)
{
	cnt++;
	edge[cnt].to=v;
	edge[cnt].cost=c;
	edge[cnt].flow=f;
	edge[cnt].next=head[u];
	head[u]=cnt;
	return;
}
void add(int u,int v,int c,int f)
{
	add_edge(u,v,c,f);
	add_edge(v,u,-c,0);
	return;
}
int s,t;
long long dis[N];
bool spfa()
{
	static bool vis[N];
	memset(vis,false,sizeof(vis));
	for(int i=0;i<=2*n+5;i++)
		dis[i]=-LINF;
	vis[s]=true;
	dis[s]=0;
	queue<int>q;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=head[u];i;i=edge[i].next)
		{
			int v=edge[i].to;
			if(edge[i].flow<=0) continue;
			if(dis[v]<dis[u]+edge[i].cost)
			{
				dis[v]=dis[u]+edge[i].cost;
				if(!vis[v])
				{
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
	return dis[t]!=-LINF;
}
bool book[N];
pair<long long,long long> dfs(int u,long long flow)
{
	if(u==t||flow==0) return make_pair(flow,0);
	book[u]=true;
	long long used=0,res=0;
	for(int &i=cur[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(book[v]||dis[v]!=dis[u]+edge[i].cost||edge[i].flow<=0) continue;
		pair<long long,long long>t=dfs(v,min(flow,edge[i].flow));
		long long now=t.first;
		res+=t.second+now*edge[i].cost;
		flow-=now;
		edge[i].flow-=now;
		edge[i^1].flow+=now;
		used+=now;
		if(flow==0) break;
	}
	book[u]=false;
	return make_pair(used,res);
}
pair<long long,long long> dinic()
{
	long long ans=0,Min=0;
	while(spfa())
	{
		memcpy(cur,head,sizeof(head));
		pair<long long,long long> res=dfs(s,INF);
		ans+=res.first,Min+=res.second;
	}
	return make_pair(ans,Min);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&rx[i],&ry[i],&rc[i]);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&bx[i],&by[i],&bc[i]);
	s=0,t=2*n+1;
	int p1=2*n+2,p2=2*n+3,p3=2*n+4,p4=2*n+5;
	for(int i=1;i<=n;i++)
	{
		add(s,i,0,rc[i]);
		add(i,p1,rx[i]+ry[i],INF);
		add(i,p2,rx[i]-ry[i],INF);
		add(i,p3,-rx[i]+ry[i],INF);
		add(i,p4,-rx[i]-ry[i],INF);
	}
	for(int i=1;i<=n;i++)
	{
		add(i+n,t,0,bc[i]);
		add(p1,i+n,-bx[i]-by[i],INF);
		add(p2,i+n,-bx[i]+by[i],INF);
		add(p3,i+n,bx[i]-by[i],INF);
		add(p4,i+n,bx[i]+by[i],INF);
	}
	long long ans=dinic().second;
	printf("%lld",ans);
	return 0;
}

E - Complete Compress

枚举最后到了哪个点，判断这个点是否合法。

可以发现，我们肯定只会进行两种操作，一种是将两个点的深度同时减一，一种是将一个点的深度减一，一个点的深度加一。仔细思考后发现第二种其实也是没用的，因为显然可以将所有二操作移到最后，最后也就不能移了。

令 \(Min_i,Max_i\) 表示考虑 \(i\) 子树中的所有的棋子离 \(i\) 的最小距离和，最大距离和。最大距离和即为所有的棋子到 \(i\) 的距离，考虑得出最小距离和。

对于子树中所有点到根的深度 \(d_1,d_2,\cdots ,d_n\)，操作等价于将 \(d_i,d_j\ (i\neq j)\) 分别减一。令 \(S\) 为 \(d_i\) 的和，则如果 \(\max\{d\}-(S-\max\{d\})\ge 0\)，最后剩下的即为 \(\max\{d\}-(S-\max\{d\})\)，否则剩下的即为 \(\max\{d\} \bmod 2\)。

我们需要将最后剩下的等于 \(0\)，则如果 \(\max\{d\}-(S-\max\{d\})\ge 0\)，我们可以递归 \(\max\{d\}\) 的子树，将 \(d\) 减少为 \(Min\)。

判断根节点的 \(Min\) 是否为 \(0\) 即可。

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=2005;
const int INF=1061109567;
int n;
int a[N];
vector<int>G[N];
long long Min[N],Max[N];
int siz[N];
int son[N];
void dfs1(int u,int father)
{
	siz[u]=0;
	if(a[u]) siz[u]++;
	Max[u]=0;
	son[u]=0;
	for(int v:G[u])
	{
		if(v==father) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		Max[u]+=Max[v]+siz[v];
		if(Max[v]>Max[son[u]]) son[u]=v;
	}
	return;
}
void dfs2(int u,int father)
{
	if(!son[u])
	{
		Min[u]=0;
		return;
	}
	dfs2(son[u],u);
	int mi=Min[son[u]]+siz[son[u]],mx=Max[son[u]]+siz[son[u]];
	if(mi-(Max[u]-mx)>=0) Min[u]=mi-(Max[u]-mx);
	else Min[u]=Max[u]&1;
	return;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%1d",&a[i]);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	Max[0]=-1;
	long long ans=INF;
	for(int u=1;u<=n;u++)
	{
		dfs1(u,0);
		dfs2(u,0);
		if(Min[u]==0) ans=min(ans,Max[u]/2);
	}
	if(ans>=INF) printf("-1");
	else printf("%lld",ans);
	return 0;
}

F - RNG and XOR

咕咕咕。

atcoder contest grand 034

authentic atcoder contest grand

negative atcoder contest grand

atcoder contest radius grand

atcoder contest grand 022

atcoder contest grand 001

atcoder contest descent grand

histogram atcoder contest grand

atcoder contest grand 019

atcoder contest grand 017