Contestant~. Rank 538. Rating +59 (+409 -350).

A. Rudolph and Cut the Rope

题意

给定 \(n\) 个钉子，第 \(i\) 个钉子钉在离地面 \(a_i\) 的位置，并连有 \(b_i\) 长的绳子。所有钉子的另外一端连着同一个糖果。

输出需要剪断多少根绳子，让糖果掉到地上。

思路

画个图即可，我们不难发现最后的结果就是 \(a_i > b_i\) 的钉子个数。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    for(int i=0;i<n;i++){
        int a, b;
        cin >> a >> b;
        if(a > b) ans ++;
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

具象的，抽象的，物理的

B. Rudolph and Tic-Tac-Toe

题意

\(3\) 个人玩 \(3 \times 3\) 的井字格游戏。

给定某个时刻的井字格状态，输出当前是否出现了赢家。

如果没有赢家，或者出现多个赢家，输出 \(\mathtt{DRAW}\)。

思路

直接枚举即可。

时间复杂度：\(O(1)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    vector<string> s(3);
    for(int i=0;i<3;i++) cin >> s[i];
    bool a = false, b = false, c = false;
    for(int i=0;i<3;i++){
        if(s[i][0] == s[i][1] && s[i][1] == s[i][2]){
            if(s[i][0] == 'O') a = true;
            else if(s[i][0] == 'X') b = true;
            else if(s[i][0] == '+') c = true;
        }
    }
    for(int i=0;i<3;i++){
        if(s[0][i] == s[1][i] && s[1][i] == s[2][i]){
            if(s[0][i] == 'O') a = true;
            else if(s[0][i] == 'X') b = true;
            else if(s[0][i] == '+') c = true;
        }
    }
    if(s[0][0] == s[1][1] && s[1][1] == s[2][2]){
        if(s[0][0] == 'O') a = true;
        else if(s[0][0] == 'X') b = true;
        else if(s[0][0] == '+') c = true;
    }
    if(s[0][2] == s[1][1] && s[1][1] == s[2][0]){
        if(s[0][2] == 'O') a = true;
        else if(s[0][2] == 'X') b = true;
        else if(s[0][2] == '+') c = true;
    }
    if(a && !b && !c){
        cout << 'O' << '\n';
    }else if(!a && b && !c){
        cout << 'X' << '\n';
    }else if(!a && !b && c) {
        cout << '+' << '\n';
    }else cout << "DRAW" << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

主打一个复制粘贴

C. Rudolf and the Another Competition

题意

对于 \(n\) 个人和 \(m\) 道题，给定每个人每道题需要花的时间。

每个人可以任意排列做题的顺序，给定比赛的总时长，在 \(\mathtt{ICPC}\) 规则下，若每个人都希望自己的排名尽可能高，输出第一个人最后的排名。

若第一个人和其他人的排名一致，第一个人的排名更高。

\(\mathtt{ICPC}\) 规则：

每一道题的罚时 \(=\) 通过这道题离 比赛开始 的时间；
排名的主关键词：过题数（降序），总罚时（升序）

思路

对于某一个人，我们将所有过题的时间升序排序，然后依次做题，如果某一道题做完的时候已经超过比赛总时长，那这题及以后的所有题都不用做了。

以上，我们统计过题数 \(cnt\)，罚时 \(pen\)，每个人的下标 \(i\)。

我们将三元组 \(\{-cnt, pen, i\}\) 升序排序，然后输出 \(i = 1\) 的位置即可。

不排序也是可以的，因为我们只需要知道第一个人的排名。

时间复杂度：\(O(n \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n, m, h;
    cin >> n >> m >> h;
    vector<ppii> res(n);
    for(int i=0;i<n;i++){
        vector<int> a(m);
        for(int j=0;j<m;j++) cin >> a[j];
        sort(all(a));
        int last = 0, cnt = 0, p = 0;
        for(int j=0;j<m;j++){
            if(last + a[j] <= h){
                p += last + a[j];
                cnt ++;
                last += a[j];
            }else break;
        }
        res[i] = {-cnt, {p, i}};
    }
    sort(all(res));
    for(int i=0;i<n;i++){
        if(res[i].sc.sc == 0){
            cout << i + 1 << '\n';
            return;
        }
    }
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

ICPCGPT

D. Rudolph and Christmas Tree

题意

给定一个三角形的底和高，在坐标系中，三角形底边和 \(x\) 轴平行，高和 \(y\) 轴平行。

给定 \(n\) 个上述三角形的底边所在的 \(y\) 坐标，输出最后坐标轴上的图形的面积。

思路

显然会有重叠。

对于两个重叠的三角形，我们不难发现，底下的三角形需要去掉一个小三角形。

小三角形和原三角形是相似的，因而计算面积是很容易的（相似比的平方即为面积比）。

也许你会觉得三个三角形重叠的时候不能按照上述操作计算，但本题中三角形大小都是一样的，画个图不难发现，上述操作移除的小三角形面积不受其他的三角形影响。

那么，我们降序排序底边 \(y\) 坐标，然后枚举相邻的三角形是否出现重叠即可。

p.s. 本题按照升序给出了 \(y\) 坐标。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    //《容斥》
    int n, d, h;
    cin >> n >> d >> h;
    vector<int> y(n);
    for(int i=0;i<n;i++) cin >> y[i];
    int pre = inf;
    double ans = 0;
    for(int i=n-1;i>=0;i--){
        ans += (double) (d * h) / 2;
        if(y[i] + h > pre){
            ans -= (double) (d * h) / 2 * ((double) (y[i] + h - pre) * (y[i] + h - pre) / h / h);
        }
        pre = y[i];
    }
    printf("%.7f\n", ans);
}

signed main(){
    //ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

还以为是不可做的几何题(x)。输出的时候记得输出 \(7\) 位小数

E1. Rudolf and Snowflakes (simple version)

题意

对于整数 \(k \in [2, +\inf)\)，定义 "雪花" 构造操作如下：

定义一个点为根节点；
根节点有 \(k\) 个子节点；
上述 \(k\) 个子节点，每个子节点自己有 \(k\) 个子节点；
重复任意次操作 \(3\)，操作 \(3\) 需要执行至少一次。

如 \(k = 4\)，操作 \(3\) 执行一次，雪花图如下：

现在，给定节点总数 \(n\)，判断是否可以用这些节点构造出一个雪花。

本题中，\(n \leq 1e6\)。

思路

本题的 \(n\) 比较小，我们考虑直接枚举所有 \(k\)，以及操作 \(3\) 执行的次数，对 \(n\) 打表即可。

不难发现 \(n\) 是等比数列的前 \(n\) 项和，我们套公式爆搜即可。

时间复杂度：不大

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;

map<int, bool> mp;

int qp(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a);
        a = (a * a);
        b >>= 1;
    }
    return res;
}

void init(){
    int k = 2;
    while(true){
        bool f = false;
        int p = 3;
        while(true){
            if((qp(k, p) - 1) / (k - 1) > 1e6) break;
            mp[(qp(k, p) - 1) / (k - 1)] = true;
            f = true;
            p ++;
        }
        if(!f) break;
        k ++;
    }
}

void solve() {
    int n;
    cin >> n;
    cout << (mp.count(n) ? "YES\n" : "NO\n");
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

狠狠地打表

E2. Rudolf and Snowflakes (hard version)

题意

在 \(E1\) 的基础上，\(n \leq 1e18\)。

思路

首先，因为我们枚举的是等比数列的前 \(n\) 项和，我们不妨固定项数，观察答案不超过 \(1e18\) 的 \(k\) 的最大值。

我们不难发现，在量级上考虑，\(k >1e9\) 时，只能取两项，\(k \in [1e6, 1e9]\) 时，只能取三项。

我们不可以取两项，那么我们只需对取三项的情况进行单独考虑。

取三项时，方程即为 \(q ^ 2 + q + 1 = n\)，那么如果能解出 \(q \geq 2\)，\(n\) 就是正确的。

否则，\(k\) 一定小于 \(1e6\) 量级。

分析复杂度可知，对 \(k \in [2, 1e6]\)，我们直接打表即可。

时间复杂度：还好

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;

map<int, bool> mp;

__int128 qp(__int128 a, int b) {
    __int128 res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a);
        a = (a * a);
        b >>= 1;
    }
    return res;
}

void init(){
    int k = 2;
    while(true){
        if(k > 1e6) break;
        bool f = false;
        int p = 3;
        while(true){
            if(p > 70) break;
            if((qp(k, p) - 1) / (k - 1) > 1e18 || (qp(k, p) - 1) / (k - 1) <= 0) break;
            mp[(qp(k, p) - 1) / (k - 1)] = true;
            f = true;
            p ++;
        }
        if(!f) break;
        k ++;
    }
}


void solve() {
    int n;
    cin >> n;
    int delta = 1 - 4 * (1 - n);
    if((int) sqrt(delta) * (int) sqrt(delta) == delta){
        if((-1 + (int) sqrt(delta)) % 2 == 0){
            int q = (-1 + (int) sqrt(delta)) / 2;
            if(q >= 2) {
                cout << "YES\n";
                return;
            }
        }
    }
    cout << (mp.count(n) ? "YES\n" : "NO\n");
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

注意越界 / 浮点数误差的问题！

F. Rudolph and Mimic

题意

这是一道交互题。

在长度为 \(n\) 的序列 \(a\) 中，满足 \(1 \leq a_i \leq 9\)，存在一只怪物，躲藏在某一个未知元素后。

定义一次交互如下：

输出：给定序列中需要删除的元素；

输出后：

将元素删除；
打乱序列；
怪物可以选择是否将其所在元素的值改变为另一个不同的数，但两次交互后如果都不改变，第三次一定会改变

输入：操作后的序列

在不超过 \(5\) 次交互内，确定怪物在哪个下标。

注意，本题的所有下标都是针对上一次给定的序列，而不是最初给的序列。

思路

因为怪物第三次一定会改变，那么我们只要等他改变即可。

在等他改变的时候，我们为了防止误删怪物所在的元素，我们直接不删除。

那么，当他改变的时候，我们保留所有等于他所在的元素的值的元素，然后把其他的元素全都删掉。

接着，我们继续等待，当他再改变时，那个不同的元素就是怪物了。

为了方便判断，我们不妨记录每个值对应出现的下标，然后比较每个值出现了几次即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 3e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    auto fetch = [&]() -> vector<vector<int>>{
        vector<vector<int>> a(10);
        for(int i=1;i<=n;i++){
            int cur;
            cin >> cur;
            a[cur].pb(i);
        }
        return a;
    };
    vector<vector<int>> a0 = fetch();
    int leave;
    while(true){
        cout << "- 0\n";
        cout.flush();
        vector<vector<int>> a1 = fetch();
        int ind = -1;
        for(int i=1;i<=9;i++){
            if(a1[i].size() > a0[i].size()) ind = i;
        }
        if(ind != -1){
            leave = ind;
            a0 = a1;
            break;
        }
    }
    cout << "- ";
    vector<int> del;
    for(int i=1;i<=9;i++){
        if(i == leave) continue;
        for(auto e : a0[i]) del.pb(e);
    }
    cout << del.size() << ' ';
    n -= del.size();
    for(auto e : del) cout << e << ' ';
    cout << '\n';
    cout.flush();
    while(true){
        vector<vector<int>> a1 = fetch();
        if(a1[leave].size() == a0[leave].size()){
            cout << "- 0\n";
            cout.flush();
        }else{
            for(int i=1;i<=9;i++){
                if(i == leave) continue;
                if(a1[i].size() == 1){
                    cout << "! " << a1[i][0] << '\n';
                    cout.flush();
                    return;
                }
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

但凡题面正常一点

G. Rudolf and CodeVid-23

题意

给定 \(n\) 个病症，以及 \(m\) 种药。

每种药可以治疗若干病症，但也会导致若干个并发症。每个药都有一段服用时间。同一时刻只能服用一种药。治疗的病症不会出现在并发症中。

现在，给定初始患上的病症，输出在使用若干药后所有病症痊愈的条件下需要服用的最短时间。

本题输入使用二进制表示某一个病症是否患上。

思路

首先，因为二进制串长度很短，所以我们直接将其转为十进制处理。

对于任意一个状态，如果我们确定需要用什么药，那么用药结束后的状态是唯一确定的。

那么，我们唯一需要做的，就是对于初始状态，通过状态的转换，从而变为 \(0\)。

那么我们考虑图论，从某一个状态，连一条有向边到使用某一个药之后的状态，边权就是这个药需要服用的时间。

那么很显然了，这道题就可以转化为 "求初始状态到 \(0\) 的最短路长度"。

有关计算，设 \(x, h, s\) 分别为服药前状态、能治哪些病、并发症，那么我们将 \(h\) 取反为 \(rh\)，不难发现最后结果就是 \((x\ \&\ rh)|s\)。（取反操作可以考虑异或）。

有关建图，我们用类似 "状压枚举" 的方式，枚举所有可能的状态，对于某一个状态，枚举所有的药，然后按上述操作建边即可。

时间复杂度：\(O(2^n(m+n))?\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n, m;
    cin >> n >> m;
    int mx = (1 << n) - 1;
    auto calc = [&](string s) -> int{
        int ans = 0;
        for(auto e : s) ans = ans * 2 + (e - '0');
        return ans;
    };
    auto heal = [&](int pre, int heal, int side) -> int{
        return (pre & (heal ^ mx)) | side;
    };
    string c;
    cin >> c;
    int start = calc(c);
    vector<int> w(m), h(m), s(m);
    for(int i=0;i<m;i++) {
        string a, b;
        cin >> w[i] >> a >> b;
        h[i] = calc(a), s[i] = calc(b);
    }
    vector<vector<pii>> e(mx + 1);
    for(int p=0;p<=mx;p++){ //《状压》
        for(int i=0;i<m;i++){
            e[p].pb(heal(p, h[i], s[i]), w[i]);
        }
    }
    auto dijkstra = [&](int start, int end) -> int{
        vector<int> dist(mx + 1, inf);
        vector<bool> st(mx + 1);
        dist[start] = 0;
        priority_queue<pii, vector<pii>, greater<>> q;
        q.emplace(0, start);
        while (!q.empty()){
            auto t = q.top();
            q.pop();
            int cur = t.second, d = t.first;
            if (st[cur]) continue;
            st[cur] = true;
            for (auto [j, wi] : e[cur]){
                if (dist[j] > dist[cur] + wi){
                    dist[j] = dist[cur] + wi;
                    q.emplace(dist[j], j);
                }
            }
        }
        if (dist[end] == inf) return -1;
        return dist[end];
    };
    cout << dijkstra(start, 0) << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

怎么比 \(E2\) 简单啊