atcoder 杂题 #03
arc189_b
题目大意：数轴上有 \(n\) 个点 \(x_i\)，每次可以选择连续递增四个点，记 \(M\) 为第一个和第四个点的中点，把第二个和第三个点关于 \(M\) 对称，问不断操作，点坐标和最小是多少。
这道题赛时往贪心的方向想了，一直不会做。没想到在洛谷上评了绿。
考虑操作一次后，差分数组的变化。
记 \(d_i=a_i-a_{i-1}(2\le i\le n)\)。
那么选择 \(i\sim i+4\) 操作以后，就从 \([a_i][a_{i+1}][a_{i+2}][a_{i+3}]\)，变成了 \([a_i][a_i+a_{i+3}-a_{i+1}][a_i+a_{i+3}-a_{i+2}][a_{i+3}]\)，注意第二项比第三项大，所以是 \([a_i][a_i+a_{i+3}-a_{i+2}][a_i+a_{i+3}-a_{i+1}][a_{i+3}]\)。
那么，差分数组就从 \(d_{i+1},d_{i+2},d_{i+3}\) 变成了 \(d_{i+3},d_{i+2},d_{i+1}\)，相当于交换第一个和第三个差分。
发现对于奇偶性相同的位置，我们可以随便交换。
那么由于让和最小，所以要让前面的差分尽可能小，于是对奇数位的差分和偶数位的差分分别排序即可。
时间复杂度 \(O(n\log n)\)。
AC 代码：
const int N=2e5+5;
int a[N];
int d1[N],d2[N];
int n;
int d[N];
signed main(){
cin>>n;
fo(i,1,n){
cin>>a[i];
d[i]=a[i]-a[i-1];
if(i&1)d1[i/2]=d[i];
else d2[i/2]=d[i];
}
sort(d1+1,d1+1+(n-1)/2);
sort(d2+1,d2+1+n/2);
fo(i,1,n){
if(i&1)d[i]=d1[i/2];
else d[i]=d2[i/2];
}
ll ans=a[1];
fo(i,2,n){
a[i]=a[i-1]+d[i];
ans+=a[i];
}
cout<<ans;
return 0;
}
abc227_f
首先想到二分第 \(K\) 大 \(mid\)，然后设 \(f_{i,j,k}\) 表示走到 \((i,j)\) 选了 \(k\) 个大于等于 \(mid\) 的数。
然而观察第二个样例发现并没有单调性：
input:
2 2 1
3 2
4 3
output:
3
于是考虑枚举第 \(K\) 大 \(x\)，然后还是一样的状态。
如果 \(x\) 是正确路径的第 \(K\) 大，但路径上大于等于 \(x\) 的数多于 \(K\) 个怎么办呢。
发现可以让等于 \(x\) 的数选或不选即可，最后只统计 \(f_{n,m,K}\)。
计算时间复杂度，注意 \(f_{i,j,k}\) 中 \(k\) 是 \(O(n)\) 的，于是做一次 DP 是 \(O(n^3)\)，枚举第 \(K\) 大为 \(O(n^2)\)，于是总复杂度为 \(O(n^5)\)，刚好能通过。
AC 代码：
const int N=32;
int a[N][N];
int n,m,K;
ll f[N][N][N+N];
ll ans=9e18;
signed main(){
read(n,m,K);
fo(i,1,n)fo(j,1,m)read(a[i][j]);
fo(_,1,n)fo(__,1,m){
memset(f,0x3f,sizeof f);
int t=a[_][__];
if(a[1][1]<t)f[1][1][0]=0;
else f[1][1][1]=a[1][1];
fo(i,1,n)fo(j,1,m){
if(i==1&&j==1)continue;
if(a[i][j]<=t)f[i][j][0]=min(f[i-1][j][0],f[i][j-1][0]);
fo(k,1,K){
if(a[i][j]==t){
f[i][j][k]=min(min(f[i-1][j][k],f[i][j-1][k]),min(f[i-1][j][k-1],f[i][j-1][k-1])+a[i][j]);
}
else if(a[i][j]>t){
f[i][j][k]=min(f[i-1][j][k-1],f[i][j-1][k-1])+a[i][j];
}
else f[i][j][k]=min(f[i-1][j][k],f[i][j-1][k]);
}
}
ans=min(ans,f[n][m][K]);
}
write(ans);
return 0;
}
arc189_d
首先有一个 \(O(n^2)\) 的贪心策略，对于每个点每次能往左就往左，能往右就往右。
考虑优化这个贪心策略，记当前扩展到 \([L,R]\)，获得的和为 \(sum\)，那么我们每次往左扩展到最小的 \(l\) 使得 \(\max_{l\le j<L}\{a_j\}<sum\)，往右也同理。
计算这个东西的时间复杂度，发现假若当前和为 \(sum\)，我们往左扩展了两次，那么第一次肯定有 \(a_{l-1}\ge sum\)，那么第二次结束后的 \(sum'\) 一定有 \(sum'\ge a_{l-1}+sum\ge 2\times sum\)。
于是我们经过 \(O(1)\) 次扩展一定会使得 \(sum\) 至少乘 2。往右也同理。
由于 \(a_i\le 10^9\)，我们在经过 \(O(\log a)\) 次后一定会停止或扩展到整个序列。
每次扩展时求最小的 \(l\) 和最大的 \(r\) 可以二分，可用 ST 表求区间最大值，常数较小。
时间复杂度 \(O(n\log n\log a)\)。
AC 代码：
int a[N];
int n;
int mx[19][N];
int get(int l,int r){
int len=r-l+1;
return max(mx[__lg(len)][l],mx[__lg(len)][r-(1<<__lg(len))+1]);
}
ll sum[N];
signed main(){
read(n);
fo(i,1,n){
read(a[i]);
mx[0][i]=a[i];
sum[i]=sum[i-1]+a[i];
}
fo(i,1,__lg(n))fo(j,1,n-(1<<i)+1){
mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
}
fo(i,1,n){
int L,R;
L=R=i;
ll s=a[i];
while((L>1&&s>a[L-1])||(R<n&&s>a[R+1])){
if(L>1&&s>a[L-1]){
int l=1,r=L-1,as=0;
while(l<=r){
int mid=(l+r)>>1;
if(get(mid,L-1)<s)as=mid,r=mid-1;
else l=mid+1;
}
s=s+sum[L-1]-sum[as-1];
L=as;
}
else if(R<n&&s>a[R+1]){
int l=R+1,r=n,as=0;
while(l<=r){
int mid=(l+r)>>1;
if(get(R+1,mid)<s)as=mid,l=mid+1;
else r=mid-1;
}
s=s+sum[as]-sum[R];
R=as;
}
}
write(s,' ');
}
return 0;
}
arc067_e
首先考虑我们每次新建 \(k\) 个大小为 \(j\) 的组，由于 \(k\times j\le n\)，所以合法的 \((j,k)\) 对的个数是调和级数 \(O(n\ln n)\)。
那么设 \(f_{i,j}\) 表示有 \(i\) 个人已分好组，组的大小最大为 \(j\)，且以后分的组的大小一定大于 \(j\) 的方案数。
那么转移就是枚举 \(k,j\)，得
\[\text{calc}(k,j)\times \sum_{x<j}f_{i-1,x}\to f_{i+k\times j-1,j} \]其中 \(k,j\) 表示新建了 \(k\) 个大小为 \(j\) 的组，\(\text{calc}(x,y)\) 就表示从剩下的人中选出 \(x\times y\) 个人，然后分成 \(x\) 个无标号的大小为 \(y\) 的组的方案数。
首先后面的和式可以前缀和优化。
考虑 \(\text{calc}(x,y)\) 怎么计算，首先选出 \(x\times y\) 个人 \(\binom{n-i+1}{x\times y}\)。
我们先把这些人排列 \((x\times y)!\)，然后每 \(y\) 个人分一组，除去组内的顺序 \((y!)^{-x}\)，除去组的标号 \((x!)^{-1}\)。即
组合数可以用预处理阶乘，于是预处理 \(\text{calc}(x,y)\) 可以做到 \(O(n^2\log n)\)。
初始状态 \(f_{0,0}=1\)，答案为 \(\sum_j f_{n,j}\)。
最终时间复杂度为 \(O(n^2\log n)\) 或 \(O(n^2\log^2n)\)。
AC 代码：
const int N=1e3+5;
const int mod=1e9+7;
int n,A,B,C,D;
int pow1(int x,int y){
int res=1;
for(;y;y>>=1,x=(ll)x*x%mod)if(y&1)res=(ll)res*x%mod;
return res;
}
int fac[N],inv[N];
int c(int x,int y){
return (ll)fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int sol(int x,int y){
return (ll)fac[x*y]*pow1(inv[y],x)%mod*inv[x]%mod;
}
int f[N][N];
signed main(){
read(n,A,B,C,D);
f[0][0]=1;
fac[0]=1;
inv[0]=1;
fo(i,1,n)fac[i]=(ll)fac[i-1]*i%mod,inv[i]=pow1(fac[i],mod-2);
fo(i,1,n){
fo(j,1,n)(f[i-1][j]+=f[i-1][j-1])%=mod;
fo(j,A,B){
fo(k,C,D){
if(j*k>n-i+1)break;
(f[i+j*k-1][j]+=(ll)sol(k,j)*f[i-1][j-1]%mod*c(n-i+1,j*k)%mod)%=mod;
}
}
}
int ans=0;
fo(i,0,n)(ans+=f[n][i])%=mod;
cout<<ans;
return 0;
}