20230909 B 组模拟赛 题解
前言
爆大零，T2 第一次因为数组开大了常数过大 TLE，痛失 30pts，喜提 120pts。
T1
简单题，但赛时被数据范围诈骗了，痛失 2h。
赛时一开始看到数据范围以为是指数复杂度，就猜了个最优解当且仅当两维都是最优解的结论，结果过不了第二个样例，然后又想 $O(n^6)$ DP 发现写不出来，最后想到了一维暴力枚举，另一维 DP。
首先第一维直接 $O(2^n)$ 枚举，然后第二维可以设计一个 DP。设 $dp_{i,j}$ 表示考虑前 $i$ 列，切 $j$ 刀可以得到的最小值最大是多少，转移是简单的，二维前缀和维护一下即可。复杂度 $O(2^nnm^2)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=16,inf=0x3f3f3f3f;
int n,m,a[N][N],pre[N][N];
int ans[N][N],dp[N][N];
int ppcnt(int x){
int res=0;
while(x){
x-=x&-x;++res;
}
return res;
}
signed main(){
n=read();m=read();
forup(i,1,n){
forup(j,1,m){
a[i][j]=read();
pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
}
}
forup(i,0,(1<<(m-1))-1){
vector<int> vr;
vr.push_back(0);
forup(k,1,m-1){
if(i&(1<<(k-1))) vr.push_back(k);
}
vr.push_back(m);
int cr=vr.size();
mem(dp,0);
forup(j,1,n){
int mn=inf;
forup(r,0,cr-2){
mn=min(mn,pre[j][vr[r+1]]-pre[0][vr[r+1]]-pre[j][vr[r]]+pre[0][vr[r]]);
}
dp[j][0]=mn;
forup(k,1,j-1){
forup(l,k,j-1){
int mn=inf;
forup(r,0,cr-2){
mn=min(mn,pre[j][vr[r+1]]-pre[l][vr[r+1]]-pre[j][vr[r]]+pre[l][vr[r]]);
}
dp[j][k]=max(dp[j][k],min(mn,dp[l][k-1]));
}
}
}
int pc=ppcnt(i);
forup(j,0,n-1){
ans[j][pc]=max(ans[j][pc],dp[n][j]);
}
}
forup(i,0,n-1){
forup(j,0,m-1){
printf("%d ",ans[i][j]);
}
puts("");
}
}
T2
不难，但赛时不仅打的暴力，还因为数组开大 TLE 了。
首先考虑假如没有交换操作，这道题应该怎么做，那么容易想到 DP，设 $dp_{i,j}$ 表示考虑 $a$ 前 $i$ 个、$b$ 前 $j$ 个的所有决策中，所需阈值最小是多少，由于只要知道了 $i,j$ 就能知道当前 $S$ 里面还剩几个元素，所以转移是简单的，就是考虑当前个数加一和之前的最大值取 $\max$，然后转移到下一个即可，在此略过。
那么假如把每个 $i,j$ 时剩下的元素数放在一个 $i$ 行 $j$ 列的矩阵里，容易发现交换 $a_i,a_{i+1}$ 就只有第 $i$ 行会改变，另外容易发现我们的 $dp_{i,j}$ 就等价于在刚才那个矩阵上找一条 $(0,0)\to (i,j)$ 的路径，路径上最大值最小是多少（再 $+1$），那么我们可以再预处理每个点 $(i,j)\to (n,n)$ 的路径上最大值最小是多少，这样我们最后在改变的这一列上贪心一下即可求出答案（这里“贪心”指每个阶段只保留一个状态的 DP）。
预处理可以 $O(n^2)$，然后求每个答案是 $O(n)$ 的，总复杂度 $O(n^2)$。
参考代码
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s);i<=(e);i++)
#define fordown(i,s,e) for(int i=(s);i>=(e);i--)
using namespace std;
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const int N=5005,inf=0x3f3f3f3f;
int n,a[N],b[N],dp[N][N],pd[N][N],c1[N],c2[N],cc[N][N],nc[N],f;
signed main(){
n=read();
forup(i,1,n){
a[i]=read();
}
forup(i,1,n){
b[i]=read();
}
mem(c1,0);mem(dp,inf);
int nw=0;dp[0][0]=1;
forup(i,0,n){
if(i) c1[a[i]]++;c1[a[i]]%=3;
nw=0;
forup(j,1,n){
c2[j]=c1[j];
nw+=c2[j];
}
forup(j,0,n){
if(j){
nw-=c2[b[j]];
c2[b[j]]=(c2[b[j]]+1)%3;
nw+=c2[b[j]];
}
cc[i][j]=nw;
if(i<n) dp[i+1][j]=min(dp[i+1][j],max(dp[i][j],nw+1));
if(j<n) dp[i][j+1]=min(dp[i][j+1],max(dp[i][j],nw+1));
}
}
mem(pd,0x3f);
pd[n][n]=0;
fordown(i,n,0){
fordown(j,n,0){
if(i) pd[i-1][j]=min(pd[i-1][j],max(pd[i][j],cc[i-1][j]+1));
if(j) pd[i][j-1]=min(pd[i][j-1],max(pd[i][j],cc[i][j-1]+1));
}
}
mem(c1,0);
forup(i,1,n-1){
c1[a[i+1]]++;c1[a[i+1]]%=3;
nw=0;
forup(j,1,n){
c2[j]=c1[j];
nw+=c2[j];
}
c1[a[i+1]]+=2;c1[a[i+1]]%=3;
c1[a[i]]++;c1[a[i]]%=3;
forup(j,0,n){
if(j){
nw-=c2[b[j]];
c2[b[j]]=(c2[b[j]]+1)%3;
nw+=c2[b[j]];
}
nc[j]=nw;
}
int res=inf;
f=max(dp[i-1][0],cc[i-1][0]+1);
res=min(res,max(max(f,nc[0]+1),pd[i+1][0]));
forup(j,1,n){
f=min(max(f,nc[j-1]+1),max(dp[i-1][j],cc[i-1][j]+1));
res=min(res,max(max(f,nc[j]+1),pd[i+1][j]));
}
printf("%d\n",res);
}
}