Codeforces Round 677 (Div. 3) | answerend42的Blog

A.Boring Apartments

题目描述

有一座建筑物由 $10000$ 套公寓组成，编号从 $1$ 到 $10000$，包括 $1,10000$。

如果一个公寓的号码是由相同的数字组成的，则称它无聊。无聊公寓的例子有 $11,2,777,9999$ 等等。

我们的主角是个捣蛋鬼，他给所有无聊公寓的对讲机打电话，直到有人接电话，顺序如下:

首先，他以递增的次序呼叫所有由数字 $1$ 组成的公寓($1,11,111,1111$)
接下来，他以递增的次序呼叫所有由数字 $2$ 组成的公寓($2,22,222,2222$)
诸如此类。

无聊公寓的住户 $x$ 接听了电话，我们的角色不再给任何人打电话。

我们的主角想知道他总共按了多少个数字，而你的任务就是帮助他计算按键的总数。

例如，如果无聊公寓 $22$ 的居民回答，那么我们的字符称为公寓 $1,11,111,111,2,22$，他按下的总数字是 $1 + 2 + 3 + 4 + 1 + 2 = 13$。

输入格式

输入的第一行包含一个整数 $t$ ($1\leq t \leq3 6$)为测试用例数。

每组数据中唯一的一行输入包含一个整数 $x$($1\leq x \leq 9999$)，表示接电话的居民的公寓号。保证 $x$ 由相同的数字组成。

输出格式

对于每个测试用例，打印出答案: 我们的主角总共按了多少个数字。

题解

考虑到打到 $x$ 时，前面的所有数字的所有号码都被打了一遍即 $(c-1) \times 10$,其中 $c = x \bmod 10$。

当前这个数字被打了 $\dfrac {(cnt+1) \times cnt}{2}$，其中 $cnt$ 为 $x$ 的位数。

#include <bits/stdc++.h>
using namespace std;
int _, n;
void solve(int n) {
    int cnt = 0, m = n;
    while (m) {
        m /= 10;
        cnt++;
    }
    int c = n % 10;
    int ans = (cnt + 1) * cnt / 2;
    printf("%d\n", (c - 1) * 10 + ans);
}
int main() {
    for (scanf("%d", &_); _; _--) {
        scanf("%d", &n);
        solve(n);
    }
    return 0;
}

B.Yet Another Bookshelf

题目描述

有一个可以放下 $n$ 本书的书架。如果第 $i$ 个位置上有一本书，则 $a_i=1$，否则 $a_i=0$。保证书架上至少有一本书。

在一步中，你可以移动一些连续的段 $[l,r]$ 组成的图书(也就是说，对于每个 $i$ 从 $ l$ 到 $r$，满足 $a_i=1$)：

把它移到右边 $1$ 个：把所有的 $i(l\leq i\leq r)$ 号书移到 $i+1$ 。前提是当 $r+1 \leq n$ 而且 $r+1$ 上没有书
把它移到左边 $1$ 个：把所有的 $i(l \leq i \leq r)$ 号书移到 $i-1$ 。前提是当 $l-1 \leq n$ 而且 $r+1$ 上没有书

你的任务是找到一段连续的(即没有任何间隙的段)来收集书架上所有书籍所需的最小移动次数。

输入格式

输入的第一行包含一个整数 $t$($1≤ t ≤200$)为测试用例数。

测试用例的第一行包含一个整数 $n$($1≤ n ≤50$)书架上的位置数。测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$($0 \le a_i \le 1$) ，其中如果在这个位置有一本书，则 $a_i$ 为 $1$，否则为 $0$。保证书架上至少有一本书。

输出格式

对于每个测试用例，输出一个整数：用连续段(即没有间隙的段)收集书架上所有书所需的最小移动次数。

题解

如果有两个段作为不连续的段，它们之间的空隙我们总可以一步完成。

那么对于每一个记录的段，求出它与下一个段的长度，最后将这些 “空隙”长度加起来就是我们的答案。

#include <bits/stdc++.h>
using namespace std;
int _, n, a[55];
void solve(int n) {
    int last = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1 && !last) {
            last = i;
            continue;
        } else if (a[i] == 1) {
            ans += i - last - 1;
            last = i;
        }
    }
    printf("%d\n", ans);
}
int main() {
    for (scanf("%d", &_); _; _--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        solve(n);
    }
    return 0;
}

C.Dominant Piranha

题目描述

水族馆里有 $n$ 条大小分别为 $a_1, a_2, \ldots, a_n$ 的食人鱼，按照生活在水族馆的顺序从左到右编号。

伯兰州立大学的科学家们想要找出水族馆里是否有占优势的食人鱼。如果食人鱼能吃掉水族馆里所有的其他食人鱼(当然，除了它自己) ，它就被称为优势食人鱼。其他的食人鱼什么也不会做，而占优势的食人鱼会吃掉它们。

由于水族馆相当狭长，食人鱼在一次移动中只能吃掉邻近的一条食人鱼。食人鱼可以根据自己的需要(或尽可能)做任何动作。更确切地说:

食人鱼 $i$ 可以吃食人鱼 $i-1$ 当且仅当 $a_{i-1}<a_i$
食人鱼 $i$ 可以吃食人鱼 $i+1$ 当且仅当 $a_{i+1}<a_i$

在 $i$ 号食人鱼吃掉一条鱼后，它的体积会增大一 ($a_i \to a_i+1$)

你要找到占优势的任意一条食人鱼，如果没有，输出 $-1$

输入格式

输入的第一行包含一个整数 $t$($1 \le t \le 2 \cdot 10^4$)为测试用例数。

测试用例的第一行包含一个整数 $n$($2 \le n \le 3 \cdot 10^5$)水族馆里食人鱼的数量。测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$($1 \le a_i \le 10^9$) 。

输出格式

对于每个测试用例：如果没有一条占优势的鱼输出 $-1$，否则输出任意一条优势鱼的编号

题解

无解的情况很好判断，也就是全部相等。对于其他的情况，总是能确定一个唯一最大值（也可能是吃掉鱼后的唯一最大）。我的这个做法的正确性不能保证，是通过找到最大和次大两个进行判断的，不确定有没有数据能够卡掉 = =

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int _, n, a[N];
void solve(int n) {
    int last = 0, ans = 0, flag = 1, maxx = a[1], idx = 1, max2, idx2;
    for (int i = 1; i <= n; i++) {
        if (a[i] != a[1]) {
            flag = 0;
            if (maxx < a[i]) {
                max2 = maxx, idx2 = idx;
                maxx = a[i], idx = i;
            } else if (maxx > a[i]) {
                if (a[i - 1] == maxx) {
                    max2 = maxx, idx2 = idx;
                    maxx = a[i - 1], idx = i - 1;
                } else if (a[i + 1] == maxx) {
                    max2 = maxx, idx2 = idx;
                    maxx = a[i + 1], idx = i + 1;
                }
            }
        }
    }
    if (flag)
        printf("-1\n");
    else {
        if (idx - 1 >= 1) {
            if (a[idx - 1] < maxx) {
                printf("%d\n", idx);
                flag = 1;
            }
        }
        else if (idx + 1 <= n && !flag) {
            if (a[idx + 1] < maxx) {
                printf("%d\n", idx);
                flag = 1;
            }
        } else if (idx2 + 1 <= n && !flag) {
            if (a[idx2 + 1] < max2) {
                printf("%d\n", idx2);
                flag = 1;
            }
        } else if (idx2 - 1 >= 1 && !flag) {
            if (a[idx2 - 1] < max2) {
                printf("%d\n", idx2);
                flag = 1;
            }
        }
    }
}
int main() {
    for (scanf("%d", &_); _; _--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        solve(n);
    }
    return 0;
}

注意

不应该写成 a[idx-1]<maxx&&a[idx-1]>=1 可能访问负数下标

D. Districts Connection

题目描述

城市有 $n$ 个区域，第 $i$ 个区域属于 $a_i$ 号帮派，最初没有区域互相连接。

你的任务是建立 $n-1$ 条双向边使得区域间相互连通，任意一条边的两端不属于同一个帮派。

输入格式

输入的第一行包含一个整数 $t$($1 \le t \le 500$)为测试用例数。

测试用例的第一行包含一个整数 $n$($2 \le n \le 5000$)区域的数量。测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$($1 \le a_i \le 10^9$)表示 $i$ 号区域的归属。

输出格式

对于每一个测试用例：

如果不能连接输出一行字符串 NO
如果可以连接输出一行字符串 YES，接下来 $n-1$ 行分别输出 $n-1$ 条边，用点对 $x_i$ 和 $y_i$($1 \le x_i, y_i \le n; x_i \ne y_i$)表示。

题解

无解的情况很好判断，也就是全部相等。考虑至少有两个帮派的情况，将所有非 $a_1$ 的帮派控制的区域与 $a_1$ 相连，找到最后一个与 $a_1$ 相连的区域，将所有 $a_1$ 帮派控制的区域与其相连。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int x, y;
    Node() {}
    Node(int _x, int _y) { x = _x, y = _y; }
} p[5005];
int _, n, a[5005];
void solve(int n) {
    int cnt = 0, flag = 1, idx, idx2;
    for (int i = 1; i <= n; i++) {
        if (a[i] != a[1]) {
            flag = 0;
            break;
        }
    }
    if (flag)
        puts("NO");
    else {
        puts("YES");
        for (int i = 2; i <= n; i++) {
            if (a[i] != a[1])
                p[++cnt] = { 1, i }, idx = i;
        }
        for (int i = 2; i <= n; i++) {
            if (a[i] == a[1])
                p[++cnt] = { idx, i };
        }
        for (int i = 1; i <= cnt; i++) printf("%d %d\n", p[i].x, p[i].y);
    }
}
int main() {
    for (scanf("%d", &_); _; _--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        solve(n);
    }
    return 0;
}

注意

构造函数必须先考虑无参构造，否则会报错