以下，斜体表示注意点，粗体表示技巧点。
A
依题构造即可。
实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;int _;
int n,k;void solve(){cin>>n>>k;int x=1;for(;x*(x+1)/2<k;x++);x--;int rest=k-x*(x+1)/2;x++;for(int i=1;i<=n;i++){if(i==n-x||i==n-rest+1)cout<<'b';elsecout<<'a';}cout<<'\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>_;while(_--)solve();return 0;
}
B
我们考虑最小的操作次数，无非就是加到和前缀最大值相等。
于是维护一个前缀最大值，然后取一个（\(a_i\) 与前缀最大值的）最大差 \(x\)，答案即为 \(\lceil \log_2 x \rceil\)。
这种题想不出来真可以退役了。/fn
实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;const int N=1e5+5;
int _,n;
int a[N];void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int mx=-1e9,ans=-1e9;for(int i=1;i<=n;i++){mx=max(mx,a[i]);ans=max(ans,mx-a[i]);}int cnt=0;for(;ans;cnt++,ans>>=1);cout<<cnt<<'\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>_;while(_--)solve();return 0;
}
C
枚举断点维护前后，序列考虑差分。
首先枚举 \(k\)，差分一下，发现 \(k\) 之前的必须都 \(> 0\)，\(k\) 之后的必须都 \(< 0\)。
于是我们维护前缀 \(\le 0\) 的操作次数 \(pre_i\)，后缀 \(\ge 0\) 的操作次数 \(suf_i\)，答案即为 \(\max\{\min(pre_i,suf_{i+1})\}\)。
实现
#include <bits/stdc++.h>
#define int long long
using namespace std;const int N=2e5+5;
int _,n;
int a[N],b[N],pre[N],suf[N];void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i]-a[i-1];for(int i=2;i<=n;i++)pre[i]=pre[i-1]-(b[i]<=0?b[i]-1:0);for(int i=n;i>=2;i--)suf[i]=suf[i+1]+(b[i]>=0?b[i]+1:0);int ans=LONG_LONG_MAX;for(int i=1;i<=n;i++)ans=min(ans,max(pre[i],suf[i+1]));cout<<ans;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);_=1;while(_--)solve();return 0;
}
D
数据范围启发我们枚举这个 \(x\)。
然后我们发现，如果一个对 \(i,n-i+1\) 要改 \(\le 1\) 次，则其 \(x \in [\min(a_i,a_{n-i+1})+1,\max(a_i,a_{n-i+1})+k]\)。
改 \(0\) 次的可以开个桶判断，改 \(2\) 次的减一下就行，这样便得到了一个平方做法。
观察到复杂度瓶颈在于枚举 \(i\)，我能不能直接统计当前的 \(x\) 被多少个区间覆盖（即有多少个改一次的）？答案是肯定的。发现需要区间修改操作，考虑差分一下就完事了。
实现
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#define int long long
using namespace std;const int N=4e5+5;
int _,n,k;
int a[N],d[N],e[N];void solve(){for(int i=0;i<=2*k+5;i++)d[i]=e[i]=0;cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n/2;i++){e[a[i]+a[n-i+1]]++;d[min(a[i],a[n-i+1])+1]++;d[max(a[i],a[n-i+1])+k+1]--;}for(int i=2;i<=2*k;i++)d[i]+=d[i-1];int ans=1e18;for(int i=2;i<=2*k;i++)ans=min(ans,d[i]-e[i]+(n/2-d[i])*2);cout<<ans<<'\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin>>_;while(_--)solve();return 0;
}
E
待补。。。