[题解] 2018-4-5学习

https://www.luogu.org/problemnew/show/P1879

运算符优先级害死人…

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
#include <bits/stdc++.h>

using namespace std;

namespace CORNFIELDS
{
const int maxn = 12;
int m, n, a[maxn + 1][maxn], l[maxn + 1], f[maxn + 1][1 << maxn];
vector<int> p;

inline void solve()
{
cin >> m >> n;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
cin >> a[i][j];

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if(a[i][j]) l[i] |= (1 << j);

for (int i = 0; i < (1 << n); ++i)
{
bool flag = true;
for (int j = 0; j < n - 1; ++j)
if(i & (1 << j) && i & (1 << j + 1)) flag = false, j = n;
if(flag) p.push_back(i);
}

for (int j = 0; j < (1 << n); ++j) f[0][j] = 1;

for (int i = 0; i < m; ++i)
for (int j = 0; j < p.size(); ++j)
if((l[i] & p[j]) == p[j])
for (int k = 0; k < p.size(); ++k)
if(((l[i + 1] & p[k]) == p[k]) && ((p[k] & p[j]) == 0))
f[i + 1][p[k]] = (f[i + 1][p[k]] + f[i][p[j]]) % 100000000;
int ans = 0;
for (int i = 0; i < (1 << n); ++i) {
ans = (ans + f[m][i]) % 100000000;
}
cout << ans << endl;
}
}

int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
CORNFIELDS::solve();
return 0;
}

[学习笔记] 一点SPFA的随笔

oi

一点SPFA的随笔

大佬勿喷orz…都是些很基础的东西,因为我太菜了

  1. SPFA有一个$O(m\log{n})$的堆优化策略(见魔法猪学院),而且代码很短,应该卡的没那么严重。
  2. SPFA(bfs)可以解决很大一部分状压DP的问题(见软件补丁问题、愤怒的小鸟(需要Ofast优化过)),虽然速度会慢很多,作为下策吧..应该可以骗一半以上的分。
  3. SPFA支持动态加点(详见Poq的魔法森林解法),如果能够可持久化d数组会很爽。
  4. SPFA的queue支持定制,queue中装的是转移,可以当成dp来思考(详见FULL TANK?)(可以解决k短路,k步最短路等等问题(虽然效率不行))(详见魔法猪学院配合A*,还有一个k步最短路的用矩阵快速幂解的?)