【题解】【LGR-(-15) 】SCP 2022 第一轮（初赛 S 组）模拟

wsyhb · 2022-08-23 18:24:28 · 个人记录

前言

（2022.8.28）

NOI 已经结束了，快来做初赛题吧~（大雾）

历经将近一周的打磨，这篇题解终于公开了。

最初天真地以为当天就能写完……

（2022.8.23）

原本计划着今天上午准时参加的，没想到竟完全忘了……

中午和下午花了点时间做了一遍，然后对了答案，只有 89 分。

当然实际参赛的话分会更低，因为比赛时长也就 2 h，而我做了……

话说回来我为什么错了整整四道单选啊！！！（抓狂）

和去年的那篇题解不同，这篇题解更多的是一些吐槽，实质性内容很少。

UPD（2022.8.28）：写完发现内容还是挺丰厚的。

想要复习初赛的可以去这里看看，文章包含去年初赛模拟的解析。

写了也是白写，反正肯定不会有人仔细去读的。

初赛越来越难，我该怎么办……这模拟赛给我一种连 CSP 第一轮都过不了的不祥预感……

话说你谷把初赛模拟出这么难是不是想骗大家去报初赛课程啊？

最后祝各位 CSP2022 第一轮 RP++！

正文

比赛地址：【LGR-(-15) 】SCP 2022 第一轮（初赛 S 组）模拟。

题面及答案下载地址：题面；答案。

一、单项选择题

由于是 8 进制，所以最好先转 2 进制，再转其它进制。

由于是单选题，所以根本没有必要去计算 B 选项。（应该不会有人想去算 5 进制吧）

- $6 \times 2+4 \times 8+1 \times 19+5 \times 19+2 \times 3+6 \times 5=194$
- $6 \times 2+4 \times 8+5 \times 15+1 \times 19+3 \times 3+2 \times 5=157$
- $6 \times 2+4 \times 8+5 \times 15+3 \times 3+1 \times 3+6 \times 5=161$
- $6 \times 2+4 \times 8+5 \times 15+3 \times 3+6 \times 10+1 \times 5=193$

P.S. 最好把骰子每一步的状态都在草稿纸上写清楚，不然很容易算错。

P.S. 即使你像我一样没读懂代码，第 1,2,3,5 题仍然是可做的。

闲话

即使没读懂也能猜对第 6 题，不是吗？

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 309;
const int MAXM = 109;
const int MAXP = 100000;
typedef long long ll;
int n, m, seed,rt,btm,s[MAXM],Len,dfncnt,full_dist,P,t;
int lg[MAXN],dfn[MAXN],fa[MAXN],dep[MAXN], lson[MAXN];
vector <int> e[MAXN];
vector <int> L[MAXM],leaves;
int F[MAXM];
namespace LCA {
    int st[24][MAXN];
    int minNode(int x, int y) {
        return dep[x] < dep[y] ? x : y;
    }
    void init() {
        for (int i = 1; i <= n; ++i) st[0][dfn[i]]=fa[i];
        for (int i = 1; i <= lg[n]; ++i)
            for (int j = 1; j + (1 << i) - 1 <= n; ++j)
                st[i][j] = minNode(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }
    int lca(int u, int v) {
        if (u == v) return u;
        if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
        int d = lg[v - u++];
        return minNode(st[d][u], st[d][v - (1 << d) + 1]);
    }
}
namespace Gen {
    mt19937 rnd;
    int pos[MAXN], deg[MAXN];
    vector <pair<int, int>> edges;
    void calc() {
        for (int i = 1; i <= n - 2; ++i)
            ++deg[pos[i]];
        set <int> ret;
        ret.clear();
        for (int i = 1; i <= n; ++i)
            if (deg[i] == 1) ret.insert(i);
        for (int i = 1; i <= n - 2; ++i) {
            int npos = *ret.begin();
            edges.push_back(make_pair(npos, pos[i]));
            ret.erase(ret.begin());
            --deg[pos[i]];
            if (deg[pos[i]] == 1)
                ret.insert(pos[i]);
        }
        edges.push_back(make_pair(*ret.begin(), n));
    }
    void build() {
        for (auto i : edges) {
            int u = i.first, v = i.second;
            e[u].push_back(v);
            e[v].push_back(u);
        }
    }
    void generate(int seed) {
        rnd.seed(seed);
        edges.clear();
        for (int i = 1; i <= n; ++i) deg[i] = 1;
        for (int i = 1; i <= n - 2; ++i)
            pos[i] = rnd() % n + 1;
        calc();
        build();
    }
}
int dfs(int u, int _fa, int &bottom) {
    dfn[u] = ++dfncnt;
    if (e[u].size() == 1) leaves.push_back(u);
    lson[u] = -1;
    fa[u] = _fa;
    dep[u] = dep[_fa] + 1;
    int maxlen = 0, dson = u, temp;
    for (int v: e[u])
        if (v != _fa) {
            int p = dfs(v,u,temp);
            if (p > maxlen) maxlen = p, lson[u]=v, dson=temp;
        }
    bottom = dson;
    return maxlen + 1;
}
#define dist(u, v) (dep[u]+dep[v]-2*dep[LCA::lca(u, v)])
int v[MAXP+9], prime[MAXP + 9], prime_cnt, vis[MAXP+9];
void prime_init(int n) {
    prime_cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (!v[i]) prime[++prime_cnt] = v[i] = i;
        for(int j=1; j <= prime_cnt && i*prime[j]<=n; ++j) {
            if (v[i] < prime[j]) break;
            v[i * prime[j]] = prime[j];
        }
    }
}
vector<int> answer, gline;
void solve() {
    cin >> n >> m >> seed >> t;
    lg[0] = lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) e[i].clear();
    leaves.clear();
    if (!t) Gen::generate(seed);
    else {
        for (int i = 1, u, v; i < n; ++i) {
            cin >> u >> v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
    }
    dep[0] = 0;
    dfs(1, 0, rt);
    dfncnt=0;
    leaves.clear();
    Len = dfs(rt, 0, btm);
    LCA::init();
    for (int k = rt; ~k; k = lson[k]) gline.push_back(k);
    for (int i = 1, tmp; i <= m; ++i) {
        {
            cin >> s[i];
            L[i].clear();
            for(int j = 1; j <= s[i]; ++j) {
                cin >> tmp;
                L[i].push_back(tmp);
            }
            F[i] = dist(L[i].front(), L[i].back());
            for (unsigned j = 0; j < L[i].size() - 1; ++j)
                F[i] += dist(L[i][j], L[i][j + 1]);
            int tmp = F[i] >> 1;
            while (tmp > 1) vis[v[tmp]] = 1, tmp /= v[tmp];
        }
        full_dist = dist(leaves.front(), leaves.back());
        for (unsigned i = 0; i < leaves.size() - 1; ++i)
            full_dist += dist(leaves[i], leaves[i + 1]);
        P = -100000;
        for (int i = 2; i <= prime_cnt; ++i)
            if (full_dist+2*Len<prime[i] * 2 && !vis[prime[i]]) {
                P = prime[i] * 2;
                break;
            }
        for (int i = 1; i <= m; ++i) {
            F[i] >>= 1;
            while (F[i]>1) vis[v[F[i]]] = 0, F[i] /= v[F[i]];
        }
        int left=P-full_dist;
        int fcnt = left / (2 * (Len - 1));
        answer = leaves;
        while (fcnt--) answer.push_back(rt),
                  answer.push_back(btm), left -= 2 * (Len - 1);
        if (left>>=1) answer.push_back(rt),
            answer.push_back(gline[left]);
        for (int qwq: answer) cout << qwq << " ";
        cout << endl;
    }
}
int main() {
    prime_init(MAXP);
    int T;
    cin >> T;
    while (T--) solve();
}

代码解读