开始有时间改正NOIp2017的题目了，在这篇文章中，简单写一下题解。题意和我在比赛时的原始代码见游记。
小凯的疑惑(math)
没什么可说的了，以后再证明吧。
1
2
3
4
5
6
7
8
9
10
11
#include <fstream>
using namespace std;
ifstream fin("math.in");
ofstream fout("math.out");
int main()
{
int a, b;
fin >> a >> b;
fout << 1ll * a * b - a - b << endl;
return 0;
}
时间复杂度(complexity)
参见游记。
逛公园(park)
很多人都会做这题，然而我并不会，参考了洛谷的题解。这就是day1的DP，不过比较简单。对于SSSP，我偏好Dijkstra而不是SPFA，因为我出过卡SPFA的题。不过这题并不卡SPFA。
$K=0$
$K=0$时就是$1->N$的最短路计数，与最优化问题DP计数一样。设$d[u]$为$1->u$的最短路，$dp[u]$表示$1->u$的最短路数，则有
无0权边
因为$K\le50$，可以设计$dp[u][k]$表示$1->u$比$d$多走了$k$的路径数，则有
注意到达$N$后可能可以绕一圈再回去。
有0权边
显然，如果在$d+K$内经过一个0权环，就有无穷多条路径，只要在DP时发现有重复直接返回即可。
然而这样复杂度并不对，DP可能是$\mathcal O(NMK)$的。需要反向最短路$rd$，当$d[u]+k+w_{u,v}+rd[v]>d+K$时剪枝。这样时间复杂度应该为$\mathcal O(M\log M+MK)$。
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
#include <fstream>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
ifstream fin("park.in");
ofstream fout("park.out");
const int N = 100005, M = 200005, K = 51, INF = 0x3f3f3f3f;
int n, m, k, mod, f[N][K];
typedef pair<int, int> state;
struct graph
{
int head[N], v[M], w[M], nxt[M], e, d[N];
bool vis[N];
void reset()
{
fill(head + 1, head + n + 1, 0);
e = 0;
}
void insert(int u, int v, int w)
{
graph::v[++e] = v;
graph::w[e] = w;
nxt[e] = head[u];
head[u] = e;
}
void dijkstra(int s)
{
fill(vis + 1, vis + n + 1, false);
fill(d + 1, d + n + 1, INF);
d[s] = 0;
priority_queue<state, vector<state>, greater<state> > Q;
Q.push(make_pair(0, s));
while (!Q.empty())
{
state k = Q.top();
Q.pop();
if (vis[k.second])
continue;
vis[k.second] = true;
for (int i = head[k.second]; i; i = nxt[i])
if (d[k.second] + w[i] < d[v[i]])
Q.push(make_pair(d[v[i]] = d[k.second] + w[i], v[i]));
}
}
} mat, rmat;
bool vis[N][K];
int dp(int u, int k)
{
if (vis[u][k])
return INF;
if (~f[u][k])
return f[u][k];
vis[u][k] = true;
f[u][k] = u == n;
for (int i = mat.head[u]; i; i = mat.nxt[i])
{
int nk = mat.d[u] + k + mat.w[i] - mat.d[mat.v[i]];
if (nk <= ::k && mat.d[u] + k + mat.w[i] + rmat.d[mat.v[i]] <= mat.d[n] + ::k)
{
int ret = dp(mat.v[i], nk);
if (ret == INF)
return INF;
(f[u][k] += ret) %= mod;
}
}
vis[u][k] = false;
return f[u][k];
}
int main()
{
int t;
fin >> t;
while (t--)
{
fin >> n >> m >> k >> mod;
mat.reset();
rmat.reset();
while (m--)
{
int u, v, w;
fin >> u >> v >> w;
mat.insert(u, v, w);
rmat.insert(v, u, w);
}
mat.dijkstra(1);
rmat.dijkstra(n);
fill_n(&f[0][0], sizeof(f) / sizeof(int), -1);
fill_n(&vis[0][0], sizeof(vis) / sizeof(bool), false);
int ans = dp(1, 0);
if (ans == INF)
fout << -1 << endl;
else
fout << ans << endl;
}
return 0;
}
std::vector被卡常我也无语了，比赛尤其不要用STL。
奶酪(cheese)
修改了判断条件，可以通过原来的数据范围。
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
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("cheese.in");
ofstream fout("cheese.out");
const int N = 1005;
int x[N], y[N], z[N];
bool vis[N];
inline long long sqr(long long x)
{
return x * x;
}
int main()
{
int t;
fin >> t;
while (t--)
{
int n, h, r;
fin >> n >> h >> r;
queue<int> Q;
for (int i = 1; i <= n; i++)
{
fin >> x[i] >> y[i] >> z[i];
if (abs(z[i]) <= r)
{
vis[i] = true;
Q.push(i);
}
else
vis[i] = false;
}
while (!Q.empty())
{
int k = Q.front();
Q.pop();
for (int j = 1; j <= n; j++)
if (!vis[j] && sqr(x[k] - x[j]) + sqr(y[k] - y[j]) <= 4 * sqr(r) - sqr(z[k] - z[j]))
{
vis[j] = true;
Q.push(j);
}
}
bool ans = false;
for (int i = 1; i <= n; i++)
if (vis[i] && abs(z[i] - h) <= r)
{
ans = true;
break;
}
if (ans)
fout << "Yes\n";
else
fout << "No\n";
}
return 0;
}
宝藏(treasure)
突然发现比赛时的想法只要记忆化一下就可以变成状压DP了。原来的d[]数组其实就是二进制状态，转移时直接暴力复制就可以了。
具体的，令$dist[u][v]$为$u->v$的边权，$dp[i][S],i\in S$表示以$i$为根节点，可到达的点集为$S$的最小花费，$d[i][S][u],i\in S$表示在最小花费下$i->u$的边数，则有
其中$d$可以在DP转移时同时$\mathcal O(n)$转移。时间复杂度$\mathcal O(2^n n^4)$，比我知道的最优的$\mathcal O(2^n n^3)$差一点，但也不错了。空间复杂度$\mathcal O(2^n n)$。
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
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("treasure.in");
ofstream fout("treasure.out");
const int N = 12, INF = 1e9;
int mat[N][N], f[1 << N], d[1 << N][N];
int main()
{
int n, m;
fin >> n >> m;
while (m--)
{
int u, v, w;
fin >> u >> v >> w;
u--;
v--;
if (!mat[u][v] || w < mat[u][v])
mat[u][v] = mat[v][u] = w;
}
int ans = INF;
for (int i = 0; i < n; i++)
{
fill(f, f + (1 << n), INF);
f[1 << i] = 0;
for (int j = 0; j < n; j++)
d[1 << i][j] = i == j ? 0 : INF;
for (int j = 0; j < (1 << n) - 1; j++)
for (int k = 0; k < n; k++)
if (j & (1 << k))
for (int v = 0; v < n; v++)
if (mat[k][v] && d[j][v] == INF && f[j] + (d[j][k] + 1) * mat[k][v] < f[j | (1 << v)])
{
f[j | (1 << v)] = f[j] + (d[j][k] + 1) * mat[k][v];
for (int u = 0; u < n; u++)
d[j | (1 << v)][u] = u == v ? d[j][k] + 1 : d[j][u];
}
ans = min(ans, f[(1 << n) - 1]);
}
fout << ans << endl;
return 0;
}
队列(phalanx)
其实比赛时的思路已经很接近正解了，只是我懒得想也不敢写。$n$行都维护一颗线段树，还有最后一列。一个问题是空间，但只要动态开点线段树，单次操作空间复杂度就是$\log n$级别的，完全可以。另一个问题是初始的编号，这也是比赛时我认为不可做的主要原因，现在想起来其实只要根据坐标就可以算出初始编号，思想与50%的数据类似。接下来只剩下一些细节问题，我调了不少时间，代码可能比较繁杂。事实证明，线段树并不会被卡常，至少在本地和洛谷。
时间复杂度$\mathcal O(q\log (n+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
64
65
66
67
68
69
70
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("phalanx.in");
ofstream fout("phalanx.out");
const int N = 300005, L = 12e6;
struct node
{
int sum, ls, rs;
} tree[L];
int cc, root[N], last;
vector<long long> mat[N], ml;
int query(int id, int l, int r, int x)
{
if (l == r)
return l;
int mid = (l + r) / 2;
if (mid - tree[tree[id].ls].sum >= x)
return query(tree[id].ls, l, mid, x);
return query(tree[id].rs, mid + 1, r, x + tree[tree[id].ls].sum);
}
void modify(int &id, int l, int r, int x)
{
if (!id)
id = ++cc;
if (l == r)
tree[id].sum++;
else
{
int mid = (l + r) / 2;
if (x <= mid)
modify(tree[id].ls, l, mid, x);
else
modify(tree[id].rs, mid + 1, r, x);
tree[id].sum = tree[tree[id].ls].sum + tree[tree[id].rs].sum;
}
}
int main()
{
int n, m, q;
fin >> n >> m >> q;
for (int i = 1; i <= n; i++)
mat[i].push_back(1ll * i * m);
ml.push_back(1ll * n * m);
int r = max(n, m) + q;
while (q--)
{
int x, y;
fin >> x >> y;
long long tmp = query(last, 1, r, x);
if (tmp <= n)
tmp = 1ll * tmp * m;
else
tmp = ml[tmp - n];
if (m + mat[x].size() - 1 - tree[root[x]].sum == m)
modify(root[x], 1, r, m + mat[x].size() - 1);
mat[x].push_back(tmp);
long long num = query(root[x], 1, r, y);
modify(root[x], 1, r, num);
if (num <= m)
num = 1ll * (x - 1) * m + num;
else
num = mat[x][num - m];
modify(last, 1, r, query(last, 1, r, x));
ml.push_back(num);
fout << num << '\n';
}
return 0;
}
终于断断续续的写完了这篇文章，从12/2创建到12/26完工。