Codeforces Round 382 (Div. 2) 题解

2016/11/28

A. Ostap and Grasshopper

没有技巧的签到题,没有技巧的爆搜。

 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
#include <bits/stdc++.h>
using namespace std;
int F[200];
int N, K;

int vis[200], Tgt;
bool search(int cur) {
    if(cur == Tgt) return true;
    vis[cur] = 1;
    if(cur-K >= 0 && !vis[cur-K] && !F[cur-K]) {
        if(search(cur-K)) return true;
    }

    if(cur-K < N && !vis[cur+K] && !F[cur+K]) {
        if(search(cur+K)) return true;
    }

    return false;
}

int main() {
    cin >> N >> K;
    string s; cin >> s;
    int siz = s.size();
    int S, T;
    for(int i=0;i<siz;i++) {
        switch(s[i]) {
        case '#': F[i] = 1; break;
        case '.': F[i] = 0; break;
        case 'G': S = i; break;
        case 'T': T = i; break;
        }
    }

    Tgt = T;
    cout << (search(S) ? "YES" : "NO") << endl;
}

B. Urbanization

靠猜就能做的贪心。 排序之后从大头开始取,先扔到 Cap 较小的城市里。

 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
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000 + 1000;
int N, N1, N2;
int W[MAX_N];

int main() {
    cin >> N >> N1 >> N2;
   
    if(N1 > N2) swap(N1, N2);

    for(int i=0;i<N;i++) {
        cin >> W[i];
    }

    sort(W, W+N, std::greater<int>());

    double ans = 0.0L;
    for(int i=0;i<N1;i++) {
        ans += double(W[i]) / N1;
    }

    int _ = N1 + N2;
    for(int i=N1;i<_;i++) {
        ans += double(W[i]) / N2;
    }

    printf("%.8lf \n", ans);
}

C. Tennis Championship

英语太差,题目都读不懂。 _(:3 」∠)__

大概就是说打淘汰赛,每个人已经打过的比赛为 C, 第 i 号选手只能和 abs(Ci - Cj) <= 1 的选手打比赛。

然后求冠军最多的打比赛次数。

正确做法就是 Fibonacci.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL F[100];

int main() {
    LL C; cin >> C;
    F[0] = 1; F[1] = 2;
    for(int i=2;i<=90;i++) F[i] = F[i-1] + F[i-2];
    
    int i = 2;
    while(C >= F[i])
        ++i;
    cout << i-1 << endl;
}

D. Taxes

这道题就是说将 n 拆成 k 个数 ( k 可以为 1 ) , 使得每个拆分后的数的 最大因子 相加最小。

看了下题解,正解是哥德巴赫猜想。

哥德巴赫猜想:
一个偶数可以是两个质数之和,
那么一个奇数 x 有三种情况:
1. x 本身是质数
2. (x-2) 是质数,那么可以拆成两个质数
3. 拆成一个质数和一个偶数,即三个质数

Orz

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;

bool isp(ULL x) {
    ULL _ = ceil(sqrt(x));
    for(ULL i=2;i<=_;i++) {
        if(x % i == 0) return false;
    }
    return true;
}

int main() {
    ULL x; cin >> x;
    if(x&1) { // Odd
        if(isp(x))        cout << "1" << endl;
        else if(isp(x-2)) cout << "2" << endl;
        else              cout << "3" << endl;
    } else { // Even
        if(x == 2) cout << "1" << endl;
        else       cout << "2" << endl;
    }
}

所以说还是要好好看数学结论。否则裸题都做不了。

E. Ostap and Tree

还没有写。 (,,•́ . •̀,,)