@dxbdly 2023-08-22T09:37:40.000000Z 字数 5199 阅读 172

2023.8.17 nfls集训Day10 考试总结

2023暑nfls

2023.8.17 nfls集训Day10 考试总结

前言：为什么那么多人做过最大XOR和路径

Result

F	G	H	Sum
100	100	0	200

Progress

眼镜坏了，考试时间 -1h

一回来，过 $G$ 的人比过 $F$ 多？

开题：

F：一开始以为能力值不能重复，感觉是个不好做的数数
G：啊？这不就是最大XOR和路径，也的确是线性基典题（
H：感觉很熟悉啊，又是 DS

回忆了一下 $G$ ，感觉这是个初见不是很可做的题啊（

很好写，很快过了。

看 $F$ 没什么思路，不知道啥时候，发现看错题了。

可重的话是不是随便做啊！

考虑对于一个数 $x$ ，能接在他后面的是 $[1, \lfloor \frac{n}{x}\rfloor]$

这是很明显的整除分块形式。

如果 $n$ 很小， $K$ 很大，我们可以分块建图，每个块向能到的块连边。

那么把邻接矩阵拿下来做矩阵快速幂就好了。

至于这题， $n$ 很大， $K$ 很小，就更加好做，还是按整除分块将 $n$ 变成 $O(\sqrt n)$ 级别，那就暴力 $K \sqrt n$ DP 就好了

做 $H$ 的时候没啥时间了，想了一个跟正解长得很像的东西，但是有出入。

F 能力值拟定方案

考虑暴力 $f(n, i) = Sum(n - 1, \lfloor\frac{x}{i}\rfloor)$

根据整除分块理论， $\lfloor\frac{x}{i}\rfloor$ 只有 $O(\sqrt n)$ 种取值。

也就是说我们可以将点分成 $O(\sqrt n)$ 类，将每一类当做点 DP，即可做到 $O(K\sqrt n)$

G 最大 XOR

如果不存在路径的要求，我们可以用线性基取出 XOR 的最大值。

也就是说我们需要想办法描述一条路径。

首先我们考虑如何描述路径可重，会发现，最终异或的东西，是一条 $1$ 到 $n$ 的不可重路径加上一堆环。

我们先不考虑环，考虑怎么描述一条不可重路径。

这里有个很厉害的东西，针对异或的特性，我们其实有：

每条不可重路径都可以写成任意一条不可重路径加上一堆环。

换句话说，我们可以通过加环，将所有不同的不可重路径规约到任意一条不可重路径上。

那我们就只需要处理环。

一个很明显的思路，我们只需要将所有环加到线性基里，就相当于完成了环的贡献。

但是所有环的数量显然太多。

这里是第二个很厉害的东西，考虑一个复杂的大环可以拆成很多个小环，我们只需要将这些基本环加进去就好了。

那么怎么找出基本环呢。

我们取一颗 dfs 生成树，将边区分为树边和非树边，那么每条非树边会和树边形成一个环，我们可以证明，每一条非树边与每一个单位环一一对应。

那我们只要建出一颗dfs，每次遇到非树边就将环加入线性基，最后随意取出一条 $1$ 到 $n$ 的路径放到线性基里求最大值就好了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;  
}
const int maxn = 1e5 + 5;
int n, m;
struct Xor_Base {
    int A[65];
    inline void Init() { memset(A, 0, sizeof(A)); }
    inline void Insert(int x) {
        for(register int i = 62; i >= 0; --i)
            if(x >> i & 1) {
                if(!A[i]) { A[i] = x; return ; } 
                x ^= A[i];
            }
    }
    inline int Query(int x) {
        int Answer = x;
        for(register int i = 62; i >= 0; --i) Answer = max(Answer, Answer ^ A[i]);
        return Answer;
    }
}Base;
struct node {
    int v, nex;
    int w;
}edge[maxn << 1];
int head[maxn], len, Vst[maxn], Val, Dis[maxn];
inline void make_map(int u, int v, int w) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    edge[len].w = w;
    head[u] = len;
}
inline void Search(int x, int fa) {
    Vst[x] = 1, Dis[x] = Val;
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v, z = edge[i].w;
        if(Vst[y]) Base.Insert(Val ^ Dis[y] ^ z);
        else Val ^= z, Search(y, x), Val ^= z;
    }
}
signed main() {
//    freopen("G.in", "r", stdin);
//    freopen("G.out", "w", stdout);
    n = read(), m = read(); Base.Init();
    for(register int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        make_map(u, v, w), make_map(v, u, w);
    }
    Search(1, 0);
    printf("%lld\n", Base.Query(Dis[n]));
    return 0;
}

H 大鱼吃小鱼

我们考虑一个暴力。

把所有鱼丢到权值线段树上，每次查询，我们线段树上二分出一个能吃的最大的东西，然后吃掉。

重复这个过程即可。

我们考察一下这个过程，考虑这个最大值的选取，我们假设第一次选到了第 $x$ 大的鱼，那么如果吃下 $x$ 后，能够吃下 $x + 1$ ，则 $x$ 会往后移，否则会一直往左移，知道能吃下 $x + 1$

显然会一直重复这个过程。

也就是说我们可以压缩这个选取的过程，每次找到第一个比他大的，再找到一段最短的后缀，使其能够吃下它。

而由于每轮能吃掉一个比它大的，那么每次重量至少会变大一倍。

所以复杂度会达到 $O(\log w)$

启示：

做这种合并的东西，可以考虑保证让它每次都变大一倍，就可以保证复杂度。

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e6 + 5, INF = 1e18;
int n, Q, len;
int Val[maxn], ls[maxn << 1];
struct Quer {
    int op, x, y;
}Que[maxn];
struct node {
    int l, r;
    int num, Sum;
}Tree[maxn << 3], Cnt[maxn << 3];
int St[maxn << 3], Vst[maxn << 3], top; 
#define lc(i) i << 1
#define rc(i) i << 1 | 1
inline void Push_Up(int i) { 
    Tree[i].num = (Tree[lc(i)].num + Tree[rc(i)].num);
    Tree[i].Sum = (Tree[lc(i)].Sum + Tree[rc(i)].Sum);
}
inline void Build(int i, int l, int r) {
    Tree[i].l = l, Tree[i].r = r, Tree[i].num = Tree[i].Sum = 0;
    if(l == r) { return ; }
    int mid = (l + r) >> 1;
    Build(lc(i), l, mid), Build(rc(i), mid + 1, r);
}
inline void Update(int i, int l, int r, int x, int num) {
    if(l == r) {
        Tree[i].num += num, Tree[i].Sum += ls[l] * num;
        return ;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) Update(lc(i), l, mid, x, num);
    else Update(rc(i), mid + 1, r, x, num);
    Push_Up(i);
}
inline int Find(int i, int l, int r, int x) {
    if(l == r) return Tree[i].num > 0 ? l : 0;
    int mid = (l + r) >> 1, pos = 0;
    if(x <= mid && Tree[lc(i)].num) pos = Find(lc(i), l, mid, x);
    if(pos) return pos;
    if(Tree[rc(i)].num) pos = Find(rc(i), mid + 1, r, x);
    return pos;
}
inline void Delte(int i) { St[++top] = i, Cnt[top] = Tree[i], Vst[i] = 1; }
inline void ReBuild() { while(top) Tree[St[top]] = Cnt[top], Vst[St[top--]] = 0; }
inline int Eat(int i, int l, int r, int x, int &num) {
    if(!Vst[i]) Delte(i);
    if(r <= x && Tree[i].Sum <= num) {
        num -= Tree[i].Sum; int Answer = Tree[i].num;
        Tree[i].Sum = Tree[i].num = 0;
        return Answer;
    }
    if(l == r) {
        int tot = (num % ls[l] ? num / ls[l] + 1 : num / ls[l]);
        num -= tot * ls[l], Tree[i].num -= tot, Tree[i].Sum -= ls[l] * tot;
        return tot;
    }
    int mid = (l + r) >> 1, tot = 0;
    if(x > mid) tot += Eat(rc(i), mid + 1, r, x, num);
    if(num > 0) tot += Eat(lc(i), l, mid, x, num);
    Push_Up(i);
    return tot;
}
inline int Solve(int now, int Limit) {
    if(now >= Limit) return 0;
    if(now <= ls[1]) return -1;
    int flag = 1, Nex, tot, Delta, Answer = 0;
    while(now < Limit) {
        Nex = Find(1, 1, len, lower_bound(ls + 1, ls + len + 1, now) - ls);
        if(!Nex) Nex = len + 1, tot = Limit;
        else tot = min(ls[Nex] + 1, Limit);
        Delta = tot - now;
        Answer += Eat(1, 1, len, Nex - 1, Delta);
        if(Delta > 0) { flag = 0; break; }
        now = tot - Delta;
    }
    ReBuild();
    return flag ? Answer : -1;
}
signed main() {
//    freopen("H.in", "r", stdin);
//    freopen("H.out", "w", stdout);
    n = read(), len = n;
    for(register int i = 1; i <= n; ++i) ls[i] = Val[i] = read();
    Q = read();
    for(register int i = 1; i <= Q; ++i) {
        int op = read(), x = read(), y;
        Que[i].op = op, Que[i].x = x;
        if(op == 1) y = read(), Que[i].y = y;
        else ls[++len] = x;
    }
    sort(ls + 1, ls + len + 1), len = unique(ls + 1, ls + len + 1) - ls - 1; ls[++len] = INF;
    Build(1, 1, len);
    for(register int i = 1; i <= n; ++i) Update(1, 1, len, lower_bound(ls + 1, ls + len + 1, Val[i]) - ls, 1);
    for(register int i = 1; i <= Q; ++i) {
        int op = Que[i].op, x = Que[i].x, y;
        if(op == 1) {
            y = Que[i].y;
            printf("%lld\n", Solve(x, y));
        }
        else if(op == 2) Update(1, 1, len, lower_bound(ls + 1, ls + len + 1, x) - ls, 1);
        else if(op == 3) Update(1, 1, len, lower_bound(ls + 1, ls + len + 1, x) - ls, -1);
    }
    return 0;
}