2019-08-08 17:40 已编辑苏州大学算法工程师

关注

2018 China Collegiate Programming Contest Final (CCPC-Final 2018)

A. Mischievous Problem Setter

Description:

Mr. Sheep is participating in a programming contest. Mr. Panda, the mischievous problem setter gives him some “hints” on the difficulty level of the problems. As problem solving time matters for contestants who solve the same number of problems, it’s always wise to solve from easiest to hardest problems.

Unfortunately, one man’s meat is another man’s poison. People can have different opinions on the difficulty level of the problems. Especially for Mr. Panda, who always underestimates the difficulty level for hard problems, as all problems are considered easy for him…

There are N problems in the contest and the contest will last for M minutes. The $i^{t h}$ problem has an estimated difficulty $D_{i}$ by Mr. Panda, and it costs Mr. Sheep $T_{i}$ minutes to solve. Mr.Sheep always solves problems in increasing order of difficulty (i.e., from the easiest problem to the hardest problem estimated by Mr. Panda). How many problems will Mr. Sheep solve at the end of the contest?

Input:

The first line of the input gives the number of test cases, $T (1 \leq T \leq 20)$ . T test cases follow.

For each test case, the first line contains two integers $N (1 \leq N \leq 1 0^{5})$ and $M (1 \leq M \leq 1 0^{5})$ , where $N$ is the number of problems in the contest and $M$ is the length of the contest in minutes.

The next line contains $N$ distinct integers $D_{1}, D_{2}, . . ., D_{N} (1 \leq D_{i} \leq 1 0^{5})$ representing the difficulty levels estimated by the problem setter.

The following line contains $N$ integers $T_{1}, T_{2}, . . ., T_{N} (1 \leq T_{i} \leq 1 0^{5})$ representing the actual time (in minutes) it costs for Mr. Sheep to solve the problems.

Output:

For each test case, output one line containing “Case x: y”, where x is the test case number (starting from

and y is the number of problems solved by Mr. Sheep after the contest ends.

Sample Input:

2
5 120
5 10 20 35 100
10 20 35 100 100000
13 300
52 55 82 11 62 79 38 8 58 28 1 70 32
27 62 45 77 22 69 34 43 21 43 85 22 36

Sample Output:

Case 1: 3
Case 2: 5

题目链接

$n$ 道题目每个题目有两个属性：难度，解决用时，只能按照难度递增顺序做题，求 $m$ 分钟内解体数量

按照难度排序，由于不能跳题，所以直接对每道题目用时求和判断即可

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int t; cin >> t;
    for (int Case = 1; Case <= t; ++Case) {
        int n, m; cin >> n >> m;
        vector<pair<ll, ll>> arr(n);
        for (auto &it : arr) cin >> it.first;
        for (auto &it : arr) cin >> it.second;
        sort(arr.begin(), arr.end(), [&](pair<ll, ll> k1, pair<ll, ll> k2) {return k1.first < k2.first;});
        ll sum = 0, ans = 0;
        for (auto &it : arr) {
            if (sum + it.second <= m) {
                sum += it.second;
                ans++;
            }
            else break;
        }
        cout << "Case " << Case << ": " << ans << endl;
    }
    return 0;
}

G. Pastoral Life in Stardew Valley

Description:

Mr. Panda and Mrs. Panda is bored of the hustle and bustle of city life. They decide to make a change. They drop everything they belong to and move to a place where they can find real connections with people and nature. Here in Stardew Valley, they start their life as farmers. They are now embarking on tasks of reclaiming wastelands, sowing seeds, and planting trees.

They are now looking for a rectangle area from the reclaimed wasteland to cultivate their first crop. To prevent crops being damaged by annoying crows, they place several scarecrows inside this rectangle area. The scarecrows occupy a rectangle area that is surrounded by the crops. The wasteland is of $N$ rows and $M$ columns. They wonder how many different ways to pick a rectangle area and place crops and scarecrows inside the rectangle. As the number can be large, return the answer modulo $1 0^{9} + 7$ .

Input:

The first line of input gives the number of test cases $T$ ( $1 \leq T \leq 1 0^{5}$ ). $T$ test cases follow. Each test case starts with a line consisting of two integers $N$ , $M$ ( $1 \leq N, M \leq 1 0^{5}$ ), the number of rows and columns of the wasteland.

Output

For each test case, output one line containing “Case x: y”, where x is the test case number (starting from $1$ ) and y is the number of different ways to place the crops and scarecrows, modulo $1 0^{9} + 7$ .

Sample Input:

3
2 3
3 3
4 4

Sample Output:

Case 1: 0
Case 2: 1
Case 3: 25

题目链接

在 $n \times m$ 的棋盘上选择两个长方形使一个长方形完全包含另一个长方形，求方案数

先考虑选择两个长方形的宽

例如在 $1 \times n$ 的棋盘中选择两个长方形就有 $C_{n}^{3} + C_{n}^{4}$ 种选法

例如在如图 $1 \times 9$ 的棋盘上选则两个长方形就会选择四个方格来分别代表大小长方形的左右边界，其中最左最右的两个方格（如图 $A 、 B$ 方格）代表大长方形的边界，中间的两个方格（如图 $C 、 D$ 方格）代表小长方形的边界，所以这样选法就为 $C_{9}^{4}$ （在 $9$ 个方格种选出四个方格），还有另一种小长方形只占一个方格的情况，即只用选出三个方格中间的方格代表小长方形，这种情况共有 $C_{9}^{3}$ 种，这样就可以把大小长方形的宽统计完了

大小长方形高的统计方法同理，最后把两个结果相乘即为最终结果

注意特判 $n < 3$ 和 $m < 3$ 的情况

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

ll C[maxn][5];

void Init() {
    C[0][0] = 1;
    for (int i = 1; i < maxn; ++i) {
        C[i][0] = 1;
        for (int j = 1; j < 5; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    Init();
    int t; cin >> t;
    for (int Case = 1; Case <= t; ++Case) {
        int n, m; cin >> n >> m;
        if (n < 3 || m < 3) {
            cout << "Case " << Case << ": " << 0 << endl;
            continue;
        }
        cout << "Case " << Case << ": " << ((C[n][3] + C[n][4]) % mod) * ((C[m][3] + C[m][4]) % mod) % mod << endl;
    }
    return 0;
}

I. Cockroaches

Description:

There are $N$ cockroaches in the field. Cockroach $i$ is located at coordinate $(x_{i}, y_{i})$ . No two cockroaches are located at the same spot. Boss Luo has a powerful pesticide that can instantly kill all cockroaches on the horizontal and vertical line of the spot where it is used. i.e. cockroaches with either the same x coordinate or y coordinate as the pesticide spot will be killed.
Boss Luo wonders how many cockroaches can be killed at most when the pesticide is used in one spot. He is also interested in the number of different subsets of the annihilated cockroaches when the pesticide kills most cockroaches.

Input:

The first line of the input gives the number of test cases, $T$ ( $1 \leq T \leq 100$ ). $T$ test cases follow.
For each test case, the first line contains an integers $N$ ( $1 \leq N \leq 1 0^{5}$ ), the number of cockroaches.
The next $N$ lines each contains two integers $x$ and $y$ ( $1 \leq x, y \leq 1 0^{9}$ ), describing the coordinates of the cockroaches.
For at least 80 test cases, it is guaranteed that $N \leq 5 000$ .

Output

For each test case, output one line containing “Case x: y z”, where x is the test case number (starting from $1$ ), y is the maximum number of cockroaches that can be killed with pesticide applied on one spot, and z is the number of different subsets of the annihilated cockroaches when the pesticide kills most cockroaches.

Sample Input:

2
5
1 2
1 3
2 3
4 5
6 7
3
1 2
2 3
3 1

Sample Output:

Case 1: 3 5
Case 2: 2 3

题目链接

在平面直角坐标系上有 $n$ 个蟑螂（编号为 $[1, n]$ ），现你可以指定坐标系上的任意一个点，和其横坐标或纵坐标相同的蟑螂全部被消灭，求出消灭最多蟑螂的集合种类数

先特判 $1$ 个点和 $n$ 个点横纵坐标都互不相同的情况

之后消灭最多蟑螂有两种情况（设同一横坐标下最多点数为 $b e s t_x$ ，同一纵坐标下最多点数为 $b e s t_y$ ）

$b e s t_x$ 所在的 $x$ 与 $b e s t_y$ 所在的 $y$ 的交点上有 $n$ 个点其中一点
$b e s t_x$ 所在的 $x$ 与 $b e s t_y$ 所在的 $y$ 的交点上无 $n$ 个点其中一点

统计两种情况的数量即可

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    ll t; cin >> t;
    for (ll Case = 1; Case <= t; ++Case) {
        ll n; cin >> n;
        pair<ll, ll> ans;
        vector<pair<ll, ll>> p(n);
        map<ll, ll> cnt_x, cnt_y;
        ll best_x = 0, best_y = 0;
        for (auto &it : p) {
            cin >> it.first >> it.second;
            best_x = max(best_x, ++cnt_x[it.first]);
            best_y = max(best_y, ++cnt_y[it.second]);
        }

        if (cnt_x.size() == 1 || cnt_y.size() == 1) {
            cout << "Case " << Case << ": " << n << " " << 1 << endl;
            continue;
        }
        if (best_x == 1 && best_y == 1) {
            cout << "Case " << Case << ": " << 2 << " " << n * (n - 1) / 2 << endl;
            continue;
        }

        ll cnt_x_1 = 0, cnt_x_2 = 0, cnt_y_1 = 0, cnt_y_2 = 0;
        for (auto &it : cnt_x) {
            if (it.second == best_x) cnt_x_1++;
            else if (it.second == best_x - 1) cnt_x_2++;
        }
        for (auto &it : cnt_y) {
            if (it.second == best_y) cnt_y_1++;
            else if (it.second == best_y - 1) cnt_y_2++;
        }

        ll best = best_x + best_y;
        ll cnt_1 = cnt_x_1 * cnt_y_1, cnt_2 = cnt_x_1 * cnt_y_2 + cnt_x_2 * cnt_y_1;
        for (auto &it : p) {
            int cnt = cnt_x[it.first] + cnt_y[it.second];
            if (cnt == best) {
                cnt_1--;
                cnt_2++;
            }
            else if (cnt == best - 1) cnt_2--;
        }

        if (cnt_1 > 0) cout << "Case " << Case << ": " << best << " " << cnt_1 << endl;
        else cout << "Case " << Case << ": " << best - 1 << " " << cnt_2 << endl;
    }
    return 0;
}

L. Ultra Weak Goldbach’s Conjecture

Description:

In number theory, Goldbach’s conjecture states that every even integer greater than $2$ is the sum of two prime numbers. A weaker version of this conjecture states that every odd number greater than $5$ is the sum of three prime numbers.
Here is an ultra weak version of Goldbach’s conjecture: every integer greater than $11$ is the sum of $<mtext mathvariant="bold"> six </mtext>$ prime numbers. Can you help to verify or disprove this conjecture?

Input:

The first line of the input gives the number of test cases, $T$ ( $1 \leq T \leq 200$ ). $T$ test cases follow.
Each test case contains one integer $N$ ( $1 \leq N \leq 1 0^{12}$ ).

Output

For each test case, output “Case x:” first, where x is the test case number (starting from $1$ ). If the solution exist, output six prime numbers separated by spaces; otherwise output “IMPOSSIBLE” (quotes for clarity) when the solution does not exist. When the solution exists, any valid solution is acceptable.

Sample Input:

5
6
13
200
570
680

Sample Output:

Case 1: IMPOSSIBLE
Case 2: 2 2 2 2 2 3
Case 3: 43 29 31 29 31 37
Case 4: 97 101 103 107 101 61
Case 5: 137 137 107 113 89 97

题目链接

将一个数 $n$ 分解为 $6$ 个素数之和

首先特判小于等于 $11$ 的数肯定无法分解（题目也说了）

对于每个大于 $11$ 的 $n$ 进行分解，有两种情况

若 $n$ 为偶数，则其可以分为 $2$ $2$ $2$ $2$ 和 $n - 8$ ，由于 $n$ 为偶数，则 $n - 8$ 也一定为偶数，所以 $n - 8$ 一定可以分解为两个素数之和
若 $n$ 为奇数，则其可以分为 $2$ $3$ $2$ $2$ 和 $n - 9$ ，由于 $n$ 为奇数，则 $n - 9$ 一定为偶数，所以 $n - 9$ 一定可以分解为两个素数之和

现在只用考虑将一个偶数分解为两个素数之和

那么对素数表中的素数暴力枚举判断剩下的 $n$ 减去素数之后是否为素数就可以了

由于 $n$ 的数据范围较大，所以判定素数的时候就不能用素数表，我这里直接暴力判断就过了

如果会 $M i l l e r - R a b i n$ 的话还是码上比较保险

AC代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e8 + 5;
typedef long long ll;

bool isPrime[maxn];
vector<int> prime;

bool _isPrime(ll key) {
    for (ll i = 2; i * i <= key; ++i) {
        if (key % i == 0) return false;
    }
    return true;
}

void _sieve() {
    memset(isPrime, true, sizeof(isPrime));
    for (ll i = 2; i < maxn; ++i) {
        if (isPrime[i]) {
            prime.push_back(i);
            for (ll j = i * i; j < maxn; j += i) isPrime[j] = false;
        }
    }
}

void _solve(ll x) {
    for (auto &p : prime) {
        if (_isPrime(x - p)) {
            cout << p << " " << x - p << endl;
            break;
        }
    }
}

int main() {
    _sieve();
    int t; cin >> t;
    for (int Case = 1; Case <= t; ++Case) {
        ll n; cin >> n;
        cout << "Case " << Case << ": ";
        if (n < 12) {
            cout << "IMPOSSIBLE" << endl;
            continue;
        }
        if (n & 1) {
            cout << 2 << " " << 3 << " " << 2 << " " << 2 << " ";
            n -= 9;
        }
        else {
            cout << 2 << " " << 2 << " " << 2 << " " << 2 << " ";
            n -= 8;
        }
        _solve(n);
    }
    return 0;
}