kick start 2018 Round A

Posted on | In | 阅读
  1. Even Digits
  2. Lucky Dip
  3. Scrambled Words

  1. Even Digits

    给一个数，找离他最近的不包含奇数位的数。

    思路：从左到右找第一个奇数，首先判断是要找比他大的数还是比他小的数（+1还是-1）。这取决于后面的数以及这位数的情况。

    如果这位数位9，一定是找比他小的，因为+1将会造成进位，高位为了保持偶数需要进两位，肯定比-1要大。

    如果后面的数小于4444……（字典序比较一下），则找比他小的，奇数位-1，后面改成8888……

    如果后面的数大于4444……，则找比他大的，奇数位+1（不是9，不会进位），后面改成0000……

    最后相减获得答案

C++ Code

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
96
97
98
99
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <string.h>

using std::cin;
using std::cout;
using std::endl;
using std::string;

bool judge(char* ch, int pos, int len) {
    for(int i = pos; i < len; ++i) {
        if(ch[i] > '4') {
            return true;
        }else if(ch[i] < '4') {
            return false;
        }
    }
    return true;
}

int main() {
    int t;
    char num[20];
    char new_num[20];
    long long ans;
    int flag;
    while(cin >> t) {
        for(int c = 1; c <= t; ++c) {
            
            getchar();
            scanf("%s", num);
            flag = -1;
            for(int i = 0; i < strlen(num); ++i) {
                new_num[i] = num[i];
                if((num[i] - '0') % 2 == 1) {
                    if(i == strlen(num) - 1) {
                        --new_num[i];
                        flag = 0;
                        break;
                    }else if(!judge(num, i+1, strlen(num)) || (num[i] - '0') == 9){
                        --new_num[i];
                        flag = 0;
                        ++i;
                        while(i < strlen(num)) {
                            new_num[i] = '8';
                            ++i;
                        }
                        break;
                    }else {
                        ++new_num[i];
                        flag = 1;
                        ++i;
                        while(i < strlen(num)) {
                            new_num[i] = '0';
                            ++i;
                        }
                        break;
                    }
                }
            }
            new_num[strlen(num)] = '\0';
            int tui = 0;
            ans = 0;
            long long pos = 1;
            if(flag < 0) {
                printf("Case #%d: %lld\n", c, 0);
            }else if(flag == 0){
                for(int i = strlen(num)-1; i >= 0; --i) {
                    int tmp = num[i] - new_num[i] - tui;
                    if(tmp < 0) {
                        tui = 1;
                        tmp += 10;
                    }else{
                        tui = 0;
                    }
                    ans += tmp * pos;
                    pos *= 10;
                }
                printf("Case #%d: %lld\n", c, ans);
            }else{
                for(int i = strlen(num)-1; i >= 0; --i) {
                    int tmp = new_num[i] - num[i] - tui;
                    if(tmp < 0) {
                        tui = 1;
                        tmp += 10;
                    }else{
                        tui = 0;
                    }
                    ans += tmp * pos;
                    pos *= 10;
                }
                printf("Case #%d: %lld\n", c, ans);
            }
        }
    }
    return 0;
}

  1. Lucky Dip

    给定一堆数，问给定放回机会数的情况下采取最优策略抽取的数的期望是多少。

    最优策略是若当前抽出的数小于当前的期望，有机会放回则放回重抽。所以每多一次机会的情况就是小于当前期望的所有数的期望变成当前的期望，然后计算新的期望。

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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int t, n, k;
    scanf("%d", &t);
    double sum;
    double tmp_e;
    for(int c = 1; c <= t; ++c) {
        scanf("%d%d", &n, &k);
        sum = 0;
        vector<long long> arr(n);
        vector<long long> suffix_sum(n);
        for(int i = 0; i < n; ++i) {
            scanf("%lld", &arr[i]);
            sum += arr[i];
        }
        tmp_e = sum / n;
        sort(arr.begin(), arr.end());
        suffix_sum[n-1] = arr[n-1];
        for(int i = n-2; i >= 0; --i) {
            suffix_sum[i] = suffix_sum[i+1] + arr[i];
        }
        for(int i = 0; i < k; ++i) {
            int l = 0, r = n-1;
            while(l <= r) {
                int mid = (l + r) >> 1;
                if(arr[mid] < tmp_e) {
                    l = mid + 1;
                }else {
                    r = mid - 1;
                }
            }
            if(l == 0) {
                tmp_e = arr[0];
                break;
            }else {
                tmp_e = (l * tmp_e + suffix_sum[l]) / n;
            }
        }
        printf("Case #%d: %.6lf\n", c, tmp_e);
    }
    return 0;
}

  1. Scrambled Words

    给定一段文本的生成规则，生成文本后，给定一个字典，问有多少个字典中的词的乱序（除了首位字母之外，其他字母可以随意排列）在文本中出现。

    由于字典中词不同的长度种类不会太多，题目中说总长度为1e5，那么长度数X*(X+1) <= 1e5

    所以统计不同的长度，使用字符串的首尾字符以及字符的频数来作为一个字符串的key建立hash表。

C++ Code

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <array>
#include <set>
#include <stdio.h>
#define NUM_CHARACTER 26

using namespace std;

struct Key {
    char first;
    char last;
    array<int, NUM_CHARACTER> freq;
    Key(string &s) {
        freq.fill(0);
        first = s[0];
        last = s[s.size()-1];
        for(int j = 0; j < s.size(); ++j) {
            ++freq[s[j] - 'a'];
        }
    }
    bool operator==(const Key &k) const {
        return (first == k.first && last == k.last && freq == k.freq);
    }
};

namespace std {
    template<>
    struct hash<Key> {
        size_t operator()(const Key &k) const {
            size_t ret = 17, seed = 31;
            ret = ret * seed + k.first;
            ret = ret * seed + k.last;
            for(auto item: k.freq) {
                ret = ret * seed + item;
            }
            return ret;
        }
    };
}


int main() {
    int t, l, n;
    long long a, b, c, d;
    char s1, s2;
    string tmp;
    string text;
    scanf("%d", &t);
    unordered_map<Key, int> mp;
    unordered_set<int> len_set;
    vector<int> x;
    for(int ca = 1; ca <= t; ++ca) {
        mp.clear();
        len_set.clear();
        scanf("%d", &l);
        for(int i = 0; i < l; ++i) {
            cin >> tmp;
            len_set.insert(tmp.size());
            Key key(tmp);
            ++mp[key];
        }
        cin >> s1 >> s2;
        cin >> n >> a >> b >> c >> d;
        x.resize(n);
        text.resize(n);
        text[0] = s1;
        text[1] = s2;
        x[0] = text[0];
        x[1] = text[1];
        for(int i = 2; i < n; ++i) {
            x[i] = (a * x[i-1] + b * x[i-2] + c) % d;
            s1 = (97 + (x[i] % 26));
            text[i] = s1;
        }
        int ans = 0;
        for(int len: len_set) {
            if(len > n) {
                continue;
            }
            int l_pos = 0;
            int r_pos = len-1;
            string tmp_str = text.substr(l_pos, len);
            Key len_key(tmp_str);
            while(r_pos < text.size()) {
                auto iter = mp.find(len_key);
                if(iter != mp.end()) {
                    ans += iter->second;
                    mp.erase(iter);
                }
                --len_key.freq[text[l_pos] - 'a'];
                ++l_pos;
                ++r_pos;
                if(r_pos < text.size()) {
                    ++len_key.freq[text[r_pos] - 'a'];
                    len_key.first = text[l_pos];
                    len_key.last = text[r_pos];
                }
            }

        }
        printf("Case #%d: %d\n", ca, ans);
    }
    return 0;
}