[Codeforces]Educational Codeforces Round 37 (Rated for Div. 2)

时间：2023-03-10 04:52:04
[Codeforces]Educational Codeforces Round 37 (Rated for Div. 2)

Water The Garden

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

int x[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    int n, k, t;

    cin >> t;

    while (t--) {

        cin >> n >> k;

        int ans = ;

        for (int i = ; i < k; i++) cin >> x[i];

        ans = max(ans, x[]);

        ans = max(ans, n - x[k - ] + );

        for (int i = ; i < k; i++) ans = max(ans, (x[i] - x[i - ] + ) / );

        cout << ans << endl;

    }

    return ;

}

Tea Queue

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

int l[], r[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    int n, t;

    cin >> t;

    while (t--) {

        cin >> n;

        for (int i = ; i < n; i++) cin >> l[i] >> r[i];

        int time = ;

        for (int i = ; i < n; i++) {

            if (time < l[i]) time = l[i];

            if (time > r[i]) {

                cout <<  << ' ';

                continue;

            }

            cout << time << ' ';

            time++;

        }

        cout << endl;

    }

    return ;

}

Swap Adjacent Elements

显然一段1+0子段是可以变换为任意顺序的，而各个1+0中间单独存在的0必须满足a[i]=i时才能完成排序。对于某一段1+0子段，假设对应区间为a[i]~a[j]由于它无法与其他子段发生交换，所以a[i]~a[j]中的数字必须由i~j组成。

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

int a[], p[], b[];

bool f[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    int n;

    cin >> n;

    for (int i = ; i <= n; i++) {

        cin >> a[i];

        p[a[i]] = i;

    }

    char ch;

    for (int i = ; i < n; i++) {

        cin >> ch;

        b[i] = ch - '';

    }

    b[n] = ;

    bool ok = true;

    int ptr = ;

    while (ptr <= n) {

        if (b[ptr] == ) {

            if (a[ptr] != ptr) ok = false;

            ptr++;

        } else {

            int l = ptr;

            while (b[ptr] == ) ptr++;

            int r = ptr;

            for (int i = l; i <= r; i++) f[i] = false;

            for (int i = l; i <= r; i++) f[a[i]] = true;

            for (int i = l; i <= r; i++) if (!f[i]) ok = false;

            ptr++;

        }

    }

    if (ok) cout << "YES" << endl;

    else cout << "NO" << endl;

    return ;

}

Tanks

如果所有的水箱中水量加起来不到v，则方案不存在。

首先选出若干个水箱，他们当前的水量加起来与v对k取余相同，若选不出来，则方案不存在。

对于选出的水箱，首先把这部分水箱中的水集中在一起，然后把其余的水箱中的水集中在一起，然后再舀回若干次k即可。

代码鸽了。

Connected Components

观察一下这个数据，其实挺搞笑的。对于小数据，怎么搞都可以。对于n和m都是20w的大数据，其答案肯定是199990+和几个一位数组成。

对于大小是S1和S2的两个强联通分量，其中的不直连关系至少要有S1*S2个。对于给定条件，每个点都缺少若干条边，其中有一个缺少的边数量最少的点，设为r，r缺边数量设为p。p能有多少呢？如果p能上万，那有缺边现象的点就不会超过20个。所以p估计也就是个四五百顶天了，那么最大的一个强联通分量就已经直接预订了这（n-四五百）这么多的点。

对于剩下的点，先不考虑外面，把他们内部的强连通分量分别算出来，然后对于每个强联通分量，如果其中一个点有连向外部的边，那么它属于最大的强联通分量的一部分，否则就是一个独立的真强联通分量。

代码鸽了

SUM and REPLACE

List of  Integers

相关文章