令人望而生畏的AGC——被称为算法竞赛题目质量之最的比赛，究竟是怎样的难度

ACM算法日常

发布于 2021-09-28 16:14:59

1.8K0

发布于 2021-09-28 16:14:59

文章被收录于专栏：ACM算法日常ACM算法日常

AGC, 即 AtCoder Grand Contest 006, 是日本一个在线比赛网站的最高难度级别比赛。AGC 的比赛频率非常低，这也是保证了其题目质量之高。

经常有人“心血来潮，开了一套AGC”，然后发现各种不会做，“感觉智商被AGC摁在地上摩擦”

今天我们来看一套比较古老的 AGC ，AGC 006

A - Prefix and Suffix

这道题目还是送温暖的...

直接枚举长度从

到

n+n

最后的

为用第二个字符串填充，剩余空缺从前到后一次用第一个字符串填充

最后验证前

位是否满足第一个字符串即可

由于是从小到大枚举，枚举到可行直接输出答案即可

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
 
using namespace std;


int n,m;
char s[110],t[110],p[210];

bool check(int x)
{
 for (int i=1;i<=n;i++)
  if (s[i]!=p[i]) return false;
 return true;
}

int main()
{
 n=read(s),n=strlen(s+1);
 m=read(t);int x=0;
 for (int i=n;i<=n+n;i++)
 {
  for (int j=1;j<=i-n;j++)
   p[j]=s[j];
  for (int j=1;j<=n;j++)
   p[(i-n)+j]=t[j];
  if (check(i)) {print(i),puts("");return 0;}
 }
 return 0;
}

B - Median Pyramid Easy

这道题目就比较有意思了

首先考虑不可行的情况，显然当

x=1

或

2*n-1

的时候是不可行的

因为每一次取的都是三个格子中的中位数，显然到第二行的时候，

或

2*n-1

就消失不见了，更高的行中不可能出现

然后考虑其余情况的构造方法

一种比较通用的构造方法是，最高行为

，我们使得下一行出现至少两个

即可，如下图所示

我们只要保证图中所有的红色格子都是

的话，最后一行一定是

那么，现在，我们只需要构造最后一行的四个格子，使得从第二行开始就在指定位置出现连续的两个

了

这样就比较思博了，

(x-1),(x),(x+1),(x-2)

即可

但是我们发现，当

x=2

的时候，会有点问题，那么我们对

x=2

特判一下，构造

(x+1),(x),(x-1),(x+2)

当然，构造的方法不唯一

最后注意特判

n=2

的情况，不过我这样构造的话，不会出现问题

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
 
using namespace std;

int n,m,a[200010],b[200010];

int main()
{
 read(n);read(m);
 if (m==1 || m==2*n-1) puts("No");
 else
 {
  puts("Yes");
  memset(a,0,sizeof(a));
  memset(b,0,sizeof(b));
  if (m>2)
  {
   a[n-1]=m-1,a[n]=m,a[n+1]=m+1,a[n+2]=m-2;
   b[m-2]=1,b[m-1]=1,b[m]=1,b[m+1]=1;
  }
  else
  {
   a[n-1]=m+1,a[n]=m,a[n+1]=m-1,a[n+2]=m+2;
   b[m-1]=1,b[m]=1,b[m+1]=1,b[m+2]=1;
  }
  int x=1;
  for (int i=1;i<n-1;i++)
  {
   while (b[x]==1) x++;
   a[i]=x;b[x]=1;
  }
  for (int i=n+3;i<=2*n-1;i++)
  {
   while (b[x]==1) x++;
   a[i]=x;b[x]=1;
  }
  for (int i=1;i<=2*n-1;i++)
   print(a[i]),puts("");
 }
 return 0;
}

C - Rabbit Exercise

这道期望题目一颗赛艇啊

首先考虑对称位置的处理，显然

x_i

关于

x_{i-1}

和

x_{i+1}

的对称位置分别是

2*x_{i-1}-x_{i}

和

2*x_{i+1}-x_{i}

考虑兔子

的期望

E(x_i')=\frac{1}{2}E(2x_{i-1}-x_i)+\frac{1}{2}E(2x_{i+1}-x_i)

=E(x_{i-1})+E(x_{i+1})-E(x_i)

这样，我们似乎已经得到了

O(MK)

的算法

我们从几何角度来考虑一下这个操作

其实就是

y_i

相对于

y_{i-1}

和

y_{i-2}

的相对位置发生了变化，

y_i

在外面的情况也是如此

再一般的来说，就是

E(x_i)-E(x_{x-1})

和

E(x_i)-E(x_{x+1})

的值进行了交换

那么，我们考虑差分，这样，每一次的操作就是对两个数进行交换了

而交换操作是分组进行的，我们可以根据类似快速幂的方式，在

O(logk)

的时间内完成交换

那么总的复杂度就是

O(nlogk)

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
 
using namespace std;

int n,m,a[200010],b[200010];

int main()
{
 read(n);read(m);
 if (m==1 || m==2*n-1) puts("No");
 else
 {
  puts("Yes");
  memset(a,0,sizeof(a));
  memset(b,0,sizeof(b));
  if (m>2)
  {
   a[n-1]=m-1,a[n]=m,a[n+1]=m+1,a[n+2]=m-2;
   b[m-2]=1,b[m-1]=1,b[m]=1,b[m+1]=1;
  }
  else
  {
   a[n-1]=m+1,a[n]=m,a[n+1]=m-1,a[n+2]=m+2;
   b[m-1]=1,b[m]=1,b[m+1]=1,b[m+2]=1;
  }
  int x=1;
  for (int i=1;i<n-1;i++)
  {
   while (b[x]==1) x++;
   a[i]=x;b[x]=1;
  }
  for (int i=n+3;i<=2*n-1;i++)
  {
   while (b[x]==1) x++;
   a[i]=x;b[x]=1;
  }
  for (int i=1;i<=2*n-1;i++)
   print(a[i]),puts("");
 }
 return 0;
}


int n,m,a[100010],b[100010],ans[100010],c[100010];
LL K;
double x[100010],z[100010];

void Work(LL x)
{
 for (;x;x>>=1)
 {
  if (x&1)
  {
   for (int i=1;i<n;i++)
    c[i]=ans[b[i]];
   for (int i=1;i<n;i++)
    ans[i]=c[i];
  }
  for (int i=1;i<n;i++)
   c[i]=b[b[i]];
  for (int i=1;i<n;i++)
   b[i]=c[i];
 }
}

int main()
{
 read(n);
 int y;
 for (int i=1;i<=n;i++)
  read(y),x[i]=(double)y;
 read(m),read(K);
 for (int i=1;i<=m;i++)
  read(a[i]);
 for (int i=1;i<n;i++)
  b[i]=i,ans[i]=i;
 for (int i=1;i<=m;i++)
  swap(b[a[i]],b[a[i]-1]);
 Work(K);
 z[1]=x[1];
 for (int i=1;i<n;i++)
  z[i+1]=z[i]+(x[ans[i]+1]-x[ans[i]]);
 for (int i=1;i<=n;i++)
  printf("%0.10lf\n",z[i]);
 return 0;
}

D - Median Pyramid Hard

这道题目似乎是B题的SPJ啊.....

考虑二分答案，假设当前需要验证的答案为

，表示答案

≥x

是否成立

那么，根据最下面一行和

≥x

的关系，我们可以得到底层的

0/1

数列，

表示

≥x

我们现在得到了底层的

0/1

数列，而题目所给的条件，上一层的一格为

，当且仅当下一层与之对应的三个中至少有两个

现在，符合情况的话，那么就是顶层为

我们可以画画图来分析一下底层的情况，如何向上传导

我们可以发现，当出现连续的两个

的时候，他们所对应的的上面，全部为

那么，这样的情况如何向外拓展呢？

我们发现，当连续的两个

旁边出现隔着一个位置的

的是否，这个全是

的竖行，可以向着隔着一个位置的

的方向拓展一列

那么我们只需要正着反着，各扫一遍

这样一来，我们就可以在

O(2n)

的时间内验证答案了

还有一种比较特殊的情况是，底层不需要出现连续的两个

特判一下

总的时间复杂度是

O(3n*logn)

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
 
using namespace std;
 
inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}
 
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline int read(char *s)
{
 char c=nc();int len=1;
 for(;!(c>='a' && c<='z');c=nc()) if (c==EOF) return 0;
 for(;(c>='a' && c<='z');s[len++]=c,c=nc());
 s[len++]='\0';
 return len;
}

inline void read(char &x){
  for (x=nc();!(x>='A' && x<='Z');x=nc());
}

int wt,ss[19];
inline void print(int x){
 if (x<0) x=-x,putchar('-'); 
 if (!x) putchar(48); else {
 for (wt=0;x;ss[++wt]=x%10,x/=10);
 for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
 if (x<0) x=-x,putchar('-');
 if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

int n,a[200010];

bool check1(int x)
{
 for (int i=1;i<2*n;i+=2)
  if (a[i]<x) return false;
 return true;
}

bool check(int x)
{
 if (check1(x)) return true;
 int y=0,z;
 for (int i=1;i<n;i++)
  if (a[i]>=x && a[i+1]>=x) y=i+1;
 z=y;
 if (z!=0)
 {
  while (a[z+2]>=x)
  {
   z+=2,y++;
   if (z+2>=2*n) break;
  }
  if (y>=n) return true;
 }
 y=0;
 for (int i=2*n-1;i>n;i--)
  if (a[i]>=x && a[i-1]>=x) y=i-1;
 z=y;
 if (z!=0)
 {
  while (a[z-2]>=x)
  {
   z-=2,y--;
   if (z-2<1) break;
  }
  if (y<=n) return true;
 }
 return false;
}

int main()
{
 read(n);
 memset(a,0,sizeof(a));
 for (int i=1;i<2*n;i++)
  read(a[i]);
 int l=2,r=2*n-2,mid,res;
 while (l<=r)
 {
  mid=l+r>>1;
  if (check(mid)) l=mid+1,res=mid;else r=mid-1;
 }
 print(res),puts("");
 return 0;
}

E - Rotate 3x3

这道题目很繁琐啊QAQ......

画了满满一页草稿纸......

首先，我们透过现象看本质，3*3Rotate 实际上就是把左右两列交换，然后在把三列全部倒置

那么，其实可以发现，每一列中的三个数是不会改变的，而且三个数要么正向，要么逆向

再其次，因为交换的是间隔的两列，所以矩阵中的奇数列和偶数列其实是相对独立的

我们把操作分成两个来思考

对间隔的两列旋转(这个旋转操作自带一个倒置和一个左右交换)、对某一列倒置

对于第一个问题的数量，我们可以转为这个问题：给出

个数的一个全排列，每次可以交换相邻的两个数，求每个数被交换的次数

贪心的做，我们先把在最后的数换下去，然后在换倒数第二个.......

暴力的做是

O(n^2)

，考虑用树状数组维护一波，

O(nlogn)

第二个问题，只要判断第一个问题的奇偶性，就可以直接得到答案了

那么回到原问题，可行性怎么判断

首先判断前面提到的一些条件...balabala

然后，就是对后面两个子问题的判断了

对于奇数列的第一个问题，左右交换的前提是其中间的偶数列进行倒置

那么，也就是说，奇数列的第一个问题的奇偶性应当与偶数列的第二个问题相同；偶数列的判断亦是如此

这样一来，问题就解决了，时间复杂度

O(nlogn)

，不过题解里给出的复杂度是

O(n)

，不是很明白他是怎么实现的，可能他的

数组可以线性求吧Orz

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
 
using namespace std;
 
int n,a[100010],b[100010],c[100010],d[100010],e[100010],f[100010];
int sum[100010],g[100010];

void updata(int x,int y)
{
 for (;x<=n;x+=x&(-x)) g[x]+=y;
}

int SUM(int x)
{
 int res=0;
 for (;x;x-=x&(-x)) res+=g[x];
 return res;
}

void change(int x,int y)
{
 for (;x<=n;x+=x&(-x)) sum[x]+=y;
}

int query(int x)
{
 int res=0;
 for (;x;x-=x&(-x)) res+=sum[x];
 return res;
}
 
bool check()
{
 int x,y,z,t;
 for (int i=1;i<=n;i++)
 {
  x=(a[i]-1)/3;t=x+1;
  f[i]=t;
  if (i%2!=t%2) return false;
  y=x*3+2,z=x*3+3,x=x*3+1;
  if (a[i]==x && b[i]==y && c[i]==z) {e[t]=2*n;continue;}
  if (a[i]==z && b[i]==y && c[i]==x) {e[t]=2*n+1;continue;}
  return false;
 }
 return true;
}
 
int main()
{
 read(n);
 for (int i=1;i<=n;i++)
  read(a[i]);
 for (int i=1;i<=n;i++)
  read(b[i]);
 for (int i=1;i<=n;i++)
  read(c[i]);
 if (!check()) {puts("No");return 0;}
 memset(sum,0,sizeof(sum));
 memset(g,0,sizeof(g));
 for (int i=1;i<=n;i++)
  if (i%2==1) change(i,1);
 int x;
 for (int i=n;i>=1;i--)
  if (i%2==1)
  {
   x=f[i];
   d[x]=query(n)-query(x);
   d[x]+=SUM(x);
   change(x,-1);updata(x,1);
  }
 memset(sum,0,sizeof(sum));
 memset(g,0,sizeof(g));
 for (int i=1;i<=n;i++)
  if (i%2==0) change(i,1);
 for (int i=n;i>=1;i--)
  if (i%2==0)
  {
   x=f[i];
   d[x]=query(n)-query(x)+SUM(x);
   change(x,-1);updata(x,1);
  }
 for (int i=1;i<=n;i++)
  e[i]=(e[i]-d[i])%2;
 int s=0,t=0;
 for (int i=1;i<=n;i++)
  if (i%2==0) s+=e[i];else t+=d[i];
 t/=2;
 if (s%2!=t%2) {puts("No");return 0;}
 s=0,t=0;
 for (int i=1;i<=n;i++)
  if (i%2==1) s+=e[i];else t+=d[i];
 t/=2;
 if (s%2!=t%2) {puts("No");return 0;}
 puts("Yes");
 return 0;
}

F - Blackout

又一次深刻体会到了出题人的强大Orz...

首先，我们可以把这个矩阵问题转变为图论问题

我们把格子

(x,y)

转变为一条有向边

x\rightarrow y

，那么，当

x\rightarrow y

和

y\rightarrow z

存在时，有边

z\rightarrow x

我们可以先来尝试探索一些规律

对于图中的

个点，每个点

都有边连向

x+1

，我们尝试更新一波边，发现只有在

和

满足

x+1\equiv y (mod\; 3)

的时候，

有指向

的边

以此，我们发现这张图和

有关系（出题人是这么说的.......）

于是，我们用三色来对图进行染色，使得相邻的节点不同色

接下来，我们分别讨论三种情况

【1】染色成功，且图中出现了不同的三种颜色

、

那么，我们对于三种不同颜色的边，可以把所有

x\rightarrow y

、

y\rightarrow z

、

z\rightarrow x

都连上

证明:如下图，如果上述情况成立的话，那么，一定至少存在

x\rightarrow y

、

y\rightarrow z

，我们当然可以把

z\rightarrow x

连上，当有新的边

u\rightarrow x

时，我们发现，

y\rightarrow u

也同样可以连上，那么，联通的所有点都是可以两先关的

【2】染色成功，图中出现的颜色不足三种

那么显然，不存在

x\rightarrow y

、

y\rightarrow z

这样的边对，那么，答案就是边数

【3】染色失败

那么，画画图很容易看出，一定存在着环（且环的大小一定不是

的倍数）

那么，很显然得，所有联通的点之间，两两之间的所有边均可以连上

这样一来，我们对于每一个联通块一次这样讨论即可，时间复杂度

O(m)

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
 
using namespace std;

int n,m,f[100010];
LL A,B,C,S;
struct data
{
 int x,y;
}a[100010];
vector<int> b[100010],c[100010];
bool v[100010];

bool check(int x)
{
 v[x]=1;bool flag=1;S+=b[x].size()+c[x].size();
 if (f[x]==1)
 {
  for (int i=0;i<b[x].size();i++)
   if (f[b[x][i]]==0) f[b[x][i]]=2,B++;
   else if (f[b[x][i]]!=2) flag&=0;
  for (int i=0;i<c[x].size();i++)
   if (f[c[x][i]]==0) f[c[x][i]]=3,C++;
   else if (f[c[x][i]]!=3) flag&=0;
  for (int i=0;i<b[x].size();i++)
   if (!v[b[x][i]]) flag&=check(b[x][i]);
  for (int i=0;i<c[x].size();i++)
   if (!v[c[x][i]]) flag&=check(c[x][i]);
 }
 else if (f[x]==2)
 {
  for (int i=0;i<b[x].size();i++)
   if (f[b[x][i]]==0) f[b[x][i]]=3,C++;
   else if (f[b[x][i]]!=3) flag&=0;
  for (int i=0;i<c[x].size();i++)
   if (f[c[x][i]]==0) f[c[x][i]]=1,A++;
   else if (f[c[x][i]]!=1) flag&=0;
  for (int i=0;i<b[x].size();i++)
   if (!v[b[x][i]]) flag&=check(b[x][i]);
  for (int i=0;i<c[x].size();i++)
   if (!v[c[x][i]]) flag&=check(c[x][i]);
 }
 else
 {
  for (int i=0;i<b[x].size();i++)
   if (f[b[x][i]]==0) f[b[x][i]]=1,A++;
   else if (f[b[x][i]]!=1) flag&=0;
  for (int i=0;i<c[x].size();i++)
   if (f[c[x][i]]==0) f[c[x][i]]=2,B++;
   else if (f[c[x][i]]!=2) flag&=0;
  for (int i=0;i<b[x].size();i++)
   if (!v[b[x][i]]) flag&=check(b[x][i]);
  for (int i=0;i<c[x].size();i++)
   if (!v[c[x][i]]) flag&=check(c[x][i]);
 }
 return flag; 
}

LL calc()
{
 memset(f,0,sizeof(f));
 for (int i=1;i<=m;i++)
  b[a[i].x].push_back(a[i].y),
  c[a[i].y].push_back(a[i].x);
 LL ans=0;
 for (int i=1;i<=n;i++)
  if (b[i].size()>0 && f[i]==0)
  {
   f[i]=1;A=1,B=0,C=0;S=0;
   memset(v,0,sizeof(v));
   if (!check(i)) 
    ans+=(A+B+C)*(A+B+C);
   else if (C==0) ans+=S/2;
   else ans+=(A*B)+(B*C)+(C*A);
  }
 return ans;
}

int main()
{
 read(n);read(m);
 for (int i=1;i<=m;i++)
  read(a[i].x),read(a[i].y);
 print(calc());puts("");
 return 0;
}

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-09-05，如有侵权请联系 cloudcommunity@tencent.com 删除

median

pyramid

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

median

pyramid

登录后参与评论

0 条评论

热度