CodeForces Round #529 Div.3

#include <bits/stdc++.h>
using namespace std;

int N;
string s;
string ans = "";

int main() {
    scanf("%d", &N);
    cin >> s;
    int cnt = 0;
    for(int i = 0; i < N;) {
        ans += s[i];
        cnt ++;
        i += cnt;
    }
    cout << ans;
    return 0;
}

View Code

B. Array Stabilization

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int N;
int a[maxn];

int main() {
    scanf("%d", &N);
    for(int i = 0; i < N; i ++)
        scanf("%d", &a[i]);

    sort(a, a + N);
    int ans1 = a[N - 2] - a[0];
    int ans2 = a[N - 1] - a[1];
    printf("%d
", min(ans1, ans2));
    return 0;
}

View Code

C. Powers Of Two

#include <bits/stdc++.h>
using namespace std;

int N, K;
priority_queue<int> q;
int cnt = 0;

int main() {
    scanf("%d%d", &N, &K);
    for(int i = 30; i >= 0; i --) {
        if(N >= (1 << i)) {
            q.push(i);
            N -= (1 << i);
            cnt ++;
        }
    }

    if(K < cnt) printf("NO
");
    else {
        while(cnt < K) {
            int rec = q.top();
            if(rec == 0) {
                printf("NO
");
                return 0;
            }

            q.pop();
            q.push(rec - 1);
            q.push(rec - 1);

            cnt ++;
        }

        printf("YES
");
        while(!q.empty()) {
            int t = q.top();
            printf("%d ", (1 << t));
            q.pop();
        }

    }

    return 0;
}

View Code

D. Circular Dance

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
vector<int> v[maxn];
int a[maxn][3], vis[maxn];
int N;
vector<int> ans;

void dfs(int step) {
    vis[step] = 1;
    ans.push_back(step);
    for(int i = 0; i < v[step].size(); i ++) {
        if(!vis[v[step][i]] && (v[step][i] == a[step][0] || v[step][i] == a[step][1])) {
            vis[v[step][i]] = 1;
            dfs(v[step][i]);
        }
    }
}

int main() {
    scanf("%d", &N);
    for(int i = 1; i <= N; i ++) {
        int st, en;
        scanf("%d%d", &st, &en);
        a[i][0] = st, a[i][1] = en;
        v[st].push_back(en);
        v[en].push_back(st);
    }

    dfs(1);
    for(int i = 0; i < ans.size(); i ++)
        printf("%d%s", ans[i], i != ans.size() - 1 ? " " : "
");

    return 0;
}

View Code

E. Almost Regular Bracket Sequence

（合法的括号匹配串的充要条件是 ① 前 i 项前缀和非负 ② sum[N] == 0）

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
int N;
string s;
int a[maxn], sum[maxn], b[maxn], c[maxn];

int main() {
    cin >> N >> s;
    for(int i = 0; i < N; i ++) {
        if(s[i] == '(')
            a[i] = 1;
        else a[i] = -1;
    }

    sum[0] = a[0];
    for(int i = 1; i < N; i ++)
        sum[i] = a[i] + sum[i - 1];

    c[0] = sum[0];
    for(int i = 1; i < N; i ++)
        c[i] = min(c[i - 1], sum[i]);

    b[N - 1] = sum[N - 1];
    for(int i = N - 2; i >= 0; i --)
        b[i] = min(sum[i], b[i + 1]);

    int ans = 0;
    for(int i = 0; i < N; i ++) {
        if(s[i] == '(') {
            if(c[i - 1] >= 0 && b[i] - 2 >= 0 && sum[N - 1] - 2 == 0) ans ++;
        } else {
            if(c[i - 1] >= 0 && b[i] + 2 >= 0 && sum[N - 1] + 2 == 0) ans ++;
        }
    }

    printf("%d
", ans);

    return 0;
}

View Code

F. Make It Connected

（很久没写最小生成树这个先留一哈）

写的好烦脑子不好用想不到然后开始吃薯片还是暴躁越来越暴躁在放弃的边缘大鹏展翅所以完全不想看题目想豁奶茶想吹风