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

link

A. Telephone Number

• 判断下8出现的第一个位置然后剪一下再判断就行了
• 11打成8wa了一发…
• ac代码

/*************************************************************************
    > 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

• 第一次做交互体题, 懵逼. 不过看了下别人的代码马上理解是个什么东西了
• 题意 :
  • 总共有６个数, 每一个可能为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代码

/*************************************************************************
    > 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代码

/*************************************************************************
    > 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代码

/*************************************************************************
    > 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;
}