A.^&^

签到

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll A, B, C;

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        scanf("%lld%lld", &A, &B);
        C = 0;
        for (int i = 32; i >= 0; --i) {
            if ((A >> i) % 2 && (B >> i) % 2)
                C |= (1ll << i);
        }
        if (C == 0) {
            for (int i = 0; i <= 32; ++i) {
                if (((A >> i) % 2) + ((B >> i) % 2) == 1) {
                    C |= (1ll << i);
                    break;
                }
            }
        }
        printf("%lld\n", C);
    }
    return 0;
}

B. array

权值线段树线段树维护每个数出现的下标，树上二分

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

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, q, m, a[N], b[N];

struct SEG {
    int t[N << 2];
    void build(int id, int l, int r) {
        if (l == r) {
            t[id] = b[l]; 
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    }
    void update(int id, int l, int r, int pos) { 
        if (l == r) {
            t[id] = INF;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(id << 1, l, mid, pos);
        else update(id << 1 | 1, mid + 1, r, pos);
        t[id] = max(t[id << 1], t[id << 1 | 1]);
    }
    int ask(int id, int l, int r, int ql, int qr) {
        if (l >= ql && r <= qr) return t[id];
        int mid = (l + r) >> 1;
        int res = 0;
        if (ql <= mid) res = max(res, ask(id << 1, l, mid, ql, qr));
        if (qr > mid) res = max(res, ask(id << 1 | 1, mid + 1, r, ql, qr));
        return res;
    }
    int query(int id, int l, int r, int k, int R) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        if (mid < k || ask(id << 1, l, mid, k, mid) <= R) return query(id << 1 | 1, mid + 1, r, k, R);
        if (t[id << 1] <= R) return query(id << 1 | 1, mid + 1, r, k, R);
        else return query(id << 1, l, mid, k, R);
    }
}seg;

int main() {
    int _T; cin >> _T; 
    while (_T--) {
        scanf("%d%d", &n, &q); m = n + 1;
        for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[a[i]] = i; 
        b[m] = INF;
        seg.build(1, 1, m);
        int lstans = 0; 
        for (int _q = 1, op, x, k; _q <= q; ++_q) {
            scanf("%d%d", &op, &x);
            x ^= lstans;
            if (op == 1) {
                seg.update(1, 1, m, a[x]);
            } else {
                scanf("%d", &k);
                k ^= lstans;
                printf("%d\n", lstans = seg.query(1, 1, m, k, x));
            }
        }
    }
    return 0;
}

C. K-th occurrence

队友太强了

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

const int N = 1e5 + 10;
const int M = 23;
int n, q;
char s[N];
struct DA {
    int t1[N], t2[N], c[N];
    int sa[N];
    int Rank[N];
    int height[N];
    int str[N];
    int n, m;
    void init(char *s, int m, int n) {
        this->m = m;
        this->n = n;
        for (int i = 0; i < n; ++i) str[i] = s[i];
        str[n] = 0;
    }
    bool cmp(int *r, int a, int b, int l) {
        return r[a] == r[b] && r[a + l] == r[b + l];
    }
    void work() {
        ++n;
        int i, j, p, *x = t1, *y = t2;
        for (i = 0; i < m; ++i) c[i] = 0;
        for (i = 0; i < n; ++i) c[x[i] = str[i]]++;
        for (i = 1; i < m; ++i) c[i] += c[i - 1];
        for (i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i;
        for (j = 1; j <= n; j <<= 1) {
            p = 0;
            //直接利用sa数组排序第二关键字
            //后面的j个数第二关键字为空的最小
            for (i = n - j; i < n; ++i) {
                y[p++] = i;
            }
            for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
            //这样数组y保存的就是按照第二关键字排序的结果
            //基数排序第一关键字
            for (i = 0; i < m; ++i) c[i] = 0;
            for (i = 0; i < n; ++i) c[x[y[i]]]++;
            for (i = 1; i < m; ++i) c[i] += c[i - 1];
            for (i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
            //根据sa和x数组计算新的x数组
            swap(x, y);
            p = 1; x[sa[0]] = 0;
            for (i = 1; i < n; ++i) {
                x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
            }
            if (p >= n) break;
            //下次基数排序的最大值
            m = p;
        }
        int k = 0;
        --n;
        for (i = 0; i <= n; ++i) Rank[sa[i]] = i;
        //build height
        for (i = 0; i < n; ++i) {
            if (k) --k;
            j = sa[Rank[i] - 1];
            while (str[i + k] == str[j + k]) ++k;
            height[Rank[i]] = k; 
        }
    }
    struct RMQ {
        int Min[N][M]; 
        int mm[N];
        void init(int n, int *b) {
            mm[0] = -1;
            for (int i = 1; i <= n; ++i) {
                mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
                Min[i][0] = b[i];
            }
            for (int j = 1; j <= mm[n]; ++j) {
                for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
                    Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
                }
            }
        }
        int queryMin(int x, int y) {
            int k = mm[y - x + 1];
            return min(Min[x][k], Min[y - (1 << k) + 1][k]);  
        }
    }rmq;
    void initrmq() {
        rmq.init(n, height);
    }
    int lcp(int x, int y) {
        if (x == y) return 1e9;
        if (x > y) swap(x, y);
        ++x;
        return rmq.queryMin(x, y);   
    }
}da;

int getl(int x, int len) {
    int l = 1, r = x, res = x;
    while (r - l >= 0) {
        int mid = (l + r) >> 1;
        if (da.lcp(x, mid) >= len) {
            res = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return res;
}

int getr(int x, int len) {
    int l = x, r = n, res = x;
    while (r - l >= 0) {
        int mid = (l + r) >> 1;
        if (da.lcp(x, mid) >= len) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return res;
}

struct SEG {
    struct node {
        int sum, ls, rs;
        node() {
            ls = rs = sum = 0;
        } 
    }t[N * 50];
    int rt[N], cnt;
    void init() { 
        cnt = 0; 
        memset(rt, 0, sizeof rt);
    }
    void build(int &id, int l, int r) {
        id = ++cnt;
        t[id] = node();
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(t[id].ls, l, mid);
        build(t[id].rs, mid + 1, r);  
    }
    void up(int id) {
        int ls = t[id].ls, rs = t[id].rs;
        t[id].sum = 0;
        if (ls) t[id].sum += t[ls].sum;
        if (rs) t[id].sum += t[rs].sum; 
    }
    void update(int &now, int pre, int l, int r, int pos) {
        now = ++cnt;
        t[now] = t[pre];  
        if (l == r) {
            ++t[now].sum; 
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(t[now].ls, t[pre].ls, l, mid, pos);
        else update(t[now].rs, t[pre].rs, mid + 1, r, pos);
        up(now);
    }
    int query(int tl, int tr, int l, int r, int k) {
        if (l == r) return l;
        int mid = (l + r) >> 1;
        int lsum = t[t[tr].ls].sum - t[t[tl].ls].sum;    
        if (lsum >= k) {
            return query(t[tl].ls, t[tr].ls, l, mid, k);
        } else {
            return query(t[tl].rs, t[tr].rs, mid + 1, r, k - lsum); 
        }
    }
}seg;

int main() {
    int _T; scanf("%d", &_T);
    while (_T--) {
        scanf("%d%d", &n, &q);
        scanf("%s", s);
        da.init(s, 220, n);
        da.work(); da.initrmq();
        seg.init(); seg.build(seg.rt[0], 1, n);  
        for (int i = 1; i <= n; ++i)
            seg.update(seg.rt[i], seg.rt[i - 1], 1, n, da.sa[i] + 1);
        for (int i = 1, x, l, r, k, len; i <= q; ++i) {
            scanf("%d%d%d", &l, &r, &k);
            len = r - l + 1; 
            x = da.Rank[l - 1];  
            int L = getl(x, len);
            int R = getr(x, len);
            if (R - L + 1 < k) puts("-1");
            else printf("%d\n", seg.query(seg.rt[L - 1], seg.rt[R], 1, n, k));   
        }
    }
    return 0;
}

D. path

维护一个大小为$MaxK$的$multiset$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 100010

struct Edge {
    int to, w;

    Edge() {}
    
    Edge(int to, int w) : to(to), w(w) {}
    
    bool operator<(const Edge &other) const {
        return w < other.w;
    }
};

struct node {
    int now;
    ll w;

    node() {}
    
    node(int now, ll w) : now(now), w(w) {}
    
    bool operator<(const node &other) const {
        if (w == other.w) {
            return now < other.w;
        } else {
            return w < other.w;
        }
    }
};

int n, m, q, MaxK;
vector<vector<Edge>> G;
int Q[N];
ll res[N];
multiset<node> s;

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &q);
        G.clear();
        G.resize(n + 1);
        s.clear();
        for (int i = 1, u, v, w; i <= m; ++i) {
            scanf("%d %d %d", &u, &v, &w);
            G[u].push_back(Edge(v, w));
        }
        MaxK = 0;
        for (int i = 1; i <= q; ++i) {
            scanf("%d", Q + i);
            MaxK = max(MaxK, Q[i]);
        }
        for (int i = 1; i <= n; ++i) {
            sort(G[i].begin(), G[i].end());
            for (auto it : G[i]) {
                if (s.empty()) {
                    s.insert(node(it.to, it.w));
                    continue;
                }
                if (s.size() >= MaxK + 1) {
                    auto item = s.end();
                    item--;
                    if (it.w >= (*item).w) {
                        break;
                    } else {
                        s.erase(item);
                        s.insert(node(it.to, it.w));
                    }
                } else {
                    s.insert(node(it.to, it.w));
                }
            }
        }
        for (int i = 1; i <= MaxK; ++i) {
            res[i] = (*s.begin()).w;
            if (i == MaxK) break;
            int u = (*s.begin()).now;
            ll w = (*s.begin()).w;
            s.erase(s.begin());
            for (auto it : G[u]) {
                node now = node(it.to, w + it.w);
                if (s.empty()) {
                    s.insert(now);
                    continue;
                }
                if (s.size() >= MaxK - i + 1) {
                    auto item = s.end();
                    item--;
                    if (now.w >= (*item).w) {
                        break;
                    } else {
                        s.erase(item);
                        s.insert(now);
                    }
                } else {
                    s.insert(now);
                }
            }
        }
        for (int i = 1; i <= q; ++i) {
            printf("%lld\n", res[Q[i]]);
        }
    }
    return 0;
}

E. huntian oy

队友太强了

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

#define ll long long
const int N = 2e6 + 10;
const int M = 1e5 + 10;
const ll mod = 1e9 + 7;
int pri[N], check[N], phi[N], tot;
ll f[N], F[N], inv2, inv6, n, a, b; 
void init() {
    memset(check, 0, sizeof check);
    tot = 0;
    phi[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!check[i]) {
            pri[++tot] = i;
            phi[i] = i - 1;
        } 
        for (int j = 1; j <= tot; ++j) {
            if (1ll * i * pri[j] >= N) break;
            check[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            } else {
                phi[i * pri[j]] = phi[i] * (pri[j] - 1); 
            }
        }
    }
    f[1] = 0;
    for (int i = 1; i < N; ++i) {
        f[i] = f[i - 1];
        f[i] += 1ll * i * phi[i] % mod;
        f[i] %= mod;
    }
}

ll qpow(ll base, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}

ll sum_2(ll n) {
    return n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod;
}

ll sum(ll n) {
    return n * (n + 1) % mod * inv2 % mod;
}

map <int, int> mp;
bool vis[M]; 
ll S(ll x) {
    if (x < N) return f[x];
    if (mp.find(x) != mp.end()) return mp[x];
    ll res = sum_2(x);
    for (int i, j = 1; j < x; ) {
        i = j + 1;
        j = x / (x / i);
        res += mod - (sum(j) - sum(i - 1) + mod) % mod * S(x / i) % mod;
        res = res % mod;
    }
    return mp[x] = res;
}

int main() {
    init();
    inv2 = qpow(2, mod - 2); inv6 = qpow(6, mod - 2);
    mp.clear();
    memset(vis, 0, sizeof vis);
    int _T; scanf("%d", &_T);
    while (_T--) {
        scanf("%lld%lld%lld", &n, &a, &b);
        ll res = S(n);
        res = (res + mod - 1) % mod;
        res = res * inv2 % mod;
        printf("%lld\n", res);
    }
    return 0;
}

F. Shuffle Card

签到

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 100010

int n, m;
int a[N], b[N], vis[N], res[N];

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    while (~scanf("%d %d", &n, &m)) {
        memset(vis, 0, sizeof vis);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
        }
        for (int i = 1; i <= m; ++i) {
            scanf("%d", b + i);
        }
        int cnt = 0;
        for (int i = m; i >= 1; --i) {
            if (vis[b[i]]) {
                continue;
            }
            vis[b[i]] = 1;
            res[++cnt] = b[i];
        }
        for (int i = 1; i <= n; ++i) {
            if (!vis[a[i]]) {
                res[++cnt] = a[i];
            }
        }
        for (int i = 1; i <= n; ++i) {
            printf("%d ", res[i]);
        }
    }
    return 0;
}

G. Windows Of CCPC

签到

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

const int N = 1100;
int n, k;
char s[N][N]; 

void gao(int x, int y, int k) {
    if (k == 1) {
        s[x][y] = 'C';
        s[x][y + 1] = 'C';
        s[x + 1][y] = 'P';
        s[x + 1][y + 1] = 'C';
        return;
    } else {
        int n = 1 << (k - 1);
        gao(x, y, k - 1);
        gao(x, y + n, k - 1);
        gao(x + n, y, k - 1);
        gao(x + n, y + n, k - 1);
        for (int i = x + n; i < x + 2 * n; ++i) {
            for (int j = y; j < y + n; ++j) {
                if (s[i][j] == 'C') s[i][j] = 'P';
                else s[i][j] = 'C';
            }
        }
    }
}

int main() {
    int _T; scanf("%d", &_T);
    while (_T--) {
        int k; scanf("%d", &k);
        n = 1 << k;
        gao(1, 1, k);    
        for (int i = 1; i <= n; ++i) {
            s[i][n + 1] = 0;
            printf("%s\n", s[i] + 1);
        }
    }
    return 0;
}

H. Fishing Master

假设都在炖鱼的时候捕鱼，那么再补一条鱼的时间为$k-a[i]\%k$，根据这个排序，保证正好$n$条鱼

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 100010

int n, k;
ll a[N];


int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &k);
        ll cnt = 1, res = k;
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", a + i);
            res += a[i];
            cnt += a[i] / k;
            a[i] %= k;
        }
        cnt -= n;
        cnt = -cnt;
        sort(a + 1, a + 1 + n);
        for (int i = n; i >= 1 && cnt > 0; --i, --cnt) {
            res += k - a[i];
        }
        printf("%lld\n", res);
    }
    return 0;
}

I. Kaguya

题意：一个二分图，左边有有$n$个点，右边有$m$个点，两点连接概率为$\frac{1}{2}$，其期望

思路：$dp[i][j][k][l]$表示$BFS$到第$i$层，左边用了$j$个点，右边用了$k$个点，当前层有$l$个点，那么如果当前层为左边，下一层为右边，$dp[i+1][j][k+o][o]=dp[i][j][k][l]*P, P=\tbinom{m-k}{o}\cdot \frac{(2^l-1)^o}{2^{l\cdot (m-k)}}$

枚举转移

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 31;

ll p;

ll qpow(ll x, ll n) {
    ll res = 1;;
    while (n) {
        if (n & 1)res = res * x % p;
        x = x * x % p;
        n >>= 1;
    }
    return res;
}

int n, m;
int C[N][N];
int pw2[N * N], pw3[N][N], INV[N * N];
int f[N << 1][N][N][N];

void pre() {
    C[0][0] = 1ll;
    for (int i = 1; i < N; ++i) {
        C[i][0] = 1ll;
        for (int j = 1; j < N; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % p;
        }
    }
    pw2[0] = 1;
    for (int i = 1; i < N * N; ++i) {
        pw2[i] = pw2[i - 1] * 2ll % p;
    }
    for (int i = 1; i < N; ++i) {
        ll x = (pw2[i] + p - 1) % p;
        pw3[i][0] = 1;
        for (int j = 1; j < N; ++j) {
            pw3[i][j] = 1ll * pw3[i][j - 1] * x % p;
        }
    }
    for (int i = 1; i < N * N; ++i) {
        INV[i] = qpow(pw2[i], p - 2);
    }
}

void up(int &x, int y) {
    x += y;
    if (x >= p) x -= p;
}

void RUN() {
    scanf("%d %d %lld", &n, &m, &p);
    pre();
    memset(f, 0, sizeof f);
    f[0][1][0][1] = 1ll;
    ll res = 0;
    ll inv = qpow(m, p - 2);
    for (int i = 0; i <= n + m; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int k = 0; k <= m; ++k) {
                if (i & 1) {
                    for (int l = 1; l <= k - (i / 2); ++l) {
                        if (f[i][j][k][l] == 0) continue;
                        res = (res + 1ll * i * f[i][j][k][l] % p * inv % p * l % p) % p;
                        for (int o = 1; o + j <=
                                        n; ++o) {//f[i + 1][j + o][k][o] += f[i][j][k][l] * P, P = C[n - j][o] * (2^l - 1)^o/2^l(n-j)
                            up(f[i + 1][j + o][k][o],
                               1ll * f[i][j][k][l] * C[n - j][o] % p * pw3[l][o] % p * INV[l * (n - j)] % p);
                        }
                    }
                } else {
                    for (int l = 1; l <= j - (i / 2); ++l) {
                        if (f[i][j][k][l] == 0) continue;
                        for (int o = 1; o + k <=
                                        m; ++o) {//f[i + 1][j][k + o][o] += f[i][j][k][l]*P, P = C[m - k][o]*(2^l-1)^o/2^l(m-k)
                            up(f[i + 1][j][k + o][o],
                               1ll * f[i][j][k][l] * C[m - k][o] % p * pw3[l][o] % p * INV[l * (m - k)] % p);
                        }
                    }
                }
            }
        }
    }
    printf("%d\n", res);
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int _T;
    scanf("%d", &_T);
    while (_T--) {
        RUN();
    }

#ifdef LOCAL_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}