AtCoder Grand Contest 006
吐槽
这套题要改个名字，叫神仙结论题大赛
A - Prefix and Suffix
翻译
给定两个串，求满足前缀是(S)，后缀是(T)，并且长度至少为(n)的最短串串长。
题解
暴力枚举(S)和(T)的重叠部分长度，然后直接(check)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX 105
int n,l1,l2,ans=1e9;
char S[MAX],T[MAX];
bool check(int l)
{
for(int i=l1-l+1,j=1,k=1;k<=l;++k,++i,++j)
if(S[i]!=T[j])return false;
return true;
}
int main()
{
scanf("%d",&n);scanf("%s",S+1);scanf("%s",T+1);
l1=strlen(S+1);l2=strlen(T+1);
for(int l=0;l1+l2-l>=n&&l<=l1&&l<=l2;++l)
if(check(l))ans=min(ans,l1+l2-l);
printf("%d
",ans);
return 0;
}
B - Median Pyramid Easy
翻译
给定一个塔状结构，从上往下的第(i)层有(2i-1)个位置。在最底层有一个((2n-1))的排列，然后往上的每一个格子都等于正下方，左下方，右下方三个数中第二大的那个。
显然已知顶端的数，构造一个满足条件的排列。无解输出"No"
题解
不会啊，(B)题就这么难，身败名裂。大概就是把要的数放在中间，然后让它到达上一层的个数最多，剩下的空位置按照顺序搞就行了。
#include<iostream>
#include<cstdio>
using namespace std;
int n,x,a[200200];
bool vis[200200];
int main()
{
cin>>n>>x;int m=n+n-1;
if(x==1||x==n+n-1){puts("No");return 0;}
a[(m+1)>>1]=x;a[m>>1]=x-1;a[(m>>1)+2]=x+1;
vis[x]=vis[x-1]=vis[x+1]=true;
if(m/2>1&&x+2<=m)a[m/2-1]=x+2,vis[x+2]=true;
if(m/2+3<=m&&x>=3)a[m/2+3]=x-2,vis[x-2]=true;
for(int i=1,p=1;i<=m;++i)
{
if(a[i])continue;
while(vis[p])++p;
a[i]=p;vis[p]=true;
}
puts("Yes");
for(int i=1;i<=m;++i)printf("%d
",a[i]);
return 0;
}
C - Rabbit Exercise
翻译
数轴上有(n)个点，一开始第(i)个点在位置(a_i)。
现在按照次序进行(m)次操作，每次给定一个(x)，然后从(x-1)和(x+1)两个点中等概率随机选择一个点，将(x)的坐标关于这个点对称。
这(m)次操作重复进行(K)轮，求最终每个点所在位置的期望。
题解
无论怎么样任何一个点每次操作一定是变成(2a_{x-1}(a_{x+1})-a_x)。设(f_x)表示(x)这个点当前的期望，假设当前点要进行依次变换，那么期望为(frac{1}{2}((2f_{x-1}-f_x)+(2f_{x+1}-f_x))=f_{x+1}+f_{x-1}-f_x)。
好的，然后进行(K)轮就不会了。怎么办呢？(当然是点开题解了啊)。闲着无聊来差分一下(菊开：差分是人类智慧)，设(d_i=f_i-f_{i-1})，那么执行完一次操作之后：(d_i=(f_{i-1}+f_{i+1}-f_i)-f_{i-1}=f_{i+1}-f_i)，(d_{i+1}=f_{i+1}-(f_{i-1}+f_{i+1}-f_i)=f_i-f_{i-1})。
好啊，一次操作等价于交换(d_i,d_{i+1})，那么我们只要记录一下做完一轮操作之后(d_i)都到哪里去了，然后就可以倍增了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 100100
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,x[MAX],m,d[MAX],ans[MAX],tmp[MAX];ll K;
double a[MAX];
int main()
{
n=read();
for(int i=1;i<=n;++i)x[i]=read();
m=read();cin>>K;
for(int i=1;i<=n;++i)d[i]=i,ans[i]=i;
for(int i=1;i<=m;++i)
{
int x=read();
swap(d[x],d[x+1]);
}
while(K)
{
if(K&1)
{
for(int i=1;i<=n;++i)tmp[i]=ans[d[i]];
for(int i=1;i<=n;++i)ans[i]=tmp[i];
}
for(int i=1;i<=n;++i)tmp[i]=d[d[i]];
for(int i=1;i<=n;++i)d[i]=tmp[i];
K>>=1;
}
for(int i=1;i<=n;++i)a[i]=x[ans[i]]-x[ans[i]-1];
for(int i=1;i<=n;++i)printf("%.1lf
",a[i]+=a[i-1]);
return 0;
}
D - Median Pyramid Hard
翻译
题解
一般这种比大小的题目，我们都可以二分答案，然后把所有比二分值小的设为(0)，比二分值大的设为(1)，然后再来考虑问题。
那么现在如果在最底层出现了两个连续的(1)，那么它们的上面两个数字(如果存在)也必定是两个连续的(1)，(0)同理。那么检查一下(0)还是(1)能够走到更上面就好了。否则没有出现任意两个连续的数字，那么必定和最底下那一行中奇数位置上(01)相同。
这种性质题还是要多手玩，要不然还真的想不到。而(OI)题目最重要的一点永远都是抓住题目的性质。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 100100
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,m;
int a[MAX<<1],b[MAX<<1];
bool check(int mid)
{
for(int i=1;i<=m;++i)b[i]=a[i]>=mid;
for(int 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();m=n+n-1;
for(int i=1;i<=m;++i)a[i]=read();
int l=1,r=m,ret;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))ret=mid,l=mid+1;
else r=mid-1;
}
printf("%d
",ret);
return 0;
}
E - Rotate 3x3
翻译
给定一个(3*n)的矩阵，每次可以将一个(3*3)的子矩阵旋转(180)°，初始状态下，第(i)行第(j)列填着(3*(j-1)+i)，给定目标矩阵，问是否能够旋转得到。
题解
既然说了抓性质，那就来抓旋转的性质。首先发现第二行怎么换都在第二行，然后发现无论怎么换，一个数所在位置的列永远不会变化。还发现一列的三个数是不会变动的，并且每次交换必定使得两列反过来。首先(check)一下每列的数字是否合法。接下来按列考虑，首先我们发现是可以构造出直接翻转相隔为(2)的两列而不影响其他列的方法。分奇偶考虑，计算奇数和偶数列被翻转的列的个数，显然这个的奇偶性只会与相反的奇偶性下被列被交换的次数相关，举个例子，比如说当且要交换偶数两列，那么必定以一个奇数列为中心进行交换，而这个奇数列也会被翻转，反过来一样的。那么模拟一下交换的过程，最后判断奇偶性即可。
为什么我什么题都不会做啊，总是能想一个开头却做不出来
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 100100
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n,a[4][MAX],b[4],c[MAX],t[2];
void WA(){puts("No");exit(0);}
int main()
{
n=read();
for(int i=1;i<=3;++i)
for(int j=1;j<=n;++j)
{
int p=read();
int x=(p-1)%3+1,y=(p+2)/3;
if((i==2&&x!=2)||(i!=2&&x==2))WA();
if((y&1)^(j&1))WA();
a[i][j]=p;
}
for(int j=1;j<=n;++j)
{
for(int i=1;i<=3;++i)b[i]=a[i][j];
int y=(b[1]+2)/3,x=3*y-3;
for(int i=1;i<=3;++i)if(b[i]!=x+i&&b[i]!=x+4-i)WA();
t[j&1]^=(a[1][j]>a[2][j]);c[j]=y;
}
for(int i=1;i<=n;++i)
{
while(c[i]!=i)
{
t[i&1^1]^=1;
swap(c[i],c[c[i]]);
}
}
if(t[0]||t[1])WA();
puts("Yes");return 0;
}
F - Blackout
翻译
给定一个(n*n)的网格图，有些格子是黑色的。如果((x,y),(y,z))都是黑色的，那么((y,x))也会被染黑，求最终黑格子数量。
题解
继续不会做系列
我唯一能够想到的就是网格图我们显然是存不下的，把它转化成图来考虑。于是题目变成了:给定一个(n)个点(m)条边的图，如果(x ightarrow y)，(y ightarrow z)的边都存在，那么连边(z ightarrow x)，回答边的数量。
然后开始手动翻译题解。
首先，我们可以计算每一个弱联通块(把边看成无向边的联通块)，那么答案显然就是所有弱联通块的答案的总和。我们先假定图是一个弱联通图。
考虑这样一种情况，我们把点依次标号，然后在(i)和(i+1)之间连边，那么如果(s)和(t)之间存在边(s ightarrow t)，那么当且仅当(tequiv s+1(mod 3))。具有一定启发意义，我们考虑在模(3)的意义下搞点事情。我们用(A,B,C)给所有点做标记，并且强制要求对于任意一条边，只可能是(A ightarrow B)，(B ightarrow C)，(C ightarrow A)。这样标号的方式可能不存在，但是不难证明一旦存在合法的标号方案，那么标号的方法唯一(不考虑循环(ABC)的顺序)。你可以把整个图给(dfs)一遍，这样子可以得到唯一的染色方案，或者证明它不存在。
通过标号的结果，我们可以得到三种情况，给出每种情况下的结论，等下再给出证明。
- 当标号存在，但是并没有用到所有的三种颜色，那么你无法在这个联通块中进行任何操作。
- 当标号存在，并且所有的三种颜色都被用到，那么你可以把所有(AB)之间连边，(BC)之间连边，(CA)之间连边，并且只能连这些边。
- 当标号方案不存在，你可以给任意一对点之间连边，包括自环。
利用结论，可以很容易的计算出答案，时间复杂度(O(m))。代码如下，证明内容(当然是翻译的啊)在代码后面。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 100100
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Line{int v,next,w;}e[MAX<<1];
int h[MAX],cnt=1,dg[MAX];
inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}
int n,m;ll ans;
int vis[MAX],f[3],edge,size;bool label;
void dfs(int u,int d)
{
vis[u]=d;f[d]+=1;++size;
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].v;if(e[i].w==1)++edge;
if(vis[v]==-1)dfs(v,(d+e[i].w)%3);
else if(vis[v]!=(vis[u]+e[i].w)%3)label=false;
}
}
int main()
{
n=read();m=read();
for(int i=1;i<=m;++i)
{
int x=read(),y=read();
Add(x,y,1);Add(y,x,2);
}
memset(vis,-1,sizeof(vis));
for(int i=1;i<=n;++i)
if(vis[i]==-1)
{
label=true;f[0]=f[1]=f[2]=0;size=edge=0;dfs(i,0);
if(label)ans+=(!min(f[0],min(f[1],f[2])))?(edge):(1ll*f[0]*f[1]+1ll*f[1]*f[2]+1ll*f[2]*f[0]);
else ans+=1ll*size*size;
}
cout<<ans<<endl;
return 0;
}
-
当标号存在，但是并没有用到所有的三种颜色，那么你无法在这个联通块中进行任何操作。
如果存在边((x,y))和((y,z))，那么必定意为这所有的三种颜色都会被用到。既然如此，那么意味着这里不存在上述的边，所以你不能连出任何一条新边。
-
当标号存在，并且所有的三种颜色都被用到，那么你可以把所有(AB)之间连边，(BC)之间连边，(CA)之间连边，并且只能连这些边。
必定存在若干形如((x,y),(y,z))这样的边，我们不妨令(x)染(A)，(y)染(B)，(z)染(C)。我们可以看出所有新连的边加上原边会构成一个个三角形。举个例子，令(v)存在一条边((v,x))，那么必定存在边((y,v))，那么我们不难证明任意一个(v)一定和(x,y,z)三个点中的两个有直接的边相连。所以任意的(A)都会连出一条(A ightarrow B)，其他的边同理。
-
当标号方案不存在，你可以给任意一对点之间连边，包括自环。
我们证明至少会存在一个自环。既然标号方案不存在，那么必定存在一个环导致了矛盾，注意，这个环不一定是有向环。那么这个环至少存在两条边((x,y)),((y,z))，那么我们可以连上((z,x))，那么等价于我们看这个环的时候可以直接跳过(y)。既然原先的环会导出矛盾，那么当前这个环照样会导出矛盾，那么我们重复这个过程，就可以得到自环。而其他的边存在的原因和前面两个证明类似，不再重复证明。