曾经做过的一些小水题, 总之我是不会做.
这是第2篇.
TCO 2014 Wildcard Round
解题口胡报告.
275
假如有两个$[0,2^n-1]$的排列 $p$ 和 $q$ , 还有一个01矩阵. 矩阵的格子$(i,j)$的值取决于$p_i\,\,AND\,\,q_j$ 是否非0.
现在给你一个矩阵, 问是否存在一种方案能构造这幅画.
orz jcvb.
首先找到每个2的幂次在哪一行(当然列也可以). 特征是这一行有$2^{n-1}$个1.
然后我们就可以对于二的幂次根据每一列在这些行的01状态计算出每一列的值了. 这期间发现不合法就判掉了.
然后再计算出每一行的值, 判掉不合法情况.
AndPicture.cpp:
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
| #include <bits/stdc++.h>
using namespace std;
int bit[10], ptr;
int mp[100], use[100], mtr[100][100];
int col[100], mp2[100], row[100];
class AndPicture {
public:
inline int checkLine(vector<string>::iterator Line) {
int Count = 0;
for (string::iterator ch = Line->begin(); ch != Line->end(); ++ch) {
if ((*ch) == '1') Count++;
}
return Count;
}
string isPossible(int n, vector<string> picture) {
int idx = 0;
for (vector<string>::iterator Line = picture.begin(); Line != picture.end(); ++Line) {
idx++;
if (checkLine(Line) == (1 << (n - 1))) {
bit[ptr] = 1;
mp[idx] = (1 << ptr);
ptr++;
}
for (int i = 0; i < (1 << n); ++i) {
mtr[idx][i + 1] = (Line->at(i) == '1');
}
}
if (ptr != n) return string("Impossible");
for (int j = 1; j <= (1 << n); ++j) {
int bitcount = 0;
for (int i = 1; i <= (1 << n); ++i) {
if (mp[i] && mtr[i][j]) col[j] |= mp[i], bitcount++;
}
if (use[col[j]]) return string("Impossible");
else use[col[j]] = 1;
if (bitcount == 1)
mp2[j] = col[j];
}
memset(use, 0, sizeof use);
for (int i = 1; i <= (1 << n); ++i) {
if (mp[i]) {
if (use[mp[i]]) return string("Impossible");
else use[mp[i]] = 1;
continue;
}
for (int j = 1; j <= (1 << n); ++j) {
if (mp2[j] && mtr[i][j]) row[i] |= mp2[j];
}
if (use[row[i]]) return string("Impossible");
else use[row[i]] = 1;
}
for (int i = 1; i <= (1 << n); ++i)
for (int j = 1; j <= (1 << n); ++j) {
if (bool(row[i] & col[j]) != bool(mtr[i][j])) return string("Impossible");
}
return string("Possible");
}
};
|
750
一个$n \times m$矩阵的每个格子, 可以选$[1,c]$的一个整数, 求有多少种方案使得任意两行之间, 任意两列之间都不相同. $n \le 5000$.
先不考虑列. 只让每行都不同, 有$n! {c^{m} \choose n}$种方案. 这样列上就有至多$m$种, 至少1种等价类. 下面考虑把等价类限制在$m$.
如果我们记至多$i$类为$f_i$, 恰好为$g_i$, 那么我们有$f_i = \sum_{j=1}^{i}{S(i,j)g_j}$, $S$是第二类斯特林数, 对应把$i$个物品分为$j$个集合的方案数.
因为$S(i,i)=1$, 移项得$g_i = f_i - \sum_{j = 1}^{i - 1}S(i,j)g_j$. 这可以$O(n^2)$做的. $f$就是下降幂.
CountTables.cpp:
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e+9 + 7;
const int maxn = 5005;
ll s[maxn][maxn], f[maxn], g[maxn];
class CountTables {
public:
void init() {
s[1][1] = 1;
for (int i = 2; i <= 4000; ++i) {
s[i][1] = s[i][i] = 1;
for (int j = 2; j < i; ++j)
s[i][j] = (s[i - 1][j - 1] + 1ll * s[i - 1][j] * j % mod) % mod;
}
}
inline ll quick_power(ll base, ll index) {
ll ret = 1;
while (index) {
if (index & 1) ret = ret * base % mod;
base = base * base % mod;
index >>= 1;
}
return ret;
}
int howMany(int N, int M, int C) {
init();
for (int i = 1; i <= M; ++i) {
ll bgn = quick_power(C, i), minus = 0;
ll ret = bgn;
for (int j = 2; j <= N; ++j) {
minus--;
ret = (ret * ((bgn + minus + mod) % mod)) % mod;
}
f[i] = ret;
}
for (int i = 1; i <= M; ++i) {
g[i] = f[i];
for (int j = 1; j < i; ++j) {
g[i] = (g[i] - s[i][j] * g[j] % mod + mod) % mod;
}
}
return g[M];
}
};
|
1100
一个矩阵, 有些地方是坏点. 给你开始坐标和目的坐标, 一开始有$E$点能量. 每次你可以选择原地不动耗费一点能量, 或者向四个方向跳当前能量的距离.
问能否到达目的坐标.
不想写了把每个点拆成四个点, 可以向四个方向转移. 然后按能量做分层BFS, 求到达每个点的剩余最大能量.
