插头 dp / 轮廓线 dp / 连通性 dp 做题笔记
牢游看见我正在做插头 dp，于是给我了一个 Claris 的连通性 dp 的 pdf。
好了，现在又有可以软性颓废的事可干了。
好多题目在其他平台都找不到了，这时候我们 becoder 的优越性就体现出来了！（这就是到处搬题的好处）所以大部分题目链接都会放 becoder 的链接。
什么？你不知道 becoder 或者没有 becoder 账号？亲爱的快快点我去进行注册吧！
（注意到这是一个推广链接，燕国的地图还是太短了。但是这个 72 小时刷新一次是不是也在变相催更我自己啊。）
后面考虑补一个插头 dp 的学习笔记？
插头 dp 学习笔记
咕咕咕
插头 dp 做题笔记
Becoder# 10030. Ants
如果做过模板题了的话这道题就很轻松了。
从图论的角度考虑，最后每个格子仍然有麻衣蚂蚁的话那么每个格子都会恰好有一个入度，所以会形成若干个有向回路。
回路覆盖计数是经典的插头 dp，而且这道题还没要求是一条回路！那就更简单了，定义三种插头：\(0\) 表示无插头，\(1\) 表示出度插头，\(2\) 表示入度插头：
分以下几种情况讨论：
- 右插头和下插头都是空插头：此时直接新建两个插头，一个入度插头和一个出度插头，因为每个格子都必须被回路覆盖到。
- 有一个空插头，另一个是非空插头：可以继续按照原来的方向延续这个插头，或是使其转向（右插头变下插头，下插头变右插头），注意插头的类型不能改变。
- 两个都是非空插头，直接合并，注意要判断两个插头是否是一个入度插头一个出度插头，如果不是的话需要忽略掉。
roll 的时候要把行末还有右插头的状态舍弃掉。
代码还是轻松的：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int mod = 299987;
int n, last = 1, now, bit, lx, dx, cnt[2], head[mod], nxt[200005], q[2][200005];
ll v, val[2][200005];
void push(int bit, ll v) {
static int r, pos;
r = bit % mod, pos = head[r];
while(pos) {
if(q[now][pos] == bit) {
val[now][pos] += v;
return;
}
pos = nxt[pos];
}
nxt[++cnt[now]] = head[r];
head[r] = cnt[now];
tie(q[now][cnt[now]], val[now][cnt[now]]) = tie(bit, v);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
push(0, 1);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= cnt[now]; ++j) {
if(q[now][j] >> (n << 1)) val[now][j] = 0;
q[now][j] <<= 2;
}
for(int j = 1; j <= n; ++j) {
swap(last, now);
fill(head, head + mod, 0);
cnt[now] = 0;
for(int k = 1; k <= cnt[last]; ++k) {
tie(bit, v) = tie(q[last][k], val[last][k]);
if(!v) continue;
lx = (bit >> ((j - 1) << 1)) & 3, dx = (bit >> (j << 1)) & 3;
if(!lx && !dx) {
push(bit ^ (1 << ((j - 1) << 1)) ^ (2 << (j << 1)), v);
push(bit ^ (2 << ((j - 1) << 1)) ^ (1 << (j << 1)), v);
}
else if(lx && !dx) {
push(bit, v);
push(bit ^ (lx << ((j - 1) << 1)) ^ (lx << (j << 1)), v);
}
else if(!lx && dx) {
push(bit, v);
push(bit ^ (dx << ((j - 1) << 1)) ^ (dx << (j << 1)), v);
}
else if((lx ^ dx) == 3) {
push(bit ^ (lx << ((j - 1) << 1)) ^ (dx << (j << 1)), v);
}
}
}
}
for(int i = 1; i <= cnt[now]; ++i) {
if(!q[now][i]) {
cout << val[now][i];
return 0;
}
}
cout << "0";
return 0;
}
Becoder# 17125. 「BZOJ3125」CITY
这不就是模板题的魔改版本吗？？？
只需要多加两个对于当前格子的判断即可：
- 横向格子：存在且仅存在一个右插头，需要将右插头延续向右。
- 纵向格子：存在且仅存在一个下插头，需要将下插头延续向下。
其他就和模板题没啥区别了。
注意要判断合并插头的时机，如果合并了同一连通块的插头那么只能在最后一个 . 位置合并，我因为这个唐诗错误调了 1h。
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int mod = 299987;
int n, m, last = 1, now, bit, rx, dx, ex, ey, cnt[2], head[mod], nxt[1600005], q[2][1600005];
char ch[13][13];
ll v, val[2][1600005];
void push(int bit, ll v) {
static int r, pos;
r = bit % mod, pos = head[r];
while(pos) {
if(q[now][pos] == bit) {
val[now][pos] += v;
return;
}
pos = nxt[pos];
}
nxt[++cnt[now]] = head[r];
head[r] = cnt[now];
tie(q[now][cnt[now]], val[now][cnt[now]]) = tie(bit, v);
}
int get_pos(int bit, int x, int sp) {
if(x == 1) {
for(int i = sp, sum = 0; i <= m + 1; ++i) {
if((bit >> (i << 1)) & 1) ++sum;
if((bit >> (i << 1)) & 2) --sum;
if(!sum) return i;
}
}
else {
for(int i = sp, sum = 0; i >= 0; --i) {
if((bit >> (i << 1)) & 1) --sum;
if((bit >> (i << 1)) & 2) ++sum;
if(!sum) return i;
}
}
cerr << "fuck data\n";
return -1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
cin >> ch[i][j];
if(ch[i][j] == '.') tie(ex, ey) = tie(i, j);
}
}
push(0, 1);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= cnt[now]; ++j) {
if(q[now][j] >> (m << 1)) val[now][j] = 0;
q[now][j] <<= 2;
}
for(int j = 1; j <= m; ++j) {
swap(last, now);
fill(head, head + mod, 0);
cnt[now] = 0;
for(int k = 1; k <= cnt[last]; ++k) {
tie(bit, v) = tie(q[last][k], val[last][k]);
if(!v) continue;
rx = (bit >> ((j - 1) << 1)) & 3, dx = (bit >> (j << 1)) & 3;
if(ch[i][j] == '.') {
if(!rx && !dx) {
push(bit ^ (1 << ((j - 1) << 1)) ^ (2 << (j << 1)), v);
}
else if(rx && !dx) {
push(bit, v);
push(bit ^ (rx << ((j - 1) << 1)) ^ (rx << (j << 1)), v);
}
else if(!rx && dx) {
push(bit, v);
push(bit ^ (dx << ((j - 1) << 1)) ^ (dx << (j << 1)), v);
}
else {
if(rx != dx) {
if(make_pair(rx, dx) == make_pair(2, 1) || make_pair(i, j) == make_pair(ex, ey)) push(bit ^ (rx << ((j - 1) << 1)) ^ (dx << (j << 1)), v);
}
else {
if(rx == 1) {
push(bit ^ (rx << ((j - 1) << 1)) ^ (dx << (j << 1)) ^ (3 << (get_pos(bit, dx, j) << 1)), v);
}
else {
push(bit ^ (rx << ((j - 1) << 1)) ^ (dx << (j << 1)) ^ (3 << (get_pos(bit, rx, j - 1) << 1)), v);
}
}
}
}
else if(ch[i][j] == '-') {
if(rx && !dx) {
push(bit ^ (rx << ((j - 1) << 1)) ^ (rx << (j << 1)), v);
}
}
else if(ch[i][j] == '|') {
if(!rx && dx) {
push(bit ^ (dx << ((j - 1) << 1)) ^ (dx << (j << 1)), v);
}
}
else if(ch[i][j] == '#') {
if(!rx && !dx) push(bit, v);
}
}
}
}
for(int i = 1; i <= cnt[now]; ++i) {
if(!q[now][i]) {
cout << val[now][i];
return 0;
}
}
cout << "0";
return 0;
}