1. 首页
  2. 文章中心
  3. 杂项

Atcoder AGC006 题解A - Prefix and SuffixB - Median Pyramid EasyC - Rabbit ExerciseD - Median Pyramid HardE - Rotate 3x3F - Blackout

69 阅读 0 评论
我是靠谱客的博主 老迟到酒窝，最近开发中收集的这篇文章主要介绍Atcoder AGC006 题解A - Prefix and SuffixB - Median Pyramid EasyC - Rabbit ExerciseD - Median Pyramid HardE - Rotate 3x3F - Blackout，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A - Prefix and Suffix

这个…暴力匹配就可以啦。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int N=105;
int n;char S[N],T[N];
int check(int l) {
	for(RI i=n-l+1;i<=n;++i)
		if(S[i]!=T[i-n+l]) return 0;
	return 1;
}
int main()
{
	scanf("%d",&n);
	scanf("%s",S+1),scanf("%s",T+1);
	for(RI i=n;i>=0;--i)
		if(check(i)) {printf("%dn",2*n-i);break;}
	return 0;
}

B - Median Pyramid Easy

如果 x = 1 x=1 x=1或者 2 n − 1 2n-1 2n−1，显然无解。

否则在金字塔的所有行的中间位置都放上 x x x。

看向从下往上第一行的中间位置，既然第二行的中间位置也要是 x x x，则说明中间位置两边两个位置，要分别是一个比 x x x大的数和一个比 x x x小的数。

接着发现，如果三个数中出现了一个 x x x和一个比 x x x大的数，则它们的中位数一定是大于等于 x x x的数。那么第二行 x x x两边一定是一个大于等于 x x x的数和一个小与等于 x x x的数，再往上也是同样。

所以只要在中间位置摆上 x x x， x x x的两边摆上 x − 1 x-1 x−1和 x + 1 x+1 x+1，剩下的位置就可以随便放了。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int n,x;
int main()
{
	scanf("%d%d",&n,&x);
	if(x==1||x==2*n-1) {puts("No");return 0;}
	puts("Yes");
	int now=0;
	for(RI i=1;i<n-1;++i) {
		++now;while(now==x-1||now==x||now==x+1) ++now;
		printf("%dn",now);
	}
	printf("%dn%dn%dn",x-1,x,x+1);
	for(RI i=1;i<n-1;++i) {
		++now;while(now==x-1||now==x||now==x+1) ++now;
		printf("%dn",now);
	}
	return 0;
}

C - Rabbit Exercise

假设 p i p_i pi​为第 i i i个点的期望位置，则执行一次操作 x x x后， p x p_x px​将变为 2 p x + 1 − p x + 2 p x − 1 − p x 2 = p x + 1 + p x − 1 − p x frac{2p_{x+1}-p_x+2p_{x-1}-p_x}{2}=p_{x+1}+p_{x-1}-p_x 22px+1​−px​+2px−1​−px​​=px+1​+px−1​−px​

令 d i = p i − p i − 1 d_i=p_i-p_{i-1} di​=pi​−pi−1​，带入上面的式子算一下 d d d的改变情况，发现 d x d_x dx​会变成 p x + 1 − p x p_{x+1}-p_x px+1​−px​而 d x + 1 d_{x+1} dx+1​会变成 p x − p x − 1 p_x-p_{x-1} px​−px−1​。那么这么这个操作相当于将 d x + 1 d_{x+1} dx+1​和 d x d_x dx​交换位置。

先求出进行一轮操作后，在 i i i位置上的 d d d会被换到哪个位置。然后利用倍增求解 K K K轮操作，再通过 d d d还原出 p p p即可。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
LL read() {
	LL q=0,w=1;char ch=' ';
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-') w=-1,ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+(LL)(ch-'0'),ch=getchar();
	return q*w;
}
const int N=100005;
int n,m,to[60][N];LL K,bin[60],p[N],d[N],a[N],b[N];
int work(int x) {
	for(RI i=59;i>=0;--i) if(K&bin[i]) x=to[i][x];
	return x;
}
int main()
{
	n=read();
	for(RI i=1;i<=n;++i) p[i]=read(),d[i]=p[i]-p[i-1];
	m=read(),K=read();
	for(RI i=1;i<=n;++i) a[i]=i;
	for(RI i=1;i<=m;++i) {int x=read();swap(a[x],a[x+1]);}
	for(RI i=1;i<=n;++i) to[0][a[i]]=i;
	bin[0]=1;for(RI i=1;i<=59;++i) bin[i]=bin[i-1]<<1;
	for(RI j=1;j<=59;++j)
		for(RI i=1;i<=n;++i) to[j][i]=to[j-1][to[j-1][i]];
	for(RI i=1;i<=n;++i) a[i]=work(i);
	for(RI i=1;i<=n;++i) b[a[i]]=i;
	for(RI i=1;i<=n;++i)
		p[i]=p[i-1]+d[b[i]],printf("%lld.0n",p[i]);
	return 0;
}

D - Median Pyramid Hard

二分答案，将大于等于你二分出的这个答案的数都变成 1 1 1，否则变成 0 0 0。

任意两个连续的 1 1 1的上面一定是两个连续的 1 1 1。 0 0 0也同理。

对于一段 0101010101 0101010101 0101010101，我们发现往上一行，这一串两边会被 0 0 0或者 1 1 1“吞掉”一格（即这一串的两端会融入一段连续的0或者1中），中间的01则全部取反。

所以我们只要从中间往两边，找到第一次出现的连续01串，是0还是1即可。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
const int N=100005;
int n,a[N<<1],b[N<<1];
int check(int x) {
	for(RI i=1;i<=2*n-1;++i) b[i]=(a[i]>=x);
	for(RI i=0;i<n;++i) {
		if(b[n-i]==b[n-i-1]) return b[n-i];
		if(b[n+i]==b[n+i+1]) return b[n+i];
	}
	return b[1];
}
int main()
{
	n=read();
	for(RI i=1;i<=2*n-1;++i) a[i]=read();
	int l=1,r=2*n-1,ans;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%dn",ans);
	return 0;
}

E - Rotate 3x3

很神仙的性质题啊。

首先发现每一次操作相当于交换你选择的矩阵的第一列和第三列，然后将三列都翻转过来。这也说明：

1.任何一列的三个数字不会被拆开到不同列中

2.第二行的数字不会去其他行，第一行和第三行的数字也不会到第二行

3.原来的奇数列操作后也应该在奇数列，原来的偶数列操作后也应该在偶数列。

于是我们可以判掉一些基本的不合法情况，对奇偶性列做黑白染色。

然后构造两种操作：

1.同色相邻两列同时翻转。

记大写字母与小写字母为两种正反状态，则：

abcde -> CBAde -> CBEDa -> ebcDa -> ebAdC -> aBEdC -> aBcDe

abcde -> aDCBe -> cdABe -> cbaDe -> ABCDe -> AbCde(执行上面那串操作）

2.交换同色相邻两列，正反状态不变，改变异色列中某一列的正反状态。这个只要直接选矩阵翻转，然后执行1操作即可达成。

2操作告诉我们，如果我们将两个白色列交换（无论是否相邻），都会导致黑色列中，当前正反状态和目标矩阵的正反状态不同的列的数量的奇偶性，发生改变。将两个黑色列交换同理。

于是我们这样交换一下，就得到了黑白列关于目标矩阵，正反状态不同的列的数量的奇偶性。

如果是偶数，则可以通过1状态全部消去。否则无法消去，所以出现一个奇数，则应该输出No。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
const int N=100005;
int n,a[4][N],b[N],ans[2];
void NO() {puts("No");exit(0);}
int main()
{
	n=read();
	for(RI i=1;i<=3;++i)
		for(RI j=1;j<=n;++j) {
			a[i][j]=read();
			int x=(a[i][j]-1)%3+1,y=(a[i][j]+2)/3;
			if((i!=2&&x==2)||(i==2&&x!=2)) NO();
			if((j&1)^(y&1)) NO();
		}
	for(RI j=1;j<=n;++j) {
		int x=(a[1][j]-1)%3+1,y=(a[1][j]+2)/3;
		if((a[2][j]+2)/3!=y||(a[3][j]+2)/3!=y) NO();
		if(x==1&&(a[3][j]-1)%3+1!=3) NO();
		if(x==3&&(a[3][j]-1)%3+1!=1) NO();
		if(x==3) ans[j&1]^=1;
		b[j]=y;
	}
	for(RI i=1;i<=n;++i)
		while(b[i]!=i) ans[(i&1)^1]^=1,swap(b[i],b[b[i]]);
	if(ans[0]||ans[1]) NO();
	puts("Yes");
	return 0;
}

F - Blackout

将原题模型转化为，如果存在一个黑格子 ( x , y ) (x,y) (x,y)，则从点 x x x向点 y y y连一条有向边，如果存在边 ( x , y ) (x,y) (x,y)和边 ( y , z ) (y,z) (y,z)，则连边 ( z , x ) (z,x) (z,x)，问最后边数。

我们假设边是无向的，这样分出若干连通块，在每个连通块里搞一下。

我们将一个连通块里的点三染色，使得红点连向蓝点，蓝点连向黄点，黄点连向红点。

如果无法完成染色，则该图会被连成完全图，贡献为 n 2 n^2 n2

如果只能染出一种或两种颜色，则不会加边，贡献为 m m m

否则所有红点会向所有蓝点连边，所有蓝点会向所有黄点连边，所有黄点会向所有红点连边。设 c 1 , c 2 , c 3 c_1,c_2,c_3 c1​,c2​,c3​为三种颜色点的数量，贡献为 c 1 c 2 + c 2 c 3 + c 3 c 1 c_1c_2+c_2c_3+c_3c_1 c1​c2​+c2​c3​+c3​c1​

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
typedef long long LL;
const int N=100005;
int h[N],ne[N<<1],to[N<<1],w[N<<1],col[N];
int n,m,tot,c1,c2,flag,js[5];LL ans;
void add(int x,int y,int z) {to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
int dfs(int x,int cc) {
	col[x]=cc,++js[cc],++c1;
	for(RI i=h[x];i;i=ne[i]) {
		if(w[i]==1) ++c2;
		int nxt=(cc+w[i])%3==0?3:(cc+w[i])%3;
		if(!col[to[i]]) dfs(to[i],nxt);
		else if(col[to[i]]!=nxt) flag=1;
	}
}
int main()
{
	int x,y;
	n=read(),m=read();
	for(RI i=1;i<=m;++i) x=read(),y=read(),add(x,y,1),add(y,x,-1);
	for(RI i=1;i<=n;++i) {
		if(col[i]) continue;
		c1=c2=js[1]=js[2]=js[3]=flag=0;
		dfs(i,1);
		if(flag) ans+=1LL*c1*c1;
		else if(js[1]&&js[2]&&js[3])
			ans+=1LL*js[1]*js[2]+1LL*js[2]*js[3]+1LL*js[3]*js[1];
		else ans+=c2;
	}
	printf("%lldn",ans);
	return 0;
}

最后

以上就是老迟到酒窝为你收集整理的Atcoder AGC006 题解A - Prefix and SuffixB - Median Pyramid EasyC - Rabbit ExerciseD - Median Pyramid HardE - Rotate 3x3F - Blackout的全部内容，希望文章能够帮你解决Atcoder AGC006 题解A - Prefix and SuffixB - Median Pyramid EasyC - Rabbit ExerciseD - Median Pyramid HardE - Rotate 3x3F - Blackout所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(46)

相关文章

AGC005 补题小结
AGC005 补题小结
AGC016 A - Shrinking（暴力）
AGC016 A - Shrinking（暴力）
leetcode1015 至少有1位重复的数字
leetcode1015 至少有1位重复的数字
【AGC016F】Games on DAG（SG函数，状压DP，子集枚举）
【AGC016F】Games on DAG（SG函数，状压DP，子集枚举）
Atcoder AGC006 题解A - Prefix and SuffixB - Median Pyramid EasyC - Rabbit ExerciseD - Median Pyramid HardE - Rotate 3x3F - Blackout
Atcoder AGC006 题解A - Prefix and SuffixB - Median Pyramid EasyC - Rabbit ExerciseD - Median Pyramid HardE - Rotate 3x3F - Blackout
[agc016d]XOR Replace前言题意做法
[agc016d]XOR Replace前言题意做法
【agc028E】High Elements（动态规划，线段树，贪心）【agc028E】High Elements（动态规划，线段树，贪心）
【agc028E】High Elements（动态规划，线段树，贪心）【agc028E】High Elements（动态规划，线段树，贪心）
agc027 ABCD 题解
agc027 ABCD 题解

评论列表共有 0 条评论

立即
投稿
返回
顶部