A. Add and Divide

#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

#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

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

#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啥的都不用了，直接类似于国际象棋棋盘那样“染色”就行，即白的地方不管，黑的地方加上该位置上初始数字的四次方，这样就构造出来了符合题意的新矩阵。

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

于是乎问题迎刃而解。

#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]$ 表示红色移动到x点时，这时候能得到的最多的分数。此时状态的转移有两种方案：

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

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

#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]$ 的和，易证明j的取值只有至多n种可能。定义 $dp[j]$ 为前k项的和为j时，有多少种不同的构造方案（前k项）。然后状态转移分如下两种方案：（dp数组需要还要再加一层，为 $dp[i][j]$ ，不然会导致错误，这里为了方便表述就省略了)

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

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

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

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

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

#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;
}