u1s1 我是真的不知道为什么现场这么多人切了 D，感觉 D 对思维要求显然要高于其他 300+ 人切掉的 D 吧（也有可能是 Atc 用户整体水平提升了？）
A
开 幕 雷 击（这题似乎 wjz 交了 2 发，ymx 交了 3 发）
分类讨论，想到就很简单，想不到就很烦，反正条条大路通罗马，这种难度的题最后都能 A 掉：
-
如果 \(2b\le a+c\)，且 \(a+c\) 为偶数，我们肯定会只对 \(b\) 进行 \(+1\) 操作，答案 \(\dfrac{a+c}{2}-b\)
-
如果 \(2b\le a+c\)，且 \(a+c\) 为奇数，我们肯定会先选择对 \(a\)（或 \(c\)）进行 \(+1\) 操作，再操作 \(b\)，答案 \(\dfrac{a+c+1}{2}-b+1\)
-
如果 \(2b>a+c\)，那么我们显然只会操作 \(a\)（或 \(c\)），答案 \(2b-a-c\)
B
tbh 感觉这个 B 比 A 简单（London Fog
首先将 \(a\) 数组从小到大排个序，然后每次贪心地找到 \(>a_i\) 的最小的 \(b_j\)，再找到 \(>b_j\) 的最小的 \(c_k\)，如果能找到这样 \(b_j,c_k\)，答案就加一。感性理解一下可知该做法是正确的。
C
现场用了一个比较好想的方法，所以成为了现场第二十几（？）个过掉这道题的人。
首先注意到答案肯定不会太大，因此考虑枚举答案然后检验答案是否可行。
怎样检验答案是否可行呢？考虑一个 \(dp\)，\(dp_{i,j,k}\) 表示填好了最低的 \(i\) 位，当前这一位进位为 \(j\)，并且有 \(k\) 个数能够延伸到这一位是否可行，转移我们就考虑延伸到这一位上 \(k\) 个数拼出的和是多少，设为 \(s\)，那么显然必须有 \(s\le 3k\) 且 \((s+j)\bmod 10\) 等于 \(n\) 第 \(i+1\) 低位上的数，如果 \(s\ge k\)，那么可以转移到 \(dp_{i+1,\lfloor\frac{s+j}{10}\rfloor,k}\)，否则应转移到 \(dp_{i+1,\lfloor\frac{s+j}{10}\rfloor,s}\)，因为最多只有 \(s\) 个 \(\{1,2,3\}\) 中的数能够拼出 \(s\)。初始 \(dp_{0,0,ans}=1\)。
不知道标算给的什么做法
D
一道思维题。
首先看到上升、下降可以想到差分，我们设 \(A,B,C\) 的差分序列分别为 \(D,E,F\)，那么原问题的约束条件等价于：
- \(A_1=B_1+C_1\)
- \(E_i\ge 0\)
- \(F_i\le 0\)
- \(D_i=E_i+F_i,i\in[1,n)\)
显然最后我们要最大化 \(B,C\) 中负数的和，因为 \(\sum\limits_{i=1}^nB_i+C_i=\sum\limits_{i=1}^nA_i\)，因此 \(\sum\limits_{i=1}^n|B_i|+|C_i|=\sum\limits_{i=1}^nA_i\) 减去 \(B,C\) 中负数之和的两倍。直接做显然不行，我们考虑挖掘一些性质。
Observation \(1\). 在最优方案中，一定有 \(E_i=\max(D_i,0),F_i=\min(D_i,0)\)
以 \(F_i\) 为例，由于 \(C_i\) 为不上升序列，因此我们可以找到一个分界点 \(i\) 满足 \(C_i>0\) 且 \(C_{i+1}\le 0\)（如果找不到那么 \(C\) 序列全部 \(>0\) 或全部 \(\le 0\)，此时结论显然满足），那么我们固定住 \(C_i\) 的值，那么：
- 对于 \(i\) 右边的某个 \(j\)，如果 \(F_j<\min(D_j,0)\)，那么我们将 \(F_j\) 加 \(1\)，那么此时 \(C_j,C_{j+1},\cdots C_n\) 都会 \(+1\)，而显然它们都是负数，因此 \(C\) 序列中负数之和会加 \(n-j+1\)，虽然这样会导致 \(E_j\) 减 \(1\)，导致有的本来非负的 \(B_j\) 变为负数，但这样 \(B\) 序列中负数之和最多减少 \(n-j+1\)，因此负数的总和还是不降的。
- 对于 \(i\) 左边某个 \(j\)，如果 \(F_j<\min(D_j,0)\)，那么我们将 \(F_j\) 加 \(1\)，由于我们固定了 \(C_j\) 的值，因此此次操作带来的效果是 \(C_1,C_2,\cdots,C_j\) 全部减 \(1\)，但由于它还是单调减序列，因此这些值依然大于 \(0\)，不影响 \(C\) 中负数之和，而这样带来的副作用是 \(B_1,B_2,\cdots,B_j\) 全部加 \(1\)，显然 \(B\) 序列中负数的和会不降，因此负数的总和不降
对于 \(E_i\) 也同理。
Observation \(2\). 在最优方案中，一定存在某个 \(E_i=0,F_i=0\)
证明：对于某个状态如果不存在 \(E_i=0\lor F_i=0\)，那么记 \(c_1\) 为 \(B\) 序列中负数的个数，\(c_2\) 为 \(C\) 序列中负数的个数，那么：
- 如果 \(c_1>c_2\)，将 \(B\) 序列向上平移直到某个值为 \(0\)，答案更优
- 如果 \(c_1\le c_2\)，将 \(C\) 序列向上平移直到某个值为 \(0\)，答案不比之前更差
看出这两个性质之后，就可以枚举 \(0\) 的位置然后一通 xjb 计算了，由于我使用了二分，因此复杂度 \(n\log n\)，不知道能不能优化到线性？
似乎这题有一车做法，标算还给了个 DP+斜率优化？而且我看了 4 个人现场 AC 的程序，他们竟然全写的三分 \(A_1\) 找极值？我直接 i 了 i 了！！！111
还是给个现场写的代码吧：
const int MAXN=2e5;
int n,a[MAXN+5],d[MAXN+5],e[MAXN+5],f[MAXN+5];
ll b[MAXN+5],c[MAXN+5],sb[MAXN+5],sc[MAXN+5];
int main(){
scanf("%d",&n);ll ans=-6e18;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++) d[i]=a[i+1]-a[i];
for(int i=1;i<n;i++) e[i]=max(d[i],0),f[i]=min(d[i],0);
for(int i=2;i<=n;i++) b[i]=b[i-1]+e[i-1],c[i]=c[i-1]+f[i-1];
for(int i=1;i<=n;i++) sb[i]=sb[i-1]+b[i],sc[i]=sc[i-1]+c[i];
// for(int i=1;i<=n;i++) printf("%lld%c",b[i]," \n"[i==n]);
// for(int i=1;i<=n;i++) printf("%lld%c",c[i]," \n"[i==n]);
for(int i=1;i<=n;i++){
ll b1=0-b[i];
ll sum=sb[i]+b1*i;
// printf("%d %lld %lld\n",i,b1,sum);
ll c1=a[1]-b1;
int l=1,r=n,p=n+1;
while(l<=r){
int mid=l+r>>1;
if(c1+c[mid]<0) p=mid,r=mid-1;
else l=mid+1;
} sum+=sc[n]-sc[p-1]+c1*(n-p+1);
// printf("%lld\n",sum);
chkmax(ans,sum);
}
for(int i=1;i<=n;i++){
ll c1=0-c[i];
ll sum=sc[n]-sc[i]+c1*(n-i);
// printf("%d %lld %lld\n",i,c1,sum);
ll b1=a[1]-c1;
int l=1,r=n,p=0;
while(l<=r){
int mid=l+r>>1;
if(b1+b[mid]<0) p=mid,l=mid+1;
else r=mid-1;
} sum+=sb[p]+b1*p;
chkmax(ans,sum);
} ll s=0;
for(int i=1;i<=n;i++) s+=a[i];
printf("%lld\n",s-ans*2);
return 0;
}
E
考虑 \(F(x)=A_1+\lfloor\dfrac{x}{B_1}\rfloor,G(x)=A_2+\lfloor\dfrac{x}{B_2}\rfloor\)，那么显然题目等价于 \(F(x)=G(x)\) 的个数。
注意到这东西啥性质也没有，既不成段分布也不是什么东西的倍数，直接计算又涉及到 \(B_1,B_2\) 两个周期，非常棘手，因此考虑另一个东西。我们设 \(f(x)=A_1+\dfrac{x}{B_1},g(x)=A_2+\dfrac{x}{B_2}\)，那么对于 \(F(x)=G(x)\) 的 \(x\)，\(f(x)\) 和 \(g(x)\) 肯定不能相差太多，具体来说：
- 如果 \(f(x)<g(x)-1\)，那么 \(F(x)\) 不可能等于 \(G(x)\)
- 如果 \(g(x)-1\le f(x)\le g(x)\)，那么 \(F(x)\in\{G(x)-1,G(x)\}\)
- 如果 \(g(x)\lt f(x)\le g(x)+1\)，那么 \(F(x)\in\{G(x),G(x)+1\}\)
- 如果 \(f(x)>g(x)+1\)，那么 \(F(x)\) 不可能等于 \(G(x)\)
我们考虑对中间两部分分别计算，以上面那种为例，我们求出 \(g(x)-1\le f(x)\le g(x)\) 的 \(x\) 组成的集合——显然是一个区间，用小学奥数的追及问题可以求出。那么考虑怎样求出 \(F(x)=G(x)\) 的个数，直接做还是不容易，因为两部分不独立，不过注意到 \(F(x)\) 只可能等于 \(G(x)-1\) 或 \(G(x)\)，因此我们考虑对这个区间内 \(G(x)\) 的和减去 \(F(x)\) 的和——这必然可以得到 \(F(x)=G(x)-1\) 的 \(x\) 的个数，然后减一下即可直到 \(F(x)=G(x)\) 的 \(x\) 的个数。对于另外一半镜像即可。至于怎样求 \(\sum\limits_{i=l}^rF(x)\)……\(\sum\limits_{i=l}^rF(x)=A_1·(r-l+1)+\sum\limits_{i=1}^r\lfloor\dfrac{x}{B_1}\rfloor-\sum\limits_{i=1}^{l-1}\lfloor\dfrac{x}{B_1}\rfloor\)，发现是 \(\sum\limits_{i=1}^x\lfloor\dfrac{i}{k}\rfloor\) 的形式，它显然等于 \(\sum\limits_{i=1}^x\dfrac{i-i\bmod k}{k}\)，前面直接套等差数列求和，后面 \(i\bmod k\) 显然呈周期分布，求出每个周期的和，乘上周期个数，再加上最后的零头即可。
ll n,ax,bx,ay,by;
ll getsum(ll b,ll x){
ll sum=x*(x+1)/2,cnt=x/b,rem=x%b;
sum-=cnt*(b*(b-1)/2);sum-=rem*(rem+1)/2;
return sum/b;
}
ll calc(ll a,ll b,ll l,ll r){
ll res=a*(r-l+1);
res+=getsum(b,r);
res-=getsum(b,l-1);
return res;
}
void solve(){
scanf("%lld%lld%lld%lld%lld",&n,&ax,&bx,&ay,&by);
if(bx==by) return printf("%lld\n",(ax==ay)?n:0),void();
if(bx>by) swap(ax,ay),swap(bx,by);
ll l=(ll)ceil(1.0*(ay-ax-1)/(by-bx)*bx*by);
ll r=(ll)floor(1.0*(ay-ax)/(by-bx)*bx*by);
chkmax(l,1ll);chkmin(r,n);ll ans=0;
// printf("%lld %lld\n",l,r);
if(l<=r){
ll x_sum=calc(ax,bx,l,r);
ll y_sum=calc(ay,by,l,r);
// printf("%lld %lld\n",x_sum,y_sum);
ll dif=y_sum-x_sum;
ans+=(r-l+1)-dif;
}
l=(ll)ceil(1.0*(ay-ax)/(by-bx)*bx*by);if(l==r) ++l;
r=(ll)floor(1.0*(ay-ax+1)/(by-bx)*bx*by);
chkmax(l,1ll);chkmin(r,n);
// printf("%lld %lld\n",l,r);
if(l<=r){
ll x_sum=calc(ax,bx,l,r);
ll y_sum=calc(ay,by,l,r);
// printf("%lld %lld\n",x_sum,y_sum);
ll dif=x_sum-y_sum;
ans+=(r-l+1)-dif;
} printf("%lld\n",ans);
}
int main(){
int qu;scanf("%d",&qu);
while(qu--) solve();
return 0;
}