文章

校队选拔补题计划 Day 1

发表于 更新于
作者 Shirakawa
18 分钟阅读
校队选拔补题计划 Day 1

题目来源：2020-2021 ICPC Southwestern Europe Regional Contest

A - Gratitude

题意：统计 $3n$ 行输入中每行出现的次数，然后按出现次数降序、最后出现时间降序输出前 $k$ 个。

签到题排序即可。

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

struct Node
{
    string s;
    int idx, t;
    bool operator<(const Node &ano) const
    {
        return t == ano.t ? idx > ano.idx : t > ano.t;
    }
} a[100005];
map<string, int> mp;
int cnt;
int main()
{
    int n, k;
    cin >> n >> k;
    getchar();
    F(i, 1, 3 * n)
    {
        string str;
        getline(cin, str);
        if(mp[str] == 0)
        {
            mp[str] = ++ cnt;
            a[cnt] = {str, i, 1};
        }
        else
        {
            a[mp[str]].idx = i；
            a[mp[str]].t ++;
        }
    }
    sort(a + 1, a + cnt + 1);
    F(i, 1, k)
        cout << a[i].s << endl;
    return 0;
}

B - Rule 110

不可做题。

不是我能做的题，直接放弃。

C - Safe Distance

题意：在一个宽为 $X$、高为 $Y$ 的矩形房间内，给定 $n$ 个点。$awa$ 从 $(0,0)$ 出发，要走到 $(X,Y)$，求她在移动过程中能与所有点保持的最大的最小距离。值域 $10^6$，$n\leq 10^3$，精度要求 $10^{-6}$。

二分答案，答案具有单调性：更小的答案一定能满足恰好的答案。$\log_2\frac{10^6}{10^{-6}}=40$。

然后 check(double r) 怎么写？

考察距离的实质。距离就是圆。所以考虑两种情况：

  1. 以 $awa$ 为圆心，$r$ 为半径，这个圆在某个路径上不会碰到任何点；

  2. 以 各个点 为圆心，$r$ 为半径，$awa$ 在某个路径上不会碰到任何圆。

首先肯定不能是情况 1！因为这个路径是你不知道的，而且很难求！（窝当时考场上就不知道怎么想着维护中位线啥的奇妙想法）因此我们肯定是用下面这种情况（因为每个点是固定的），然后维护一个并查集：如果和其他点相连，那就直接合并。然后你注意到，能把路堵死的一定是

  • 上、下边相连
  • 左、右边相连
  • 左、下边相连
  • 右、上边相连

这四种情况。于是与边界也要合并，暴力判断就行。

时间复杂度 $O(N\log V)$。

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

int n, m, k;
db X, Y;
using Point = pair<db, db>;
Point a[1005];
int fa[1010];
void clear()
{
    F(i, 1, n + 4)
        fa[i] = i;
}
int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
    fa[find(x)] = find(y);
}
bool query(int x, int y)
{
    return find(x) == find(y);
}
db dis(Point a, Point b)
{
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
bool check(db r)
{
    clear();
    F(i, 1, n)
    {
        F(j, i + 1, n)
            if(dis(a[i], a[j]) <= r + r)
                merge(i, j);
        if(a[i].first <= r)
            merge(i, n + 1);
        if(a[i].second <= r)
            merge(i, n + 2);
        if(X - a[i].first <= r)
            merge(i, n + 3);
        if(Y - a[i].second <= r)
            merge(i, n + 4);
    }
    return query(n + 1, n + 3) || query(n + 2, n + 4) || query(n + 1, n + 2) || query(n + 3, n + 4);
}
signed main()
{
    cin >> X >> Y;
    cin >> n;
    F(i, 1, n)
        cin >> a[i].first >> a[i].second;
    db l = 0, r = max(X, Y);
    while(r - l > 1e-6)
    {
        db mid = (l + r) / 2;
        if(!check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << l << endl;
    return 0;
}

D - Jogging

题意：在一个有 $n$ 个交叉口和 $m$ 条街道的社区中，$awa$ 从 $0$ 号交叉口出发并返回，每次跑步的距离 $l$ 到 $r$ 之间。如果某次跑步经过了之前未跑过的街道，那么这次跑步就 “有趣”。她可以只跑街道的一部分，但只要经过了就算跑过整条街。求她最多能连续跑 “有趣” 的次数。$n\leq 10^5$，无重边自环。

这题你赛时不会做？脑子被妮芙吃掉了。

这个问题的本质不就是问有多少本质不同的路线嘛。只要每次新走一个之前没走过的路就行了。而且你的下界是无意义的，你只用在某一段来回跑就行。

于是 Dijkstra 跑一遍，然后检查每条边是否满足条件：只要边的两点至少有一个点的两倍 dis 小于 $r$，就可以计入。

为什么是 小于 而不是 小于等于？如果是等于的话，有可能是恰好到达了边的一个端点而没有走进去，这种情况自然不能计算进这一条边了。所以必须是小于。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

signed main()
{
    int l, r;
    read(n, m, l, r);
    F(i, 1, m)
    {
        int u = readint() + 1;
        int v = readint() + 1;
        int w = readint();
        addedge(u, v, w);
        addedge(v, u, w);
    }
    Dijkstra(1);
    int ans = 0;
    F(i, 1, m)
    {
        int u = e[i << 1].u;
        int v = e[i << 1].v;
        if(dis[u] * 2 < r || dis[v] * 2 < r)
            ans ++;
    }
    write('\n', ans);
    return 0;
}

E - Cakes

题意：给定制作一个蛋糕所需的 $n$ 种配料的量 $a_i$ 以及每种配料现有的量 $b_i$，求最多能制作多少个蛋糕。

签到题。$ans=\max\limits_{i=1}^n\lfloor\frac{b_i}{a_i}\rfloor$。

F - Mentors

题意：给定 $n$ 个点，每个点的权值是自己的下标。要求出满足

  1. 父节点的权值大于子节点的权值

  2. 子节点数量不超过 $2$

  3. 编号 $r$ 的节点必须是叶子节点

的树形结构的数量并对 $p$ 取模。$n\leq 2021,p\leq 10^9$。

How to count? 首先显然不能推柿子。困难。然后想 dp。考虑父节点一定大于子节点，因此子问题有重叠。

来自 写完这题的 awa：我操，我被 AI 骗了，这几把题简单无比哪有那么多分类讨论，气死我了。

首先，我们考虑一个简化版的问题：只满足条件 1 和 2，暂时忽略条件 3。

设 $f_{i,j}$ 为 使用前 $i$ 个数字生成的 $j$ 颗树的森林的方案数，然后考虑 $f_{i-1}$ 怎么向 $f_i$ 转移：

  1. 新的点自己作为一棵新树的节点，$f_{i,j} = f_{i-1,j-1}$。

  2. 新的点在其他树里面挑一棵，$f_{i,j} = \binom{j}{1}\times f_{i-1,j}=j\times f_{i-1,j}$。

  3. 新的点在其他树里面挑两颗，$f_{i,j} = \binom{j+1}{2}\times f_{i-1,j+1}=\frac{j(j+1)}{2}\times f_{i-1,j+1}$。

结合上述三种情况就是

\[f_{i,j}=f_{i-1,j-1}+j\times f_{i-1,j}+\frac{j(j+1)}{2}\times f_{i-1,j+1}\]

再考虑加入条件 3 的情况。首先，在 $i<r$ 的时候没有任何问题，直接转移就行。

$i=r$ 的时候，我们肯定不能让 $r$ 当爹，只能让他新开一个树，因此 $f_{i,j}=f_{i-1,j-1}$。

$i>r$ 时，发现 $r$ 啥的根本没影响。同 $i<r$ 的情况。

最终的转移就是

\[f_{i,j}=\begin{cases} f_{i-1,j-1}+j\times f_{i-1,j}+\frac{j(j+1)}{2}\times f_{i-1,j+1} &(i\neq r)\\ f_{i-1,j-1} &(i=r)\\ \end{cases}\]

初始状态是 $f_{1,1}=1$，最终答案是 $f_{n,1}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#define int ll
int f[2025][2025];
int n, r, p;
signed main()
{
    cin >> r >> n >> p;
    f[1][1] = 1;
    F(i, 2, n)
        F(j, 1, n)
        {
            f[i][j] = f[i - 1][j - 1];
            if(i != r)
            {
                f[i][j] = (f[i][j] + j * f[i - 1][j]) % p;
                f[i][j] = (f[i][j] + j * (j + 1) / 2 * f[i - 1][j + 1]) % p;
            }
        }
    int ans = 0;
    cout << f[n][1] << endl;
    return 0;
}

G - Decoration

题意：给定 $n$ 和 $p$，求一个长度为 $n$ 的整数序列 $a_1, \dots, a_n$，满足以下三个条件：

  1. $a_1, \dots, a_n$ 互不相同。

  2. $0 \leq a_i < p$。

  3. 对于 $1 \leq i < n$，有 $a_{i+1} \equiv a_i + \tau(a_i) \pmod p$，其中 $\tau(a_i)$ 是 $a_i$ 的因子数量。

在满足上述条件的前提下，求一个使得 $\sum\limits_{i=1}^n a_i$ 最小的序列。如果不存在，则输出 -1。$n,p\leq 10^6$。

注意到，如果 $a_i$ 确定了，那么 $a_{i+1}$ 也是确定的。也就是说一定有 $a_i\to a_{i+1}$ 的一条有向边。因此，找到这样一个序列是好找的，关键的问题是让 $\sum\limits_{i=1}^n a_i$ 最小。

我们考虑使用倍增的做法来优化。一次跳一个点可以改为跳 $2^k$ 的点，然后递推出来。这样的话给定起始点就可以以 $O(n\log n)$ 预处理、$O(\log n)$ 询问的复杂度而不是 $O(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
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

#define int ll
const int maxp = 1e6 + 10;
int n, p;
int nxt[maxp]; // 连边
void getnxt()
{
    F(i, 1, p - 1)
    {
        for(int j = i; j < p; j += i)
            nxt[j] ++;
        nxt[i] = (nxt[i] + i) % p;
    }
}
int col[maxp]; // 染色
#define NOT_VISITED 0
#define VISITING 1
#define VISITED 2
int c_dis[maxp], c_len[maxp]; // 到环的距离 环的长度
void dfs(int u)
{
    vector<int> path(1, u);
    col[u] = VISITING;
    while(col[u = nxt[u]] == NOT_VISITED)
    {
        col[u] = VISITING;
        path.push_back(u);
    }
    if(col[u] == VISITING) // 末尾发现是环
    {
        int len = 0, c_pos; // 求环长度
        UF(i, path.size() - 1, 0)
        {
            len ++;
            if(path[i] == u)
            {
                c_pos = i;
                break;
            }
        }
        F(i, 0, path.size() - 1)
        {
            c_len[path[i]] = len;
            c_dis[path[i]] = i < c_pos ? c_pos - i : 0;
        }
    }
    else // 末尾发现汇入
    {
        F(i, 0, path.size() - 1)
        {
            c_len[path[i]] = c_len[u];
            c_dis[path[i]] = c_dis[u] + path.size() - i;
        }
    }
    for(int i : path)
        col[i] = VISITED;
}
int fa[21][maxp], sum[21][maxp]; // fa[i][j] 代表 j 的 2^i 级下一个
ll Log2(ll x)
{
    return 63 - __builtin_clzll(x);
}
void pre() // 倍增优化
{
    F(j, 0, p - 1)
    {
        fa[0][j] = nxt[j];
        sum[0][j] = j;
    }
    F(i, 1, Log2(n))
        F(j, 0, p - 1)
        {
            fa[i][j] = fa[i - 1][fa[i - 1][j]];
            sum[i][j] = sum[i - 1][j] + sum[i - 1][fa[i - 1][j]];
        }
}
int ans_p()
{
    int minsum = n * p;
    int s = p; // 答案开始的节点
    F(i, 0, p - 1)
    {
        int maxlen = c_dis[i] + c_len[i];
        if(n > maxlen)
            continue;
        int S = 0;
        int pos = i;
        F(j, 0, Log2(n))
            if((n >> j) & 1)
            {
                S += sum[j][pos];
                pos = fa[j][pos];
            }
        if(S < minsum)
        {
            s = i;
            minsum = S;
        }
    }
    return s;
}
void ans(int pos)
{
    if(pos == p)
        cout << -1;
    else 
        F(i, 1, n)
        {
            cout << pos << " ";
            pos = nxt[pos];
        }
}
signed main()
{
    cin >> p >> n;
    getnxt();
    F(i, 0, p - 1)
        if(col[i] == NOT_VISITED)
            dfs(i);
    pre();
    ans(ans_p());
    return 0;
}

H - Figurines

题意：给定 $n$ 个编号为 $0\sim n-1$ 的迷你手办，以及 $n$ 天的手办添加和移除记录。同时，给定一个长度为 $n$ 的序列 $d_0, \dots, d_{n-1}$，每个 $d_i$ 在 $[0, n]$ 范围内。需要计算一个序列 $x_0, \dots, x_n$，其中 $x_0=0$，并且 $x_{i+1} = (x_i + y_i) \pmod n$。这里的 $y_i$ 是第 $d_i$ 天货架上编号大于或等于 $x_i$ 的手办数量。最终输出 $x_n$。$n\leq 10^5$。

byd 这不是主席树板子题吗。气笑了。让你看看主席树咋写，这个唐 b 输入方式气笑我了。

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

int n;
struct Node
{
    int sum;
    int ls, rs;
} tr[maxn << 6];
int rts[maxn];
int tot;
int update(int p, int l, int r, int pos, int v)
{
    int q = ++ tot;
    tr[q] = tr[p];
    tr[q].sum += v;
    if(l == r)
        return q;
    int mid = l + r >> 1;
    if(pos <= mid)
        tr[q].ls = update(tr[p].ls, l, mid, pos, v);
    else 
        tr[q].rs = update(tr[p].rs, mid + 1, r, pos, v);
    return q;
}
int query(int p, int l, int r, int L, int R)
{
    if(!p || L > R)
        return 0;
    if(L <= l && R >= r)
        return tr[p].sum;
    int res = 0, mid = l + r >> 1;
    if(L <= mid)
        res += query(tr[p].ls, l, mid, L, R);
    if(R > mid)
        res += query(tr[p].rs, mid + 1, r, L, R);
    return res;
}

I - Emails

题意：【模板】无向无权简单连通图的直径。求出来之后答案是 $\lceil\log_2 d\rceil$。

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

int n, m, k;
using Edge = pair<int, int>;
Edge e[maxn << 1];
int head[maxn], cnt;
void addedge(int u, int v)
{
    e[++ cnt] = {v, head[u]};
    head[u] = cnt;
}
int fa[maxn];
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

Edge bfs(int s)
{
    vector<int> d(n + 1);
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i; i = e[i].second)
        {
            int v = e[i].first;
            if(d[v])
                continue;
            q.push(v);
            d[v] = d[u] + 1;
        }
    }
    Edge ans(0, 0);
    F(i, 1, n)
        ans = max(ans, {d[i], i});
    return ans;
}
int Log(int x)
{
    return 31 - __builtin_clz(x);
}
signed main()
{
    read(n, m);
    F(i, 1, n)
        fa[i] = i;
    F(i, 1, m)
    {
        int u = readint(), v = readint();
        addedge(u, v);
        addedge(v, u);
        fa[find(u)] = find(v);
    }
    F(i, 2, n)
        if(find(1) ^ find(i))
            return 0 & puts("-1");
    write('\n', Log(bfs(bfs(1).second).first - 1) + 1);
    return 0;
}

J - Daisy’s Mazes

J
18 / 137

我，我吗？

K - Unique Activities

题意：给定一个由大写字母组成的字符串，找到只出现一次的最短子串。如果有多个最短子串，输出第一次出现的那个。

二分答案+字符串哈希。

注意：写双重哈希，不要自然溢出，不然有坏人随手卡掉你的代码。

不想贴代码，一点也不好看。

Contests
ICPC XJTU
本文由作者按照 CC BY 4.0 进行授权