20230928 B 组模拟赛 题解
前言
本来不想写的，但改着改着发现挺有意思的，就挑两道写了。
T1
题意是：若 $A$ 为 $n$ 阶 $01$ 矩阵，$A^k$ 为全 $0$ 矩阵，那么 $A$ 中最多有几个 $1$。
非常有意思的题。
首先这道题不是构造题，考虑从矩阵乘法的本质思考。
我们发现我们只关心每个位置是不是 $0$，那么矩阵乘法的乘 $\times$ 完全可以换成逻辑与 $\land$，加法换成逻辑或 $\lor$。
所以矩阵乘法的式子就化为：
$$C_{i,j}=\bigvee_{k=1}^{n} A_{i,k}\land B_{k,j}$$
这里有个非常巧妙地转化。如果把原矩阵视作 $01$ 矩阵，那么上式表示 $C$ 图中 $i,j$ 有边当且仅当存在一个 $k$，使得 $A$ 图中 $i,k$ 有直接连边，$B$ 图中 $k,j$ 有直接连边。
这就让我们想到它和 floyd 很类似。那么容易发现 $A^k_{i,j}=1$ 当且仅当 $A$ 图中 $i$ 能通过恰好 $k$ 条边到达 $j$。
那么容易想到贪心，把所有点平均分成 $k$ 份，余数均分到前面，然后每份向后面所有份连边。
关于如何计算，我们可以简单容斥，假设所有点两两之间有有向边，那么答案就是 $n^2$，但是每一份内部无边，减去即可。
参考代码
结论题要什么代码？
T4
我不知道这个做法是怎么想出来的，但确实很妙。
首先考虑两个操作其实就是二进制中左移右移，低于 $0$ 的位数就删掉。
那么容易发现答案必然不会超过 $\sum_{i=1}^n (\left\lfloor\log a_i\right\rfloor+1)$，因为如果把所有数都变成 $0$ 得到的序列显然是单调不降的。
另外，容易发现最终序列里面的每个数 $a_i'$ 必定是 $a_i$ 先连续进行若干次右移再连续进行若干次左移得到的。因为显然先左移后右移对结果不会产生影响。另外容易发现右移的次数不会多于 $\left\lfloor\log a_i\right\rfloor+1$，不然就变成 $0$ 了。
我们可以把序列分为两半，前半部分的 $a_i'$ 均小于 $2^{17}(2^{\left\lfloor\log 10^5\right\rfloor})$，后半部分均大于等于 $2^{17}$，这样分显然是可行的，如果全归为其中一类可以考虑把分界取到 $0,1$ 之间或 $n,n+1$ 之间。
对于前一半，容易发现对于每个 $a_i$ 只有 $(\left\lfloor\log a_i\right\rfloor+1)^2$ 个对应的 $a_i'$。那么就可以设 $dp_{i,j}$ 表示考虑前 $i$ 个数，第 $i$ 个数取编号为 $j$（这个编号自己预处理）的 $a'$，所需要的最小代价。转移可以排序后用双指针，复杂度 $O(n\log^2 V\log\log V)$。
对于后一半，容易发现 $a_i'$ 都是 $a_i$ 二进制下的一个前缀后面加至少一个 $0$。容易发现假如固定每个 $a_i$ 具体取哪个前缀，那么加 $0$ 的最小数量是容易唯一确定的。
具体来说，我们先对于每个前缀加上若干个 $0$ 使得最高位恰好为 $2^{17}$，设这样得到的序列为 $b$，那么若 $b_{i+1}\ge b$ 则无事发生，若 $b_{i+1}<b$ 则在 $b_{i+1\sim n}$ 末尾均加上一个 $0$ 即可。由于最高位对齐，这样显然能使 $b_{i+1}\ge b_i$，且容易发现不存在加 $0$ 数量更少的方法，因为每个 $0$ 都是不得不加的。
那么设 $f_{i,j}$ 表示考虑后 $i$ 个数，第 $i$ 个数取编号为 $j$ 的前缀，所需要的最小代价。转移自己推一推，核心思想刚刚已经说过了。这部分貌似可以用前后缀最小值做到 $O(n\log V\log\log V)$，但是我的评价是没必要，反正瓶颈也不在这里。
参考代码
#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=1e5+5,M=1<<17,inf=0x3f3f3f3f;
int t,id,n,a[N],dp[N][300],ct[N],dp2[N][20],ct2[N],ans;
struct Node{
int val,cst;
}sta[N][300],stb[N][17];
void solve(){
n=read();ans=0;
forup(i,1,n){
a[i]=read();
ct[i]=0;
int c1=0;
for(int j=a[i];j;j>>=1){
int c2=0;
for(int k=j;k<M;k<<=1){
sta[i][++ct[i]]=Node{k,c1+c2};
++c2;
}
++c1;
stb[i][c1]=Node{sta[i][ct[i]].val<<1,sta[i][ct[i]].cst+1};
}
ans+=c1;
ct2[i]=c1;
sort(sta[i]+1,sta[i]+ct[i]+1,[](Node a,Node b){
return a.val<b.val;
});
}
forup(i,1,ct[1]){
dp[1][i]=sta[1][i].cst;
}
forup(i,2,n){
int l=1,mn=inf;
forup(j,1,ct[i]){
while(l<=ct[i-1]&&sta[i-1][l].val<=sta[i][j].val){
mn=min(mn,dp[i-1][l]);
++l;
}
dp[i][j]=mn+sta[i][j].cst;
}
}
forup(i,1,ct2[n]){
dp2[n][i]=stb[n][i].cst;
}
fordown(i,n-1,1){
forup(j,1,ct2[i]){
dp2[i][j]=inf;
forup(k,1,ct2[i+1]){
if(stb[i+1][k].val>=stb[i][j].val){
dp2[i][j]=min(dp2[i][j],dp2[i+1][k]+stb[i][j].cst);
}else{
dp2[i][j]=min(dp2[i][j],dp2[i+1][k]+stb[i][j].cst+(n-i));
}
}
}
}
forup(i,1,n){
int a1=inf,a2=inf;
forup(j,1,ct[i]){
a1=min(a1,dp[i][j]);
}
if(i+1>n){
a2=0;
}else{
forup(j,1,ct2[i+1]){
a2=min(a2,dp2[i+1][j]);
}
}
ans=min(ans,a1+a2);
}
printf("%d\n",ans);
}
signed main(){
t=read();id=read();
while(t--){
solve();
}
}