首页 > 其他分享 >Atcoder Regular Contest ARC 153 A B C D 题解

Atcoder Regular Contest ARC 153 A B C D 题解

时间：2023-01-15 19:55:06浏览次数：65  
标签：Atcoder 153 10 int 题解 rep ans sum define

点我看题

A - AABCDDEFE

一个beautiful number是形如这样的：\(S1S1S3S4S5S5S7S8S7\)。如果选定了\(S1\)，后面的数有100000种选法，所以先求出答案的\(S1\)。假设现在我们要求出以\(S1\)开头的第\(n\)小的beautiful number。发现这个条件其实等价于\(S3S4S5S7S8\)这个五位数等于\(n-1\)，所以直接求即可。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

int n,ans[20];

int main()
{
  fileio();

  cin>>n;
  int s1=1;
  while(n>100000)
  {
    ++s1;
    n-=100000;
  }
  --n;
  ans[1]=ans[2]=s1;
  ans[8]=n%10;n/=10;
  ans[7]=ans[9]=n%10;n/=10;
  ans[5]=ans[6]=n%10;n/=10;
  ans[4]=n%10;n/=10;
  ans[3]=n%10;
  repn(i,9) cout<<ans[i];

  termin();
}

B - Grid Rotations

发现行和列实际上是独立的，每次操作\(a,b\)实际上我们相当于依次做了这四步：把第\(1\cdots a\)行翻转(注意是行与行之间的顺序reverse，不是把每行的内容reverse，后面的"翻转"同理)；把第\(a+1\cdots n\)行翻转；把第\(1\cdots b\)列翻转；把第\(b+1\cdots m\)列翻转。如果我们能求出两个数组\(r,c\)，\(r_i\)表示所有操作做完后，原来的第\(i\)行被移到了第\(r_i\)行，第\(j\)列被移到了第\(c_j\)列，那么原来的\(a_{i,j}\)就被移动到了\((r_i,c_j)\)。用两个平衡树维护两维的翻转情况即可。

时间复杂度单log。

其实也可以线性，因为行列坐标的变换也可以看成是加一个数再取模。但平衡树的优势是不要动脑子。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

int to[2][500010];

mt19937 rndtr(114514);
struct node{int val,key,ls,rs,sz,tag;};
struct tr
{
	int len;
	node a[1000000];
	int newNode(int x){a[++len].val=x;a[len].key=rndtr();a[len].ls=a[len].rs=a[len].tag=0;a[len].sz=1;return len;}
  void addTag(int x)
  {
    if(x==0) return;
    swap(a[x].ls,a[x].rs);a[x].tag^=1;
  }
  void pushDown(int x)
  {
    if(x==0||a[x].tag==0) return;
    addTag(a[x].ls);addTag(a[x].rs);
    a[x].tag=0;
  }
	void calc(int x){if(x==0) return;a[x].sz=a[a[x].ls].sz+1+a[a[x].rs].sz;}
	int merge(int x,int y)
	{
		if(x==0||y==0) return max(x,y);
    pushDown(x);pushDown(y);
		int ret;
		if(a[x].key<=a[y].key){ret=x;a[ret].rs=merge(a[ret].rs,y);}
		else{ret=y;a[ret].ls=merge(x,a[ret].ls);}
		calc(ret);return ret;
	}
	pii splitSz(int x,int y)//左边y个
	{
		if(x==0) return mpr(0,0);if(y==0) return mpr(0,x);if(y==a[x].sz) return mpr(x,0);
    pushDown(x);
		int ret1,ret2;
		if(a[a[x].ls].sz>=y){pii p=splitSz(a[x].ls,y);ret1=p.fi;ret2=x;a[ret2].ls=p.se;}
		else{pii p=splitSz(a[x].rs,y-1-a[a[x].ls].sz);ret1=x;a[ret1].rs=p.fi;ret2=p.se;}
		calc(ret1);calc(ret2);return mpr(ret1,ret2);
	}
  void build(int x,int frt,int w)
  {
    if(x==0) return;
    to[w][a[x].val]=frt+a[a[x].ls].sz;
    pushDown(x);
    build(a[x].ls,frt,w);build(a[x].rs,frt+a[a[x].ls].sz+1,w);
  }
}row,col;

int n,m;
string a[500010],ans[500010];
char c[500010];

int main()
{
  fileio();

  cin>>n>>m;
  rep(i,n)
  {
    scanf("%s",c);
    a[i]=ans[i]=c;
  }
  row.len=0;col.len=0;
  int rootr=0,rootc=0;
  rep(i,n) rootr=row.merge(rootr,row.newNode(i));
  rep(i,m) rootc=col.merge(rootc,col.newNode(i));
  int q;cin>>q;
  rep(qn,q)
  {
    int x,y;
    scanf("%d%d",&x,&y);
    pii p=row.splitSz(rootr,x);
    row.addTag(p.fi);row.addTag(p.se);
    rootr=row.merge(p.fi,p.se);
    p=col.splitSz(rootc,y);
    col.addTag(p.fi);col.addTag(p.se);
    rootc=col.merge(p.fi,p.se);
  }
  row.build(rootr,0,0);
  col.build(rootc,0,1);
  rep(i,n) rep(j,m) ans[to[0][i]][to[1][j]]=a[i][j];
  rep(i,n) printf("%s\n",ans[i].c_str());

  termin();
}

C - ± Increasing Sequence

(A数组的下标从0开始)

令\(suf_i=\sum_{j=i}^{n-1}a_i\)。我们其实是要找出一个序列\(b_0\cdots b_{n-1}\)，满足\(b_1\cdots b_{n-1}\)都是正整数，且\(\sum b_isuf_i=0\)。其实b就是题目中x的差分数组。

由于b中除了第一个数都要取正数，那就先把\(b_1\cdots b_{n-1}\)都取1，\(b_0\)取0，后面如果需要可以再加。如果此时\(\sum b_isuf_i\)已经为0，那就直接输出解。否则，如果\(suf_1\cdots suf_{n-1}\)中有正有负，那肯定有解，因为\(suf_{n-1}\)是1或-1，如果是1的话就随便找一个\(<0\)的\(suf_i\)，不断给\(b_i\)加1直到\(\sum b_isuf_i\le 0\)，然后再用\(suf_{n-1}\)加回来即可。\(suf_{n-1}=-1\)同理。

剩下的情况，如果\(suf_0=0\)肯定无解，这是显然的。否则也肯定有解，比如\(suf_{n-1}=1\)时，可以像上面一样，先用\(suf_0\)把\(\sum b_isuf_i\)压到非正数，在用\(suf_{n-1}\)加回来。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

LL n,a[200010],ans[200010],sufsum[200010];

void print()
{
  puts("Yes");
  rep(i,n)
  {
    printf("%d ",ans[i]);
    ans[i+1]+=ans[i];
  }
  puts("");
  termin();
}
void fuck(){puts("No");termin();}

int main()
{
  fileio();

  cin>>n;
  rep(i,n) scanf("%lld",&a[i]);
  LL sum=0,cur=0,posi=-1,nega=-1;
  for(int i=n-1;i>0;--i)
  {
    sum+=a[i];sufsum[i]=sum;
    ans[i]=1;cur+=sum;
    if(sum>0) posi=i;else if(sum<0) nega=i;
  }
  if(cur==0) print();
  //if(a[n-1]==1) posi=n-1;else nega=n-1;
  if(posi>-1&&nega>-1)
  {
    if(a[n-1]==1)
    {
      LL usenega=(max(0LL,cur)-sufsum[nega]-1)/(-sufsum[nega]);
      ans[nega]+=usenega;cur+=usenega*sufsum[nega];
      ans[n-1]-=cur;
    }
    else
    {
      LL useposi=(-min(0LL,cur)+sufsum[posi]-1)/sufsum[posi];
      ans[posi]+=useposi;cur+=useposi*sufsum[posi];
      ans[n-1]+=cur;
    }
    print();
  }
  if(sum+a[0]==0) fuck();
  sum+=a[0];
  if(a[n-1]==1)
  {
    LL targ=(cur+llabs(sum)-1)/llabs(sum)*llabs(sum);
    ans[n-1]+=targ-cur;
    ans[0]=-(targ/sum);
  }
  else
  {
    LL targ=(-cur+llabs(sum)-1)/llabs(sum)*llabs(sum);targ=-targ;
    ans[n-1]+=llabs(targ-cur);
    ans[0]=-(targ/sum);
  }
  print();

  termin();
}

D - Sum of Sum of Digits

看起来像数位dp，其实也确实是dp。

令原数组所有数的数位和为\(S\)，x的数位和为X。那么最终的数位和为\(S+nX-所有数加x的总进位次数\cdot 9\)，这个模拟一下加法的过程就能发现。我们把进位次数\(\cdot 9-nX\)称为"收益"，我们想让收益最大。

我们从低往高确定x的每一位。关键观察：当确定了x的最低的i位时，\(a\)数组中那些会从第i位到第i+1位进一位的数，肯定是\(a\)中前i位按照数值比较最大的一些数。所以就可以dp了：\(dp_{i,j}\)表示计算到第i位，前\(i-1\)位最大的j个数被第\(i-1\)位到第\(i\)位进位了一次的情况下的最大收益。转移时枚举x的当前这一位选什么，计算第i位到第i+1位的进位数只要用前缀和预处理一下就行了。

时间复杂度\(O(10^2n)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

void chmax(LL &x,LL y){if(x<y) x=y;}

LL n,a[200010],pw10[15],clue[200010],lft[200010],ord[20][200010];
LL pref[15][200010][15];//pref[i][j][k]: 第i层，前缀最大的j个中，当前位>=k的个数
LL dp[15][200010];//dp[i][j]: 第i层，前缀最大的j个被进位的最大收益

int main()
{
  fileio();

  pw10[0]=1;repn(i,12) pw10[i]=pw10[i-1]*10;
  cin>>n;
  rep(i,n) scanf("%lld",&a[i]);
  rep(i,10)
  {
    rep(j,n) clue[j]=a[j]%pw10[i],lft[j]=a[j]/pw10[i]%10,ord[i][j]=j;
    sort(ord[i],ord[i]+n,[](LL x,LL y){return clue[x]>clue[y];});
    rep(j,n)
    {
      rep(k,12) pref[i][j+1][k]=pref[i][j][k];
      for(int k=0;k<=lft[ord[i][j]];++k) ++pref[i][j+1][k];
    }
  }
  rep(i,14) rep(j,n+3) dp[i][j]=-1e18;
  dp[0][0]=0;
  rep(i,10) rep(j,n+1) if(dp[i][j]>-1e18)
  {
    rep(nxt,10)
    {
      LL gain=(LL)(-nxt)*n,add=pref[i][j][10-nxt-1]+pref[i][n][10-nxt]-pref[i][j][10-nxt];
      gain+=add*9;
      chmax(dp[i+1][add],dp[i][j]+gain);
    }
  }
  LL ans=-1e18;
  rep(j,n+1) ans=max(ans,dp[10][j]);
  LL ori=0;
  rep(i,n)
  {
    while(a[i]>0)
    {
      ori+=a[i]%10;
      a[i]/=10;
    }
  }
  ans=ori-ans;
  cout<<ans<<endl;

  termin();
}

标签：Atcoder,153,10,int,题解,rep,ans,sum,define
From： https://www.cnblogs.com/legendstane/p/atcoder-regular-contest-arc-153-a-b-c-d-solution.htm

相关文章

  • CF1536F. Omkar and Akmar
    牛B题首先因为n>=2，可以发现后手必胜：①当n为偶数时，后手跟着先手走对称，按照n和1的分界线作为对称轴，位置对称+棋子反转②当n为奇数时，设先手走x，后手走x+2，按照x+1作为对称......
  • 【题解】P5397 [Ynoi2018] 天降之物
    码力人的甜品，口嗨者的末路。感觉手牵手那个题才是第四分块正体，这个不如叫最初根号分治。思路根号分治。对于每个值，把它们分成出现大于根号次和小于等于根号次两类。先......
  • AtCoder Beginner Contest 254（C，D，E，F)
    AtCoderBeginnerContest254（C，D，E，F)CC这个题是给你一个乱序的数组，你可以把ai和ai+k进行交换，我们需要判断是否可以最后变成从小到大的顺序那么我们可以想到所有下标对k......
  • 【题解】P5692 [MtOI2019]手牵手走向明天
    春节前做大分块是什么奇妙传统吗……这个题好想是好想，但是写起来就是另外一回事了……思路分块。第四分块加强版。区间查询，根号分治做法寄了。看到合并颜色可以想到......
  • AtCoder Regular Contest 153
    喜提全场独一无二的score！ATC还是很友善的，如果每题等分就寄了A签到B真的是凭着实力不会做的呀。。。太菜了发现两维可以分别做，所以考虑一维的情况，然而并不会对于两......
  • Codeforces 732 Div2 A-D题解
    感觉做过这场啊，要不就是看过A题AquaMoonandTwoArrays问前加后减能不能把A变成B，首先这个貌似是经典老题了，无论怎么操作数列总和不变，如果和不相同，变不了，其他情况暴力判......
  • ARC153 ABC 题解
    A【题意】给定\(N\)，求第\(N\)个满足以下条件的数：它是一个\(9\)位数，没有前导\(0\)。它的第一位等于它的第二位。它的第五位等于它的第六位。它的第七位等于它......
  • Atcoder abc275F
    Atcoderabc275F题意：给出一个长度为\(n\)的数组\(A=(a_1​,a_2​,…,a_N)\)，问是否能通过删掉一些子段使剩下的数之和为\(q\)。若可以，求出最小操作次数，否则输出−1......
  • XMU 2023.1.14 题解汇总
    A、CF1779A原题B、https://www.cnblogs.com/wondering-world/p/17038860.htmlC、https://www.luogu.com.cn/problem/solution/P4305D、快速幂模板点击查看代码#incl......
  • DTOJ-2023-01-02-测试-题解
    （2023省选模拟Round#4）之前感冒了一阵子，错过了两场省选模拟，不过我不打算补（乐成绩：0+42+0（就是说T1写挂了）A题目链接题目大意小\(\omega\)最近学习了分治\(\text{......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99