CF2132 Div.3
目录
A
code
1int T,n,m;
2string a,b,c;
3int main()
4{
5 cin>>T;
6 while(T--)
7 {
8 cin>>n;
9 cin>>a;
10 cin>>m;
11 cin>>b;
12 cin>>c;
13 for(int i=0;i<m;i++)
14 if(c[i]=='D')
15 {
16 a+=b[i];
17 }
18 else a= b[i]+a;
19 cout<<a<<'\n';
20 }
21 return 0;
22}B
code
1int T;
2ll n,a[20],tot;
3int main()
4{
5 read(T);
6 while(T--)
7 {
8 read(n);
9 ll p=1;
10 tot=0;
11 for(int i=1;i<=18;i++)
12 {
13 p*=10;
14 if(p+1>n)break;
15 if(n%(p+1)==0)a[++tot]=n/(p+1);
16 }
17 reverse(a+1,a+tot+1);
18 write(tot);
19 for(int i=1;i<=tot;i++)write(a[i],i<tot?' ':'\n');
20 }
21 flushout();
22 return 0;
23}C1
code
1int T,n;
2int main()
3{
4 read(T);
5 while(T--)
6 {
7 read(n);
8 int cost=0,p=1,i=0;
9 while(n)cost+=n%3*(p*3+i*p/3),nn/=3,i++,p*=3;
10 printf("%lld\n",cost);
11 }
12 return 0;
13}C2. The Cunning Seller
题意
每次交易可以花 $3^{x+1} + x \cdot 3^{x-1}$ 元, 买 $3^x$ 个物品. 求购买次数不超过 $k$ 次, 购买总数恰好为 $n$ 的物品最少要花多少钱.
题解
首先每次买只能买 $3^x$ 个, 第一反应肯定是转三进制考虑问题. 进一步观察每次的花费考虑如果将一次购买分为三次会有如下变化:
$$ 3^{x+1} + x \cdot 3^{x-1} - 3(3^x + (x - 1)3^{x-2}) = 3^{x-1} $$
也就是将一次购买分解成三次购买更优, 并且分解越高位的购买省的钱越多. 所以只需在次数限制内贪心的从高位到低位往下分解即可.
code
1int T;
2int n,k,num[40],tot;
3int main()
4{
5 read(T);
6 while(T--)
7 {
8 read(n),read(k);
9 int nn=n,cnt=0;
10 tot=0;
11 while(nn)num[tot++]=nn%3,nn/=3;
12 for(int i=0;i<tot;i++)cnt+=num[i];
13 if(cnt>k)puts("-1");
14 else
15 {
16 for(int i=tot-1;i;i--)
17 {
18 if(num[i]*2+cnt<=k)
19 {
20 num[i-1]+=num[i]*3;
21 cnt+=num[i]*2;
22 num[i]=0;
23 }
24 else
25 {
26 int ct=(k-cnt)/2;
27 num[i-1]+=ct*3;
28 num[i]-=ct;
29 break;
30 }
31 }
32 ll cost=0,p=1;
33 for(int i=0;i<tot;i++)
34 {
35 cost+=num[i]*(p*3+i*p/3);
36 p*=3;
37 }
38 printf("%lld\n",cost);
39 }
40 }
41 return 0;
42}D From 1 to Infinity
题意
将自然数写成一列 (123456789101112…), 求其中前 $k$ 个数字的和.
题解
首先先算出完整的数字到那里, 将后面不完成的答案统计一下, 然后就是经典数位 dp [ZJOI2010] 数字计数.
ps: 若干年前的紫题现在都绿了.
code
1const int N=1e5+10,lm=18;
2int T;
3const ll c[]={0,1,3,6,10,15,21,28,36,45};
4ll d[20],k;
5ll work(int n,ll cnt,int re)
6{
7 int nn=n;
8 ll p=1;
9 while(n--)p*=10;
10 p/=10;
11 p+=cnt;
12 nn-=re;
13 while(nn--)p/=10;
14 ll res=0;
15 while(p)res+=p%10,p/=10;
16 return res;
17}
18ll b[20],lb;
19ll as[20],cnt[20],pw[20],f[20];
20inline void work2(ll *a,int len,ll *ans,int tp)
21{
22 memset(cnt,0,sizeof(cnt));
23 for(int i=1;i<=len;i++)cnt[a[i]]++,ans[a[i]]=(ans[a[i]]+tp);
24 ll val=1;
25 for(int i=1;i<=len;i++)
26 {
27 cnt[a[i]]--;
28 for(int j=0;j<10;j++)ans[j]=(ans[j]+1ll*tp*cnt[j]*a[i]*pw[i-1]+1ll*tp*f[i-1]*a[i]);
29 for(int j=(i<len?0:1);j<a[i];j++)ans[j]=(ans[j]+1ll*tp*pw[i-1]);
30 if(i>1)ans[0]=(ans[0]-tp*pw[i-2]);
31 }
32 return;
33}
34int main()
35{
36 pw[0]=1;
37 for(int i=1;i<=lm;i++)pw[i]=pw[i-1]*10;
38 for(int i=1;i<=lm;i++)
39 d[i]=pw[i-1]*9*i;
40 f[1]=1;
41 for(int i=2;i<lm;i++)f[i]=(1ll*f[i-1]*10+pw[i-1]);
42 read(T);
43 while(T--)
44 {
45 read(k);
46 int n=1;
47 ll sm=0,ans=0;
48 while(sm+d[n]<=k)sm+=d[n],n++;
49 ll cnt=(k-sm)/n,p=1;
50 ans+=work(n,cnt,(k-sm)%n);
51 for(int i=1;i<n;i++)p*=10;
52 cnt+=p-1;
53 lb=0;
54 ll bb=cnt;
55 for(int i=1;i<=lm;i++)as[i]=0;
56 while(bb)b[++lb]=bb%10,bb/=10;
57 work2(b,lb,as,1);
58 for(int i=1;i<=9;i++)ans+=as[i]*i;
59 write(ans);
60 }
61 return 0;
62}E Arithmetics Competition
题意
给你两个数组 $a_i, b_i$, 长度分别为 $n, m$. 有 $q$ 次询问, 每次询问给出 $x, y, z$, 要求从这两个数组中一共选 $z$ 个数, 其中从 $a_i$ 中选取不超过 $x$ 个, 从 $b_i$ 中选取不超过 $y$ 个. 求这 $z$ 个数的和最大是多少.
题解
首先, 肯定要排序, 最终在各个数组内部的数肯定是最大的若干个.
下面就要考虑每个数组取多少个数.
做一次归并排序, 求出取 $x$ 个 $a_i$ 会取出总的多少个数, $b_i$ 同理.
那么对于一次询问, 我们就可以通过预处理的东西快速得到两个数组放一起按顺序取哪一个数组先取到个数限制, 然后剩下的数都从另一个数组取即可.
code
1const int N=2e5+10;
2int T,n,m,q,a[N],b[N],ra[N<<1];
3ll suma[N],sumb[N];
4int main()
5{
6 read(T);
7 while(T--)
8 {
9 read(n),read(m),read(q);
10 for(int i=1;i<=n;i++)read(a[i]);
11 for(int i=1;i<=m;i++)read(b[i]);
12 sort(a+1,a+n+1);
13 reverse(a+1,a+n+1);
14 sort(b+1,b+m+1);
15 reverse(b+1,b+m+1);
16 for(int i=1;i<=n;i++)suma[i]=suma[i-1]+a[i];
17 for(int i=1;i<=m;i++)sumb[i]=sumb[i-1]+b[i];
18 a[n+1]=b[m+1]=-1;
19 for(int i=1,p1=1,p2=1;i<=n+m;i++)
20 {
21 if(a[p1]>b[p2]) p1++;
22 else p2++;
23 ra[i]=p1-1;
24 }
25 for(int i=1,x,y,z;i<=q;i++)
26 {
27 read(x),read(y),read(z);
28 if(ra[z]>x)write(suma[x]+sumb[z-x]);
29 else if(z-ra[z]>y)write(suma[z-y]+sumb[y]);
30 else write(suma[ra[z]]+sumb[z-ra[z]]);
31 }
32 }
33 flushout();
34 return 0;
35}F Rada and the Chamomile Valley
题意
给出一个 $n$ 个点 $m$ 条边的无向图, 称 $1 \sim n$ 必经的边为特殊边, 求每个点最近的特殊边编号.
题解
题意得特殊边就是这个图从 $1 \sim n$ 的桥, 所以先一个 tarjan 求出边双, 然后在 dfs 出哪些桥是 $1 \sim n$ 的必经边, 最后以这些边的端点为起点做多源 bfs 扩展到每个点.
code
1const int N=2e5+10;
2int T,n,m;
3int low[N], dfn[N], idx;
4bool isbridge[N];
5vector<pii> G[N],e[N];
6int tot;
7
8pii a[N<<1],ed[N];
9void tarjan(int u, int fa) {
10 low[u] = dfn[u] = ++idx;
11 for (const auto &ev : G[u]) {
12 int v=ev.fi;
13 if (!dfn[v]) {
14 tarjan(v, u);
15 low[u] = min(low[u], low[v]);
16 if (low[v] > dfn[u])
17 isbridge[ev.se] = true;
18 } else if (v != fa) {
19 low[u] = min(low[u], dfn[v]);
20 }
21 }
22}
23int dis[N],ans[N],id[N],cnt;
24void dfs(int now)
25{
26 id[now]=cnt;
27 for(auto &ev:G[now])
28 if(!id[ev.fi]&&!isbridge[ev.se])
29 dfs(ev.fi);
30}
31int stk[N],top;
32void dfs2(int now,int fa)
33{
34 if(id[n]==now)
35 {
36 for(int i=1;i<=top;i++)
37 {
38 int ii=stk[i];
39 a[++tot]={ii,ed[ii].fi};
40 a[++tot]={ii,ed[ii].se};
41 }
42 return;
43 }
44 for(auto ev:e[now])
45 if(ev.fi!=fa)
46 {
47 stk[++top]=ev.se;
48 dfs2(ev.fi,now);
49 top--;
50 }
51 return;
52}
53int main()
54{
55 read(T);
56 while(T--)
57 {
58 read(n),read(m);
59 idx=tot=0;
60 cnt=0;
61 top=0;
62 for(int i=1;i<=n;i++)
63 {
64 G[i].clear();
65 e[i].clear();
66 id[i]=0;
67 ans[i]=-1;
68 dfn[i]=low[i]=0;
69 dis[i]=-1;
70 }
71 for(int i=1;i<=m;i++)isbridge[i]=0;
72 for(int i=1,u,v;i<=m;i++)
73 {
74 read(u),read(v);
75 ed[i]={u,v};
76 G[u].push_back({v,i});
77 G[v].push_back({u,i});
78 }
79 for(int i=1;i<=n;i++)
80 if(!dfn[i])tarjan(i,0);
81 for(int i=1;i<=n;i++)
82 if(!id[i])++cnt,dfs(i);
83 for(int i=1;i<=m;i++)
84 if(isbridge[i])
85 {
86 e[id[ed[i].fi]].push_back({id[ed[i].se],i});
87 e[id[ed[i].se]].push_back({id[ed[i].fi],i});
88 }
89 dfs2(1,0);
90 sort(a+1,a+tot+1);
91 queue<pii>q;
92 for(int i=1;i<=tot;i++)
93 if(dis[a[i].se]==-1)
94 dis[a[i].se]=0,ans[a[i].se]=a[i].fi,q.push(a[i]);
95 while(!q.empty())
96 {
97 pii now=q.front();
98 q.pop();
99 for(auto ev:G[now.se])
100 {
101 int to=ev.fi;
102 if(dis[to]==-1)
103 dis[to]=dis[now.se]+1,ans[to]=now.fi,q.push({now.fi,to});
104 }
105 }
106 int Q;
107 read(Q);
108 while(Q--) write(ans[read<int>()],' ');
109 Putc('\n');
110 }
111 flushout();
112 return 0;
113}G Famous Choreographer
题意
给出一个 $n \cdot m$ 的字符矩阵, 求最少需要添加的字符, 是的添加后仍构成矩阵, 且新矩阵中心对称.
题解
二维哈希, 枚举每一个可能的中心点并检验是否合法. 注意中心点不一定是某个字符, 可能是两个字符中间.
code
1mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
2const int N=2e6+10,mod=998244353;
3mint<mod>base=rng(),ibase=base.inv(),pw[N],ipw[N];
4int T,n,m;
5int main()
6{
7 pw[0]=ipw[0]=1;
8 for(int i=1;i<N;i++)pw[i]=pw[i-1]*base,ipw[i]=ipw[i-1]*ibase;
9 cin>>T;
10 while(T--)
11 {
12 cin>>n>>m;
13 vector<string>s(n);
14 for(int i=0;i<n;i++)cin>>s[i];
15 vector h1(n+1,vector<mint<mod>>(m+1)),h2(h1);
16
17 for(int i=1;i<=n;i++)
18 for(int j=1;j<=m;j++)
19 {
20 h1[i][j]=h1[i][j-1]+h1[i-1][j]-h1[i-1][j-1]+pw[(i-1)*m+j]*s[i-1][j-1];
21 h2[i][j]=h2[i][j-1]+h2[i-1][j]-h2[i-1][j-1]+ipw[(i-1)*m+j]*s[i-1][j-1];
22 }
23 int ans=4*n*m;
24 for(int i=1;i<2*n;i++)
25 for(int j=1;j<2*m;j++)
26 {
27 int l1=max(0,i-n),r1=min(n,i);
28 int l2=max(0,j-m),r2=min(m,j);
29 mint<mod>v1=h1[r1][r2]-h1[r1][l2]-h1[l1][r2]+h1[l1][l2];
30 mint<mod>v2=h2[r1][r2]-h2[r1][l2]-h2[l1][r2]+h2[l1][l2];
31 if(v1 == v2 * pw[(i-1)*m+j+1])
32 ans=min(ans,(2*n-r1+l1)*(2*m-r2+l2)-n*m);
33 }
34 cout<<ans<<'\n';
35 }
36 return 0;
37}