Codeforces Round 479 (Div. 3)

发表于 | 更新于: | 分类于

概况：场外补题ak

题目链接

479

A - Wrong Subtraction

大意：将n操作k次，如果n的末尾不是0就减一否则除以10

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <sstream>
#include <string>

#define ll long long
using namespace std;

int main(int argc,char *argv[]) {
    int n, t;
    while (scanf("%d%d", &n, &t) != EOF) {
        while (t--) {
            if (n % 10) --n;
            else n /= 10;
        }
        printf("%d\n", n);
    }
    return 0;
}

B - Two-gram

题解：找到最靠前的重复次数最多的二位子串，数据范围奇小双重循环暴力即可

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <sstream>
#include <string>

#define ll long long
using namespace std;

int main(int argc,char *argv[]) {
    int n;
    char mp[200];
    while (scanf("%d%s", &n, mp) != EOF) {
        int res = 0, flag = 0, pp = 0;
        for (int i = 0; i < n - 1; ++i) {
            flag = 0;
            for (int j = i + 1; j < n - 1; ++j) {
                if (mp[i] == mp[j] && mp[i + 1] == mp[j + 1]) {
                    ++flag;
                }
            }
            if (flag > pp) {
                pp = flag;
                res = i;
            }
        }
        printf("%c%c\n", mp[res], mp[res + 1]);
    }
    return 0;
}

C - Less or Equal

大意：大概就是很蠢的把序列排个序看它第k个和k+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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <sstream>
#include <string>

#define ll long long
using namespace std;

int mp[200005];
int main(int argc,char *argv[]) {
    int n, k;
    while (scanf("%d%d", &n, &k) != EOF) {
        for (int i = 0; i < n; ++i) scanf("%d", &mp[i]);
        sort(mp, mp + n);
        if (k == 0) printf("%d\n", mp[0] == 1 ? -1 : 1);
        else if (k == n) printf("%d\n", mp[n - 1]);
        else printf("%d\n", mp[k - 1] == mp[k] ? -1 : mp[k - 1]);
    }
    return 0;
}

D - Divide by three, multiply by two

大意：一个数可以有除以三和乘二两种操作，现在给你一个打乱的序列，要求重新排序使得输出序列中a[i] = a[i - 1] * 2 or a[i] = a[i - 1] / 3（a[i - 1] % 3 == 0），他们说什么鬼dfs居然没tle不知道什么情况，其实分析一下就知道按照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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <sstream>
#include <string>

#define ll long long
using namespace std;

ll a[105];
ll x[100] = {1};
int lim;

bool qwq(ll a, ll b) {
    int i = 0;
    while (i <= lim && a % x[i] == 0) ++i;
    int j = 0;
    while (j <= lim && b % x[j] == 0) ++j;
    if (i != j) return i > j;
    return a < b;
}

int main(int argc,char *argv[]) {
    int n;
    for (int i = 1; x[i - 1] < (ll)3e18; ++i) {
        x[i] = x[i - 1] * 3;
        lim = i;
    }
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; ++i) scanf("%lld", &a[i]);
        sort(a, a + n, qwq);
        for (int i = 0; i < n; ++i) printf("%lld%c", a[i], i == n - 1 ? '\n' : ' ');
    }
    return 0;
}

E - Cyclic Components

大意：给一个图求单环的数量，水到是挺水的但是读题又是大问题，把所有连通的点度都是2的计算一下就出来了。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <sstream>
#include <string>

#define ll long long
using namespace std;

vector <int> p[200005];
int vis[200005];
vector <int> kk[200005];
int c[200005];
int n, m;
int pos = 0;

void dfs(int x) {
    if (vis[x] == 1) return;
    vis[x] = 1;
    kk[pos].push_back(x);
    for (int i = 0; i < p[x].size(); ++i) {
        dfs(p[x][i]);
        ++c[p[x][i]];
    }
}

int main(int argc,char *argv[]) {
    while (scanf("%d%d", &n, &m) != EOF) {
        memset(vis, 0, sizeof vis);
        memset(c, 0, sizeof c);
        pos = 0;
        for (int i = 0; i < 200005; ++i) {
            kk[i].clear();
            p[i].clear();
        }
        int x, y;
        for (int i = 0; i < m; ++i) {
            scanf("%d%d", &x, &y);
            p[x].push_back(y);
            p[y].push_back(x);
        }
        for (int i = 1; i <= n; ++i) {
            if (!vis[i] && p[i].size()) {
                dfs(i);
                ++pos;
            }
        }
        int flag;
        int res = 0;
        // for (int i = 1; i <= n; ++i) printf("%d%c", c[i], i == n ? '\n' : ' ');
        for (int i = 0; i < pos; ++i) {
            // printf("*");
            // for (int j = 0; j < kk[i].size(); ++j) printf("%d ", kk[i][j]);
            // printf("\n");
            flag = 1;
            for (int j = 0; j < kk[i].size(); ++j) {
                if (c[kk[i][j]] != 2) {
                    flag = 0;
                    break;
                }
            }
            res += flag;
        }
        printf("%d\n", res);
    }
    return 0;
}

F - Consecutive Subsequence

大意：给一个序列输出一个子序列的下标，使得这个子序列是原序列最长的具有a[i] = a[i - 1] + 1性质的序列。

题解：我的解法很暴力就是用map然后从前往后遍历一次，把它每个点改成dp[a[i] - 1] + 1记录一下最大值最后从前往后搜一遍就行，总复杂度不算map的开销的话就是o(n)

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <string>

#define ll long long
using namespace std;

int mp[200005];
map <int, int> dp;

int main(int argc,char *argv[]) {
    int n;
    while (scanf("%d", &n) != EOF) {
        dp.clear();
        int res = 0, kk = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", &mp[i]);
            dp[mp[i]] = max(dp[mp[i]], dp[mp[i] - 1] + 1);
            if (res < dp[mp[i]]) {
                res = dp[mp[i]];
                kk = i;
            }
        }
        int gg = mp[kk] - dp[mp[kk]] + 1;
        int flag = 1;
        printf("%d\n", dp[mp[kk]]);
        for (int i = 0; i < n; ++i) {
            if (mp[i] != gg) continue;
            if (flag == 1) flag =  0;
            else printf(" ");
            printf("%d", i + 1);
            ++gg;
            if (gg > mp[kk]) break;
        }
        printf("\n");
    }
    return 0;
}

总之庆祝我cf第一次的ak写了一篇博客