2020 CCF CCSP竞赛(含分赛区竞赛) wu-kan

现役选手凑不够人手来参加这个比赛,于是退役老人家又给抓回来了,感觉手生了好多啊…最后在校内排 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;
        }
    }
}

垃圾回收器

这一题题目很有意思,可以开多线程,本身也是和高性能计算有一点点相关的题目,感觉自己可以做,只是在最短路上浪费了三四个小时还是很亏。