比賽鏈接

A. Sort

暴力

1. k = 1 k=1 k=1 檢查陣列是否有序；
2. k = 2 k=2 k=2 相當于再環上找個起點使得陣列有序，直接判斷；
3. k ≥ 3 k\ge 3 k≥3 考慮插入排序，每次暴力找到第 i i i 小的數的位置 p i p_i pi? ，構造 0 p i ? 1 p i n 0\ p_i-1\ p_i\ n 0 pi??1 pi? n 和排列 1 3 2 1\ 3\ 2 1 3 2 將第 i i i 小的放到最后面，重復 n n n 次即可，段數和 ≤ 3 n \le 3n ≤3n 滿足要求，

O ( n 2 ) O(n^2) O(n2)

#include<bits/stdc++.h>

using namespace std;
const int N = 1e3 + 5;
int n, k, a[N], b[N];
void Solve() {
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[i] = a[i];
    if (is_sorted(a + 1, a + n + 1))
        return puts("0"), void();
    if (k == 1) return puts("-2"), void();
    if (k == 2) {
        int i = n;
        for (; i; --i) if (a[i - 1] > a[i]) break;
        if (a[n] > a[1] || !is_sorted(a + 1, a + i)) puts("-2");
        else printf("1\n2\n0 %d %d\n2 1\n", i - 1, n);
        return;
    }
    vector<int> v;
    int *c = b + 1;
    sort(b + 1, b + n + 1);
    for (int i = 1, j; i <= n; ++i, ++c) {
        for (j = 1; j <= n - i + 1; ++j) if (a[j] == *c) break;
        if (j == n) continue;
        v.push_back(j);
        for (int t = j; t <= n - i; ++t) a[t] = a[t + 1];
    }
    printf("%d\n", (int) v.size());
    for (auto x: v)
        if (x == 1) printf("2\n0 %d %d\n2 1\n", x, n);
        else printf("3\n0 %d %d %d\n1 3 2\n", x - 1, x, n);
}
int main() {
    int T; scanf("%d", &T);
    while (T--) scanf("%d%d", &n, &k), Solve();
    return 0;
}

樹狀陣列

先預處理出最初第 i i i 小的數的位置 p i p_i pi? ，將 i i i 挪到最后相當于對所有 p j > p i p_j>p_i pj?>pi? 減 1 ，那么第 i i i 小的數的真實位置應該為 p i ? ∑ j < i [ p j < p i ] \displaystyle p_i-\sum_{j<i}[p_j<p_i] pi??j<i∑?[pj?<pi?] ，用樹狀陣列維護順序對即可，

O ( n log ? n ) O(n\log n) O(nlogn)

#include<bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int n, k, a[N], c[N], p[N];
void mdy(int i, int w) { for (; i <= n; i += i & -i) c[i] += w; }
int qry(int i, int w = 0) { for (; i; i -= i & -i) w += c[i]; return w; }
void Solve() {
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), p[i] = i, c[i] = 0;
    if (is_sorted(a + 1, a + n + 1))
        return puts("0"), void();
    if (k == 1) return puts("-2"), void();
    if (k == 2) {
        int i = n;
        for (; i; --i) if (a[i - 1] > a[i]) break;
        if (a[n] > a[1] || !is_sorted(a + 1, a + i)) puts("-2");
        else printf("1\n2\n0 %d %d\n2 1\n", i - 1, n);
        return;
    }
    vector<int> v;
    sort(p + 1, p + n + 1, [&](int x, int y) { return a[x] < a[y]; });
    for (int i = 1, j; i <= n; ++i) {
        j = p[i] + qry(p[i]);
        if (j == n) continue;
        v.push_back(j), mdy(p[i], -1);
    }
    printf("%d\n", (int) v.size());
    for (auto x: v)
        if (x == 1) printf("2\n0 %d %d\n2 1\n", x, n);
        else printf("3\n0 %d %d %d\n1 3 2\n", x - 1, x, n);
}
int main() {
    int T; scanf("%d", &T);
    while (T--) scanf("%d%d", &n, &k), Solve();
    return 0;
}

B. Mailman

經過的路徑總是一條歐拉回路，所以題目可以轉化為動態修改某個點度數，并詢問將所有點度數變為偶數的最小花費，

由于 n ≤ 3 n\le 3 n≤3 ，考慮對列建線段樹，每個節點維護中間節點度數全為偶數，且左右側節點度數狀態分別為 S , T S,T S,T 的最小花費，

合并的時候 O ( 2 3 n ) O(2^{3n}) O(23n) 列舉左右和中間的狀態，只用橫向邊連接，

注意當 L + 1 = R / m i d + 1 = R L+1=R\ /\ mid+1=R L+1=R / mid+1=R 的時候，中間連的邊會改變左右端點的狀態，

修改點度直接遞回到葉子暴力修改然后向上合并即可，

O ( 2 3 n ( m + q ) log ? m ) O(2^{3n}(m+q)\log m) O(23n(m+q)logm)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
using ll = int64_t;
const ll Inf = 1e18;
const int N = 5e4 + 5;
int k, n, q, a[N][2]; ll b[N][8]; // 3 * 1e9 > int
void cmin(ll &x, ll y) { x > y ? x = y : 0; }
struct Seg {
    ll tr[N << 2][8][8];
#define lc (p << 1)
#define rc (p << 1 | 1)
    void Up(int p, int L, int R) {
        int m = (L + R) >> 1;
        fp(i, 0, k) fp(j, 0, k) tr[p][i][j] = Inf;
        if (L + 1 == R) fp(i, 0, k) fp(j, 0, k) fp(t, 0, k) cmin(tr[p][i ^ t][j ^ t], tr[lc][i][i] + b[m][t] + tr[rc][j][j]);
        else if (m + 1 == R) fp(i, 0, k) fp(j, 0, k) fp(t, 0, k) cmin(tr[p][i][j ^ t], tr[lc][i][t] + b[m][t] + tr[rc][j][j]);
        else fp(i, 0, k) fp(j, 0, k) fp(t, 0, k) cmin(tr[p][i][j], tr[lc][i][t] + b[m][t] + tr[rc][t][j]);
//        int x = m == L ? k : 0, y = m + 1 == R ? k : 0; // Unified, but twice as slow
//        fp(i, 0, k) fp(j, 0, k) fp(t, 0, k) cmin(tr[p][i ^ (x & t)][j ^ (y & t)], tr[lc][i][x ? i : t] + b[m][t] + tr[rc][y ? j : t][j]);
    }
    void Build(int p, int L, int R) {
        if (L == R) {
            auto &w = tr[p];
            int x = a[L][0], y = a[L][1];
            fp(i, 0, k) fp(j, 0, k) w[i][j] = Inf;
            if (k == 3) {
                if (L == 1 || L == n) w[3][3] = x, w[0][0] = 0;
                else w[0][0] = x, w[3][3] = 0;
            } else {
                if (L == 1 || L == n)
                    w[7][7] = x + y, w[4][4] = y, w[2][2] = 0, w[1][1] = x;
                else w[0][0] = x + y, w[3][3] = y, w[5][5] = 0, w[6][6] = x;
            }
            return;
        }
        int m = (L + R) >> 1;
        Build(lc, L, m), Build(rc, m + 1, R), Up(p, L, R);
    }
    void mdy(int p, int L,int R, int x,int y){
        if (L == R) {
            static ll w[8];
            x = 1 << (x - 1);
            fp(i, 0, k) w[i ^ x] = tr[p][i][i];
            fp(i, 0, k) tr[p][i][i] = w[i];
            return;
        }
        int m = (L + R) >> 1;
        y <= m ? mdy(lc, L, m, x, y) : mdy(rc, m + 1, R, x, y), Up(p, L, R);
    }
}T;

int main() {
    ll ans = 0;
    scanf("%d%d%d", &k, &n, &q);
    fp(i, 0, k - 2) fp(j, 1, n) scanf("%d", a[j] + i), ans += a[j][i];
    fp(i, 0, k - 1) fp(j, 1, n - 1) scanf("%lld", b[j] + (1 << i)), ans += b[j][1 << i];
    fp(j, 1, n - 1) fp(i, 0, 7) b[j][i] = b[j][i & (i - 1)] + b[j][i & -i];
    k = (1 << k) - 1, T.Build(1, 1, n);
    for (int x1, y1, x2, y2, w; q--;) {
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &w), ans += w;
        T.mdy(1, 1, n, x1, y1), T.mdy(1, 1, n, x2, y2);
        printf("%lld\n", ans + T.tr[1][0][0]);
    }
    return 0;
}

C. Range Subsequence

莫隊+分塊 1

考慮如何從 [ l + 1 , r ] [l+1,r] [l+1,r] 的答案求出 [ l , r ] [l,r] [l,r] 的答案，

設 f ( l , r ) f(l,r) f(l,r) 表示 [ l , r ] [l,r] [l,r] 中以 a l a_l al? 開頭的最長 Range 子序列長度， b i b_i bi? 表示 i i i 所在的塊，

則 a n s l , r = a n s l + 1 , r + f ( l , r ) ? f ( n x l , r ) ans_{l,r}=ans_{l+1,r}+f(l,r)-f(nx_l,r) ansl,r?=ansl+1,r?+f(l,r)?f(nxl?,r) ，其中 n x l nx_l nxl? 表示下一個值等于 a l a_l al? 的位置，

考慮分塊預處理，對于所有 i i i ，暴力求出 f 1 ( i , k ) = f ( i , k n ) , k ≥ b i f_1(i,k)=f(i,k\sqrt n),k\ge b_i f1?(i,k)=f(i,kn ?),k≥bi? 和 f 2 ( i , j ) = f ( i , i + j ) f_2(i,j)=f(i,i+j) f2?(i,j)=f(i,i+j) ，其中 i , i + j i,i+j i,i+j 在同一個塊中，

對于每個塊 t t t 維護塊內每個數第一次和最后一次出現的位置 p t , x , q t , x p_{t,x},q_{t,x} pt,x?,qt,x? ，則有
f 1 ( i , k ) = f 1 ( i , k ? 1 ) + f 1 ( p k , a i + f 1 ( i , k ? 1 ) , k ) f_1(i,k)=f_1(i,k-1)+f_1(p_{k,a_i+f_1(i,k-1)},k) f1?(i,k)=f1?(i,k?1)+f1?(pk,ai?+f1?(i,k?1)?,k)
同理若 l , r l,r l,r 不在一個塊中，則
f ( l , r ) = f 1 ( l , b r ? 1 ) + f 2 ( p b r , a l + f 1 ( l , b r ? 1 ) , r ) f(l,r)=f_1(l,b_r-1)+f_2(p_{b_r,a_l+f_1(l,b_r-1)},r) f(l,r)=f1?(l,br??1)+f2?(pbr?,al?+f1?(l,br??1)?,r)
對于從 [ l , r ? 1 ] [l,r-1] [l,r?1] 的答案求出 [ l , r ] [l,r] [l,r] ，對稱地維護以 a r a_r ar? 結尾的答案 g ( l , r ) g(l,r) g(l,r) ，同樣也可以得到 g 1 ( i , k ) = g ( k n , i ) , k < b i g_1(i,k)=g(k\sqrt n,i),k<b_i g1?(i,k)=g(kn ?,i),k<bi? 和 g 2 ( i , j ) = g ( i ? j , i ) g_2(i,j)=g(i-j,i) g2?(i,j)=g(i?j,i) ，

注意到 f 1 , g 1 f_1,g_1 f1?,g1? 以及 f 2 , g 2 f_2,g_2 f2?,g2? 的空間互補，所以可以壓縮空間到 2 n n ≈ 241 M B 2n\sqrt n\approx 241{\ \rm MB} 2nn ?≈241 MB ，所以 p , q p,q p,q 可以直接開成兩個 n n n\sqrt n nn ? 的桶（因為 u n o r d e r e d _ m a p \rm unordered\_map unordered_map 的 c o u n t \rm count count 太慢過不了），總空間約 500 M B 500\ \rm MB 500 MB ，

O ( n n + n m ) O(n\sqrt n+n\sqrt m) O(nn ?+nm ?)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
#define fd(i, a, b) for(int i = (a), _##i = (b) - 1; i > _##i; --i)
using namespace std;
using ll = int64_t;
const int N = 1e5 + 5;
struct qry { int l, r, id; } q[N];
int a[N], b[N], pr[N], nx[N];
vector<int> f1[N], f2[N], f3[N], p1[315], p2[315];
int main() {
    int n, m, B, S, T; ll val = 0;
    scanf("%d%d", &n, &m), B = sqrt(n) + 1, S = n / sqrt(m) + 1, T = n / B + 1;
    vector<int> pos(n); vector<ll> ans(m);
    fp(i, 1, n) scanf("%d", a + i), --a[i];
    fp(i, 0, m - 1) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    sort(q, q + m, [&](qry a, qry b) { return a.l / S == b.l / S ? (a.l / S & 1 ? a.r > b.r : a.r < b.r) : a.l < b.l; });
    fp(t, 0, T - 1) {
        int L = t * B + 1, R = min(n, L + B - 1);
        p1[t].assign(n, 0), p2[t] = p1[t];
        fp(i, L, R) {
            auto &f = f2[i];
            pr[i] = pos[a[i]], pos[a[i]] = i, b[i] = t;
            f.assign(R - i + 1, 0), f[0] = 1, p2[t][a[i]] = i;
            fp(j, i + 1, R) f[j - i] = f[j - i - 1] + (a[j] == a[i] + f[j - i - 1]);
            f1[i].assign(T + 1, 0), f1[i][t + 1] = f[R - i];
        }
        fd(i, R, L) {
            auto &f = f3[i];
            f.assign(i - L + 1, 0), f[0] = 1, p1[t][a[i]] = i;
            fd(j, i - 1, L) f[i - j] = f[i - j - 1] + (a[j] == a[i] - f[i - j - 1]);
            f1[i][t] = f[i - L];
            fd(k, b[i] - 1, 0) f1[i][k] = f1[i][k + 1] + (a[i] >= f1[i][k + 1] && p2[k][a[i] - f1[i][k + 1]] ? f3[p2[k][a[i] - f1[i][k + 1]]].back() : 0);
        }
    }
    pos.assign(n, n + 1);
    fd(i, n, 1) {
        nx[i] = pos[a[i]], pos[a[i]] = i;
        fp(k, b[i] + 1, T - 1) f1[i][k + 1] = f1[i][k] + (a[i] + f1[i][k] < n && p1[k][a[i] + f1[i][k]] ? f2[p1[k][a[i] + f1[i][k]]].back() : 0);
    }
    auto f = [&](int L, int R) {
        if (L > R) return 0;
        if (b[L] == b[R]) return f2[L][R - L];
        int w = f1[L][b[R]], nx = a[L] + w, p;
        if (nx < n && (p = p1[b[R]][nx]) && p <= R) w += f2[p][R - p];
        return w;
    };
    auto g = [&](int L, int R) {
        if (L > R) return 0;
        if (b[L] == b[R]) return f3[R][R - L];
        int w = f1[R][b[L] + 1], nx = a[R] - w, p;
        if (nx >= 0 && (p = p2[b[L]][nx]) && p >= L) w += f3[p][p - L];
        return w;
    };
    int L = 1, R = 0;
    fp(i, 0, m - 1) {
        int ql = q[i].l, qr = q[i].r;
        while (L > ql) --L, val += f(L, R) - f(nx[L], R);
        while (R < qr) ++R, val += g(L, R) - g(L, pr[R]);
        while (L < ql) val -= f(L, R) - f(nx[L], R), L++;
        while (R > qr) val -= g(L, R) - g(L, pr[R]), R--;
        ans[q[i].id] = val;
    }
    for (auto w: ans) printf("%lld\n", w);
    return 0;
}

莫隊+分塊 2

上面那種寫法太麻煩了，而且還卡空間，卡常，

考慮將 f 1 ( i , k ) f_1(i,k) f1?(i,k) 的定義改為值 a i + f ( i , k n ) a_i+f(i,k\sqrt n) ai?+f(i,kn ?) 的位置，則 f ( i , k n ) = a f 1 ( i , k ) ? a i + 1 f(i,k\sqrt n)=a_{f_1(i,k)}-a_i+1 f(i,kn ?)=af1?(i,k)??ai?+1，；記 n x t i nxt_i nxti? 表示下一個 a i + 1 a_i+1 ai?+1 出現的位置，

從大到小列舉 i i i ，從 i i i 開始，在塊內不斷跳 n x t nxt nxt 得到 f 1 ( i , b i + 1 ) f_1(i,b_i+1) f1?(i,bi?+1) ，然后再跳一次 n x t nxt nxt 得到下一個位置 p ≥ i p\ge i p≥i ，則 f 1 ( p , k ) f_1(p,k) f1?(p,k) 已經求出，于是有

f 1 ( i , k ) = { f 1 ( i , b i + 1 ) b p ≥ k f 1 ( p , k ) b p < k f_1(i,k)=\left\{\begin{aligned} &f_1(i,b_i+1) & b_p\ge k\\ &f_1(p,k) & b_p<k \end{aligned}\right. f1?(i,k)={?f1?(i,bi?+1)f1?(p,k)?bp?≥kbp?<k?

其他陣列也可以做同樣的簡化，

O ( n n + n m ) O(n\sqrt n+n\sqrt m) O(nn ?+nm ?)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
#define fd(i, a, b) for(int i = (a), _##i = (b) - 1; i > _##i; --i)
using namespace std;
const int N = 1e5 + 5;
using ll = int64_t;
using arr = int[N];
struct qry { int l, r, id; } q[N];
arr a, b, p1, n1, p2, n2;
vector<int> f1[N];
vector<short> f2[N], f3[N];
int f(int L, int R) {
    if (L > R) return 0;
    if (b[L] == b[R]) return f2[L][R - L];
    int p = f1[L][b[R]], w = a[p] - a[L] + 1;
    if ((p = n2[p]) <= R) w += f2[p][R - p];
    return w;
}
int g(int L, int R) {
    if (L > R) return 0;
    if (b[L] == b[R]) return f3[R][R - L];
    int p = f1[R][b[L] + 1], w = a[R] - a[p] + 1;
    if ((p = p2[p]) >= L) w += f3[p][p - L];
    return w;
}
int main() {
    int n, m, B, S, T; ll val = 0;
    scanf("%d%d", &n, &m);
    b[0] = -1, b[n + 1] = n + 1;
    vector<int> pos(n + 1); vector<ll> ans(m);
    B = sqrt(n) + 1, S = n / sqrt(m) + 1, T = n / B + 1;
    fp(i, 1, n) scanf("%d", a + i), f1[i].assign(T + 1, 0);
    fp(i, 0, m - 1) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    sort(q, q + m, [&](qry a, qry b) { return a.l / S == b.l / S ? (a.l / S & 1 ? a.r > b.r : a.r < b.r) : a.l < b.l; });
    fp(t, 0, T - 1) {
        int L = t * B + 1, R = min(n, L + B - 1), x, p;
        fp(i, L, R) {
            f3[i].assign(i - L + 1, 1), b[i] = t;
            p1[i] = pos[x = a[i]], pos[x] = i, p = p2[i] = pos[x - 1];
            fd(j, p, L) f3[i][i - j] = f3[p][p - j] + 1;
            for (p = i; p >= L; p = p2[p]) f1[i][t] = p;
            fd(k, t - 1, 0) f1[i][k] = b[p] >= k ? f1[p][k] : f1[i][t];
        }
    }
    pos.assign(n + 2, n + 1);
    fd(t, T - 1, 0) {
        int L = t * B + 1, R = min(n, L + B - 1), x, p;
        fd(i, R, L) {
            f2[i].assign(R - i + 1, 1);
            n1[i] = pos[x = a[i]], pos[x] = i, p = n2[i] = pos[x + 1];
            fp(j, p, R) f2[i][j - i] = f2[p][j - p] + 1;
            for (p = i; p <= R; p = n2[p]) f1[i][t + 1] = p;
            fp(k, t + 2, T - 1) f1[i][k] = b[p] < k ? f1[p][k] : f1[i][t + 1];
        }
    }
    int L = 1, R = 0;
    fp(i, 0, m - 1) {
        int ql = q[i].l, qr = q[i].r;
        while (L > ql) --L, val += f(L, R) - f(n1[L], R);
        while (R < qr) ++R, val += g(L, R) - g(L, p1[R]);
        while (L < ql) val -= f(L, R) - f(n1[L], R), L++;
        while (R > qr) val -= g(L, R) - g(L, p1[R]), R--;
        ans[q[i].id] = val;
    }
    for (auto w: ans) printf("%lld\n", w);
    return 0;
}

回滾莫隊

D. Linear Algebra

E. Nearest Point

考慮固定一個點 i i i ，并以 i i i 為參考系，

設 P r o j ( j , α ) {\rm Proj}(j,\alpha) Proj(j,α) 表示 j j j 在 v α = ( cos ? α , sin ? α ) v_{\alpha}=(\cos\alpha,\sin\alpha) vα?=(cosα,sinα) 方向上的投影長，

對于任意兩個向量 j , k j,k j,k ，存在 4 個臨界角度 α \alpha α 使得 P r o j ( j , α ) = P r o j ( k , α ) {\rm Proj}(j,\alpha)={\rm Proj}(k,\alpha) Proj(j,α)=Proj(k,α) ，易證 v α ⊥ j + k v_\alpha\perp j+k vα?⊥j+k 或 v α ⊥ j ? k v_\alpha\perp j-k vα?⊥j?k （畫圖理解一下），

一共有 O ( n 2 ) O(n^2) O(n2) 個臨界角，把 [ ? π , π ) [-\pi,\pi) [?π,π) 分成了 O ( n 2 ) O(n^2) O(n2) 段，每一段內 i i i 的最近點是不變的，所以可以每一段內任取一個角度，算出最近點，并把這一段的概率都算到那個點上即可，

O ( n 4 log ? n ) O(n^4\log n) O(n4logn)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
using db = double;
const db Pi = acos(-1);
struct Vec {
    int x, y;
    Vec operator+(Vec b) const { return {x + b.x, y + b.y}; }
    Vec operator-(Vec b) const { return {x - b.x, y - b.y}; }
    db v_deg() const { return atan2(x, -y); }
};
int main() {
    int n; scanf("%d", &n);
    vector<db> d, ans(n);
    vector<Vec> a(n), b(n);
    for (auto &p: a) scanf("%d%d", &p.x, &p.y);
    auto Proj = [&](db x, db y, Vec c) { return abs(x * c.x + y * c.y); };
    fp(i, 0, n - 1) {
        ans.assign(n, 0), d = {-Pi, Pi};
        fp(j, 0, n - 1) b[j] = a[j] - a[i];
        fp(j, 0, n - 1) fp(k, j + 1, n - 1)
            d.push_back((b[j] - b[k]).v_deg()), d.push_back((b[j] + b[k]).v_deg());
        for (auto deg: d) d.push_back(deg + (deg < 0 ? Pi : -Pi));
        sort(d.begin(), d.end());
        fp(t, 1, d.size() - 1) {
            if (d[t] - d[t - 1] < 1e-11) continue;
            int k = 0; db L = d[t] - d[t - 1], m = d[t - 1] + L * 0.5, x = cos(m), y = sin(m), mn = 1e18, w;
            fp(j, 0, n - 1) if (j != i && mn - (w = Proj(x, y, b[j])) > 1e-9) mn = w, k = j;
            ans[k] += L;
        }
        fp(j, 0, n - 1) printf("%.9lf%c", i == j ? 0 : ans[j] / Pi * .5, " \n"[j == n - 1]);
    }
    return 0;
}

F. Leapfrog

題目等價于找到一個排列 p p p ，最大化 a p n + ∑ i = 1 n ? 1 b p i t p i n ? i \displaystyle a_{p_n}+\sum_{i=1}^{n-1}b_{p_i}t_{p_i}^{n-i} apn??+i=1∑n?1?bpi??tpi?n?i?

設 p ′ p' p′ 為以 t t t 第一關鍵字降序， b b b 第二關鍵字升序， a a a 第三關鍵字升序排序后的排列，

注意到 b ≤ 1 0 4 , t ∈ { 2 , 3 } b\le10^4,t\in\{2,3\} b≤104,t∈{2,3} ，而 1 0 4 × 2 23 < 3 23 10^4\times2^{23}<3^{23} 104×223<323 ，所以 p ′ p' p′ 與最優排列的前 n ? 23 n-23 n?23 項一定相同，

考慮用 D P \rm DP DP 來求出最后剩下的 m m m 個物品的最優排列，

設 f i , j , 0 / 1 f_{i,j,0/1} fi,j,0/1? 表示放了 i i i 個物品，其中有 j j j 個 t = 2 t=2 t=2 的物品，以及是否有物品放到了最后的最優答案， x i / y i x_i/y_i xi?/yi? 分別表示第 i i i 個 t = 2 / 3 t=2/3 t=2/3 的物品的位置，

則有
f i , j , 0 = max ? { f i ? 1 , j , 0 + b x i ? j 2 m ? i , f i ? 1 , j ? 1 , 0 + b y j 3 m ? i } f i , j , 1 = max ? { f i ? 1 , j , 1 + b x i ? j 2 m ? i + 1 , f i ? 1 , j ? 1 , 1 + b y j 3 m ? i + 1 , f i ? 1 , j , 0 + a x i ? j , f i ? 1 , j ? 1 , 0 + a y j } \begin{aligned} f_{i,j,0}&=\max\{f_{i-1,j,0}+b_{x_{i-j}}2^{m-i}, f_{i-1,j-1,0}+b_{y_j}3^{m-i}\}\\ f_{i,j,1}&=\max\{f_{i-1,j,1}+b_{x_{i-j}}2^{m-i+1}, f_{i-1,j-1,1}+b_{y_j}3^{m-i+1},f_{i-1,j,0}+a_{x_{i-j}}, f_{i-1,j-1,0}+a_{y_j}\}\\ \end{aligned} fi,j,0?fi,j,1??=max{fi?1,j,0?+bxi?j??2m?i,fi?1,j?1,0?+byj??3m?i}=max{fi?1,j,1?+bxi?j??2m?i+1,fi?1,j?1,1?+byj??3m?i+1,fi?1,j,0?+axi?j??,fi?1,j?1,0?+ayj??}?
O ( n log ? n + 2 3 2 ) O(n\log n+23^2) O(nlogn+232)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
using ll = int64_t;
const int N = 1e5 + 5, P = 998244353;
struct Data { int a, b, t; } p[N];
int n; ll f[24][24][2], p2[N], p3[N];
void cmax(ll &x, ll y) { x < y ? x = y : 0; }
ll dp(vector<Data> &a, vector<Data> &b) {
    int A = a.size(), B = b.size();
    memset(f, 0x80, sizeof f), f[0][0][0] = 0, n = A + B;
    fp(i, 0, n - 1) fp(j, 0, min(i, B)) {
        if (i - j < A) {
            cmax(f[i + 1][j][1], f[i][j][0] + a[i - j].a);
            fp(k, 0, 1) cmax(f[i + 1][j][k], f[i][j][k] + a[i - j].b * p2[n - i - 1 + k]); // + k !!
        }
        if (j == B) continue;
        cmax(f[i + 1][j + 1][1], f[i][j][0] + b[j].a);
        fp(k, 0, 1) cmax(f[i + 1][j + 1][k], f[i][j][k] + b[j].b * p3[n - i - 1 + k]); // + k !!
    }
    return f[n][B][1];
}
void Solve() {
    fp(i, 1, n) scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].t);
    sort(p + 1, p + n + 1, [](Data x, Data y) { return x.t == y.t ? (x.b == y.b ? x.a < y.a : x.b > y.b) : x.t > y.t; });
    ll ans = 0, m = max(0, n - 23); vector<Data>a, b;
    fp(i, 1, m) ans += (ll) p[i].b * (p[i].t == 2 ? p2[n - i] : p3[n - i]) % P;
    fp(i, m + 1, n) p[i].t == 2 ? a.push_back(p[i]) : b.push_back(p[i]);
    printf("%lld\n", (ans + dp(a, b)) % P);
}
int main() {
    p2[0] = p3[0] = 1;
    fp(i, 1, 23) p2[i] = 2 * p2[i - 1], p3[i] = 3 * p3[i - 1];
    fp(i, 24, N - 1) p2[i] = 2 * p2[i - 1] % P, p3[i] = 3 * p3[i - 1] % P;
    int T; scanf("%d", &T);
    while (T--) scanf("%d", &n), Solve();
    return 0;
}

G. Limit

直接泰勒展開，原式可化為
x ? t ∑ i = 1 n a i ∑ j ≥ 1 ( ? 1 ) j + 1 ( b i x ) j j = ∑ j ≥ 1 1 j x j ? t ∑ i = 1 n ( ? 1 ) j + 1 a i b i j x^{-t}\sum_{i=1}^na_i\sum_{j\ge1}(-1)^{j+1}\frac{(b_ix)^j}{j}=\sum_{j\ge1}\frac1jx^{j-t}\sum_{i=1}^n(-1)^{j+1}a_ib_i^j x?ti=1∑n?ai?j≥1∑?(?1)j+1j(bi?x)j?=j≥1∑?j1?xj?ti=1∑n?(?1)j+1ai?bij?
算出所有系數，根據極限定義輸出答案即可，

O ( t n ) O(tn) O(tn)

#include<bits/stdc++.h>

using namespace std;
using ll = int64_t;
int main() {
    int n, t;
    scanf("%d%d", &n, &t);
    if (!t)return printf("0"), 0;
    vector<ll> a(6);
    ll x, y, z, g, b = t;
    for (int i = 0; i < n; ++i) {
        scanf("%lld%lld", &x, &y), z = y;
        for (int j = 1; j < 6; ++j) a[j] += (j & 1 ? 1 : -1) * x * z, z *= y;
    }
    for (int i = 1; i < t; ++i)
        if (a[i]) return printf("infinity"), 0;
    g = __gcd(a[t], b), a[t] /= g, b /= g;
    if (abs(b) == 1) printf("%lld", a[t]);
    else printf("%lld/%d", a[t], b);
    return 0;
}

H. Set

隨機

每次隨機在 S S S 中隨機選取 l = ? 512 r ? \displaystyle l=\left\lceil\frac{512}r\right\rceil l=?r512?? 個數即可，

考慮出錯的概率，即存在 r r r 個集合，這 r r r 個集合的并至多為 256 256 256 個數中的任意 127 127 127 個，即
p E r r o r ≤ ( k r ) ( 256 127 ) [ ( 127 l ) ( 256 l ) ] r < 3.502 × 1 0 ? 88 p_{\rm Error}\le {k\choose r}{256\choose 127}\left[\frac{{127\choose l}}{{256\choose l}}\right]^r<3.502\times10^{-88} pError?≤(rk?)(127256?)[(l256?)(l127?)?]r<3.502×10?88
完全可以通過，

O ( 256 k ) O(256k) O(256k)

#include<bits/stdc++.h>

using namespace std;
int main() {
    int k, r;
    scanf("%d%d", &k, &r), r = (512 + r - 1) / r;
    while (k--) {
        string s(256, '0');
        for (int i = 0; i < r; ++i) s[rand() & 255] = '1';
        puts(s.c_str());
    }
    return 0;
}

構造

設 I t = { i + ( t ? 1 ) x m o d ?? 256 + 1 ∣ 0 ≤ i < l } I_t=\{i+(t-1)x \mod 256 + 1\mid 0\le i< l\} It?={i+(t?1)xmod256+1∣0≤i<l} ，任選 r r r 個集合的并集大小最小為 l + ( r ? 1 ) x ≥ 128 l+(r-1)x\ge 128 l+(r?1)x≥128 ，取 x ≥ ? 128 ? l r ? 1 ? \displaystyle x\ge\left\lceil\frac{128-l}{r-1}\right\rceil x≥?r?1128?l?? 即可，

實際上可以求出下界為 10 10 10 ，所以只需要任選一個 10 ≤ x ≤ 246 10\le x\le 246 10≤x≤246 即可，

O ( 256 k ) O(256k) O(256k)

#include<bits/stdc++.h>

using namespace std;
int main() {
    int k, r, y = 0;
    scanf("%d%d", &k, &r), r = (512 + r - 1) / r;
    for (; k--; y += 10) {
    	string s(256, '0');
        for (int i = 0; i < r; ++i) s[(i + y) & 255] = '1';
        puts(s.c_str());
    }
    return 0;
}

I. Discrete Mathematics

J. Leaking Roof

高格子向四周低格子連邊跑拓撲排序即可，

O ( n 2 ) O(n^2) O(n2)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
const int N = 500 + 5, M = N * N;
using ll = int64_t;
using db = double;
using arr = int[N];
int in[M], a[N][N], id[N][N];
vector<int> G[M];

void ADD(int u, int v) { G[u].push_back(v), ++in[v]; }

int main() {
    int n, m, cnt = 0;
    scanf("%d%d", &n, &m);
    fp(i, 1, n)a[i][0] = a[i][n + 1] = a[0][i] = a[n + 1][i] = 1e9;
    fp(i, 1, n)fp(j, 1, n)scanf("%d", a[i] + j), id[i][j] = ++cnt;
    fp(i, 1, n) fp(j, 1, n) {
        if (a[i][j] > a[i - 1][j]) ADD(id[i][j], id[i - 1][j]);
        if (a[i][j] > a[i + 1][j]) ADD(id[i][j], id[i + 1][j]);
        if (a[i][j] > a[i][j - 1]) ADD(id[i][j], id[i][j - 1]);
        if (a[i][j] > a[i][j + 1]) ADD(id[i][j], id[i][j + 1]);
    }
    queue<int> q;
    vector<db> f(cnt + 1, m);
    fp(i, 1, cnt) if (!in[i]) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (!G[u].empty()) f[u] /= G[u].size();
        for (auto v: G[u]) {
            f[v] += f[u];
            if (!--in[v]) q.push(v);
        }
    }
    for (int i = 1; i <= n; ++i, puts(""))
        fp(j, 1, n) a[i][j] ? printf("0 ") : printf("%lf ", f[id[i][j]]);
    return 0;
}

K. Meal

實際上題目相當于每個人從當前沒有被選的菜中以 a i , j a_{i,j} ai,j? 的概率選取一道菜，

所以直接記錄當前已經打了的菜的集合為 S S S 的概率 f ( S ) f(S) f(S) ，然后直接列舉下一道菜轉移即可，

O ( n 2 n ) O(n2^n) O(n2n)

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
const int N = 21, M = 1 << 20 | 5, P = 998244353;
using ll = int64_t;
using arr = int[N];
vector<int> inv;
int a[N][N];

int main() {
    inv.resize(2005), inv[1] = 1;
    fp(i, 2, 2e3) inv[i] = (ll) (P - P / i) * inv[P % i] % P;
    int n, m;
    scanf("%d", &n), m = (1 << n) - 1;
    fp(i, 0, n - 1) fp(j, 0, n - 1) scanf("%d", a[i] + j);
    vector<int> f(m + 1), g(m + 1), cnt(m + 1);
    f[0] = 1;
    fp(s, 0, m) cnt[s] = __builtin_popcount(s);
    fp(i, 0, n - 1) {
        vector<ll> ans(n);
        g = f, f.assign(m + 1, 0);
        fp(s, 0, m) if (cnt[s] == i) {
            ll sum = 0, val;
            vector<int> vj;
            for (int t = m ^ s; t; t &= t - 1) vj.push_back(__builtin_ctz(t)), sum += a[i][vj.back()];
            sum = inv[sum];
            for (auto j: vj) val = (ll) g[s] * a[i][j] % P * sum % P, f[s | 1 << j] = (f[s | 1 << j] + val) % P, ans[j] += val;
        }
        fp(j, 0, n - 2) printf("%lld ", ans[j] % P);
        printf("%lld%c", ans.back() % P, "\n\0"[i == n - 1]);
    }
    return 0;
}

L. Euler Function

設 p p p 是質數，根據歐拉函式的性質可得：

1. 當 p ∣ q p\mid q p∣q 時， φ ( p q ) = φ ( p ) q \varphi(pq)=\varphi(p)q φ(pq)=φ(p)q
2. 當 p ? q p\nmid q p?q 時， φ ( p q ) = φ ( p ) ( q ? 1 ) \varphi(pq)=\varphi(p)(q-1) φ(pq)=φ(p)(q?1)

注意到 w ≤ 100 w\le 100 w≤100 ，最多只有 25 25 25 個質數，

考慮線段樹，每個節點開一個長度為 25 25 25 的 b i t s e t \rm bitset bitset 表示區間內是否所有數都含有這個質因子，

當整個區間的數都含有質因子 p p p 時，可以直接打上一個乘法標記，沒有則向下遞回，

由于只有 25 25 25 個質數，所以每個節點至多被暴力修改 25 25 25 次，

O ( 25 n + m log ? n ) O(25n+m\log n) O(25n+mlogn)

預處理寫得有點長，應該用埃氏篩法，

#include<bits/stdc++.h>

#define fp(i, a, b) for(int i = (a), _##i = (b) + 1; i < _##i; ++i)
using namespace std;
const int N = 1e5 + 5, A = 101, P = 998244353;
using ll = int64_t;
bitset<A> vis;
int a[N], phi[A], pr[A], id[A];
vector<pair<int, int>> val[A];
bitset<26> G[A];
void sieves() {
    phi[1] = 1;
    fp(i, 2, A - 1) {
        if (!vis[i]) pr[++pr[0]] = i, phi[i] = i - 1, val[i] = {{i, id[i] = pr[0] - 1}}, G[i][pr[0] - 1] = 1;
        for (int j = 1, x, p; j <= pr[0] && (x = i * (p = pr[j])) < A; ++j) {
            vis[x].flip(), val[x] = val[i], G[x] = G[i];
            if (i % pr[j]) phi[x] = phi[i] * (pr[j] - 1), val[x].emplace_back(pr[j], id[p]), G[x][id[p]] = 1;
            else {
                phi[x] = phi[i] * p;
                for (auto &w: val[x])
                    if (w.second == id[p])
                        w.first *= p;
                break;
            }
        }
    }
}
struct Seg {
    int tag[N << 2], tr[N << 2];
    bitset<26> f[N << 2];
#define lc (p << 1)
#define rc (p << 1 | 1)
    void Up(int p) { tr[p] = (tr[lc] + tr[rc]) % P, f[p] = f[lc] & f[rc]; }
    void upd(int p, int w) { tr[p] = (ll) tr[p] * w % P, tag[p] = (ll) tag[p] * w % P; }
    void Down(int p) { int &w = tag[p]; if (w > 1) upd(lc, w), upd(rc, w), w = 1; }
    void Build(int p, int L, int R) {
        tag[p] = 1;
        if (L == R) return f[p] = G[a[L]], tr[p] = phi[a[L]], void();
        int m = (L + R) >> 1;
        Build(lc, L, m), Build(rc, m + 1, R), Up(p);
    }
    void mdy(int p, int L, int R, int a, int b, int x, int i) {
        if (a <= L && R <= b && f[p][i]) return upd(p, x);
        if (L == R) return f[p][i] = 1, tr[p] = (ll) tr[p] * phi[x] % P, void();
        int m = (L + R) >> 1; Down(p);
        if (a <= m) mdy(lc, L, m, a, b, x, i);
        if (b > m) mdy(rc, m + 1, R, a, b, x, i);
        Up(p);
    }
    int qry(int p, int L, int R, int a, int b) {
        if (a <= L && R <= b) return tr[p];
        int m = (L + R) >> 1, w = 0; Down(p);
        if (a <= m) w = qry(lc, L, m, a, b);
        if (b > m) w = (w + qry(rc, m + 1, R, a, b)) % P;
        return w;
    }
} T;

int main() {
    sieves();
    int n, q; scanf("%d%d", &n, &q);
    fp(i, 1, n) scanf("%d", a + i);
    T.Build(1, 1, n);
    for (int op, l, r, w; q--;) {
        scanf("%d%d%d", &op, &l, &r);
        if (!op) {
            scanf("%d", &w);
            for (auto x: val[w])
                T.mdy(1, 1, n, l, r, x.first, x.second);
        } else printf("%d%c", T.qry(1, 1, n, l, r), "\n\0"[!q]);
    }
    return 0;
}

M. Addition

先求出和 c c c ，若 c ≥ 0 c\ge 0 c≥0 ，則默認符號位全為 1 1 1 ，否則令 c = ? c c=-c c=?c 并默認符號位為 ? 1 -1 ?1 ，

若當前位為 1 1 1 且實際符號位與默認不符，則高位 + 1 +1 +1 ，即 2 k = 2 k + 1 ? 2 k 2^k=2^{k+1}-2^k 2k=2k+1?2k ，

O ( n ) O(n) O(n)

#include<bits/stdc++.h>

using namespace std;
using ll = int64_t;

int main() {
    int n; scanf("%d", &n);
    vector<int> sgn(n);
    for (auto &x: sgn)scanf("%d", &x);
    ll a = 0, b = 1;
    for (ll x, i = 0; i < n; ++i) scanf("%lld", &x), a += sgn[i] * (x << i);
    for (ll x, i = 0; i < n; ++i) scanf("%lld", &x), a += sgn[i] * (x << i);
    if (a < 0) b = -1, a = -a;
    for (ll i = 0; i < n; ++i) {
        printf("%d%c", a & 1, " \0"[i == n - 1]);
        a = (a >> 1) + (a & 1 && sgn[i] != b);
    }
    return 0;
}