打地鼠-竞赛图-糖果-树
T1 打地鼠
过水，考场上有一车人切掉
T2 竞赛图
状压思想的神仙题目，通过不断消去最后以为的方式去枚举子集
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
|
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 16777217;
template<typename type>
type read() {
type s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int lowbit(int x) {
return x & (-x);
}
bool vis[maxn];
int m[maxn];
int n;
int main() {
int t;
t = read<int>();
while (t--) {
Set(m, 0);
Set(vis, 1);
int n;
n = read<int>();
For(i, 1, n) {
For(j, 1, n) {
int x;
x = read<int>();
if (x) {
m[(1 << (i - 1))] |= (1 << (j - 1));
}
}
}
int maxs = (1 << n) - 1;
m[0] = maxs;
For(state, 1, maxs) {
m[state] = m[state ^ lowbit(state)] & m[lowbit(state)];
}
For(state, 1, maxs) {
if (vis[state]) {
for (int j = m[state]; j; j = (j - 1) & m[state]) {
vis[state | j] = 0;
}
}
}
int ans = 0;
For(state, 0, maxs) {
if (vis[state]) {
ans++;
}
}
cout << ans << endl;
}
return 0;
}
|
T3 糖果
神仙dp题
在小A和小B选数的过程中，限制有：小A和小B不能选到同一个数。对于某一个数，小A和小B经过时都没有选它，那么它之前必然已经被小C选过了。因此可以使用dp[i][j][k]表示在某一轮，小A选了第i个位置上的数，小B选了第j个位置上的数，还有k的不确定的位置（小C）因为i和j两维可以分开转移转移只需枚举i和j，若i(j) + 1位置上的数已经被选了，就换一维转移。
一些转移的细节：
转移i时：
如果当前的数a[i]在b中的位置小于j，即被选过了， 就把它删掉，状态给下一个位置
如果k不等于0，就确定下来一个k
转移j时同理
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
88
89
90
91
92
93
94
95
96
97
98
99
|
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 410;
const long long mod = 1e9 + 7;
template<typename rsp5u>
rsp5u read() {
rsp5u s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
long long min(long long a, long long b) {
return (a < b) ? a : b;
}
long long dp1[maxn][maxn][maxn], dp2[maxn][maxn][maxn];
long long a[maxn], b[maxn];
long long posa[maxn], posb[maxn];
long long n;
int32_t main() {
n = read<long long>();
long long n3 = n / 3;
long long ans = 0;
For(i, 1, n) {
long long in;
a[i] = read<long long>();
posa[a[i]] = i;
}
For(i, 1, n) {
long long in;
b[i] = read<long long>();
posb[b[i]] = i;
}
dp1[1][1][0] = 1;
For(i, 1, n + 1) {
For(j, 1, n + 1) {
For(k, 0, n / 3) {
if (dp1[i][j][k]) {
//cout << dp1[i][j][k] << " |1 "<< ' ' << i << ' ' << j << ' ' << k << endl;
if (i != n + 1) {
if (posb[a[i]] < j) { // deleted
dp1[i + 1][j][k] += dp1[i][j][k];
dp1[i + 1][j][k] %= mod;
} else {
if (k) {
dp1[i + 1][j][k - 1] += dp1[i][j][k] * k;
dp1[i + 1][j][k - 1] %= mod;
}
dp2[i][j][k] += dp1[i][j][k];
dp2[i][j][k] %= mod;
}
} else {
if (k == 0) {
ans += dp1[i][j][0];
ans %= mod;
}
}
}
if (dp2[i][j][k]) {
//cout << dp2[i][j][k] << " |2 "<< ' ' << i << ' ' << j << ' ' << k << endl;
if (posa[b[j]] < i) { // deleted
dp2[i][j + 1][k] += dp2[i][j][k];
dp2[i][j + 1][k] %= mod;
} else {
if (a[i] != b[j]) {
if (k) {
dp2[i][j + 1][k - 1] += dp2[i][j][k] * k;
dp2[i][j + 1][k - 1] %= mod;
}
dp1[i + 1][j + 1][k + 1] += dp2[i][j][k];
dp1[i + 1][j + 1][k + 1] %= mod;
}
}
}
}
}
}
ans %= mod;
For(i, 1, n3) {
ans = ans * (3 * i -1) * (3 * i - 2);
ans %= mod;
}
cout << ans << endl;
return 0;
}
`
|