对 \(n\times m\) 的矩阵进行不重复的
\([1,\ n\times m]\)
整数填数，定义局部最小值为比其八连通块都小的位置，给定局部最小值，求合法方案数
如果罗兹瓦尔说的像这样清晰该有多好
还是我语文太差了
先不讨论非局部最小值的合法性，显然这是一个拓扑排序计数问题，对于一般图的拓扑排序计数问题，通常使用状压\(DP\)，把已排序好的集合作为状态，在转移时判断加入集合的点的前驱是否都已排序，而顺序性体现已排序集合的扩大的过程中，这也是排序问题的核心思想
在这道题里还有一个比较明显的性质，局部最小值的数量不超过
\(8\)
所以考场上直接写了一个裸的拓扑排序计数和一个小小的剪枝
然后，果断便会白给
没有生成一组极限数据测状态数
正解首先是对 \(DP\) 的优化
设局部最小值的填数状态为 \(S\) 已填
\(i\) 个数的方案数 \(f_{i,S}\) 和在状态 \(S\) 下不受局部最小值限制的位置个数为 \(g_S\) 则有转移
\[
f_{i,S}\ =\ f_{i-1,S}\times (g_S-(i-1))+\sum_{p\in S}f_{i-1,S-p}
\]
前一部是当前的数不给局部最小值，后一部分是给局部最小值
时间复杂度 \(O(nm2^k)\) 其中 \(k\le8\)
接下来讨论非局部最小值的合法性，考虑直接按上述式子 \(DP\) 求出的是至少有\(0\)个非局部最小值成为局部最小值，而题意要求恰好有\(0\)个非局部最小值成为局部最小值，直接组合容斥即可
具体来说，设 \(h_k\) 为至少有\(k\)个非局部最小值成为局部最小值，那么就有
\[
ans\ =\ \sum(-1)^kh_k
\]
其中 \(h_k\) 不需要具体求出，\(DFS\) 枚举合法的转化数量即可
时间大概 \(O(tnm2^k)\) 其中 \(t\in [\Pi(nm-9i-9k),\Pi(nm-4i-4k)]\) \(t\) 离上界相差很远，总之很优秀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <map>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 4+5, M = 7+5, P = 12345678;
const int dx[8] = {0, 0, 1, 1, -1, -1, 1, -1};
const int dy[8] = {1, -1, 1, -1, 1, -1, 0, 0};
int t, n, m, d;
char w[N][M];
int f[N*M][1<<8], ans, g[1<<8];
int bit(int i, int j) { return (i-1)*m+j-1; }
pair<int, int> dbit(int p) { return make_pair(p/m+1, p%m+1); }
pair<int, int> c[N];
int hateMathers()
{
memset(f, 0, sizeof(f)); d = 0;
memset(g, 0, sizeof(g));
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(w[i][j] == 'X') c[d++] = make_pair(i, j);
for(int s = 0; s < 1<<d; ++s)
{
for(int i = 0; i < d; ++i) w[c[i].first][c[i].second] = (s>>i&1)?'.':'X';
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
if(w[i][j] == 'X') continue;
int q = 1;
for(int k = 0; k < 8; ++k) if(w[i+dx[k]][j+dy[k]] == 'X') q = 0;
g[s] += q;
}
}
for(int i = 0; i < d; ++i) w[c[i].first][c[i].second] = 'X';
f[0][0] = 1;
for(int i = 1; i <= n*m; ++i)
for(int s = 0; s < 1<<d; ++s)
{
f[i][s] = 1ll*f[i-1][s]*(g[s]-i+1)%P;
for(int p = 0; p < d; ++p)
if(s>>p&1) f[i][s] = (f[i][s]+f[i-1][s^(1<<p)])%P;
}
return f[n*m][(1<<d)-1];
}
void hateRoswaal(int p, int k)
{
if(p == n*m) return void(ans = (ans+k*hateMathers()+P)%P);
pair<int, int> par = dbit(p); int x = par.first, y = par.second;
if(w[x][y] == 'X') hateRoswaal(p+1, k);
else
{
hateRoswaal(p+1, k);
for(int i = 0; i < 8; ++i) if(w[x+dx[i]][y+dy[i]] == 'X') return;
w[x][y] = 'X'; hateRoswaal(p+1, -k); w[x][y] = '.';
}
}
int main()
{
freopen("garden.in", "r", stdin);
freopen("garden.out", "w", stdout);
t = read();
while(t--)
{
n = read(), m = read(); ans = 0;
memset(w, 0, sizeof(w));
for(int i = 1; i <= n; ++i) scanf("%s", w[i]+1);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
bool is_emp = true;
for(int k = 0; k < 8&&is_emp; ++k)
if(w[i+dx[k]][j+dy[k]] == 'X')
is_emp = false;
if(!is_emp&&w[i][j] == 'X') ans = -1;
}
if(ans == -1) printf("0\n");
else hateRoswaal(0, 1), printf("%d\n", ans);
}
return 0;
}
|
Throw
求 \((a,\ b,\ c)\) 经过 \(f(a,\ b,\ c)\) 变为 \((a',\ b',\ c')\)
的最小操作个数
很好的思维题
考试时写搜索时，想到双向搜索，想到双向搜索又想到建树，但没继续像，转而想
\(exgcd\) 和毒瘤贪心
首先题目中的丢你拉姆过于花哨，与三元素中每一个元素等价这一条件显得十分不自然，我们结合
P1007 独木桥
的想法，我们把调换顺序看作平移相同距离，这样每个元素在变化上与等价的条件相应，即
\[
f_(a,\ b,\ c)\rightarrow
\begin{cases}
(a+(b-a),\ b+(b-a),\ c),\ b-a<c-b\\\\
(a-(b-a),\ b-(b-a),\ c)\\\\
(a,\ b-(c-b),\ c-(c-b)),\ b-a>c-b\\\\
(a,\ b+(c-b),\ c+(c-b))
\end{cases}
\]
显然 \((a,\ b,\ c)\) 的变化不超过
\(3\)
我们考虑按照这种关系建树，发现以 \((A,\ B,\
C)\) 其中 \(B-A=C-B\)
时恰好为树的形态且还是一颗二叉树，那么答案就是树上两点的距离
其次答案具有单调性，所以先调整到同一高度，在二分向上跳的距离判断是否相等即可
在向上跳的过程中可以一下跳多步，用距离除一下贪心即可
或者按照这样理解
设 \(g(n,\ m)\) 其中 \(n=b-a,\ m=c-b\)
那么向上跳是一个更相减损的过程，用辗转相除优化即可，这也是 [CQOI2017]
小Q的表格 最关键的一步
还有一些细节，在注释里标注
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <queue>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int INF = 0x3f3f3f3f;
struct Node
{
int p[3];
int operator [] (const int x) { return p[x]; }
bool operator == (const Node &_) const
{
return p[0]==_.p[0]&&p[1]==_.p[1]&&p[2]==_.p[2];
}
bool operator != (const Node &_) const
{
return !(p[0]==_.p[0]&&p[1]==_.p[1]&&p[2]==_.p[2]);
}
Node(int x = 0, int y = 0, int z = 0)
{
p[0] = x, p[1] = y, p[2] = z;
sort(p, p+3);
}
}s, t;
int ds, dt, ans, buf;
Node get(Node p, int up, int &d)
{
int a = p[1]-p[0], b = p[2]-p[1], c;
if(!up||a == b) return p;
if(a < b) c = min(up, (b-1)/a), p = Node(p[0]+c*a, p[1]+c*a, p[2]);
else c = min(up, (a-1)/b), p = Node(p[0], p[1]-c*b, p[2]-c*b);
d += c; up -= c;
return get(p, up, d);
}
int main()
{
freopen("throw.in", "r", stdin);
freopen("throw.out", "w", stdout);
s = Node(read(), read(), read());
t = Node(read(), read(), read());
if(get(s, INF, ds) != get(t, INF, dt)) puts("NO");
else
{
puts("YES");
if(ds < dt) swap(s, t), swap(ds, dt);
int l = 0, r = dt; s = get(s, ds-dt, buf);
while(l <= r)
{
int mid = (l+r)>>1;
if(get(s, mid, buf) == get(t, mid, buf)) ans = mid, r = mid-1;
else l = mid+1;
}
printf("%d\n", ans*2+ds-dt);
}
return 0;
}
|