赛后——2.11 寒假模拟7
\(\text{T1}\) 矩阵
题意
小 \(S\) 有一个 \(n\times m\) 的字符矩阵，里面都是小写字母。
现在小 \(S\) 每一步可以向下或者向右走，从左上角走到右下角。现在他想让她他走出的字母拼接起来的字典序最小。
思路
一眼搜索或动态规划。现在考虑哪一个更优，显然记录当前的字符串然后比较是不行的，复杂度 \(O(nm|S|)\)，于是考虑维护一个 \(ans\) 字符数组表示第 \(i\) 步最好的字符选择。
这样深度优先搜索就成为不二之选。然而存在一个问题，若前几步的每种选择都是一样的，那么真正优的选择不一定会在队列最前，我们的解决方案如下：每次入队时更新答案，显然同一步的位置在队列是连续的，于是在第一个位置出队前，\(ans\) 就已经得到最优选择，我们只需要判断当前这一字符是否是最优选择再继续搜索即可。
代码
点击查看代码
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
}
for(int i=1;i<=n+m-1;i++){
ans[i]='z'+1;
}
vis[1][1]=1;
q.push(make_pair(1,1));
ans[1]=s[1][1];
while(!q.empty()){
int x=q.front().first,y=q.front().second;
q.pop();
if(s[x][y]>ans[x+y-1]) continue;
if(x+1<=n&&!vis[x+1][y]){
if(y==m||s[x+1][y]<=s[x][y+1]){
vis[x+1][y]=1;
ans[x+y]=min(ans[x+y],s[x+1][y]);
q.push(make_pair(x+1,y));
}
}
if(y+1<=m&&!vis[x][y+1]){
if(x==n||s[x+1][y]>=s[x][y+1]){
vis[x][y+1]=1;
ans[x+y]=min(ans[x+y],s[x][y+1]);
q.push(make_pair(x,y+1));
}
}
}
for(int i=1;i<=m+n-1;i++){
cout<\(\text{T2}\) 倒水
题意
小 \(S\) 面前有 \(n\) 个玻璃杯，每杯里都有水。
现在，小 \(S\) 想要把这 \(n\) 个杯子里的水互相倒，最终使得只有 \(m\) 个杯子里有水。
易知从把水从第 \(i\) 个玻璃杯倒到第 \(j\) 个的花费是 \(C_{i,j}\)，求最小花费。
思路
一个想法是最小生成树（森林），但这个贪心是假的。
考虑对 \(\operatorname{s}=m\) 的所有状态取一个最小，于是做法是状压dp，与正常状压不同的是，这里是大状态异或运算得到小状态，而非小状态与运算得到大状态。
代码
点击查看代码
inline int getbit(int x){
int cnt=0;
while(x){
if(x&1) cnt++;
x>>=1;
}
return cnt;
}
int dp[1<<21],ans=0x3f3f3f3f;
int main(){
n=read(),m=read();
for(int i=0;i=1;s--){
int num=getbit(s);
if(num<=1) continue;
for(int i=0;i \(\text{T3}\) 图
题意
有一个含有 \(n\) 个点的无向完全图，其中每一条边的权值都在 \([1,l]\)。要求存在多少个这样的图，使 \(1\) 到 \(n\) 的最短路长为 \(k\)。
一个相似的题
思路.
首先考虑暴力枚举每条路径的长，可以压成一个 \([0,l^e)\) 的状态，这里 \(e\) 为完全图的边数，\(e=n(n-1)/2\)，之后 \(\text{Floyd}\) 求最短路，时间复杂度是 \(O(l^e\cdot n^3)\)，大概能过 \(30\%\) 左右。
发现 \(n\) 与 \(k\) 都是极小的，可以枚举，那么就保证枚举的最短路成立的条件下求方案数并累加即可。
于是暴搜可以得到最短路的分配情况，设到 \(i\) 的最短路为 \(dis_i\)，显然 \(dis_1=1,dis_n=k\)，对于 \(dis_i>k\)，我们使其为 \(k+1\)，原因是 \(1\) 到 \(n\) 的最短路与其无关，取值是任意的（在保证最短路仍是 \(dis_i\) 的情况下）。
发现若 \(dis_i=dis_j\)，则 \(w(i,j)\) 是任意的。而若 \(dis_i>dis_j\)，应保证 \(dis_i\le dis_j+w(i,j)\)，于是 \(w(i,j)\ge dis_i-dis_j\)，目的是保持 \(dis_i\) 的合法性，此时的 \(w(i,j)\in [dis_i-dis_j,l]\)。同时，必须保证 \(dis_i\) 是可以由一个小于它的 \(dis_j\) 转移来的，于是需要减法原理。
因为：
所以正常情况下要乘上两者之差；然而如果这里的 \(dis_i\) 是大于 \(k\) 的，那么与转移无关，只要保证合法即可，直接乘全部大于等于的方案数。
然后对于相等的值，显然 \([1,l]\) 之间都是可选的，再乘上即可。
最后，因为剩余 \(n-2\) 个点的枚举是定义为有序的，乱序需要乘上多重集的方案数也就是 \(\dfrac{n!}{a_1! a_2!\cdots a_p!}\)，这里的 \(a\) 作为桶。
代码
点击查看代码
inline void dfs(int d,int num){
int lft=n-2-num;
if(d==k+1){
if(l==k&&lft) return;
cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=tot[i];j++){
dis[++cnt]=i;
}
}
dis[++cnt]=k;
for(int i=1;i<=lft;i++){
dis[++cnt]=k+1;
}
ll res1=1,res2=fac[n-2];
for(int i=1;i<=cnt;i++){
ll cnt1=1,cnt2=1;
for(int j=0;jdis[j]){
cnt1=cnt1*(l-(dis[i]-dis[j])+1)%mod;
cnt2=cnt2*(l-(dis[i]-dis[j]))%mod;
}
}
if(dis[i]<=k){
res1=res1*(cnt1-cnt2+mod)%mod;
}
else{
res1=res1*cnt1%mod;
}
for(int j=0;jl) return printf("0\n"),0;
fac[0]=1;
for(int i=1;i<=12;i++){
fac[i]=fac[i-1]*i;
}
dfs(1,0);
printf("%lld\n",ans);
return 0;
}
\(\text{T4}\) 道路建造
题意
\(n\) 个点的无向图（无重边和自环），要求将这个无向图删去或增加一条边，使其成为欧拉图的方案数，答案对 \(10^9+7\) 取模。
思路
我们设 \(f_i\) 为 \(i\) 个点的方案数，要求的答案是 \(f_n\cdot \binom{n}{2}\)。
于是求这个欧拉图个数就行了，详见
代码
点击查看代码
int main(){
n=read();
c[0][0]=1;
for(int i=1;i<=n;i++){
c[i][0]=1;
for(int j=1;j<=i;j++){
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
for(int i=0;i<=n;i++){
g[i]=q_pow(2,c[i][2]);
}
for(int i=1;i<=n;i++){
f[i]=g[i-1];
for(int j=1;j