19.5.15 Educational CF Round 65 (Div. 2) (4 / 7)

A. Telephone Number

  • 判断下8出现的第一个位置然后剪一下再判断就行了
  • 11打成8wa了一发..
  • ac代码
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
/*************************************************************************
> File Name: a.cpp
> Author: Wqr_
> Mail: xueduanwei@126.com
> Created Time: 2019年05月15日 星期三 22时28分36秒
************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
#define MAXN 200100
using namespace std;
typedef long long ll;
bool book[15];
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
string in;
cin >> in;
memset(book, 0, sizeof(book));
int min8 = 0x3f3f3f3f;
for(int i = 0; i < n; i++){
book[in[i] - '0'] = 1;
if(in[i] == '8'){
min8 = min(min8, i);
}
}
if(!book[8]) {
cout << "NO" << endl;
continue;
}
if(n - min8 >= 11){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
return 0;
}

B. Lost Numbers

  • 第一次做交互体题, 懵逼. 不过看了下别人的代码马上理解是个什么东西了
  • 题意 :
    • 总共有6个数, 每一个可能为4 8 15 16 23 42中的一个, 并且每个数出现仅一次. 四次询问, 每次输出形如? a b, 系统会返回第a个数与第b个数的乘积
    • 按顺序输出这6个数
  • 知道了意思就很好做了, 设这 6 个数为ans[6], 问ans[0] * ans[1], ans[1] * ans[2], ans[2] * ans[3], ans[3] * ans[4]. 然后就可以判断出所有的数了.
  • ac代码
    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
    /*************************************************************************
    > File Name: b.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月16日 星期四 10时18分14秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    int sum12, sum23, sum34, sum45;
    int ans[6];
    int nums[6] = {4, 8, 15, 16, 23, 42};
    int book[6];
    int main(){
    cout << "? 1 2" << endl;
    cin >> sum12;
    cout << "? 2 3" << endl;
    cin >> sum23;
    cout << "? 3 4" << endl;
    cin >> sum34;
    cout << "? 4 5" << endl;
    cin >> sum45;
    for(int i = 0; i < 6; i++){
    bool flag = 0;
    for(int j = 0; j < 6; j++){
    if(nums[i] * nums[j] == sum12){
    flag = 1;
    book[i]++;
    book[j]++;
    break;
    }
    }
    if(flag) break;
    }
    for(int i = 0; i < 6; i++){
    bool flag = 0;
    for(int j = 0; j < 6; j++){
    if(nums[i] * nums[j] == sum23){
    flag = 1;
    book[i]++;
    book[j]++;
    break;
    }
    }
    if(flag) break;
    }
    for(int i = 0; i < 6; i++){
    if(book[i] == 2){
    ans[1] = nums[i];
    }
    }
    ans[0] = sum12 / ans[1];
    ans[2] = sum23 / ans[1];
    ans[3] = sum34 / ans[2];
    ans[4] = sum45 / ans[3];
    ans[5] = 4 + 8 + 15 + 16 + 23 + 42 - ans[0] - ans[1] - ans[2] - ans[3] - ans[4];
    cout << "! ";
    for(int i = 0; i < 6; i++){
    cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
    }

C. News Distribution

  • 很明显的并查集, 但是重点是时间复杂度的优化, 刚开始朴素写法超时了几次, 后来再unite
  • ac代码
    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
    /*************************************************************************
    > File Name: c.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月15日 星期三 22时56分29秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    #define MAXN 500500
    using namespace std;
    typedef long long ll;
    int n, m;
    int par[MAXN];
    int hi[MAXN];
    int num[MAXN];//储存集合元素的个数
    void init(int n){
    for(int i = 0; i < n; i++){
    num[i] = 1;
    par[i] = i;
    hi[i] = 0;
    }
    }
    int find(int x){
    if(par[x] == x){
    return x;
    }else{
    return par[x] = find(par[x]);
    }
    }
    void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return ;
    if(hi[x] < hi[y]){
    par[x] = y;
    num[y] += num[x];//合并
    }else{
    par[y] = x;
    if(hi[x] == hi[y]) hi[x]++;
    num[x] += num[y];//合并
    }
    }
    bool same(int x, int y){
    return find(x) == find(y);
    }
    int book[500500];
    bool mark[500500];
    int main(){
    cin >> n >> m;
    init(n);
    for(int i = 0; i < m; i++){
    int ge;
    int in[MAXN];
    scanf("%d", &ge);
    int last, now;
    for(int j = 0; j < ge; j++){
    //if(j) last = now;
    scanf("%d", in + j);
    /*
    if(j){
    if(mark[last - 1] && mark[now - 1]) continue;
    unite(last - 1, now - 1);
    mark[last - 1] = 1;
    mark[now - 1] = 1;
    }
    */
    }
    for(int j = 0; j < ge - 1; j++){
    int a = in[j] - 1;
    int b = in[j + 1] - 1;
    unite(a, b);
    }
    }
    for(int i = 0; i < n; i++){
    int x = find(i);
    printf("%d ", num[x]);
    }
    return 0;
    }

D. Bicolored RBS

  • 思维题, 想出来就很好写了
  • 刚开始用的dfs, 然后超时了几发, 后来经dalao指点, 发现可以遍历一次就出答案
  • 思路 : 从string[1]开始遍历, 如果与上一个字符相同就换颜色涂, 不同就不换颜色涂
  • ac代码
    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
    /*************************************************************************
    > File Name: d2.cpp
    > Author: Wqr_
    > Mail: xueduanwei@126.com
    > Created Time: 2019年05月16日 星期四 09时57分33秒
    ************************************************************************/

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<vector>
    #include<algorithm>
    #include<map>
    #include<queue>
    #include<cmath>
    #define MAXN 200100
    using namespace std;
    typedef long long ll;
    int n;
    string in;
    bool ans[MAXN];
    int main(){
    cin >> n >> in;
    bool cr = 0;
    ans[0] = cr;
    for(int i = 1; i < n; i++){
    if(in[i] == in[i - 1]) cr = !cr;
    ans[i] = cr;
    }
    for(int i = 0; i < n; i++){
    cout << ans[i];
    }
    cout << endl;
    return 0;
    }