2018 Autumn 清北学堂普及刷题班 Day5 题解

十月 05, 2018 11486

暴力分！暴力分！

Problem A. climb

题目描述

Bob 在一旁看 Alice 爬台阶玩， Alice 突发奇想让 Bob 闭上眼记录他爬了多少台阶，规则是这样的： Alice每次会想好爬多少级台阶，每爬一级都会数数，爬完之后走回到最底层，注意走回去的那些台阶是不算级数的。 Bob 闭上眼通过 Alice 的报数来统计 Alice 总共爬了几次，每次爬了多少级。

输入格式

第一行包含一个整数 N(1 ≤ 100000)，表示 Alice 的报数次数。

第二行包含 N 个正整数 Ai(1 ≤ Ai ≤ 1000)，表示 Alice 的报数序列。

输出格式

第一行包含一个整数，表示 Alice 爬的次数 T。第二行包含 T 个整数，第 i 个整数表示 Alice 每 i 次爬的台阶数。

输入样例

1
2
7
1 2 3 1 2 3 4

输出样例

1
2
2
3 4

子任务

对于 40% 的数据， N ≤ 20。

对于 70% 的数据， N ≤ 1000。

对于 100% 的数据， N ≤ 100000。

解析

A不掉的退役吧

显然这题就是让你求有多少个1和每两个1之间的距离

当然这题题面有点歧义 求每个1之前的数也可以（数据水

就没了

代码实现

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
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
using namespace std;

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
    const int MAXN = 100000 + 10;
    
    int n;
    int seq[MAXN];
    
    int T;
    vector<int> cnt;
    
    void Work() {
        For (i, 1, n) {
            if (seq[i] == 1) ++T, cnt.push_back(seq[i-1]);
        }
        cnt.push_back(seq[n]);
    }
}

int main(int argc, char *const argv[]) {
    #ifndef HANDWER_FILE
    freopen("climb.in", "r", stdin);
    freopen("climb.out", "w", stdout);
    #endif
    using namespace Solution;
    using namespace FastIO;
    
    n = getint();
    For (i, 1, n) seq[i] = getint();
    Work();
    putint(T, '\n');
    int siz = cnt.size();
    Forw (i, 1, siz - 1) putint(cnt[i], ' ');
    putint(cnt[siz - 1], '\n');
    
    return 0;
}


Problem B. remove

题目描述

给出一个字符串 s，字符串中只会包含⼩写字母 a − z。现在需要通过重复下面这个算法
符串中删去 k 个字符：
• 如果当前字符串中还存在字符 a，就删去字符串中最前面的一个 a 字符，结束算法
• 如果当前字符串中还存在字符 b，就删去字符串中最前面的一个 b 字符，结束算法
• …
• 如果当前字符串中还存在字符 z，就删去字符串中最前面的一个 z 字符，结束算法
求删完 k 个字符后的字符串。

输入格式

第一行包含两个整数 n; k(1 ≤ k ≤ n ≤ 100000)， n 表示字符串长度， k 表示删去的字符个数。

第二行包含一个字符串 s。

输出格式

一行，包含删去k个字符的字符串。

输入样例

Case #1:

1
2
15 3
cccaabababaccbc

Case #2:

1
2
15 9
cccaabababaccbc

输出样例

Case #1:

1
cccbbabaccbc

Case #2:

1
cccccc

子任务

对于 40% 的数据， 1 ≤ k ≤ n ≤ 100。

对于 70% 的数据， 1 ≤ k ≤ n ≤ 1000。

对于 100% 的数据， 1 ≤ k ≤ n ≤ 100000。

解析

这道题我在考试结束之后20min敲出了正解。。。。。。

我们开一个桶，把所有的字母记录下来

接着把桶扫一遍：

  • 如果当前的k大于当前的字母数alphabet[i]，就让k -= alphabet[i]，然后把alphabet[i]置为0
  • 否则让alphabet[i] -= k，然后把k置为0，最后break掉即可

此时，alphabet的意义已经从字母数量变成了经过删除后的还可输出字母数量

之后，我们开一个bool数组chk[i]表示str[i]是否还能被输出，并倒序（注意是倒序，因为题目要求从前面开始删，显然我们要保留后面几位）枚举 i\ (0 < i < n)

  • 当alphabet[str[i] - 'a'] > 0时，将chk[i]设为true并--alphabet[str[i] - 'a']

最后，从头扫一遍chk，如果chk[i] == true就输出str[i]

代码实现

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <ctime>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
using namespace std;

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
    const int MAXN = 100000 + 10;
    int n, k;
    string s;
    bool chk[MAXN];
    
    string Work(string str) {
        // 此为暴力做法
        For (i, 1, k) {
            Forw (j, 0, 26) {
                cout << str << endl;
                int findnow = str.find(j + 'a');
                
//                printf("%c\n", j + 'a');
                
                if (findnow != string::npos) {
                    str[findnow] = '-';
                    break;
                }
            }
        }
        return str;
    }
    
    void nowWork(string str) {
        // 此为正解
        int alphabet[26 + 2] = { 0 };
        bool printal[26] = { true };
        Forw (i, 0, n) alphabet[str[i] - 'a']++;
        Forw (i, 0, 26) {
            //cerr << (char)(i + 'a')<< '=';
            //cerr << alphabet[i] << endl;
            if (alphabet[i] < k) {
                k -= alphabet[i];
                alphabet[i] = 0;
            } else {
                alphabet[i] -= k;
                k = 0;
                break;
            }
        }
        Bak (i, n-1, 0) {
            if (alphabet[str[i] - 'a'] == 0) continue;
            chk[i] = true;
            
            --alphabet[str[i] - 'a'];
        }
        Forw (i, 0, n) if (chk[i]) putchar(str[i]);
    }
    
    void Print(string str) {
        // 此为暴力做法的输出
        Forw (i, 0, n) if (str[i] != '-') putchar(str[i]);
    }
}
    
int main(int argc, char *const argv[]) {
    #ifndef HANDWER_FILE
    freopen("remove.in", "r", stdin);
    freopen("remove.out", "w", stdout);
    #endif
    using namespace Solution;
    ios::sync_with_stdio(false);
//    int t = clock();
    
    cin >> n >> k;
    cin >> s;
    //Print(Work(s));
    nowWork(s);
    
//    cerr << clock() - t << endl;
    
    return 0;
}


Problem C. cut

题目描述

给出一个字符串 s，其中每个字符都是 0 9 的数字。现在需要把字符串 s 分割开，这样每个
部分就可以看做一个数，求这些数中最多有多少个数是 3 的倍数。

如对于字符串 3121，可以分割为 3 | 12 | 1，这样会有两个数是 3 的倍数，如果分割为 31 | 2 | 1，这样就没有数是 3 的倍数了。0 是 3 的倍数，如果 1200045 被拆分为 120 | 0045，则认为分割出来的两个数是 120 和 45，即忽略前导零。

输入格式

一行包含一个字符串s， |s|\le100000

输出格式

一行包含一个整数，表示最多有多少个数是3的倍数。

输入样例

Case #1:

1
3121

Case #2:

1
201920181

输出样例

Case #1：

1
2

Case #2:

1
4

样例解释

第一个样例中可以拆分为 3 | 12 | 1。

第二个样例中可以拆分为 201 | 9 | 2 | 0 | 18 | 1。

解析

首先我们对读进来的序列整体mod 3

接着对这个序列扫一遍

  • 如果当前读到的数是0，根据贪心策略，直接在后面划上一道

  • 否则如果当前读的数的下标大于0，就看前面的数
    如果这个数与上个数的和能被3整除，而且下个数没有被选过，就在后面划上一道

  • 否则如果当前读的数的下标大于1，继续看前面的数
    如果这个数与前面两个数的和能被3整除，而且两个数都没有选过，就在后面划上一道

  • 否则什么都不干

最后输出即可

代码实现

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
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterator -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)
using namespace std;

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
    const int MAXN = 100000 + 10;
    
    bool vis[MAXN];
    
    int seq[MAXN]; 
    int len;
    
    int Work() {
        int ret = 0;
        For (i, 1, len) {
            if (seq[i] == 0) {
                ++ret;
                vis[i] = true;
            } else if (i > 0 && (seq[i] + seq[i - 1]) % 3 == 0 && !vis[i - 1]) {
                ++ret;
                vis[i] = true;
            } else if (i > 1 && (seq[i] + seq[i - 1] + seq[i - 2]) % 3 == 0 && !vis[i - 1] && !vis[i - 2]) {
                ++ret;
                vis[i] = true;
            }
        }
        return ret;
    }
}

int main(int argc, char *const argv[]) {
    #ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
    #endif
    using namespace Solution;
    string s;
    cin >> s;
    len = s.length();
    For (i, 1, len) seq[i] = (s[i-1] - '0') % 3;
    int ans = Work();
    cout << ans << endl;
    return 0;
}

Problem D. sum

题目描述

某些数有奇怪的性质：它十进制下的各位数的平方和的 T 倍等于它本身。求在 [A, B] 范围内的数有多少满足这个性质

输入格式

第一行包含三个整数 T, A, B(1 ≤ T; A; B ≤ 10^18; A ≤ B)。

输出格式

一个整数，表示满足条件的数量。

输入样例

1
51 5000 10000

输出样例

1
3

子任务

对于 40% 的数据， 1 ≤ T; A; B ≤ 100000; A ≤ B。
对于 100% 的数据， 1 ≤ T; A; B ≤ 10^18; A ≤ B。

代码实现

此为标程

1
2
3
4
5
6
7
8
long long calc(long long x) {
    long long ans = 0;
    while (x) {
        ans += (x % 10) * (x % 10);
        x /= 10;
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
long long k, a, b, ans = 0;
    scanf("%lld%lld%lld", &k, &a, &b);
    for(int i = 1; i <= 1600; i++) {
        if (a <= k * i && i <= b / k)
            if (calc(k * i) == i) {
                printf("%lld\n", k * i);
                ans++;
            }
    }
    printf("%lld\n", ans);
    return 0;