2021牛客暑期多校训练营6

F

题意

1. 个锅，个牛排
2. 第个牛排要炸分钟
3. 一个牛排可以拆成两段时间炸，

输出行，每行描述烹饪计划 个三元组，表示第个锅，时间从到

思路

贪心。

考虑一个时间上限，指最后一块牛排煎完那一刻的时间。

1. 首先要考虑每一块牛排煎的时间。因为一块牛排不管怎么分配到多少个锅里，时间是连续的。即
2. 时间是可以无缝切换的资源池。考虑每个锅的平均的牛排时间消耗。即

确定了以后，考虑每个锅可分配的时间资源，顺序分配即可

solution

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, t, r) for (int i = t; i <= r; ++i)
using namespace std;
typedef long long ll;
void pb(list<ll> &a, ll x, ll y, ll z) {
    a.emplace_front(z), a.emplace_front(y), a.emplace_front(x);
}
signed main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> a(n);
    ll sum = 0, ddl = 0;
    for (int &x : a) scanf("%d", &x), ddl = max((ll)x, ddl), sum += x;
    ddl = max(1LL * ddl, sum / m + (sum % m != 0));
    vector<list<ll>> res(n);
    int p = 0;  // steak
    rep(i, 1, m) {
        ll tot = ddl, t = 0;
        while (p < n and tot >= a[p]) {
            pb(res[p], i, t, t += a[p]);
            tot -= a[p++];
        }
        if (p == n) break;
        if (tot) pb(res[p], i, t, ddl), a[p] -= ddl - t;
    }
    for (const list<ll> &v : res) {
        printf("%d ", v.size() / 3);
        for (const ll &x : v) printf("%lld ", x);
        printf("\n");
    }
    return 0;
}

I

题意

给定一些环形区间，要求构造一组区间，满足构造的区间的并是全集，且构造的区间的交是给定区间。

区间可能有重。

思路

首先把所有的区间合并。

然后按照如下方法构造区间:

简单来说，就是本区间的左端点和上一区间的右端点构成的优弧，形成了一个新的区间。

solution

双指针写法

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e3 + 7;
const int mod = 1e9 + 7;
int a[N];
signed main() {
    int T = 1, n, m, l, r;
    struct intersection {
        int L, R;
    };
    scanf("%d", &T);
    while (T--) {
        memset(a, 0, sizeof a);
        scanf("%d%d", &n, &m);
        while (m--) {
            scanf("%d%d", &l, &r);
            if (l > r)  // [l,n] + [1,r]
                a[l]++, a[n + 1]--, a[1]++, a[r + 1]--;
            else  // [l,r]
                a[l]++, a[r + 1]--;
        }
        rep(i, 1, n) a[i] += a[i - 1];
        vector<intersection> v;
        int l = 1, r = 1;
        while (r <= n) {
            while (a[l] <= 0 && l <= n) ++l;
            for (r = l + 1; r <= n && a[r] > 0; ++r)
                ;
            --r;
            if (l <= r && r <= n) {
                v.push_back({l, r});
                l = r + 1;
            }
        }
        printf("%d\n", v.size());
        for (int i = 0; i < v.size(); ++i)
            printf("%d %d\n", v[i].L, v[(i - 1 + v.size()) % v.size()].R);
    }
    return 0;
}

简单写法

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e3 + 7;
const int mod = 1e9 + 7;
int a[N];
signed main() {
    int T = 1, n, m, l, r;

    scanf("%d", &T);
    while (T--) {
        memset(a, 0, sizeof a);
        scanf("%d%d", &n, &m);
        while (m--) {
            scanf("%d%d", &l, &r);
            if (l > r)  // [l,n] + [1,r]
                a[l]++, a[n + 1]--, a[1]++, a[r + 1]--;
            else  // [l,r]
                a[l]++, a[r + 1]--;
        }
        rep(i, 1, n) a[i] += a[i - 1];
        vector<int> L, R;
        rep(i, 1, n) {
            if (a[i - 1] <= 0 and a[i] > 0) L.push_back(i);
            if (a[i] > 0 and a[i + 1] <= 0) R.push_back(i);
        }
        printf("%d\n", L.size());
        for (int i = 0; i < L.size(); ++i)
            printf("%d %d\n", L[i], R[(i - 1 + R.size()) % R.size()]);
    }
    return 0;
}

C

题意

给定一个n个点的完全图，每次删除一个完整的三角形，给出一种删法，让图的边数少于n

思路

因为每次删除的都是三角形，其实只用维护三角形，使后面出现的三角形和前面的三角形没有重复边即可。所以可以使用离散数学中群的知识来维护，维持三个点的递增性即可。

solution

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define rep(i, l, r) for (int i = l; i <= r; ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
signed main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", n % 3 ? (n * n - 3 * n + 2) / 6 : (n * n - 3 * n + 6) / 6);
    rep(i, 1, n) rep(j, i + 1, n) {
        int k = (2 * n - i - j - 1) % n + 1;
        if (k > j) printf("%d %d %d\n", i, j, k);
    }
    return 0;
}