题解牛客练习赛 88

A 题

简单的贪心，不妨令 $numV$ 和 $numI$ 分别表示 V 和数量和 I 的数量。

$numV + numI \leq n$ 的时候就直接先输出所有的 V 然后再输出所有的 I 即可。
否则就尝试先用 V 填满前面的尽可能多的数字位，然后考虑将 I 先用来占没有填满的位，如果还有富余的 I 就尽量往前面的数字位 $+ 1$ 就完事了。

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0, flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}
int T;

int main() {
    T = read();
    while(T --) {
        int V = read(), I = read(), Num = read();
        if(V + I <= Num) {
            for(int i = 1 ; i <= V + I ; i ++) {
                if(i <= V) putchar('5');
                else putchar('1');
            }
        }
        else {
            int L = I - max(0, Num - V);
            for(int i = 1 ; i <= Num ; i ++) {
                if(i <= V) {
                    putchar(5 + min(L, 3) + '0');
                    L = max(L - 3, 0);
                }
                else {
                    putchar(1 + min(L, 2) + '0');
                    L = max(L - 2, 0);
                }
            }
        }
        putchar('\n');
    }
    return 0;
}

B 题

就简单的字符串 hash 就完事了。

设字符串长度是 $N$ 。

先把 C 串的末尾 $K$ 个字符去掉，然后我们枚举 M 串的位置 $P$ ，然后如果 $M[P... P + K - 1]$ 能够匹配上 C 串末尾的 $K$ 个字符就判断 $M[1...P - 1]$ 以及 $M[P + K...N]$ 能否与 C 串匹配就行了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 50;
const int Mod1 = 998244353, B1 = 31;
const int Mod2 = 1e9 + 7, B2 = 137;
int P1[MAXN], P2[MAXN];
inline int read() {
    int x = 0, flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}
int T, K;
char M[MAXN], C[MAXN], Suffix[10];
struct Hash {
    int x, y;
    bool operator == (const Hash a) const {
        return (a.x == x) & (a.y == y);
    }
} Ha[MAXN], Hb[MAXN];
void Prepare(Hash *H, char *s) {
    int len = strlen(s + 1);
    for(int i = 1 ; i <= len ; i ++) {
        H[i].x = (1ll * H[i - 1].x * B1 % Mod1 + s[i] - 'A' + 1) % Mod1;
        H[i].y = (1ll * H[i - 1].y * B2 % Mod2 + s[i] - 'A' + 1) % Mod2;
    }
    return ;
}
Hash Get(Hash *H, int l, int r) {
    Hash ans;
    ans.x = (H[r].x - (1ll * H[l - 1].x * P1[r - l + 1]) % Mod1 + Mod1) % Mod1;
    ans.y = (H[r].y - (1ll * H[l - 1].y * P2[r - l + 1]) % Mod2 + Mod2) % Mod2;
    return ans;
}

int main() {
    T = read(); P1[0] = P2[0] = 1;
    for(int i = 1 ; i <= 3e5 ; i ++) {
        P1[i] = 1ll * P1[i - 1] * B1 % Mod1;
        P2[i] = 1ll * P2[i - 1] * B2 % Mod2;
    }
    while(T --) {
        scanf("%s%s%d", M + 1, C + 1, &K);
        int lm = strlen(M + 1), lc = strlen(C + 1);
        Prepare(Ha, M), Prepare(Hb, C);
        for(int j = lc - K + 1 ; j <= lc ; j ++)
            Suffix[j - lc + K] = C[j];
        int Ans = 0;
        for(int i = 1 ; i <= lm - K + 1 ; i ++) {
            int flag = 1;
            for(int j = 0 ; j < K ; j ++)
                if(M[i + j] != Suffix[j + 1]) { flag = 0; break; }
            if(flag == 0) continue;
            if(i == lm - K + 1) {
                if(Get(Ha, 1, lm - K) == Get(Hb, 1, lm - K)) Ans = 1;
            }
            else if(i == 1) {
                if(Get(Ha, K + 1, lm) == Get(Hb, 1, lm - K)) Ans = 1;
            }
            else {
                int Len1 = i - 1;
                if(Get(Ha, 1, Len1) == Get(Hb, 1, Len1)) {
                    Hash a = Get(Ha, i + K, lm), b = Get(Hb, Len1 + 1, lm - K);
                    if(a == b) Ans = 1;
                }
            }
        }
        Ans == 0 ? printf("NO\n") : printf("YES\n");
    }
    return 0;
}

C题

可以发现我们并不关心是哪一位数字上运用了 同或 运算，而是只关心用了还是没用 同或运算。

可以发现，对于 $a$ 同或上 $b$ ，就是相当于 $a$ 异或上 $b$ 再异或上 $1 << K$ 。

于是就考虑我们能不能通过异或上 $1 << K$ 使得得到的答案变大即可。但是需要注意 $n = 1$ 的时候是不能运用同或运算的。

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int MAXN = 1e6 + 50;
inline int read() {
    int x = 0;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) ;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x;
}
int n, A[MAXN], K;
int Ans;

signed main() {
    n = read(), K = read();
    for(int i = 1 ; i <= n ; i ++) 
        A[i] = read(), Ans ^= A[i];
    int Max = 18446744073709551615ULL;
    if(n != 1) {
        if(K == 64) Ans = max(Ans, Ans ^ Max);
        else Ans = max(Ans, Ans ^ (((1ULL << K) - 1ULL)));
    }
    cout << Ans;
    return 0;
}

D题

可以发现一个很显然的性质，我们对于原图建最小生成树后，再次按照题意重建边权是没有意义的，因为得到的最小生成树还是不会变。

于是就是对于原图跑 Kruscal 最小生成树并且建一个 Kruscal 重构树，求 Kruscal 重构树上两个叶子节点的 LCA 即是询问的答案。

我们发现无聊到极致的出题人还顺手无意义地卡了 LCA 并且觉得很有意义。

采用 $O(n \log n) - O(1)$ 的 LCA 算法即可。或者是用 tarjan 算法离线后算就可以了。

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0, flag = 1;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}
typedef unsigned long long ull;
ull a1, a2;
ull myRand(ull &k1, ull &k2){
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 <<23);
    k2 = k3 ^ k4 ^ (k3 >>17) ^ (k4 >>26);
    return k2 + k4;
}
pair<int,int>myRanq(ull&k1,ull&k2,int N){
    int x=myRand(k1,k2)%N+1, y=myRand(k1,k2)%N+1;
    if(x > y)return make_pair(y,x);
    else return make_pair(x,y);
}
const int MAXN = 2e6 + 50;
int n, m, f[MAXN << 1], tot, rt, start[MAXN], q, V[MAXN << 1];
int dep[MAXN], now = 0;
int LOG[MAXN << 2], Euler[MAXN << 2], Cnt, ST[MAXN << 2][24];
int ID[MAXN << 2];
vector <int> Son[MAXN];
struct Edge {
    int from, to, w;
} e[MAXN];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
bool cmp(Edge a, Edge b) { return a.w < b.w; }
int MIN(int a, int b) { return dep[a] < dep[b] ? a : b; }

void DFS(int x, int from) {
    dep[x] = dep[from] + 1, Euler[++ Cnt] = x, ID[x] = Cnt;
    for(int i = 0 ; i < Son[x].size(); i ++) {
        int to = Son[x][i];
        DFS(to, x), Euler[++ Cnt] = x;
    }
    return ;
}
void Prepare() {
    for(int i = 2 ; i <= Cnt ; i ++) LOG[i] = LOG[i >> 1] + 1;
    for(int i = 1 ; i <= Cnt ; i ++) ST[i][0] = Euler[i];
    for(int i = 1 ; i <= LOG[Cnt] ; i ++) {
        for(int j = 1 ; j + (1 << i) - 1 <= Cnt ; j ++)
        ST[j][i] = MIN(ST[j][i - 1], ST[j + (1 << (i - 1))][i - 1]);
    }
    return ;
}
int LCA(int l, int r) {
    if(l > r) swap(l, r);
    int k = LOG[r - l + 1];
    return MIN(ST[l][k], ST[r - (1 << k) + 1][k]);
}
signed main() {
    n = read(), m = read(), rt = n;
    for(int i = 1 ; i <= m ; i ++) {
        int u = read(), v = read(), w = read();
        e[i] = (Edge) { u, v, w };
    }
    for(int i = 1 ; i <= n + m ; i ++) f[i] = i;
    sort(e + 1, e + 1 + m, cmp);
    for(int i = 1 ; i <= m ; i ++) {
        int u = find(e[i].from), v = find(e[i].to);
        if(u != v) {
            rt ++, f[u] = f[v] = f[rt] = rt;
            V[rt] = e[i].w;
            Son[rt].push_back(u), Son[rt].push_back(v);
        }
    }
    DFS(rt, 0), Prepare(), q = read(), cin >> a1 >> a2;
    int Ans = 0;
    for(int i = 1 ; i <= q ; i ++) {
        pair <int, int> ques = myRanq(a1, a2, n);
        Ans ^= V[LCA(ID[ques.first], ID[ques.second])];
    }
    cout << Ans;
    return 0;
}

E 题

强行二合一的恶心板子题，很无聊，大概就是线段树分治 + exLucas，出题人差不多得了。

考虑对于边的出现时刻进行线段树分治。可以发现一条边要是在 $t_0$ 时刻出现并且在 $t_1$ 时刻消失，那么它存在的时间区间就是 $[t_0,t_1]$ 。

将这个区间放到线段树上，最后 DFS 遍历整个线段树，这样子我们只会有 $q \log q$ 次加边操作，于是就没有删边操作了。

假设我们合并两个联通块，那么就用可撤销的并查集维护一下，同时统计 size 和权值总和即可，因为是可撤销，所以得使用按重量启发式合并的并查集。

然后算 $C(n,m)$ 就直接用 exLucas 即可，为了方便统计答案开一个 set + map 或者是 mulity set 就可以了。

~~强行考板子很有意思吗？不理解~~

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define DEF template<typename Type, typename... Types>
#define V(x) solve(Sum[x], Siz[x])
#define Rep(i,a,b) for(int i=(a);i<=(b);++i)
#define Repe(i,a,b) for(int i=(a);i>=(b);--i)
inline void read() {}
DEF inline void read(Type& x, Types&... args) {
    int flag = 1; x = 0;
    char ch = getchar();
    for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = x * 10 + ch - '0';
    x = x * flag, read(args...);
}
typedef long long LL;
const int MAXN = 2e5 + 50;
int n, m, tot, Mod, q;
int st[MAXN], w[MAXN], Ans[MAXN];
unordered_map <int, int> mp;
struct cmp {
    bool operator ()( int a, int b ) { return a > b; }
} ;
set <int, cmp> S;
vector <int> G[MAXN << 2];
struct Edge {
    int u, v;
} E[MAXN << 1];
namespace DSU {
    LL Sum[MAXN];
    int top, tack[MAXN][2], f[MAXN], Siz[MAXN];
    int find(int x) { return x == f[x] ? x : find(f[x]); }

    int P;
    int fac[3][MAXN * 20];
    int ans = -1;
    int pri[MAXN], pw[MAXN], tt;
    inline int exgcd(int a, int b, int &x, int &y){
        if(!b){
            x = 1; y = 0;
            return a;
        }
        int t = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return t;
    }
    inline int power(int u, int v, int md) {
        int sm;
        for (sm = 1; v; v >>= 1, u = (LL)u * u % md)
            if (v & 1) sm = (LL)sm * u % md;
        return sm;
    }
    inline int getfac(LL u, int p, int pw, int id) {
        if (u <= p) return fac[id][u];
        //cout <<
        //"ctr mml" << fac[id][pw] << endl;
        return (LL)fac[id][u % pw] * power(fac[id][pw], u / pw % (pw / p * (p - 1)), pw) % pw * getfac(u / p, p, pw, id) % pw;
    }

    inline int getans(LL n, LL m, int p, int pw, int id) {
        int up = getfac(n, p, pw, id), dow = (LL)getfac(m, p, pw, id) * getfac(n - m, p, pw, id) % pw;
        //cout << "\n" << n << " " << m << " ";
        //cout << up << endl;
        LL lefp = 0ll, x = n;
        while (x) lefp += x / p, x /= p;
        x = m;
        while (x) lefp -= x / p, x /= p;
        x = n - m;
        while (x) lefp -= x / p, x /= p;
        Rep(i, 1, lefp) {
            up = (LL)up * p % pw;
            if (!up) return 0;
        }
        return (LL)up * power(dow, pw / p * (p - 1) - 1, pw) % pw;
    }

    LL CRT(LL a1, LL a2, LL md1, LL md2) {
        LL M = Mod, ret = 0;
        LL x, y;
        LL tm = M / md1;
        exgcd(tm, md1, x, y);
        ret = (ret + tm * x * a1) % M;
        tm = M / md2;
        exgcd(tm, md2, x, y);
        ret = (ret + tm * x * a2) % M;
        return (ret + M) % M;
    }
    inline int solve(LL n, LL m) {
        ans = getans(n, m, pri[1], pw[1], 1);
        //cout << "f:" << n <<" " << m << " " << ans << endl;
        int ans2;
        if(Mod != 1145141) ans2 = getans(n, m, pri[2], pw[2], 2), ans = CRT(ans, ans2, pw[1], pw[2]);
        return ans;
    }

    void init() {
        P = Mod;
        int lm = sqrt(P) + 1, x = P;
        Rep(i, 2, lm)
        if (x % i == 0) {
            pri[++ tt] = i, pw[tt] = 1;
            while (x % i == 0) pw[tt] *= i, x /= i;
        }
        if (x > 1) ++ tt, pri[tt] = pw[tt] = x;
        for(int j = 1 ; j <= tt; j ++) {
            int PW = pw[j];
            fac[j][0] = 1;
            for(int i = 1 ; i <= PW ; i ++) {
                fac[j][i] = fac[j][i - 1];
                if(i % pri[j] != 0) fac[j][i] = (LL)fac[j][i] * i % PW;
            }
        }
    }

    void Del() {
        int x = tack[top][0], y = tack[top][1]; top --;
        int Y = V(y);
        if( !(-- mp[Y]) ) S.erase(Y);
        f[x] = x, Siz[y] -= Siz[x], Sum[y] -= Sum[x];
        int Vx = V(x), Vy = V(y);
        if( (++ mp[Vx]) == 1) S.insert(Vx);
        if( (++ mp[Vy]) == 1) S.insert(Vy);
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return ;
        if(Siz[x] > Siz[y]) swap(x, y);
        int Vx = V(x), Vy = V(y);
        if( (-- mp[Vx]) == 0) S.erase(Vx);
        if( (-- mp[Vy]) == 0) S.erase(Vy);
        f[x] = y, Siz[y] += Siz[x], Sum[y] += Sum[x];
        ++ top, tack[top][0] = x, tack[top][1] = y;
        int Y = V(y);
        if( (++ mp[Y]) == 1 ) S.insert(Y);
    }
    void reset() { top = 0; for(int i = 1 ; i <= n ; i ++) f[i] = i, Siz[i] = 1, Sum[i] = w[i]; }
} ;
void Clean(int x) { while(DSU::top != x) DSU::Del(); }
void puton(int x, int L, int R, int l, int r, int id) {
    if(L >= l && R <= r) { G[x].push_back(id); return ; }
    int mid = (L + R) >> 1;
    if(L == R) return ;
    if(l <= mid) puton(x << 1, L, mid, l, r, id);
    if(r  > mid) puton(x << 1 | 1, mid + 1, R, l, r, id);
    return ;
}
void DFS(int x, int L, int R) {
    int mid = (L + R) >> 1, top = DSU::top;
    for(int i = 0 ; i < G[x].size() ; i ++)
        DSU::merge(E[G[x][i]].u, E[G[x][i]].v);
    if(L == R) { Ans[L] = *S.begin(), Clean(top); return ; }
    DFS(x << 1, L, mid);
    DFS(x << 1 | 1, mid + 1, R);
    Clean(top); return ;
}

signed main() {
    int u, v, op;
    read(n, q, Mod), DSU::init();
    for(int i = 1 ; i <= n ; i ++) read(w[i]), S.insert(w[i] % Mod), mp[w[i] % Mod] ++;
    for(int i = 1 ; i <= q ; i ++) {
        read(op);
        if(op == 0) read(u, v), E[++ tot] = (Edge) { u, v }, st[tot] = i;
        else read(u), (puton(1, 1, q, st[u], i - 1, u), st[u] = 0);
    }
    for(int i = 1 ; i <= q ; i ++) if(st[i]) puton(1, 1, q, st[i], q, i);
    DSU::reset(), DFS(1, 1, q);
    for(int i = 1 ; i <= q ; i ++) printf("%d\n", Ans[i]);
    return 0;
}

F 题

写了 E 之后就呕吐去了，没有做了。

做了前 5 题的体验

给出题人的建议就是 E 题还可以多套一个线性基，就要求输出所有答案的最大异或和，这样就更加恶心了，出题人你说是不是？

或者再来套一个，让你以这个答案序列做某个 dp 什么的。(doge)