摘要：三道原，比较之前的难，发挥不好，八点半从机房外面过去的帅哥真的真的真的好帅我一下子无心大模拟赛了一整个惊艳到。
状压 dp，据说爆搜也能过。本蒟蒻不会写剪枝，喜提 20pts。
状压 dp 思路：
首先 \(n*m<=50\)，\(m<=n\)，则 \(n,m<8\)，状压去做是非常可行的。
设 \(f_{i,j,k}\) 表示到了第 \(i\) 行时，这一行的状态作为 \(j\)、上一行状态作为 \(k\) 时的最小代价。
不难想到转移为：\(f_{i,j,k}=min(f_{i-1,k,l}+sum_{i,j})\)
对于这个代价 \(sum_{i,j}\) 我们预处理一下就好了。
考虑转移条件，对于 \(f_{i-1,k,l}\)，第 \(1\) 行到 \(i-2\) 行一定全部满足油田相邻的条件，所以只需要考虑 \(i-1\) 行，即 \(j|k|l|(k<<1)|(k>>1)\)。
然后油田总数 \(cnt\) 随着 \(f\) 一起转移。在这里 __builtin_popcount(i) 可以以常数的时间复杂度去求 i 的二进制下 1 的个数。
#include<bits/stdc++.h>
using namespace std;
const int N=10,M=52;
const int inf=0x3f;
int n,m;
int ans1=0x7fffffff,ans2=0x7fffffff;
int a[M][N],s[M][1<<N];
int f[M][1<<N][1<<N],cnt[M][1<<N][1<<N];
int main(){
memset(f,inf,sizeof f);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=0;j<(1<<m);j++)
for(int k=0;k<m;k++) if(j&(1<<k)) s[i][j]+=a[i][k+1];
for(int i=0;i<(1<<m);i++){
f[1][i][0]=s[1][i];
cnt[1][i][0]=__builtin_popcount(i);
}
for(int i=2;i<=n;i++)
for(int j=0;j<(1<<m);j++)
for(int k=0;k<(1<<m);k++)
for(int l=0;l<(1<<m);l++)
if(((j|k|l|(k<<1)|(k>>1))&(1<<m)-1)==(1<<m)-1){
int t=f[i-1][k][l]+s[i][j];
int p=cnt[i-1][k][l]+__builtin_popcount(j);
if(f[i][j][k]>t||(f[i][j][k]==t&&cnt[i][j][k]>p)){
f[i][j][k]=t;
cnt[i][j][k]=p;
}
}
for(int i=0;i<(1<<m);i++)
for(int j=0;j<(1<<m);j++)
if(((i|j|(i<<1)|(i>>1))&(1<<m)-1)==(1<<m)-1)
if(ans1>f[n][i][j]||(f[n][i][j]==ans1&&cnt[n][i][j]<ans2))
ans1=f[n][i][j],ans2=cnt[n][i][j];
printf("%d %d",ans2,ans1);
}
大部分写了 BFS。我写分层图的成小丑了。而且数组开小了，分层图的边还挺多的。
分层图思路：将没喝药水和喝了药水分两层。每层中内部，上下左右相互连边；对于层外连边，没喝药水的这一层能连到另一层的相同位置，代价为 0。喝药水就是，没喝的这一层连到下一层的那个位置。
这是我的分层图：
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
//十年 oi 一场空，数组开小见祖宗。
const int M=1010;
int n,m;
char a[M][M];
int vis[N],d[N];
int idx,e[N],w[N],nxt[N],head[N];
priority_queue<pair<int,int> > q;
void add(int x,int y,int z){
e[++idx]=y;
w[idx]=z;
nxt[idx]=head[x];
head[x]=idx;
}
void dij(){
memset(d,0x3f,sizeof d);
d[1]=0;
q.push(make_pair(0,1));
while(q.size()){
int x=q.top().second;
q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=head[x];i;i=nxt[i]){
if(d[e[i]]>d[x]+w[i]){
d[e[i]]=d[x]+w[i];
q.push(make_pair(-d[e[i]],e[i]));
}
}
}
}
int main(){
int x,y;
scanf("%d%d%d%d",&n,&m,&x,&y);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>a[i][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='#') continue;
if(i>1&&a[i-1][j]=='.'){
add((i-1)*m+j,(i-2)*m+j,1);
add((i-1)*m+j+n*m,(i-2)*m+j+n*m,1);
}
if(j>1&&a[i][j-1]=='.'){
add((i-1)*m+j,(i-1)*m+j-1,1);
add((i-1)*m+j+n*m,(i-1)*m+j-1+n*m,1);
}
if(i<n&&a[i+1][j]=='.'){
add((i-1)*m+j,i*m+j,1);
add((i-1)*m+j+n*m,i*m+j+n*m,1);
}
if(j<m&&a[i][j+1]=='.'){
add((i-1)*m+j,(i-1)*m+j+1,1);
add((i-1)*m+j+n*m,(i-1)*m+j+1+n*m,1);
}
add((i-1)*m+j,(i-1)*m+j+n*m,0);
if(i+x<=n&&j+y<=m&&i+x>=1&&j+y>=1&&a[i+x][j+y]=='.') add((i-1)*m+j,(i+x-1)*m+j+y+n*m,1);
}
}
dij();
if(min(d[n*m],d[2*n*m])==0x3f3f3f3f) puts("-1");
else printf("%d",min(d[n*m],d[2*n*m]));
}
先不补 BFS 了，如果边权为 1 的话 dij 还是容易被卡。希望有空补补 BFS 相关内容。
CF703D Mishka and Interesting sum
利用性质维护莫队 or 树状数组等数据结构。
不会写树形问题暴力导致的。写了 LCA 但不会暴力枚举子树，可能时间没把握好大脑宕机了。
赛时记录：
10 min：看了 ABCD，感觉题目质量更比前几天高了，比较困难。先开 A。
30 min：好消息啊，正解不是爆搜。
打模拟赛打到一半看到外面过去一个帅哥，甚至还对视上了，我草，怎么这么帅，我草一下子就无心写题了我草这也太。。回味无穷。。。。
假了。80 min 开 B。
140 min：切了 B，中间水了很久，一直试图调 A。B 就是一个可爱的分层图板板题。开 C。
170 min：事实上是仔细的看了看 D，然后写了个 C 的暴力。
滚回看 A。还是考虑最短路吧。我可能懂了。
还有 45 min。懂你吗。开始写 D。
end.