「解题报告」牛客练习赛68

牛客的题还是比较板啊，像我这样的菜鸡都能打到 rk30？？？/jk

A 牛牛的mex

主席树模板题。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 4e5 + 5;

int read(){
    int s = 0,ne = 1; char c = getchar();
    while(c < '0' || c > '9') ne = c == '-' ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
    return s * ne;
}

class SGT {
  public: int d[CN * 50], rt[CN], ch[CN * 50][2], idx;
    SGT() {idx = 0;}
    #define lc ch[u][0]
    #define rc ch[u][1]
    int make() {return ++idx;}
    void ins(int &u, int v, int l, int r, int p){
        if(!u) u = make(); if(l == r) return (void)(d[u] = d[v] + 1);
        int m = (l + r) >> 1;
        if(p <= m) rc = ch[v][1], ins(lc, ch[v][0], l, m, p);
        else lc = ch[v][0], ins(rc, ch[v][1], m + 1, r, p);
        d[u] = d[lc] + d[rc];
    }
    int qu(int u, int v, int l, int r){
        if(l == r) return l;
        int m = (l + r) >> 1, s = d[lc] - d[ ch[v][0] ];
        if(s < m - l + 1) return qu(lc, ch[v][0], l, m);
        else return qu(rc, ch[v][1], m + 1, r);
    }
} D;

int n, q, ai;

int main()
{
    freopen("_in.in", "r", stdin);

    n = read(), q = read();
    for(int i = 1; i <= n; i++) ai = read(), D.ins(D.rt[i], D.rt[i - 1], 1, n, ai + 1);
    int x, y;
    while(q--) x = read(), y = read(), printf("%d", y - x + 1 < n ? D.qu(D.rt[y], D.rt[x - 1], 1, n) - 1 : n), puts("");
}

B 牛牛的算术

傻题，随便推一推柿子，特判下就好了。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 5e5 + 5;
const int P = 199999;

int qp(int a,int b) {int r = 1; while(b) {if(b & 1) r = 1ll * r * a % P; a = 1ll * a * a % P; b >>= 1;} return r;}

#define i2 qp(2, P - 2)

int t, f[CN], p[CN];

char ch[CN];

int cal(int x) {
    int squ = 1ll * x * x % P; squ = 1ll * squ * (x + 1) % P;
    return squ;
}

int main()
{
    freopen("_in.in", "r", stdin); std::ios::sync_with_stdio(false);

    for(int i = 1; i < P; i++) f[i] = (f[i - 1] + cal(i)) % P;
    p[0] = 1;
    for(int i = 1; i < P; i++) p[i] = 1ll * p[i - 1] * i % P, p[i] = 1ll * p[i] * f[i] % P, p[i] = 1ll * p[i] * i2 % P;

    cin >> t;
    while(t--){
        cin >> ch; int l = strlen(ch); if(l >= 6) {puts("0"); continue;}
        int n = 0;
        for(int i = 0; i < l; i++) n = n * 10 + (ch[i] - '0');
        if(n >= P) puts("0");
        else printf("%d", p[n]), puts("");
    }
}

C 牛牛的无向图

容易想到把边和询问都按权值排序，然后依次加边，能加就加，然后对于每个连通块就可以 $O(1)$ 算答案了。维护一个并查集就解决了，时间复杂度 $O(m\log m + (m + q)\alpha(n))$。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define LL long long

const int CN = 5e5 + 5;

class DSU {
  public: int fa[CN];
    DSU() {for(int i = 1; i <= 100000; i++) fa[i] = i;}
    int fd(int x) {return fa[x] ^ x ? fa[x] = fd(fa[x]) : x;}
} C;

int n, m, q, LIM, X[CN], Y[CN], W[CN], id[CN], pos = 1, L[CN], sz[CN]; 
LL ans[CN];
bool cmp(int i, int j) {return W[i] < W[j];}
LL cal(int x) {return 1ll * x * (x - 1) / 2ll;}

unsigned int SA, SB, SC; 
unsigned int rng61(){
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}
void gen(){
    scanf("%d%d%d%u%u%u%d", &n, &m, &q, &SA, &SB, &SC, &LIM);
    for(int i = 1; i <= m; i++){
        X[i] = rng61() % n + 1;
        Y[i] = rng61() % n + 1;
        W[i] = rng61() % LIM; id[i] = i;
    }
    for(int i = 1; i <= q; i++){
        L[i] = rng61() % LIM;
    }
}

int main()
{
    freopen("_in.in", "r", stdin);

    gen();

    sort(L + 1, L + q + 1), sort(id + 1, id + m + 1, cmp);
    for(int i = 1; i <= n; i++) sz[i] = 1;
    for(int i = 1; i <= q; i++){
        LL cur = ans[i - 1];
        while(W[ id[pos] ] <= L[i] && pos <= m){
            int u = X[ id[pos] ], v = Y[ id[pos] ], fu = C.fd(u), fv = C.fd(v);
            if(fu ^ fv) 
                cur += 1ll * sz[fu] * sz[fv], 
                C.fa[fv] = fu, sz[fu] += sz[fv];
            pos++;
        }
        ans[i] = cur;
    }

    for(int i = 1; i <= q; i++) ans[0] ^= ans[i];
    printf("%lld", ans[0]);
}

D 牛牛的粉丝

显然是个矩乘优化 DP 转移，设 $f[k,i]$ 表示 $k$ 轮后点 $i$ 的答案这样，直接做复杂度 $O(n^3\log k)$，好像不太行。
然后就没有想法了……

upd：转移矩阵是循环的啊……既然是循环的就没必要 $O(n^3)$ 算了……存下第一行来矩乘就变卷积了……于是做到 $O(n^2\log k)$……甚至还可以 $O(n\log n\log k)$ /jk……

E 牛牛的字符串

回文不会处理啊……看上去我只会 $O(n^3)$ 的辣鸡 DP，也许可以通过一些字符串算法优化到 $O(n^2)$？不可做不可做。

upd：并没有什么神仙算法……所以说还是要观察性质……