25浙江省赛

发表于 分类于 ， 阅读次数： 作者 Pomelorin

I. Version Number

题意简述

有 \(T\) 组测试数据。每组给出两个版本号 \(A\) 和 \(B\)，版本号由若干个数字段用点号分隔，且所有版本号的段数相同。

按顺序逐段比较 \(A\) 和 \(B\) 的对应数字段：若 \(A\) 的当前段大于 \(B\) 的当前段，则 \(A\) 更新；若小于，则 \(B\) 更新；若相等，则继续比较下一段。若所有对应段都相等，则输出 Equal；否则输出更新版本的编号 A 或 B。

数据范围

\(1 \le T \le 100\)；每个版本号最多包含 \(3\) 个点，即最多 \(4\) 个数字段；每个数字段的长度不超过 \(9\)，且不含前导零。

题解

模拟 ？！噩梦梦噩！？

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 0, inf = 1e17;

struct Data {
    ll num[10];

    Data() { memset(num, 0, sizeof(num)); }

    bool operator<(Data x) {
        for (int i = 1; i <= 8; i++) {
            if (num[i] == x.num[i]) {
                continue;
            }
            return num[i] < x.num[i];
        }
        return 0;
    }
};

ll to_number(string s) {
    ll ret = 0, len = s.size();
    for (ll i = 0; i < len; i++) {
        ret = ret * 10 + s[i] - '0';
    }
    return ret;
}

void solve() {
    string A, B;
    cin >> A >> B;
    Data dA, dB;
    for (int i = 1; i <= 4; i++) {
        ll pos = A.find(".");
        if (pos != -1) {
            dA.num[i] = to_number(A.substr(0, pos));
            A.replace(0, pos + 1, "");
        } else {
            dA.num[i] = to_number(A);
            break;
        }
    }
    for (int i = 1; i <= 4; i++) {
        ll pos = B.find(".");
        if (pos != -1) {
            dB.num[i] = to_number(B.substr(0, pos));
            B.replace(0, pos + 1, "");
        } else {
            dB.num[i] = to_number(B);
            break;
        }
    }
    if (dA < dB) {
        cout << "B\n";
    } else if (dB < dA) {
        cout << "A\n";
    } else {
        cout << "Equal\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

F. Challenge NPC III

题意简述

有 \(T\) 组测试数据。每组给定一个有向图，包含 \(n\) 个顶点、\(m\) 条有向边，每个顶点有一个颜色 \(c_i\)，以及参数 \(k\)。定义简单路径为顶点互不相同的序列 \(u_1,u_2,\dots,u_L\)，且对每个 \(i\in[1,L-1]\) 都存在边 \(u_i\to u_{i+1}\)，该路径的长度为 \(L\)（即路径中顶点个数）。判断图中所有长度不超过 \(k\) 的简单路径是否都满足：路径上各顶点的颜色两两不同。若满足则输出 YES，否则输出 NO。

数据范围

\(1\le T\le 10^5\)；每组 \(1\le n,k\le 10^5\)，\(0\le m\le 10^5\)，\(1\le c_i\le 50\)，\(1\le u_j,v_j\le n\)。保证所有测试用例的 \(\sum n\) 与 \(\sum m\) 均不超过 \(10^5\)。

题解

最短路 考虑枚举每个颜色，问题变成求点集中的最短距离，使用多源最短路处理。

需要维护 from 记录从哪个节点开始的路径，维护最短路和次短路（这个最/次短路是类似于从超级源点出发的最短路，本同色点附近的最短路被自己占据，次短路用来判断能不能从另外的同色点到本同色点）。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 1e5 + 10, inf = 1e17;

struct Data {
    ll id, dis, from;
    bool operator<(const Data &a) const { return dis > a.dis; }
};

ll n, m, k, c[N], dis[N][2], from[N];
vector<ll> e[N];
priority_queue<Data> q;

ll bfs() {
    while (!q.empty()) {
        Data u = q.top();
        q.pop();
        // cout << u.id << " " << u.dis << " " << u.from << endl;
        if (from[u.id] == u.id && u.id != u.from) {
            while (!q.empty()) {
                q.pop();
            }
            return 1;
        }
        if (u.dis >= k) {
            continue;
        }
        for (auto v : e[u.id]) {
            if (dis[v][0] > u.dis + 1) {
                dis[v][0] = u.dis + 1;
                from[v] = u.from;
                q.push({v, u.dis + 1, u.from});
            } else if (dis[v][1] > u.dis + 1 && u.from != from[v]) {
                dis[v][1] = u.dis + 1;
                q.push({v, u.dis + 1, u.from});
            }
        }
    }
    return 0;
}

void solve() {
    cin >> n >> m >> k;
    for (ll i = 1; i <= n; i++) {
        e[i].clear();
    }
    for (ll i = 1; i <= n; i++) {
        cin >> c[i];
    }
    for (ll i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        e[u].push_back(v);
    }
    for (ll i = 1; i <= 50; i++) {
        for (ll j = 1; j <= n; j++) {
            dis[j][0] = dis[j][1] = inf;
            from[j] = 0;
        }
        for (ll j = 1; j <= n; j++) {
            if (c[j] == i) {
                dis[j][0] = 1;
                from[j] = j;
                q.push({j, 1, j});
            }
        }
        if (bfs()) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

L. Nailoongs Always Lie

题意简述

有 \(n\) 个生物，编号为 \(1\) 到 \(n\)。其中一部分生物是“奶龙”，其余不是奶龙。

已知两条规则：

  • 奶龙总是说谎；
  • 其他生物可能说真话，也可能说谎。

第 \(i\) 个生物声称：“编号为 \(a_i\) 的生物是奶龙。”

请判断在这些规则下，最多可能有多少个生物是奶龙。

数据范围

\(1 \le n \le 10^5\)，\(1 \le a_i \le n\)。

题解

贪心 动态规划 树形 DP

限制相当于任意相邻两个生物不能同时为奶龙。同时，将 \(i\) 向 \(a_i\) 连边后图为基环树。

每次可以贪心将一个度数最小的点标记为奶龙，然后将和其相邻的点标记为不是奶龙，并断开这两个点和其余点的连边。统计这样贪心后有多少奶龙即可。

另一种做法是在基环树上 DP。

D. Too Clever by Half

题意简述

有一条从 \(0\) 到 \(n\) 的水平跑道，共 \(n+1\) 个位置。机器人初始在位置 \(0\)，最终也必须回到位置 \(0\)。机器人可执行两种操作：

  • L：向左移动一格，即从 \(x\) 到 \(x-1\)，不能在位置 \(0\) 执行；
  • R：向右移动一格，即从 \(x\) 到 \(x+1\)，不能在位置 \(n\) 执行。

要求机器人执行完操作后，到达位置 \(i\) 的次数恰好为 \(c_i\)（不计初始位置），其中 \(0\le i\le n\)。操作序列长度必须为 \(\sum_{i=0}^{n}c_i\)。

若存在合法操作序列，输出字典序最小的一个，其中 L 的字典序小于 R；若不存在，输出 Impossible。

数据范围

\(1\le T\le 10^5\)；\(1\le n\le 5\cdot10^5\)；\(1\le c_i\le 10^6\)，其中 \(0\le i\le n\)。

保证所有测试用例的 \(n\) 之和不超过 \(5\cdot10^5\)，所有测试用例的 \(\sum_{i=0}^{n}c_i\) 之和不超过 \(2\cdot10^6\)。

题解

思维题 弄拙成巧。移动过程可以看成总体上 0-n-0 转一圈，序列是 1 2 2 ... 2 1。多余的数字可以通过 RL 折返操作填充，相当于相邻的数字 +1+1。如果不能按这种方法构造就是不可能。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 0, inf = 1e17;

void solve() {
    ll n, flag = 1;
    cin >> n;
    ll a[n + 10];
    string ans;
    for (ll i = 0; i <= n; i++) {
        cin >> a[i];
        a[i]--;
        if (i != 0 && i != n) {
            a[i]--;
        }
        if (a[i] < 0) {
            flag = 0;
        }
    }
    for (ll i = 0; i < n; i++) {
        while (a[i] > 0 && a[i + 1] > 0) {
            a[i]--, a[i + 1]--;
            ans += "RL";
        }
        if (a[i] > 0) {
            flag = 0;
        }
        ans += "R";
    }
    if (a[n] > 0) {
        flag = 0;
    }
    for (ll i = 1; i <= n; i++) {
        ans += 'L';
    }
    if (flag == 0) {
        cout << "Impossible\n";
    } else {
        cout << ans << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

M. Master of Both VII

题意简述

本题为交互题。有 \(T\) 组测试数据。每组给定一个正 \(n\) 边形，顶点按逆时针顺序编号为 \(1,2,\dots,n\)。该多边形内隐藏了一个三角剖分，由 \(n-3\) 条连接顶点的边组成。交互器非自适应，即三角剖分在交互过程中不会改变。

你可以进行如下查询：

  • ? u v：查询连接 \(u\) 和 \(v\) 的边。其中 \(1\le u\ne v\le n\)，且 \(u,v\) 在凸多边形上不相邻。若边 \(u-v\) 存在于隐藏的三角剖分中，返回 \(0\)；否则返回三角剖分中与 \((u,v)\) 在非端点处相交的边数。

你需要在不超过 \(n-3\) 次查询内确定该三角剖分。确定后，输出一行：

! a1 b1 a2 b2 ... a_{n-3} b_{n-3}

表示三角剖分包含边 \((a_i,b_i)\)，其中 \(1\le i\le n-3\)。提交答案不计入查询次数。

若某次查询无效或超过查询次数限制，交互器返回 \(-1\)，此时应终止程序。提交答案后，交互器返回 \(r\)：若 \(r=1\) 表示答案正确；若 \(r=0\) 表示答案错误，应终止程序。处理完当前测试用例后继续处理下一组；所有测试用例处理完后程序应终止。每次输出查询或答案后都需要换行并刷新输出缓冲区。

数据范围

\(1\le T\le 2500\)，\(4\le n\le 100\)，保证所有测试用例的 \(\sum n\le 10^4\)。每个测试用例最多允许 \(n-3\) 次查询；提交答案不计入查询次数。

题解

交互题 思维题 考虑询问所有 \(3\le i\le n−1\) 的 \((1,i)\)，设询问结果为 \(d_i\)。

相比 \(d_{i-1}\)，如果 \(d_i\) 增大了 \(x\)，说明有 \(x\) 条线段从 \(i-1\) 节点发出；如果 \(d_i\) 减少了 \(y\)，说明有 \(y\) 条线段在 \(i\) 节点终止。不可能同时发出、终止。那么如何求终止的线段的发出点？应当让最近发出的线段终止，否则肯定会和后面的线段冲突（交叉），可以使用栈维护发出点的编号。

额外考虑如果 \(d_i=0\) 直接把 \((1,i)\) 加入答案。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 0, inf = 1e17;

void solve() {
    ll n;
    cin >> n;
    ll stk[n + 10] = {}, top = 0, cnt = 0, num;
    PII ans[n + 10];
    for (ll i = 1; i <= n - 3; i++) {
        cout << "? 1 " << i + 2 << endl;
        cin >> num;
        while (top < num) {
            stk[++top] = i + 1;
        }
        while (top > num) {
            ans[++cnt] = {stk[top], i + 2};
            top--;
        }
        if (num == 0) {
            ans[++cnt] = {1, i + 2};
        }
    }
    while (top > 0) {
        ans[++cnt] = {stk[top], n};
        top--;
    }
    cout << "! ";
    for (ll i = 1; i <= n - 3; i++) {
        cout << ans[i].first << " " << ans[i].second << " ";
    }
    cout << endl;
    cin >> num;
}

int main() {
    ll T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

G. Tariff-ied

题意简述

有 \(n\) 个国家依次排列，商品初始价格为 \(x\)。第 \(i\) 个国家的初始关税为 \(0\%\)，每次提高关税会增加 \(l_i\%\)。若第 \(i\) 个国家提高 \(t_i\) 次，则其关税为 \(l_i t_i\%\)，商品经过后价格变为 \(\left(1+\frac{l_i t_i}{100}\right)x\)。

总共可以提高关税 \(k\) 次，且可任意分配给各国，即选择非负整数 \(t_1,t_2,\dots,t_n\)，满足 \(\sum_{i=1}^{n}t_i=k\)。求商品依次经过所有国家后的最大价格乘数：

\[ \max \prod_{i=1}^{n}\left(1+\frac{l_i t_i}{100}\right) \] 输出该最大值。

数据范围

\(1\le T\le 5000\)；\(1\le n\le 40\)，\(1\le k\le 10^6\)；\(1\le l_i\le 100\)。对 \(n\) 与 \(k\) 的总和没有额外限制。输出实数，绝对或相对误差不超过 \(10^{-4}\)。

题解

贪心 二分 首先考虑贪心：每次选择一个性价比提升最高的国家提高税率。但是直接贪心会超时。考虑对性价比二分，这样对于每个国家可以直接算出提高关税的次数（推一下式子），让次数不超过 \(k\) 次。

但是这样有一个问题：有多个国家性价比相同，会出现不填时次数小于 \(k\)，填时次数大于 \(k\) 的情况。可以考虑枚举 \(n\) 次填写解决（最多只有 \(n\) 个相同的性价比）。

有一个小问题：公式里出现减号，没有使用 max(0, cnt)。因为二分的性价比，有些国家性价比本来就低，所以会出现负数，这种不应该填写。

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
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define double long double
using namespace std;

const int N = 100;
const int INF = 1e15;

ll n, k, l[N];

ll check(double x) {
    ll cnt = 0;
    for (ll i = 1; i <= n; i++) {
        cnt += max(0ll, (ll)(((double)l[i] - x * 100) / (l[i] * x)));
        if (cnt > k) {
            return 1;
        }
    }
    if (cnt == k) {
        return 0;
    }
    return -1;
}

void solve() {
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) {
        cin >> l[i];
    }
    double L = 0, R = 1, res;
    double ans = 1;
    for (ll i = 1; i <= 1000; i++) {
        double mid = (L + R) / 2;
        if (check(mid) == 1) {
            L = mid;
        } else if (check(mid) == -1) {
            R = mid;
            res = mid;
        } else {
            res = mid;
            break;
        }
    }
    ll tmp = k;
    vector<double> fk;
    for (ll i = 1; i <= n; i++) {
        ll cnt = max(0ll, (ll)(((double)l[i] - res * 100) / (l[i] * res)));
        tmp -= cnt;
        ans *= ((double)l[i] * cnt / 100 + 1);
        fk.push_back(((double)l[i] * (cnt + 1) / 100 + 1) /
                     ((double)l[i] * cnt / 100 + 1));
    }
    sort(fk.begin(), fk.end(), greater<double>());
    for (int i = 0; i < tmp; i++) {
        ans *= fk[i];
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    ll T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}