CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
现役选手凑不够人手来参加这个比赛，于是退役老人家又给抓回来了，感觉手生了好多啊…最后在校内排 3/10，华南赛区 4/98（Au），总榜 67/1016（Ag）。中大排团体第五名，也是最近几年最好成绩。
办签证
让我看看是谁连个 dijstra 都敲 RE 了…是我啊，那没事了。一开始想先拿个三十分保底，结果敲得 dij 就只有二十分，无奈又重新敲了 SPFA。
拿三十分的做法是，对每个城市建立入点和出点共 $2\times\lvert V\rvert$ 个顶点（因为是要求一个折返），入点到入点、出点到出点两个子图分别按照题目要求连边，并在使领馆所在城市 $U$ 的入点和出点连上不延误概率为 $1$、路费为 $c_\mathrm{visa}(v)$ 的边。然后把概率的对数看成边长跑最短路就行了，这样能过预算限制不产生实际作用的测试集 1。
然后突然发现可以把每个点继续分层，拆成 $C+1$ 个顶点来代表到达这个顶点之后手上剩余钱的数量，这样做能拿四十分，其他测试点出现 MLE 的情况。
在这一点的基础上，发现上一步很多边都是重复的，于是建图的时候对于同一个点的 $C+1$ 个顶点只连一条边，在图上遍历的时候再去计算实际遍历的边（注意要区分 $U$ 集合入点出点的边），这样就有七十分了，剩下测试点是 TLE。
赛场上不确定是自己建图复杂了还是滥用 STL 导致常数大，于是就没接着做了。赛后问了下边上的谭大爷，这个建图方法其实就可以拿满分了，只不过他是用 dij 的。怎么说还是自己太菜了吧，连个 dij 都敲不对，差一点拿到总榜 Au 还是有点可惜。
赛场代码到处打补丁，特别糙，将就着看看吧。
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//202012100981
//http://c.csp.thusaac.com
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef double ll;
typedef long long lld;
struct Graph
{
struct Vertex
{
vector<int> o;
};
struct Edge
{
int first, second;
ll len;
lld cvisa;
};
vector<Vertex> v; //点集
vector<Edge> e; //边集
Graph(int n) : v(n) {}
void add(const Edge &ed)
{
if (ed.first == ed.second)
return; //如果有需要请拆点
v[ed.first].o.push_back(e.size());
e.push_back(ed);
}
};
struct BellmanFord : Graph
{
int M;
vector<ll> d, visa;
vector<int> pp;
BellmanFord(int n) : Graph(n) {}
bool ask(int s)
{
d.assign(v.size(), -1);
visa.assign(v.size(), 0);
pp.assign(v.size(), -1);
d[s] = 1;
vector<int> cnt(v.size(), 0), flag(v.size(), 0);
for (deque<int> q(cnt[s] = flag[s] = 1, s); !q.empty(); q.pop_front())
{
for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u % M].o.size(); ++i)
if (k = v[u % M].o[i], u / M >= e[k].cvisa && e[k].cvisa)
if (to = e[k].cvisa ? e[k].second % M + (u / M - e[k].cvisa) * M : e[k].second,
d[to] < d[u] * e[k].len)
{
d[to] = d[u] * e[k].len, visa[to] = e[k].cvisa, pp[to] = u;
if (!flag[to])
{
if (v.size() == ++cnt[to])
return 0;
flag[to] = 1, q.push_back(to);
}
}
for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].o.size(); ++i)
if (k = v[u].o[i], to = e[k].second,
e[k].cvisa == 0 && d[to] < d[u] * e[k].len)
{
d[to] = d[u] * e[k].len, visa[to] = e[k].cvisa, pp[to] = u;
if (!flag[to])
{
if (v.size() == ++cnt[to])
return 0;
flag[to] = 1, q.push_back(to);
}
}
}
return 1;
}
};
int main()
{
int v, u, e, c;
scanf("%d%d%d%d", &v, &u, &e, &c);
BellmanFord g((c + 1) * (v << 1));
g.M = v << 1;
for (int i = 1; i <= u; ++i)
{
lld cvisa;
scanf("%lld", &cvisa);
g.add({i, i + v, 1.0, cvisa});
}
for (int i = 1; i <= e; ++i)
{
BellmanFord::Edge edge, ed;
scanf("%d%d%lf%lld", &edge.first, &edge.second, &edge.len, &edge.cvisa);
for (int j = 0; j <= 0; ++j)
{
ed = edge;
ed.len = 1 - ed.len;
g.add(ed);
ed.first += v;
ed.second += v;
g.add(ed);
}
}
for (int j = 1; j <= c; ++j)
{
g.add({j * (v << 1) + v, v, 1.0, 0});
}
g.ask(c * (v << 1));
vector<int> ans;
lld cvisa = 0;
for (int i = v; i >= 0; cvisa += g.visa[i], i = g.pp[i])
ans.push_back(i % v);
while (!ans.empty() && ans.back() == 0)
ans.pop_back();
ans.push_back(0);
reverse(ans.begin(), ans.end());
while (!ans.empty() && ans.back() == 0)
ans.pop_back();
ans.push_back(0);
for (int i = 1; i < ans.size(); ++i)
{
if (ans[i - 1] == ans[i])
{
printf("%d\n", ans[i]);
ans.erase(ans.begin() + i, ans.begin() + i + 1);
break;
}
}
printf("%lld\n", cvisa);
printf("%.9f\n", 1 - g.d[v]);
for (int i = 0; i < ans.size(); ++i)
printf("%d ", ans[i]);
printf("\n");
}
给他文件系统
看着梁大爷谭大爷在边上神仙打架实在不想继续做了 TAT
用 map 就能轻松水 60 分了…通宵熬夜之后真心不想敲可持久化数据结构了嘿嘿。
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
100
101
//202012100981
//http://c.csp.thusaac.com
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef double ll;
typedef long long lld;
const int NN = (2 << 20) + 9, MM = 255;
char s[NN], op[MM], filename[MM], cmtname[MM], mergee[MM];
int n;
map<string, string> mp;
map<string, map<string, string>> history;
int zzq_empty = 1;
int main()
{
scanf("%d", &n);
fgets(s, NN, stdin);
for (; n--;)
{
fgets(s, NN, stdin);
sscanf(s, "%s", op);
if (!strcmp(op, "write"))
{
int offset, len;
sscanf(s, "%s%s%d%d", op, filename, &offset, &len);
fgets(s, NN, stdin);
string &str = mp[filename];
if (str.size() < offset + len)
str.resize(offset + len, '.');
copy(s, s + len, str.begin() + offset);
zzq_empty = 0;
}
else if (!strcmp(op, "read"))
{
int offset, len;
sscanf(s, "%s%s%d%d", op, filename, &offset, &len);
if (!mp.count(filename))
{
for (int i = 0; i < len; ++i)
printf(".");
printf("\n");
continue;
}
string &str = mp[filename];
if (str.size() < offset)
{
for (int i = 0; i < len; ++i)
printf(".");
printf("\n");
continue;
}
if (str.size() < offset + len)
{
for (int i = offset; i < str.size(); ++i)
printf("%c", str[i]);
for (int i = str.size() - offset; i < len; ++i)
printf(".");
printf("\n");
continue;
}
for (int i = 0; i < len; ++i)
printf("%c", str[offset + i]);
printf("\n");
}
else if (!strcmp(op, "ls"))
{
if (mp.empty())
{
printf("0\n");
continue;
}
printf("%d %s %s\n", (int)mp.size(), mp.begin()->first.c_str(), mp.rbegin()->first.c_str());
}
else if (!strcmp(op, "unlink"))
{
sscanf(s, "%s%s", op, filename);
mp.erase(filename);
zzq_empty = 0;
}
else if (!strcmp(op, "commit"))
{
sscanf(s, "%s%s", op, cmtname);
if (zzq_empty || history.count(cmtname))
continue;
//history[cmtname] = mp;
}
else if (!strcmp(op, "checkout"))
{
sscanf(s, "%s%s", op, cmtname);
if (!zzq_empty || !history.count(cmtname))
continue;
//mp = history[cmtname];
}
else if (!strcmp(op, "merge"))
{
sscanf(s, "%s%s%s", op, mergee, cmtname);
if (!zzq_empty)
continue;
}
}
}
垃圾回收器
这一题题目很有意思，可以开多线程，本身也是和高性能计算有一点点相关的题目，感觉自己可以做，只是在最短路上浪费了三四个小时还是很亏。