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 还是有点可惜。
赛场代码到处打补丁，特别糙，将就着看看吧。
//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 分了…通宵熬夜之后真心不想敲可持久化数据结构了嘿嘿。
//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;
}
}
}
垃圾回收器
这一题题目很有意思，可以开多线程，本身也是和高性能计算有一点点相关的题目，感觉自己可以做，只是在最短路上浪费了三四个小时还是很亏。