2019牛客暑期多校训练营（第七场）

本文最后更新于：星期四, 二月 3日 2022, 9:15 晚上

A. String

题意：定义一个 $prefect \; string$ 表示它是循环字符串中字典序最小的，问将一个字符串分解成若干个 $prefect \; string$ 。

思路：暴力


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

#define N 210
int n;
string s;
vector <string> res;

int minRep(string s) {
    int len = s.size();
    int i = 0, j = 1, k = 0;
    while (i < len && j < len && k < len) {
        int t = s[(i + k) % len] - s[(j + k) % len];
        if (!t) ++k;
        else {
            if (t > 0) i += k + 1;
            else if (t < 0) j += k + 1;
            if (i == j) j = i + 1;
            k = 0;
        }
    //  printf("%d %d %d\n", i, j, k);
    }
    return min(i, j);
}

int ok(string s) {
    string t = s;
    s += t;
    if (minRep(s) == 0) return 1;
    return 0;
}

void solve(string s) {
    int len = s.size();
    string t = "";
    for (int i = len; i >= 1; --i) {
        if (ok(s)) {
            res.push_back(s);
            reverse(t.begin(), t.end());
            solve(t);
            return;
        } else {
            t += s[i - 1];
            s.pop_back();
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--) {
        cin >> s;
        res.clear();
        solve(s);
        for (int i = 0, sze = (int)res.size(); i < sze; ++i) {
            cout << res[i] << " \n"[i == sze - 1];
        }
    }
    return 0;
}

B. Irreducible Polynomial

题意：判断一个多项式能否被分解

思路：对于 $3$ 阶以及以上的多项式一定能被分解，剩下的只需要判断 $0,1,2$ 多项式


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 110

int n;
ll a[N];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = n; i >= 0; --i) {
            scanf("%lld", a + i);
        }
        if (n >= 3) {
            puts("No");
            continue;
        } else if (n <= 1) {
            puts("Yes");
            continue;
        } else if (n == 2) {
            ll A = a[2], B = a[1], C = a[0];
            ll d = B * B - 4 * A * C;
            if (d >= 0) {
                puts("No");
            } else {
                puts("Yes");
            }
        }
    }
    return 0;
}

C. Governing sand

题意：有 $n$ 种树，每种树具有 $H_i, P_i,C_i$ ，分别表示高度，数量，砍掉的代价，问砍掉最小代价的树，使得剩下的最高的树的个数大于一半。

思路：枚举高度，权值线段树上二分。


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

#define ll long long
#define N 100010
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n; ll tot;
struct Hash {
    int a[N], cnt;
    void init() { cnt = 0; }
    void add(int x) { a[++cnt] = x; }
    void work() {
        sort(a + 1, a + 1 + cnt);
        cnt = unique(a + 1, a + 1 + cnt) - a - 1;
    }
    int get(int x) {
        return lower_bound(a + 1, a + 1 + cnt, x) - a;
    }
}hs;
struct node {
    int h, c, p;
    void scan() {
        scanf("%d%d%d", &h, &c, &p);
        hs.add(h);     
        tot += p;
    }
}a[N];
vector <vector<node>> vec;

struct SEG {
    struct node {
        ll sum, num, base;
        node() {
            sum = num = base = 0;
        }
        void add(ll x) {
            num += x;
            sum += base * x;
        }
        node operator + (const node &other) const {
            node res = node();
            res.sum = sum + other.sum;
            res.num = num + other.num;
            return res;
        }
    }t[10010];
    void build(int id, int l, int r) {
        t[id] = node();
        if (l == r) {
            t[id].base = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }  
    void update(int id, int l, int r, int pos, ll x) {
        if (l == r) {
            t[id].add(x);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(id << 1, l, mid, pos, x);
        else update(id << 1 | 1, mid + 1, r, pos, x);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
    ll query(int id, int l, int r, ll k) {
        if (k <= 0) return 0;
        if (l == r) {
            return k * t[id].base;
        }
        int mid = (l + r) >> 1;
        if (t[id << 1].num >= k) {
            return query(id << 1, l, mid, k);
        } else {
            return t[id << 1].sum + query(id << 1 | 1, mid + 1, r, k - t[id << 1].num);
        }
    }
}seg;

int main() {
    while (scanf("%d", &n) != EOF) {
        tot = 0;
        hs.init();
        for (int i = 1; i <= n; ++i) a[i].scan();
        hs.work();
        vec.clear(); vec.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            vec[hs.get(a[i].h)].push_back(a[i]);
        }
        int m = 200;
        seg.build(1, 1, m);
        ll fee = 0, res = INF;
        for (int i = 1; i <= n; ++i) {
            seg.update(1, 1, m, a[i].c, a[i].p);
        }
        for (int i = hs.cnt; i >= 1; --i) {
            ll tmp = 0, now = 0;
            for (auto it : vec[i]) {
                now += it.p;
                tmp += 1ll * it.c * it.p;
                seg.update(1, 1, m, it.c, -it.p);  
            }
            tot -= now;
            res = min(res, fee + seg.query(1, 1, m, tot - now + 1));
            fee += tmp;
        }  
        printf("%lld\n", res);
    }
    return 0;
}

D. Number

签到


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

int n, p;
int f(int x) {
    int res = 0;
    while (x) {
        ++res;
        x /= 10;
    }
    return res;
}

int main() {
    while (scanf("%d%d", &n, &p) != EOF) {
        if (f(p) > n) {
            puts("T_T");
        } else {
            int need = n - f(p);
            printf("%d", p);
            for (int i = 1; i <= need; ++i) putchar('0');
            puts("");
        }
    }
    return 0;
}

E. Find the median

题意：每次插入一个 $[L_i, R_i]$ 范围内的所有数，问中位数

思路：线段树维护区间。


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

#define ll long long
#define N 400010
struct Hash {
    int a[N << 1], cnt;
    void init() { cnt = 0; }
    void add(int x) { a[++cnt] = x; }
    void work() {
        sort(a + 1, a + 1 + cnt);
        cnt = unique(a + 1, a + 1 + cnt) - a - 1;
    }
    int get(int x) { return lower_bound(a + 1, a + 1 + cnt, x) - a; }
}hs;
int n, m;
ll A[2], B[2], C[2], M[2];
ll L[N], R[N], X[N], Y[N];

struct SEG {
    struct node {
        int base;
        //0表示左端点　1表示右端点
        int num[2];
        ll sum[2];
        node() {
            num[0] = num[1] = 0;
            sum[0] = sum[1] = 0;
        }
        void add(ll x, int f) {
            num[f] += x;
            sum[f] += 1ll * x * base;
        }
        node operator + (const node &other) const {
            node res = node();
            for (int i = 0; i < 2; ++i) {
                res.num[i] = num[i] + other.num[i];
                res.sum[i] = sum[i] + other.sum[i];
            }
            return res;
        }
    }t[N << 3], base;
    void build(int id, int l, int r) {
        t[id] = node();
        if (l == r) {
            t[id].base = hs.a[l] - 1;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
    void update(int id, int l, int r, int pos, ll x, int f) {
        if (l == r) {
            t[id].add(x, f);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(id << 1, l, mid, pos, x, f);
        else update(id << 1 | 1, mid + 1, r, pos, x, f);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
    int query(int id, int l, int r, ll k, node left) {
//      printf("## %d %d %lld\n", l, r, k)  ;
        if (l == r) return hs.a[l]; 
        node tmp = left + t[id << 1];
        int mid = (l + r) >> 1;
        ll pl = hs.a[mid];
        ll pr = hs.a[mid + 1] - 1;
        ll resl = 1ll * pl * tmp.num[0] - tmp.sum[0] - (1ll * pl * tmp.num[1] - tmp.sum[1] - tmp.num[1]);
        ll resr = 1ll * pr * tmp.num[0] - tmp.sum[0] - (1ll * pr * tmp.num[1] - tmp.sum[1] - tmp.num[1]);
        if (resl >= k) {
            return query(id << 1, l, mid, k, left);
        } else if (resr < k) {
            return query(id << 1 | 1, mid + 1, r, k, tmp);
        } else {
            int ql = pl, qr = pr, res = pr;
            while (qr - ql >= 0) {
                int mid = (ql + qr) >> 1;
                ll tot = 1ll * mid * tmp.num[0] - tmp.sum[0] - (1ll * mid * tmp.num[1] - tmp.sum[1] - tmp.num[1]);
                if (tot >= k) {
                    res = mid;
                    qr = mid - 1;
                } else {
                    ql = mid + 1;
                }
            }
            return res;
        }
    }
}seg; 

int main() {
    while (scanf("%d", &n) != EOF) {
        scanf("%lld%lld%lld%lld%lld%lld", X + 1, X + 2, A, B, C, M);
        scanf("%lld%lld%lld%lld%lld%lld", Y + 1, Y + 2, A + 1, B + 1, C + 1, M + 1);
        hs.init();
        L[1] = X[1] + 1; R[1] = Y[1] + 1; if (L[1] > R[1]) swap(L[1], R[1]); hs.add(L[1]); hs.add(R[1]);
        L[2] = X[2] + 1; R[2] = Y[2] + 1; if (L[2] > R[2]) swap(L[2], R[2]); hs.add(L[2]); hs.add(R[2]);
        for (int i = 3; i <= n; ++i) {
            X[i] = (A[0] * X[i - 1] % M[0] + B[0] * X[i - 2] % M[0] + C[0] + M[0]) % M[0];
            Y[i] = (A[1] * Y[i - 1] % M[1] + B[1] * Y[i - 2] % M[1] + C[1] + M[1]) % M[1];
            L[i] = X[i] + 1;
            R[i] = Y[i] + 1;
            if (L[i] > R[i]) swap(L[i], R[i]);
            hs.add(L[i]); hs.add(R[i]);    
        }
    //  for (int i = 1; i <= n; ++i) printf("%lld %lld\n", L[i], R[i]); 
        hs.work();
        m = hs.cnt;
        seg.build(1, 1, m);
        ll tot = 0;
        for (int i = 1; i <= n; ++i) {
            seg.update(1, 1, m, hs.get(L[i]), 1, 0);
            seg.update(1, 1, m, hs.get(R[i]), 1, 1);
            tot += R[i] - L[i] + 1;
            seg.base = SEG::node();
            printf("%d\n", seg.query(1, 1, m, (tot + 1) / 2, seg.base));
        }
    }
    return 0;
}

F. Energy stones

题意：有 $n$ 堆能量石，每个能量石具有 $E_i，L_i,C_i$ ，其中 $E_i$ 表示能量石初始能量， $L_i$ 表示能量增长速度， $C_i$ 表示能量上限，CNZ有 $m$ 次进食，每次在 $t_i$ 吃掉区间 $[S_i, T_i]$ 范围内的能量石，问最后吃了多少能量。

思路：用 $set$ 维护时间线表示当前石头 $i$ 被吃的时间节点，然后用一颗线段树动态维护时间长度的数量，对于时间长度大于 $\lceil \frac{C_i}{L_i}\rceil$ 的时间收益为 $C_i$ ，剩下的就是长度乘上 $L_i$ ，然后动态维护时间线即可。


#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define N 200010
int n, q;

struct node {
    int e, l, c;

    void scan() {
        scanf("%d%d%d", &e, &l, &c);
    }
} a[N];

vector<vector<int>> add, del;

struct SEG {
    struct node {
        ll sum, num;
        int base;

        node() {
            sum = num = 0;
        }
     
        void add(ll x) {
            sum += x * base;
            num += x;
        }
     
        node operator+(const node &other) const {
            node res = node();
            res.sum = sum + other.sum;
            res.num = num + other.num;
            return res;
        }
    } t[N << 2], res;
     
    void build(int id, int l, int r) {
        t[id] = node();
        if (l == r) {
            t[id].base = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
     
    void update(int id, int l, int r, int pos, int x) {
        if (l == r) {
            t[id].add(x);
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(id << 1, l, mid, pos, x);
        else update(id << 1 | 1, mid + 1, r, pos, x);
        t[id] = t[id << 1] + t[id << 1 | 1];
    }
     
    void query(int id, int l, int r, int ql, int qr) {
        if (ql > qr) return;
        if (l >= ql && r <= qr) {
            res = res + t[id];
            return;
        }
        int mid = (l + r) >> 1;
        if (ql <= mid) query(id << 1, l, mid, ql, qr);
        if (qr > mid) query(id << 1 | 1, mid + 1, r, ql, qr);
    }
} seg;

int main() {
    int T;
    scanf("%d", &T);
    for (int kase = 1; kase <= T; ++kase) {
        printf("Case #%d: ", kase);
        scanf("%d", &n);
        add.clear();
        del.clear();
        add.resize(n + 10);
        del.resize(n + 10);
        for (int i = 1; i <= n; ++i) a[i].scan();
        scanf("%d", &q);
        for (int i = 1, S, T1, t; i <= q; ++i) {
            scanf("%d%d%d", &t, &S, &T1);
            add[S].push_back(t);
            del[T1 + 1].push_back(t);
        }
        int m = 200000;
        ll res = 0;
        seg.build(1, 1, m);
        set<int> se;
        int Fi = 0;
        for (int i = 1; i <= n; ++i) {
            for (auto it : add[i]) {
                if (se.empty()) {
                    se.insert(it);
                    Fi = it;
                } else {
                    auto pos = se.lower_bound(it);
                    if (pos == se.begin()) {
                        Fi = it;
                        seg.update(1, 1, m, *se.begin() - it, 1);
                        se.insert(it);
                    } else if (pos == se.end()) {
                        --pos;
                        seg.update(1, 1, m, it - *pos, 1);
                        se.insert(it);
                    } else {
                        auto pos2 = pos;
                        --pos2;
                        seg.update(1, 1, m, it - *pos2, 1);
                        seg.update(1, 1, m, *pos - it, 1);
                        seg.update(1, 1, m, *pos - *pos2, -1);
                        se.insert(it);
                    }
                }
            }
            for (auto it : del[i]) {
                auto pos = se.lower_bound(it);
                auto nx = pos;
                ++nx;
                if (pos == se.begin()) {
                    if (nx == se.end()) {
                        Fi = 0;
                    } else {
                        Fi = *nx;
                        seg.update(1, 1, m, *nx - *pos, -1);
                    }
                    se.erase(pos);
                } else if (nx == se.end()) {
                    auto pre = pos;
                    --pre;
                    seg.update(1, 1, m, *pos - *pre, -1);
                    se.erase(pos);
                } else {
                    auto pre = pos;
                    --pre;
                    seg.update(1, 1, m, *pos - *pre, -1);
                    seg.update(1, 1, m, *nx - *pos, -1);
                    seg.update(1, 1, m, *nx - *pre, 1);
                    se.erase(pos);
                }
            }
            if (Fi == 0) continue;
            res += min(1ll * a[i].e + 1ll * a[i].l * Fi, 1ll * a[i].c);
            if (a[i].l == 0) continue;
            int t = ((a[i].c + a[i].l - 1) / a[i].l);
            seg.res = SEG::node();
            //大于等于t的
            seg.query(1, 1, m, t, m);
            res += 1ll * a[i].c * seg.res.num;
            //小于t的
            seg.res = SEG::node();
            seg.query(1, 1, m, 1, t - 1);
            res += 1ll * seg.res.sum * a[i].l;
        }
        printf("%lld\n", res);
    }
    return 0;
}

H. Pair

题意：问有多少对 $<x, y>$ 其中满足 $1\leq x \leq A, 1\leq y \leq B$ ，满足以下任意条件

$x & y> C $
$x \oplus y < C$

思路：经典的数位 $dp$ , $dp[pos][f1][f2][l1][l2][one1][one2]$ ,其中 $pos$ 表示枚举到哪一位， $f1$ 表示 $x\& y$ 和 $C$ 的关系， $f2$ 表示 $x\oplus y$ 和 $C$ 的关系,， $l1,l2$ 表示是否达到上届， $one1, one2$ 表示是否有 $1$ ，所以跑得飞快


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 100

ll A, B, C;
int a[N], b[N], c[N];
ll dp[N][3][3][2][2][2][2];

//位置 x&y x^y (=0 <1 >2)
ll DFS(int pos, int flag1, int flag2, int limit1, int limit2, int one1, int one2) {
    if (pos == -1 && (flag1 == 2 || flag2 == 1) && one1 == 1 && one2 == 1) {
        return 1ll;
    } else if (pos == -1) {
        return 0ll;
    }
    ll &res = dp[pos][flag1][flag2][limit1][limit2][one1][one2];
    if (res != -1) {
        return res;
    }
    res = 0;
    if (flag1 == 1 && flag2 == 2) {//x&y<C x^y>C 不合法
        return 0ll;
    }
    int l1 = limit1 ? a[pos] : 1;
    int l2 = limit2 ? b[pos] : 1;
    for (int i = 0; i <= l1; ++i) {
        for (int j = 0; j <= l2; ++j) {
            int x = i & j;
            int y = i ^j;
            int f1 = flag1;
            if (f1 == 0) {
                if (x > c[pos]) {
                    f1 = 2;
                } else if (x == c[pos]) {
                    f1 = 0;
                } else {
                    f1 = 1;
                }
            }
            int f2 = flag2;
            if (f2 == 0) {
                if (y > c[pos]) {
                    f2 = 2;
                } else if (y == c[pos]) {
                    f2 = 0;
                } else {
                    f2 = 1;
                }
            }
            res += DFS(pos - 1, f1, f2, limit1 && (i == a[pos]),
                       limit2 && (j == b[pos]), one1 | i, one2 | j);
        }
    }
    return res;
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld %lld %lld", &A, &B, &C);
        for (int i = 30; i >= 0; --i) {
            if (A & (1ll << i)) {
                a[i] = 1;
            } else {
                a[i] = 0;
            }
            if (B & (1ll << i)) {
                b[i] = 1;
            } else {
                b[i] = 0;
            }
            if (C & (1ll << i)) {
                c[i] = 1;
            } else {
                c[i] = 0;
            }
        }
        memset(dp, -1, sizeof dp);
        printf("%lld\n", DFS(30, 0, 0, 1, 1, 0, 0));
    }
    return 0;
}

J. A+B problem

签到


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

#define ll long long
ll A, B;

ll f(ll x) {
    vector <int> vec;
    while (x) {
        vec.push_back(x % 10);
        x /= 10;   
    }
    ll res = 0;
    for (auto it : vec) res = res * 10 + it;
    return res;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &A, &B);
        printf("%lld\n", f(f(A) + f(B)));
    }
    return 0;
}

后记：最近咋回事？本队任督二脉打开了(x

2019牛客多校

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Educational Codeforces Round 70 (Rated for Div. 2) 上一篇

Multi-University-Training-Contest-6 下一篇