2019牛客暑期多校訓練營（第七場）

湖南省第一和多校前50全被隊友葬送了，BC那麼簡單卻給我送了十幾發罰時，而且還沒過！何神軒少請客吃飯是沒得跑了

A String

解法：每次暴力枚舉最長的合法串就行，簽到

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 10;
char s[maxn], t[maxn], tmp[maxn];
queue<char> q;
int ok(int i, int j) {

    int n = j - i + 1;
    for (int k = 1; k < n; k++) {
        for (int p = 0; p < n; p++) {
            int q = k + p + i;
            if (q > j)
                q = q - j - 1 + i;
            if (s[p + i] > s[q])
                return 0;
            else if (s[p + i] < s[q])
                break;
        }
    }
    return 1;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", s);
        int n = strlen(s);
        int i = 0;
        while (i < n) {

            int j = i;
            for (int pos = i + 1; pos < n; pos++)
                if (ok(i, pos))
                    j = pos;
            for (int k = i; k <= j; k++)
                printf("%c", s[k]);
            if (j == n - 1)
                puts("");
            else
                printf(" ");
            i = j + 1;
        }
    }
}
           

B Irreducible Polynomial

猜的結論：n>=3一定可以因式分解（百度驗證猜對了），接下來我們分析n <=1，一定是不能分解，n=2時就是顯然隻有一種情況無法因式分解，那就是多項式中b^2 - 4ac<0

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5e4 + 10;
ll a[maxn];
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        cin>>n;
        for (int i = 0; i <= n; i++)
            cin>>a[i];
        if (n <= 1) {
            puts("Yes");
        }
        else if (n >= 3)
            puts("No");
        else {
            if (a[1] * a[1] < 4 * a[0] * a[2])
                puts("Yes");
            else
                puts("No");
        }
    }
}
           

C Governing sand

題意：有n種樹，每種樹有高度h，數量p，和砍一顆的代價c，現在要你去砍樹，使得最高的樹的數量和大于剩下的所有樹的數量和，求出最小代價

解法：我們按照高度排序後枚舉高度，假設該數高度為最高 i，比它高的樹全部要砍掉，我們求出所有比 i 低的樹總和sum，如果sum >= 該樹的數量v，就意味着我們還有再砍sum - v + 1顆比 i 的低的樹，我們肯定優先砍便宜的樹，但是我們知道c<=200，意味着我們最多200次就可以算出砍這些樹的最小花費，最後跟答案取最小值即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
struct node {
    int h, c, p;
    bool operator<(const node& t) const {
        return h < t.h;
    }
} a[maxn];
ll suf[maxn], C[210];
int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++)
            scanf("%d%d%d", &a[i].h, &a[i].c, &a[i].p);
        sort(a + 1, a + 1 + n);
        ll ans = 1e18;
        ll sum = 0;
        suf[n + 1] = 0;
        for (int i = n; i; i--)
            suf[i] = suf[i + 1] + 1ll * a[i].c * a[i].p;
        for (int i = 1; i <= 200; i++)
            C[i] = 0;
        for (int i = 1, j; i <= n; i = j) {
            ll v = 0;
            for (j = i; j <= n; j++)
                if (a[j].h == a[i].h)
                    v += a[j].p;
                else
                    break;
            ll res = sum - v + 1;
            ll tmp = suf[j];
            if (res > 0) {
                for (int k = 1; k <= 200 && res; k++)
                    if (C[k] <= res)
                        tmp += C[k] * k, res -= C[k];
                    else
                        tmp += res * k, res = 0;
            }
            ans = min(ans, tmp);
            for (int k = i; k < j; k++)
                sum += a[k].p, C[a[k].c] += a[k].p;
        }
        printf("%lld\n", ans);
    }
}
           

E Find the median

題意：有一個初始序列（沒有元素），有n次操作，每次操作給序列加這些元素： Li， Li+1，Li+2，，，Ri，然後求序列的中位數是多少，如果序列長度為偶數n，中位數為從小到大排序第n/2個數

解法：裸線段樹，如果不卡空間，直接動态開點，如果不能動态開點，那我們把所有查詢區間變成左開右閉區間然後離散化搞搞就行，沒啥好講的，線段樹簡單題

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 8e5 + 10;
ll sum[maxn * 4];
int S[maxn], L[maxn], R[maxn], tag[maxn * 4], n, sz;
#define ls o * 2
#define rs o * 2 + 1
#define m (l + r) / 2
void pushdown(int o, int l, int r) {
    if (tag[o] == 0)
        return;
    tag[ls] += tag[o]; tag[rs] += tag[o];
    sum[ls] += tag[o] * (S[m] - S[l - 1]);
    sum[rs] += tag[o] * (S[r] - S[m]);
    tag[o] = 0;
}
void up(int o, int l, int r, int ql, int qr) {
    if (l >=ql && r <= qr) {
        sum[o] += S[r] - S[l - 1];
        tag[o]++;
        return;
    }
    pushdown(o, l, r);
    if (ql <= m)
        up(ls, l, m, ql, qr);
    if (qr > m)
        up(rs, m + 1, r, ql, qr);
    sum[o] = sum[ls] + sum[rs];
}
int qu(int o, int l, int r, ll v) {
    if (l == r) {
        int k = sum[o] / (S[r] - S[l - 1]);
        return (v + k - 1)/ k + S[l - 1];
    }
    pushdown(o, l, r);
    if (sum[ls] < v)
        return qu(rs, m + 1, r, v - sum[ls]);
    return qu(ls, l, m, v);
}
ll X[maxn], Y[maxn];
void init() {
    ll A1, B1, C1, M1;
    ll A2, B2, C2, M2;
    cin>>n;
    cin>>X[1]>>X[2]>>A1>>B1>>C1>>M1;
    cin>>Y[1]>>Y[2]>>A2>>B2>>C2>>M2;
    for (int i = 1; i <= n; i++) {
        if (i > 2) {
            X[i] = (A1 * X[i - 1] + B1 * X[i - 2] + C1) % M1;
            Y[i] = (A2 * Y[i - 1] + B2 * Y[i - 2] + C2) % M2;
        }
        L[i] = min(X[i], Y[i]);
        R[i] = max(X[i], Y[i]) + 1;
        S[++sz] = L[i];
        S[++sz] = R[i];
    }
    sort(S + 1, S + 1 + sz);
    sz = unique(S + 1, S + 1 + sz) - S - 1;
}
int main() {
    init();
    for (int i = 1; i <= n; i++) {
        L[i] = lower_bound(S + 1, S + 1 + sz, L[i]) - S;
        R[i] = lower_bound(S + 1, S + 1 + sz, R[i]) - S;
        up(1, 1, sz, L[i] + 1, R[i]);
        ll v = sum[1] / 2;
        if (sum[1] & 1)
            v++;
        printf("%d\n", qu(1, 1, sz, v));
    }
}
           

F Energy stones

題意：有n個石頭，每個石頭有初始能量Ei，每秒能增加Li能量，能量值上限Ci，初始時間為0，現在有m次操作，每次在 ti (ti < ti+1)時刻選擇一段區間的石頭，把他們能量全部拿走，然後這些石頭目前能量就會變成0，求m次操作之後，我能得到的總能量。

解法：我們 i 從1開始枚舉每個石頭對所有操作的貢獻，我們看哪些操作區間包含 i，并且用一個set把那些包含 i 的操作的時間存起來，我們知道 i 點從0開始加能量，最多需要 k = Ci / Li 的時間使得能量不會超過Ci，我們對這些時間排序，把所有時間間隔存到樹狀數組裡，然後查詢時間間隔小于等于k（即[1, k]） 的時間間隔的總和sum1，ans += sum1 * Li，k + 1的時間能量石肯定充滿了，那麼我們查詢[k + 1, Max]看有多少個時間間隔sum2，然後ans += sum2 * Ei 即可，怎麼維護這些時間間隔，假設目前我們存了時間 1 8，我們找一下所有操作左端點在 i 的時間 t，假設有個 t = 5，那麼我們從樹狀數組中删除時間間隔 (8 - 7)，插入時間間隔(5 - 1)，(8 - 5)，至于右端點，反過來即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10, N = 2e5;
set<int> st;
vector<int> S[maxn], T[maxn];
#define low(x) x&-x
int c[maxn * 2], E[maxn], L[maxn], C[maxn];
ll val[maxn * 2];
void up(int x, int v) {
    for (int i = x; i <= N; i += low(i))
        c[i] += v, val[i] += x * v;
}
int qu1(int l, int r) {
    int res = 0;
    for (int i = r; i; i -= low(i))
        res += c[i];
    for (int i = l - 1; i; i -= low(i))
        res -= c[i];
    return res;
}
ll qu2(int l, int r) {
    ll res = 0;
    for (int i = r; i; i -= low(i))
        res += val[i];
    for (int i = l - 1; i; i -= low(i))
        res -= val[i];
    return res;
}
int main() {
    int ccsu_cat, Case = 0;
    scanf("%d", &ccsu_cat);
    while (ccsu_cat--) {
        int n, l, r, t, m;
        scanf("%d", &n);
        for (int i = 1; i <= N; i++)
            c[i] = val[i] = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d%d%d", &E[i], &L[i], &C[i]);
        scanf("%d", &m);
        while (m--) {
            scanf("%d%d%d", &t, &l, &r);
            S[l].push_back(t);
            T[r + 1].push_back(t);
        }
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            for (auto time : S[i]) {
                st.insert(time);
                auto it = st.find(time);
                auto pre = it, nxt = it;
                if (pre != st.begin()) {
                    pre--;
                    up(*it - *pre, 1);
                }
                nxt++;
                if (nxt != st.end())
                    up(*nxt - *it, 1);
                if (it != st.begin() && nxt != st.end())
                    up(*nxt - *pre, -1);
            }
            for (auto time : T[i]) {
                auto it = st.find(time);
                auto pre = it, nxt = it;
                if (pre != st.begin()) {
                    pre--;
                    up(*it - *pre, -1);
                }
                nxt++;
                if (nxt != st.end())
                    up(*nxt - *it, -1);
                if (it != st.begin() && nxt != st.end())
                    up(*nxt - *pre, 1);
                st.erase(time);
            }
            if (st.empty())
                continue;
            if (1ll * (*st.begin()) * L[i] + E[i] <= C[i])
                ans += *st.begin() * L[i] + E[i];
            else
                ans += C[i];
            if (L[i] == 0)
                continue;
            int k = C[i] / L[i];
            ans += 1ll * qu1(k + 1, N) * C[i];
            ans += 1ll * qu2(1, k) * L[i];
        }
        st.clear();
        for (int i = 1; i <= n + 1; i++)
            S[i].resize(0), T[i].resize(0);
        printf("Case #%d: %lld\n", ++Case, ans);
    }
}
           

H Pair

靠，賽場寫完沒過樣例，就放棄了，賽後發現數位dp多算進了x或着y為0的貢獻，補上這個一發切了，我們求出所有的均不滿足條件的(x, y)數量，即滿足這兩個條件：(x & y) <= c && (x^y) >= c，然後用A*B 減去就是答案，設d[i][sta1][sta2][lim1][lim2]為二進制長度為 i，第一，二個數字的限制情況分别為lim1，lim2，sta1 = 0 表示目前的(x & y) = c，1表示(x & y) < c，sta2 = 0表示目前的(x ^ y) = c，1表示(x ^ y) > c，然後進行基礎的數位dp轉移，設，a[pos]，b[pos]，c[pos]分别表示三個數二進制第pos位的狀态，如果目前的sta1 = 0，且a[i] & b[i] > c[i]，肯定不合法，如果a[i] & b[i] < c[i]，那麼下個狀态的sta1就變成了1，如果sta1 = 1，那就肯定沒有任何限制直接轉移，sta2同理。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int C, a[30], b[30];
ll d[31][2][2][2][2];
ll dfs(int pos, int sta1, int sta2, int lim1, int lim2) {
    if (pos < 0)
        return 1;
    if (d[pos][sta1][sta2][lim1][lim2] != -1)
        return d[pos][sta1][sta2][lim1][lim2];
    int up1 = lim1? a[pos] : 1;
    int up2 = lim2? b[pos] : 1;
    ll ans = 0;
    for (int i = 0; i <= up1; i++)
    for (int j = 0; j <= up2; j++) {
        int x = 0;
        if (C >> pos & 1)
            x = 1;
        if ((i & j) > x && !sta1)
            continue;
        if ((i ^ j) < x && !sta2)
            continue;
        int t1 = sta1 || ((i & j) < x);
        int t2 = sta2 || ((i ^ j) > x);
        ans += dfs(pos - 1, t1, t2, lim1 && (i == up1), lim2 && (j == up2));
    }
    d[pos][sta1][sta2][lim1][lim2] = ans;
    return ans;
}
int main() {
    int T;
    cin>>T;
    while (T--) {
        int x, y;
        cin>>x>>y>>C;
        ll ans = 1ll * x * y + max(x - C + 1, 0) + max(y - C + 1, 0);
        for (int i = 0; i < 30; i++)
            a[i] = b[i] = 0;
        memset(d, -1, sizeof(d));
        for (int i = 0; x; i++, x /= 2)
            a[i] = x % 2;
        for (int i = 0; y; i++, y /= 2)
            b[i] = y % 2;
        printf("%lld\n", ans - dfs(29, 0, 0, 1, 1));
    }
}
           

I Chessboard

題意：給你一個N，M，然後你可以任意構造一個 k * k的矩陣，使得矩陣内每個元素最少是M，且任意不同行不同列的 k 個元素總和不超過N且都相同，問有多少種構造方法。

解法：隔闆法好題，我們枚舉k，我們可以把每個元素減去M，那麼就相當于N減去 k * M，簡化問題并且不影響答案，然後我們枚舉元素總和T(T <= N)， 第二個限制條件的實質是我們抽取一些行一些列，使得這些行一整行加一些數，這些列一整列加一些數，使得加的數的總和是T，再轉化一下，現在有 k * 2 + T個1擺在一排，我們要給他分成2 * k份，每一份1的個數x減去1對應某行或者某列整行整列加的數，我們都知道隔闆法，不知道？那就繼續看：每兩個1之間有一個隔間，那麼k *2 + T有k * 2 - 1 +T個隔間，我們選擇k * 2 - 1個隔間就可以把這些1分成k * 2份，那麼好像目前的答案就是C(k * 2 - 1 + T，k * 2 - 1)，實則算多了，假設2 * 2的矩陣全部是1，那麼是不是可以了解為選取兩行+1或者選取兩列+1？像這種情況，為了避免重複算，如果整個矩陣最小值都x>=1，我們假設隻能是所有行都加了x，那麼就可以這麼去重，我們預先給所有列+1，相當于k + T個1分成2 * k份，那麼真正的答案就要減去 C(k - 1 + T，k * 2 - 1)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 6010, mod = 998244353;
ll p[maxn], inv[maxn];
void add(int &x, int y) {
    x += y;
    if (x >= mod)
        x -= mod;
    if (x < 0)
        x += mod;
}
ll ksm(ll x, int y) {
    ll res = 1;
    while (y) {
        if (y & 1)
            res = res * x % mod;
        x = x * x % mod;
        y /= 2;
    }
    return res;
}
ll C(int n, int m) {
    if (n < m)
        return 0;
    return p[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
    int T;
    cin>>T;
    p[0] = inv[0] = 1;
    for (int i = 1; i < maxn; i++) {
        p[i] = p[i - 1] * i % mod;
        inv[i] = ksm(p[i], mod - 2);
    }
    while (T--) {
        int n, m, ans = 0;
        cin>>n>>m;
        for (int k = 1; k <= n; k++) {
            int N = n - m * k;
            if (N < 0)
                break;
            for (int T = 0; T <= N; T++) {
                add(ans, C(2 * k - 1 + T, 2 * k - 1));
                add(ans, -C(k - 1 + T, 2 * k - 1));
            }
        }
        cout<<ans<<'\n';
    }
}