这一场总共6题,本菜鸡只过了前四题(rank为215)QAQ,再接再厉吧

这次的D,E,F都挺有意思的,所以就写个题解总结一下。不过以后补完题还是尽量都写一写总结叭,不然太懒了也不好www


A. Add and Divide

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int a,b;
int main(){
int T;scanf("%d",&T);
while(T--){
int cnt=0,ans=1e9;
scanf("%d%d",&a,&b);
for(int i=0;i<=100;i++){

int x=a,y=b+i;if(y==1)continue;
cnt=0;
while(x){
x/=y;cnt++;
}
ans=min(ans,cnt+i);
}

printf("%d\n",ans);
}
return 0;
}

B. Replace and Keep Sorted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n,q,k,l,r;
int a[maxn],dis[maxn],sum[maxn];
int main(){
scanf("%d%d%d",&n,&q,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
dis[i]=a[i]-a[i-1]-1;
sum[i]=sum[i-1]+dis[i];
}
while(q--){
scanf("%d%d",&l,&r);
int ans=((sum[r]-sum[l])*2+k-a[r]+a[l]-1);
printf("%d\n",ans);
}
return 0;
}

C. Floor and Mod

显而易见,这是一个数论分块的模板题,只需要注意一下计算时的细节即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int a,b,x,y;
ll ans;
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&y,&x);
ans=0;
for(int i=1;i<=x;i++){
int j=y/i,k=i;
i=y/j;
if(min(j,x+1)-i-1<=0)break;
ans+=(i-k+1)*1LL*(min(j,x+1)-i-1);
}
printf("%lld\n",ans);
}
return 0;
}

D. Multiples and Power Differences

刚拿到这个题目,说实话挺懵的。总觉得是个bfs之类的,然后苦思冥想,但就是一直写不出来。

我当时心想,如果初始矩阵的所有数字都相同就好了,连bfs啥的都不用了,直接类似于国际象棋棋盘那样“染色”就行,即白的地方不管,黑的地方加上该位置上初始数字的四次方,这样就构造出来了符合题意的新矩阵。

再一看ai,ja_{i,j}居然很小,只在[1,16][1,16]这个区间内。有趣的是,这16个数字的最小公倍数是720720720720,即使加上16416^4,也小于题目要求的10610^6

于是乎问题迎刃而解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e2+10;
int m,n;
int ans[maxn][maxn],a[maxn][maxn];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans[i][j]=720720;
}
}
for(int i=1;i<=n;i++){
for(int j=i%2+1;j<=m;j+=2){
ans[i][j]+=pow(a[i][j],4);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d ",ans[i][j]);
}
printf("\n");
}
return 0;
}

E. Move and Swap

菜鸡如我看到这个题毫无头绪,以为是个树相关的图论题,众所周知,我图论相关的科技树是一点都没有,所以写完D题就去玩LOL了

但是如果对树上问题比较熟悉的话,应该能一眼看出来这道题其实是DP(呜呜呜我是傻Ⅹ)

先对该树跑一遍dfs,以1为根节点分层。红色可以是从父节点到子节点;而蓝色是从该层到下一层,不受任何约束。所以我们可以从红点入手定义DP状态。令dp[x]dp[x]表示红色移动到x点时,这时候能得到的最多的分数。此时状态的转移有两种方案:

  • 如果x点的父节点u是红色的,则dp[x]=max{dp[u]+v[i]v[x]}dp[x]=max\{ dp[u]+|v[i]-v[x]|\},其中i为与x点同层的所有的点的编号
  • 如果x点是通过交换来的,则dp[x]=max{dp[i]+max{v[son[i]]v[x]}}dp[x]=max\{ dp[i]+max\{ |v[son[i]]-v[x]|\} \},其中i为与x点父节点同层的所有的点的编号,son[i]son[i]表示i点的所有子节点

然后由于v[i]v[x]=max(v[i]v[x],v[x]v[i])|v[i]-v[x]|=max(v[i]-v[x],v[x]-v[i]),故可以在dp过程中可以这样去掉绝对值符号,简化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n,mxdep,a[maxn];
int cnt=1,h[maxn];
struct Edge{
int v,next;
}e[maxn<<1];
void add(int u,int v){
e[cnt].v=v;
e[cnt].next=h[u];
h[u]=cnt++;
}
int dep[maxn],pa[maxn];
ll dp[maxn];
vector<int>lev[maxn];
void dfs(int u,int p){
lev[dep[u]].push_back(u);
for(int i=h[u];i;i=e[i].next){
int v=e[i].v;
if(p==v)continue;
dep[v]=dep[u]+1;
pa[v]=u;
mxdep=max(mxdep,dep[v]);
dfs(v,u);
}
}
void solve(){
ll ans=0;
for(int i=1;i<=mxdep;i++){
ll mx1=-1e18,mx2=-1e18;
for(auto x:lev[i-1]){
for(int j=h[x];j;j=e[j].next){
int v=e[j].v;
if(dep[v]<dep[x])continue;
mx1=max(dp[x]+a[v],mx1);
mx2=max(dp[x]-a[v],mx2);
}
}
for(auto x:lev[i])
dp[x]=max(mx1-a[x],mx2+a[x]);

int mx=0,mn=1e9;
for(auto x:lev[i]){
mx=max(mx,a[x]);
mn=min(mn,a[x]);
}
for(auto x:lev[i]){
dp[x]=max(max(dp[pa[x]]+mx-a[x],dp[pa[x]]+a[x]-mn),dp[x]);
ans=max(dp[x],ans);
// printf("%d %d\n",x,dp[x]);
}
}
printf("%lld\n",ans);
}
void init(){
cnt=1;mxdep=0;
for(int i=1;i<=n;i++)h[i]=0,dep[i]=0,dp[i]=0;
for(int i=1;i<=n;i++)lev[i].clear();
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=2;i<=n;i++){
int v;scanf("%d",&v);
add(i,v);add(v,i);
}
for(int i=2;i<=n;i++)
scanf("%d",&a[i]);
dfs(1,0);
solve();init();
}
return 0;
}

F. Copy or Prefix Sum

又是一道喜闻乐见的DP我又喜闻乐见地没做出来

令即前k项a[i]a[i]的和,易证明j的取值只有至多n种可能。定义dp[j]dp[j]为前k项的和为j时,有多少种不同的构造方案(前k项)。然后状态转移分如下两种方案:(dp数组需要还要再加一层,为dp[i][j]dp[i][j],不然会导致错误,这里为了方便表述就省略了)

  • 如果a[k+1]==b[k+1]a[k+1]==b[k+1],则dp[j+b[k+1]]+=dp[j]dp[j+b[k+1]]+=dp[j]
  • 如果a[k+1]==b[k+1]i=1ka[i]a[k+1]==b[k+1]-\sum_{i=1}^{k}a[i],则dp[b[k+1]]+=dp[j]dp[b[k+1]]+=dp[j]

注意当j==0j==0时,只用计算一次即可

然后通过线段树可以对dp进行优化,这样nlogn的时间复杂度就可以通过了

但是,这里有一个trick,可以极大地简化代码,并且不需要写线段树,该方法如下:(有兴趣的话可以参看"Venice technique"

j=i=1ka[i]b[i]j=\sum_{i=1}^{k}a[i]-b[i]sum=dp[j]sum=\sum{dp[j]},则可知sum的递推式为sum=sum2dp[i=1kb[i]]sum=sum*2-dp[-\sum_{i=1}^{k}b[i]],而新的dp[i=1kb[i]]dp[-\sum_{i=1}^{k}b[i]]的值为sum更新之前的值。然后注意dp数组的下标可能是负数,故推荐使用map容器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
typedef long long ll;
const ll mod=1e9+7;
int n,b[maxn];
map<ll,ll>mp;
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d",&n);
mp.clear();
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
ll sum=1,k=-b[1]*1LL;mp[0]=1LL;
for(int i=2;i<=n;i++){
ll temp=sum;
sum=sum*2-mp[k],sum%=mod;
mp[k]=temp;
k-=b[i];
}
printf("%lld\n",(sum+mod)%mod);
}
return 0;
}