Atcoder Regular Contest ARC 153 A B C D 题解
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<<"
EXECUTION 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)实际上我们相当于依次做了这四步:把第(1cdots a)行翻转(注意是行与行之间的顺序reverse,不是把每行的内容reverse,后面的"翻转"同理);把第(a+1cdots n)行翻转;把第(1cdots b)列翻转;把第(b+1cdots 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<<"
EXECUTION 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
",ans[i].c_str());
termin();
}
C - ± Increasing Sequence
(A数组的下标从0开始)
令(suf_i=sum_{j=i}^{n-1}a_i)。我们其实是要找出一个序列(b_0cdots b_{n-1}),满足(b_1cdots b_{n-1})都是正整数,且(sum b_isuf_i=0)。其实b就是题目中x的差分数组。
由于b中除了第一个数都要取正数,那就先把(b_1cdots b_{n-1})都取1,(b_0)取0,后面如果需要可以再加。如果此时(sum b_isuf_i)已经为0,那就直接输出解。否则,如果(suf_1cdots suf_{n-1})中有正有负,那肯定有解,因为(suf_{n-1})是1或-1,如果是1的话就随便找一个(<0)的(suf_i),不断给(b_i)加1直到(sum b_isuf_ile 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<<"
EXECUTION 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<<"
EXECUTION 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();
}
相关文章
- Hbuilder项目转vue-cli项目
- 使用VS code将本地的项目推送到gitee的方法(图例)
- 1.5.5 HDFS读写解析-hadoop-最全最完整的保姆级的java大数据学习资料
- 数据安全新战场,EasyMR为企业筑起“安全防线”
- 1.5 HDFS分布式文件系统-hadoop-最全最完整的保姆级的java大数据学习资料
- 【NoSql】缓存管理器CacheManager使用
- DTALK直播预约 | 12月8日开播:后疫情时代,制造企业如何实现数字化转型?
- Delete ␍eslint(prettierprettier)错误
- DBeaver企业版免费下载及破解(白嫖党福利)
- SQL Server(解决问题)已成功与服务器建立连接,但是在登录过程中发生错误。provider: Shared Memory Provider, error:0 - 管道的另一端上无任何进程。
- 前端面试题学习-个人总结笔记 Day 1
- 合并代码注意事项
- flex布局 -- 弹性盒模型
- 大数据技术的现状与面临的挑战
- 网页DOM编程方法(API总结与应用)
- 袋鼠云数栈UI5.0体验升级背后的故事:可用性原则与交互升级
- CSS 网格(Grid)布局
- 聊聊Cookie、Session、Token 背后的故事
- 袋鼠云陈吉平:深耕国产自研数字化技术与服务,持续为客户创造价值
- day03-模块化编程