Codeforces Round 458 题解

2018/01/26

我(文化课)成历史最菜了。

考虑到明天考试,今天做题冷静一下。

A. Perfect Squares

之前和 icecathy 学姐讨论过浮点库的问题…… 比方说 sqrt() 能跑多少次

1
2
for(int i=1;i<SIZE;i++)
    sqrt(float(i));

这段代码在我的 Ryzen 1700 默频下一秒可以跑 2e8

保守估计 CCF 老爷机慢一百倍,也能跑 2e6 每秒,很稳。

当然这道题就暴力了。

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <functional>
#include <cmath>
using namespace std;

int N;

int main() {
    scanf("%d", &N);
    vector<int> v; v.reserve(N);
    
    for(int i=0, x;i<N;i++) {
        scanf("%d", &x);
        v.push_back(x);
    }
    
    sort(v.begin(), v.end(), greater<int>());
    
    for(int x : v) {
        int p = ceil(sqrt(x));
        
        if(p * p != x) { printf("%d\n", x); return 0; }
    }
    
    puts("-1");
}

B. Conan and Agasa play a Card Game

考虑每个数出现次数的奇偶性,可以证明序列上存在一个出现奇数次的数,等价于 Conan 赢。

他只要第一次取最大的出现次数为奇数的数即可,后面不论怎么取都是一个偶数张牌的局,Agasa 一定输。

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
typedef pair<int, int> pii;

int N;
map<int, int> LUT;

int main() {
    scanf("%d", &N);
    
    for(int i=0, x;i<N;i++) {
        scanf("%d", &x);
        LUT[x]++;
    }
    
    vector<pii> v(LUT.begin(), LUT.end());
    
    for(int i=v.size()-1;i>=0;i--) {
        if(v[i].second & 1) {
            puts("Conan"); return 0;
        }
    }
    
    puts("Agasa");
}

C. Travelling Salesman and Special Numbers

这题真是报警,看 main 函数最前面几行全是特判。

二合一场的题都好坑啊。

不难想到 数位DP 的做法,然后你会发现每个 DP值 的含义就是组合数,所以连转移方程都不用推了。

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int SIZ = 1057;
const int MOD = 1e9 + 7;

int L;
char buf[SIZ];
int num[SIZ];
int C[SIZ][SIZ];

int cnt[SIZ];

void dp() {
    C[0][0] = 1; C[1][0] = C[1][1] = 1;
    for(int i=2;i<=1007;i++) {
        C[i][0] = 1;
        for(int j=1;j<=i;j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
    
    int popcnt = 0;
    for(int i=L;i;i--) {
        if(num[i]) {
            for(int j=0;j<=i;j++) {
                cnt[j + popcnt] = (cnt[j + popcnt] + C[i-1][j]) % MOD;
            }
        }
        
        popcnt += num[i];
    }
}

int popcnt(int x) {
    #ifdef __GNUC__
    return __builtin_popcount(x);
    #else
    int ret = 0;
    while(x) {
        ret++;
        x -= x & (-x);
    }
    return ret;
    #endif
}

int count(int x) {
    int ret = 0;
    while(x != 1) {
        ret++;
        x = popcnt(x); 
    }
    
    return ret;
}

int main() {
    int K;
    scanf("%s %d", buf + 1, &K);
    L = strlen(buf + 1);
    
    if(K == 0) {
        if(L == 1 && buf[1] == '0') {
            puts("0");
        } else {
            puts("1");
        }
        
        return 0;
    }
    
    int qwq = 0;
    for(int i=1;i<=L;i++) {
        num[L - i + 1] = buf[i] - '0';
        if(num[L - i + 1]) qwq++; 
    }
    
    dp();
    
    int ans = 0;
    for(int i=1;i<SIZ;i++) {
        if(count(i) == K-1)
            ans = (ans + cnt[i]) % MOD;
    }
    
    if(count(qwq) == K-1)
        ans++;
    
    if(K == 1) ans--;
    
    printf("%d\n", ans);
}

D, E, F, G, H……

还没写