队内训练赛-2023-11-2题解

A-Rigged!

题面翻译

Sp 组织了一次举重比赛，有 $n$ 个运动员参加了比赛。其中每个运动员的力量为 $s_i$ ，耐力为 $e_i$ 。编号为 $1$ 的运动员是 SA，Sp 希望 SA 赢得比赛。

第 $i$ 名运动员无法举起重量 $w$ 严格大于他的力量 $s_i$ 的杠铃，否则如果他能举起，他将举起 $e_i$ 次。举重比赛的获胜者为所有可以举起杠铃的人中举起次数最多的人。如果有多个，则没有获胜者。

Sp 希望 SA 成为获胜者，请确定一个杠铃重量 $w$ 使得 SA 成为获胜者。

Translated by Shunpower.

题目描述

Monocarp organizes a weightlifting competition. There are $n$ athletes participating in the competition, the $i$ -th athlete has strength $s_i$ and endurance $e_i$ . The $1$ -st athlete is Monocarp’s friend Polycarp, and Monocarp really wants Polycarp to win.

The competition will be conducted as follows. The jury will choose a positive (greater than zero) integer $w$ , which denotes the weight of the barbell that will be used in the competition. The goal for each athlete is to lift the barbell as many times as possible. The athlete who lifts the barbell the most amount of times will be declared the winner (if there are multiple such athletes — there’s no winner).

If the barbell’s weight $w$ is strictly greater than the strength of the $i$ -th athlete $s_i$ , then the $i$ -th athlete will be unable to lift the barbell even one single time. Otherwise, the $i$ -th athlete will be able to lift the barbell, and the number of times he does it will be equal to his endurance $e_i$ .

For example, suppose there are $4$ athletes with parameters $s_1 = 7, e_1 = 4$ ; $s_2 = 9, e_2 = 3$ ; $s_3 = 4, e_3 = 6$ ; $s_4 = 2, e_4 = 2$ . If the weight of the barbell is $5$ , then:

the first athlete will be able to lift the barbell $4$ times;
the second athlete will be able to lift the barbell $3$ times;
the third athlete will be unable to lift the barbell;
the fourth athlete will be unable to lift the barbell.

Monocarp wants to choose $w$ in such a way that Polycarp (the $1$ -st athlete) wins the competition. Help him to choose the value of $w$ , or report that it is impossible.

输入格式

The first line contains one integer $t$ ( $1 \le t \le 100$ ) — the number of test cases.

The first line of each test case contains one integer $n$ ( $2 \le n \le 100$ ) — the number of athletes. Then $n$ lines follow, the $i$ -th of them contains two integers $s_i$ and $e_i$ ( $1 \le s_i \le 10^9$ ; $1 \le e_i \le 100$ ) — the strength and the endurance of the $i$ -th athlete.

输出格式

For each test case, print the answer as follows:

if the answer exists, print one integer — the value of $w$ meeting the constraints. The integer you print should satisfy $1 \le w \le 10^9$ . It can be shown that if the answer exists, at least one such value of $w$ exists as well. If there are multiple answers, you can print any of them;
otherwise, print one integer $-1$ .

样例 #1

样例输入 #1

样例输出 #1

5
-1
-1

提示

The first test case of the example is described in the statement.

Problem - A - Codeforces
Rigged! - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

这题是一道多答案的题，所以说，结果和样例不一样也没关系。这题我们就假设第一个人举起来的重量刚好就是答案，枚举其他人能举起的重量，如果有比第一个人还强的人，那题目无解。

C++代码

#include <iostream>
using namespace std;
void solve() {
    int n;
    cin >> n;
    int s[n], e[n];
    for(auto &&i = 0; i < n; ++i)
        cin >> s[i] >> e[i];
    int w = s[0], times = e[0];
    bool isHasAns = false;
    for(auto &&i = 1; i < n; ++i) 
        if(s[i] >= w and e[i] >= times)
           isHasAns = true; 
    cout << (isHasAns ? -1 : w) << endl; 
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B-The World is a Theatre

题面翻译

题目描述

有n个男孩和m个女孩参加了一个戏剧俱乐部，为了上演一场
名叫“生活大爆炸”的戏剧，他们需要选择t人，保证其中至少4个男孩和1个女孩。问有多少种选择方式。

当然，只有选择不同的男生或女生的选择方式才算不同，换句话说，若方案a选了男生1,2,3,4，女生1,2，而方案b选了男生4,3,2,1，女生2,1，这两种情况是等价的。

注意，C++开longlong，Delphi和Java开int64。

输入格式

只有一行，包括三个整数 $n,m,t (4 \leq n \leq 30,1 \leq m \leq 30,5 \leq t \leq n+m)$

输出格式

输出总的方案数
不要用%lld读入或输出 $C++64$ 位整数，请使用 $cin$ ， $cout$ ，%I64d

题目描述

There are $n$ boys and $m$ girls attending a theatre club. To set a play “The Big Bang Theory”, they need to choose a group containing exactly $t$ actors containing no less than 4 boys and no less than one girl. How many ways are there to choose a group? Of course, the variants that only differ in the composition of the troupe are considered different.

Perform all calculations in the 64-bit type: long long for С/С++, int64 for Delphi and long for Java.

输入格式

The only line of the input data contains three integers $n$ , $m$ , $t$ ( $4 \leq n \leq 30,1 \leq m \leq 30,5 \leq t \leq n+m$ ).

输出格式

Find the required number of ways.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

样例 #1

样例输入 #1

5 2 5

样例输出 #1

样例 #2

样例输入 #2

4 3 5

样例输出 #2

提示

Problem - B - Codeforces
The World is a Theatre - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

这就是一道简单的高中数学题啦，排列组合。我们只要实现 $C_m^n$ 就好了

C++代码

#include <iostream>
using namespace std;
using i128 = unsigned __int128;
std::istream &operator>>(std::istream &is, i128& value) {
    value = 0;
    bool isNegative = false;
    char c = cin.get();
    while(c < '0' or c > '9') {
        if(c == '-')
            isNegative = true;
        c = cin.get();
    }
    while(c >= '0' and c <= '9') {
        value = (value << 3) + (value << 1) + (c ^ '0');
        c = cin.get();
    }
    if(isNegative)
        value = -value;
    return is;
}
std::ostream &operator<<(std::ostream &os, i128 value) {
    if(value < 0) {
        value = ~value + 1;
        os.put('-');
    }
    if (value > 9)
        os << value / 10;
    os.put((value % 10) ^ '0');
    return os;
}
i128 a(i128 up, i128 down) {
    if (up == 0)
        return 1;
    return down * a(up - 1, down - 1);
}
i128 c(i128 up, i128 down) {
    up = min(up, down - up);
    if (up == 0)
        return 1;
    return a(up, down) / a(up, up);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, t;
    i128 ans{0};
    cin >> n >> m >> t;
    for (int i = max(t - m, 4); i <= min(t - 1, n); ++i)
        ans += c(i, n) * c(t - i, m);
    cout << ans;
    return 0;
}

C-Easter Eggs

题面翻译

复活节兔子把n个蛋围成了一个圆圈。她打算给它们上色。

每一个蛋都要被涂上红橙黄绿蓝靛紫七色中的一个颜色，并满足如下条件：

1、每一种颜色都必须用上

2、任何四个相连的蛋都要涂上不同的颜色。

帮助复活节兔子涂上颜色，当然，这肯定是有解的！

输入：

一行： $n（7 \leq n \leq 100）$

输出：

一行：用下列字符表示所涂上的颜色：R（红red），O（橙orange），Y（黄：yellow），G（绿green），B（蓝blue），I（靛indigo），V（紫violet）

注意：如果存在多个答案，输出其中一种即可

感谢 @233 提供的翻译。

题目描述

The Easter Rabbit laid $n$ eggs in a circle and is about to paint them.

Each egg should be painted one color out of 7: red, orange, yellow, green, blue, indigo or violet. Also, the following conditions should be satisfied:

Each of the seven colors should be used to paint at least one egg.
Any four eggs lying sequentially should be painted different colors.

Help the Easter Rabbit paint the eggs in the required manner. We know that it is always possible.

输入格式

The only line contains an integer $n$ — the amount of eggs ( $7 \leq n \leq 100$ ).

输出格式

Print one line consisting of $n$ characters. The $i$ -th character should describe the color of the $i$ -th egg in the order they lie in the circle. The colors should be represented as follows: “R” stands for red, “O” stands for orange, “Y” stands for yellow, “G” stands for green, “B” stands for blue, “I” stands for indigo, “V” stands for violet.

If there are several answers, print any of them.

样例 #1

样例输入 #1

样例输出 #1

ROYGRBIV

样例 #2

样例输入 #2

样例输出 #2

ROYGBIVGBIVYG

提示

The way the eggs will be painted in the first sample is shown on the picture:

Problem - C - Codeforces
Easter Eggs - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

思维题，画图出来分类讨论答案就出来了

C++代码

#include <iostream>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k = (cin >> n, n / 7);
    string s[]{"","G", "YG","OYG","ROYG","GROYG","YGROYG"};
    for(int &&i = 0; i < k; ++i)
        cout << "ROYGBIV";
    cout << s[n%7];
    return 0;
}

D-Rumor

题面翻译

有 $n$ 个人，其中有 $m$ 对朋友，现在你有一个秘密你想告诉所有人，第 $i$ 个人愿意出价 $a_i$ 买你的秘密，获得秘密的人会免费告诉它的所有朋友（他朋友的朋友也会免费知道），现在他们想出最少的价钱买秘密，那么你最少能得到多少钱？

题目描述

Vova promised himself that he would never play computer games… But recently Firestorm — a well-known game developing company — published their newest game, World of Farcraft, and it became really popular. Of course, Vova started playing it.

Now he tries to solve a quest. The task is to come to a settlement named Overcity and spread a rumor in it.

Vova knows that there are $n$ characters in Overcity. Some characters are friends to each other, and they share information they got. Also Vova knows that he can bribe each character so he or she starts spreading the rumor; $i$ -th character wants $c_{i}$ gold in exchange for spreading the rumor. When a character hears the rumor, he tells it to all his friends, and they start spreading the rumor to their friends (for free), and so on.

The quest is finished when all $n$ characters know the rumor. What is the minimum amount of gold Vova needs to spend in order to finish the quest?

Take a look at the notes if you think you haven’t understood the problem completely.

输入格式

The first line contains two integer numbers $n$ and $m$ ( $1\leq{n}\leq{10^{5}},0\leq{m}\leq{0^{5}}$ ) — the number of characters in Overcity and the number of pairs of friends.

The second line contains $n$ integer numbers $c_{i}$ ( $0\leq{c_{i}}\leq{10^{9}}$ ) — the amount of gold $i$ -th character asks to start spreading the rumor.

Then $m$ lines follow, each containing a pair of numbers ( $x_{i},y_{i}$ ) which represent that characters $x_{i}$ and $y_{i}$ are friends ( $1\leq{x_{i}},y_{i}\leq{n}$ ， $x_{i}≠y_{i}$ ). It is guaranteed that each pair is listed at most once.

输出格式

Print one number — the minimum amount of gold Vova has to spend in order to finish the quest.

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

10 0
1 2 3 4 5 6 7 8 9 10

样例输出 #2

样例 #3

样例输入 #3

10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10

样例输出 #3

提示

In the first example the best decision is to bribe the first character (he will spread the rumor to fourth character, and the fourth one will spread it to fifth). Also Vova has to bribe the second and the third characters, so they know the rumor.

In the second example Vova has to bribe everyone.

In the third example the optimal decision is to bribe the first, the third, the fifth, the seventh and the ninth characters.

Problem - E - Codeforces
Rumor - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

这题的朋友关系就是一个连通块问题，DFS涂色或者并查集都可以解决连通块问题，但是这道题很明显应该使用并查集，简单，优雅

C++代码

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
using i64 = long long;
class UnionFindSet {
    vector<i64> tree, size;
  public:
    UnionFindSet(const i64 &n) : tree(n), size(n, 1) {
        iota(tree.begin(), tree.end(), 0);
    }
    i64 find(const i64 &x) {
        return x == tree[x] ? x : tree[x] = find(tree[x]);
    }
    void unite(const i64 &x, const i64 &y) {
        i64 &&fx = find(x), &&fy = find(y);
        if (fx == fy)
            return;
        if (size[fx] > size[fy])
            swap(fx, fy);
        tree[fx] = fy;
        size[fy] += size[fx];
    }
    bool isAlone(const i64 &x) { return size[find(x)] == 1; }
};
struct value {
    i64 v, index;
    bool operator<(const value &other) { return v < other.v; }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    i64 n, m, count = 0;
    cin >> n >> m;
    value arr[n];
    vector<bool> vis(n + 1, false);
    for (i64 &&i = 0; i < n; ++i) {
        cin >> arr[i].v;
        arr[i].index = 1 + i;
    }
    UnionFindSet ufs(n + 1);
    for (i64 &&i = 0, x, y; i < m; ++i) {
        cin >> x >> y;
        ufs.unite(x, y);
    }
    sort(arr, arr + n);
    for (auto &&i : arr)
        if (not vis[ufs.find(i.index)]) {
            count += i.v;
            vis[ufs.find(i.index)] = true;
        }
    cout << count;
    return 0;
}

E-K-Dominant Character

题面翻译

题目描述：
您将得到一个全部由小写拉丁字母组成的字符串 $s$ ，当且仅当对于每个长度不小于 $k$ 的 $s$ 的子串都含有字符 $c$ （ $c$ 指某个小写拉丁字母），那么我们称 $c$ 为 $k-主导字符$ 。
您需要给出一个最小的 $k$ ，使得对于给定的 $s$ 至少存在一个 $k-主导字符$ 。

输入格式：
仅一行
第一行给出一个字符串 $s（1 \leq s的长度 \leq 10^5）$ 。

输出格式：
输出一个数字 $k$ ，使得对于之前给定的 $s$ 至少存在一个 $k-主导字符$ 。

题目描述

You are given a string $s$ consisting of lowercase Latin letters. Character $c$ is called $k$ -dominant iff each substring of $s$ with length at least $k$ contains this character $c$ .

You have to find minimum $k$ such that there exists at least one $k$ -dominant character.

输入格式

The first line contains string $s$ consisting of lowercase Latin letters ( $1<=|s|<=100000$ ).

输出格式

Print one number — the minimum value of $k$ such that there exists at least one $k$ -dominant character.

样例 #1

样例输入 #1

abacaba

样例输出 #1

样例 #2

样例输入 #2

zzzzz

样例输出 #2

样例 #3

样例输入 #3

abcde

样例输出 #3

提示

Problem - E - Codeforces
K-Dominant Character - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

这题可以通过二分的方法来求得k值，左边界就是1，右边界是字符串的长度。check模拟计算是否满足条件即可

C++代码

#include <algorithm>
#include <iostream>
using namespace std;
string s;
bool check(const int &w) {
    int cnt[26]{}, vis[26]{};
    for (auto &&i = 0; i < w; ++i)
        ++cnt[s[i] - 'a'];
    for(auto &&i = 0; i < 26; ++i)
        if(cnt[i])
            ++vis[i];
    for(auto i = w; i < s.length(); ++i) {
        cnt[s[i-w] - 'a']--;
        cnt[s[i] - 'a']++;
        for (auto &&j = 0; j < 26; ++j)
            if(cnt[j])
                vis[j]++;
    }
    return *max_element(vis, vis + 26) != s.length() - w + 1;
}
int binary_search_ans(int l, int r) {
    while (l < r) {
        auto &&mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1;
        else
            r = mid;
    }
    return l;
}
int main() {
    cin >> s;
    cout << binary_search_ans(1, s.length());
    return 0;
}

F-Nearly Lucky Number

题面翻译

题目要求

如果一个数仅包含 $4$ 和 $7$ ，那么它就是一个"幸运数字"。
如果一个数本身不是幸运数，但是它所含有的数字4和7的个数之和为一个"幸运数字"，那么它就是一个"类幸运数字"。
给您一个数，请编程判断它是不是"类幸运数字"。

输入格式

一行一个整数 $N$ (N在64位整数(long long / int64)范围内)。

输出格式

一行一个字符串，如果N是"类幸运数字"则输出"YES"，否则输出"NO"。

感谢@PC_DOS 提供翻译

题目描述

Petya loves lucky numbers. We all know that lucky numbers are the positive integers whose decimal representations contain only the lucky digits $4$ and $7$ . For example, numbers $47, 744, 4$ are lucky and $5, 17, 467$ are not.

Unfortunately, not all numbers are lucky. Petya calls a number nearly lucky if the number of lucky digits in it is a lucky number. He wonders whether number $n$ is a nearly lucky number.

输入格式

The only line contains an integer $n$ ( $1\leq n\leq10^{18}$ ).

Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

输出格式

Print on the single line “YES” if $n$ is a nearly lucky number. Otherwise, print “NO” (without the quotes).

样例 #1

样例输入 #1

样例输出 #1

NO

样例 #2

样例输入 #2

样例输出 #2

YES

样例 #3

样例输入 #3

1000000000000000000

样例输出 #3

NO

提示

In the first sample there are 3 lucky digits (first one and last two), so the answer is “NO”.

In the second sample there are 7 lucky digits, 7 is lucky number, so the answer is “YES”.

In the third sample there are no lucky digits, so the answer is “NO”.

Problem - F - Codeforces
Nearly Lucky Number - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

这题应该是签到题才对，但是好像没啥人做，直接暴力模拟就能过了

C++代码

#include <iostream>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    long long sum{}, t;
    for (auto &&i : s)
        if (i == '4' or i == '7')
            sum++;
    if (sum == 0) {
        cout << "NO";
        return 0;
    }
    for (; sum; sum /= 10) {
        t = sum % 10;
        if (t != 4 and t != 7) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}

题解

#模拟 #二分答案 #数学 #前缀和 #贪心

队内训练赛-2023-11-2题解

https://winterl-blog.netlify.app/2023/11/03/队内训练赛-2023-11-2题解/

作者

winterl

发布于

2023年11月3日

许可协议

洛谷P2440 木材加工上一篇

NCST-暑期基础培训-第四周排位赛-题解下一篇