31. bzoj4197

题解
一个小技巧:~x等价于x>=0

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define S 260
using namespace std;
int n, mod, ans=0;
int prime[10] = {2, 3, 5, 7, 11, 13, 17, 19};
pair<int,int> s[505];
int f[S][S], g[2][S][S];

void initlaize() {
    scanf("%d%d", &n, &mod);
    for(int i=1; i<=n; i++) {
        int x = i;
        for(int j=0; j<8; j++)
            if(x % prime[j] == 0) {
                s[i].second |= (1 << j);
                while(x % prime[j] == 0) x /= prime[j];
            }
        s[i].first = x;
    }
    sort(s+1, s+n+1);
}

void solve() {
    f[0][0] = 1;
    for(int i=2; i<=n; i++) {
        if(i==2 || s[i].first==1 || s[i].first!=s[i-1].first) {
            memcpy(g[0], f, sizeof(f));
            memcpy(g[1], f, sizeof(f));
        }
        for(int j=255; ~j; j--)
            if((s[i].second & j) == 0)
                for(int k=255; ~k; k--)
                    (g[1][j][k|s[i].second]+=g[1][j][k]) %= mod;
        for(int k=255; ~k; k--)
            if((s[i].second & k) == 0)
                for(int j=255; ~j; j--)
                    (g[0][j|s[i].second][k]+=g[0][j][k]) %= mod;
        
        
        if(i==n || s[i].first==1 || s[i].first!=s[i+1].first)
            for(int j=255; ~j; j--) for(int k=255; ~k; k--) {
                f[j][k] = (g[0][j][k] + g[1][j][k] - f[j][k]) % mod;
                if(f[j][k] < 0) f[j][k] += mod;
            }
    }
    for(int j=255; ~j; j--) for(int k=255; ~k; k--)
        if((j & k) == 0) ans = (ans + f[j][k]) % mod;
    printf("%d", ans);
}

int main() {
    initlaize();
    solve();
    return 0;
}

32. bzoj4195

这么水的题也是noi?没有调试+1A。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <algorithm>
#define N 200005
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int T, n, m, bin[N], s[N*2], tot;
pair<int,int> a[2][N]; int len[2];
map<int,int> hashit;

int find(int x) {
    if(bin[x] != x) bin[x] = find(bin[x]);
    return bin[x];
}

void initlaize() {
    m = read(); tot=0;
    len[0] = len[1] = 0;
    for(int i=1; i<=m; i++) {
        int u=read(), v=read(), e=read();
        a[e][++len[e]] = make_pair(u,v);
        s[++tot] = u; s[++tot] = v;
    }
    sort(s+1, s+tot+1);
    n = 0;
    for(int i=1; i<=tot; i++)
        if(s[i] != s[i-1]) hashit[s[i]] = ++n;
    for(int e=0; e<=1; e++)
        for(int i=1; i<=len[e]; i++) {
            a[e][i].first = hashit[a[e][i].first];
            a[e][i].second = hashit[a[e][i].second];
        }
}

bool solve() {
    for(int i=1; i<=n; i++) bin[i] = i;
    for(int i=1; i<=len[1]; i++)
        bin[find(a[1][i].first)] = find(a[1][i].second);
    for(int i=1; i<=len[0]; i++)
        if(find(a[0][i].first) == find(a[0][i].second))
            return false;
    return true;
}

int main() {
    T = read();
    while(T--) {
        initlaize();
        puts(solve() ? "YES" : "NO");
    }
    return 0;
}

33. bzoj4196

一直忽略了树剖的一个性质就是求top值时也是在dfs,所以构建出的线段树也满足dfs序的性质,于是这道题就是大水题了。然而我太久没写lazy标记,这道题一开始写错了。lazy如果没有修改应设成-1,然而我已开始只有两个值一个0,一个1,还好有大样例。
P.S. 因为算法比较裸就偷懒没有封装了,操作名小写的是线段树的操作,大写的是树链剖分的操作。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 100005
#define L(a) ((a)<<1)
#define R(a) ((a)<<1|1)
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, m, fa[N];
int dep[N], siz[N], _pos[N], top[N];
int dfn1[N], dfn2[N], Index;
char opt[20];
vector<int> son[N];
struct Node { int sum, lazy; } s[N*8];

void build(int p, int l, int r) {
    s[p].sum = 0; s[p].lazy = -1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(L(p), l, mid); build(R(p), mid+1, r);
}

void pushdown(int p, int l, int r) {
    if(l == r || s[p].lazy < 0) return;
    int mid = (l + r) >> 1;
    s[L(p)].lazy = s[R(p)].lazy = s[p].lazy;
    s[L(p)].sum = (mid - l + 1) * s[p].lazy;
    s[R(p)].sum = (r - (mid+1) + 1) * s[p].lazy;
    s[p].lazy = -1;
}

int query(int p, int Le, int Re, int l, int r) {
    pushdown(p, Le, Re);
    if(Le==l && Re==r) return s[p].sum;
    int mid = (Le + Re) >> 1;
    if(r <= mid) return query(L(p), Le, mid, l, r);
    else if(l > mid) return query(R(p), mid+1, Re, l, r);
    else return query(L(p),Le,mid,l,mid) + query(R(p),mid+1,Re,mid+1,r);
}

void modify(int p, int Le, int Re, int l, int r, int k) {
    pushdown(p, Le, Re);
    if(Le==l && Re==r) {
        s[p].sum = k * (Re - Le + 1);
        s[p].lazy = k; return;
    }
    int mid = (Le + Re) >> 1;
    if(r <= mid) modify(L(p), Le, mid, l, r, k);
    else if(l > mid) modify(R(p), mid+1, Re, l, r, k);
    else {
        modify(L(p), Le, mid, l, mid, k);
        modify(R(p), mid+1, Re, mid+1, r, k);
    }
    s[p].sum = s[L(p)].sum + s[R(p)].sum;
}

void dfs1(int p) {
    siz[p] = 1; int sz = son[p].size();
    for(int i=0; i<sz; i++) {
        dep[son[p][i]] = dep[p]+1;
        dfs1(son[p][i]);
        siz[p] += siz[son[p][i]];
    }
}

void dfs2(int p, int tp) {
    dfn1[p] = ++Index; _pos[Index] = p;
    top[p] = tp; int sz = son[p].size();
    int zson = 0;
    for(int i=0; i<sz; i++) if(siz[son[p][i]]>siz[zson]) zson = son[p][i];
    if(zson) dfs2(zson, tp);
    for(int i=0; i<sz; i++)
        if(son[p][i] != zson)
            dfs2(son[p][i], son[p][i]);
    dfn2[p] = Index;
}

void initlaize() {
    n = read();
    for(int i=2; i<=n; i++) {
        fa[i] = read(); fa[i]++;
        son[fa[i]].push_back(i);
    }
    dep[1] = 1; Index = 0;
    dfs1(1), dfs2(1, 1);
    build(1, 1, n);
}

int SUM(int x, int y) {
    int res = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        res += query(1, 1, n, dfn1[top[x]], dfn1[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    res += query(1, 1, n, dfn1[x], dfn1[y]);
    return res;
}

void MODIFY(int x, int y, int k) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        modify(1, 1, n, dfn1[top[x]], dfn1[x], k);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    modify(1, 1, n, dfn1[x], dfn1[y], k);
}

void solve() {
    m = read();
    while(m--) {
        scanf("%s", opt); int x = read()+1;
        if(opt[0] == 'i') {
            if(query(1, 1, n, dfn1[x], dfn1[x]) == 1) puts("0");
            else {
                printf("%d\n", dep[x]-SUM(1, x));
                MODIFY(1, x, 1);
            }
        }
        else {
            if(query(1, 1, n, dfn1[x], dfn1[x]) == 0) puts("0");
            else {
                printf("%d\n", query(1, 1, n, dfn1[x], dfn2[x]));
                modify(1, 1, n, dfn1[x], dfn2[x], 0);
            }
        }
    }
}

int main() {
    initlaize();
    solve();
    return 0;
}

34. bzoj2326

这道题好像是比较裸的矩阵乘法优化递推,递推式子比较好推。
一开始我WA了一次,因为我把mat.a[0][0]=ten[i] % m;写成了mat.a[0][0]=ten[i];,导致运算过程中爆了long long。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, m, ans=0;
int tot;
ll ten[20];

struct Matrix {
    ll a[3][3];
    
    Matrix operator * (const Matrix & b) const{
        Matrix c;
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++) {
                c.a[i][j] = 0;
                for(int k=0; k<3; k++) 
                    c.a[i][j] = (c.a[i][j] + (a[i][k]*b.a[k][j]) % m) % m;
            }
        return c;
    }
} base, mat;

void get_tot(ll x) { for(tot=0; x; x/=10) tot++; }

Matrix Qpow(Matrix &a, ll p) {
    if(p == 1) return a;
    Matrix cc = Qpow(a, p>>1); cc = cc * cc;
    if(p & 1) return cc * a;
    else return cc;
}

int main() {
    ten[0] = 1;
    for(int i=1; i<=18; i++) ten[i] = ten[i-1] * 10;

    scanf("%lld%lld", &n, &m);
    get_tot(n);
    
    base.a[0][0]=0; base.a[0][1]=1; base.a[0][2]=1;
    base.a[1][0]=0; base.a[1][1]=0; base.a[1][2]=0;
    base.a[2][0]=0; base.a[2][1]=0; base.a[2][2]=0;
    for(int i=1; i<tot; i++) {
        mat.a[0][0]=ten[i] % m; mat.a[0][1]=0; mat.a[0][2]=0;
        mat.a[1][0]=1;          mat.a[1][1]=1; mat.a[1][2]=0;
        mat.a[2][0]=0;          mat.a[2][1]=1; mat.a[2][2]=1;
        mat = Qpow(mat, ten[i]-ten[i-1]);
        base = base * mat;
    }
    
    mat.a[0][0]=ten[tot] % m; mat.a[0][1]=0; mat.a[0][2]=0;
    mat.a[1][0]=1;            mat.a[1][1]=1; mat.a[1][2]=0;
    mat.a[2][0]=0;            mat.a[2][1]=1; mat.a[2][2]=1;
    
    mat = Qpow(mat, n-ten[tot-1]+1);
    base = base * mat;
    printf("%lld\n", base.a[0][0]);
    return 0;
}

35. bzoj2329

这题卡了两天,我太久没有写过标记下推了。
在此总结一下标记下推的几个要点:①对子树影响较大的标记应该先下推,再下推次要的;比如说有加和乘两个标记,我们再打上乘的标记时要把加的标记也乘上这个数,下推时先推乘再推加。②应该对于节点写一个当标记打在它身上时会发生什么的函数,比如那些只要变之类的。这样标记下推时就好写一些。
这里我由于写错了一个变量名调了好久2333,以后不能用长得很像的变量名了,特别是SAM里我老喜欢用p,q,太容易写错了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, m, numl, numr;
char s[N], opt[10];
int st[N*2], top=0;
 
struct Splay_Tree {
    int fa[N], ch[N][2], siz[N], sum[N], key[N];
    int xl[N], yl[N], xr[N], yr[N]; //最大前缀和,最小前缀和,最大后缀和,最小后缀和 
    int re[N], sw[N], in[N];
    int root, Index;
     
    void replace(int p, int x) {
        key[p] = x; sum[p] = siz[p] * x;
        if(x == 1) xl[p]=xr[p]=sum[p], yl[p]=yr[p]=0;
        if(x ==-1) yl[p]=yr[p]=sum[p], xl[p]=xr[p]=0;
        re[p] = x; sw[p] = in[p] = 0;
    }
     
    void invert(int p) {
        xl[p]*=-1; yl[p]*=-1; xr[p]*=-1; yr[p]*=-1;
        swap(xl[p], yl[p]); swap(xr[p], yr[p]);
        key[p]*=-1; sum[p]*=-1;
        if(re[p]!=0) re[p]*=-1; else in[p]^=1;
    }
     
    void reverse(int p) {
        swap(xl[p], xr[p]); swap(yl[p], yr[p]);
        swap(ch[p][0], ch[p][1]);
        sw[p] ^= 1;
    }
     
    void update(int p) {
        int l = ch[p][0], r = ch[p][1];
        sum[p] = sum[l] + sum[r] + key[p];
        siz[p] = siz[l] + siz[r] + 1;
        xl[p] = max(xl[l], sum[l]+key[p]+xl[r]);
        yl[p] = min(yl[l], sum[l]+key[p]+yl[r]);
        xr[p] = max(xr[r], sum[r]+key[p]+xr[l]);
        yr[p] = min(yr[r], sum[r]+key[p]+yr[l]);
    }
     
    void pushdown(int p) {
        if(re[p]) {
            if(ch[p][0]) replace(ch[p][0], re[p]);
            if(ch[p][1]) replace(ch[p][1], re[p]);
            re[p] = 0;
        }
        if(in[p]) {
            if(ch[p][0]) invert(ch[p][0]);
            if(ch[p][1]) invert(ch[p][1]);
            in[p] = 0;
        }
        if(sw[p]) {
            if(ch[p][0]) reverse(ch[p][0]);
            if(ch[p][1]) reverse(ch[p][1]);
            sw[p] = 0;
        }
    }
     
    void Newnode(int p, int f, int x) {
        fa[p] = f; sum[p] = key[p] = x;
        siz[p] = 1;
        update(p);
    }
     
    void Init() {
        root = Index = 1;
        Newnode(1, 0, 0);
    }
     
    void rotate(int x) {
        int y=fa[x], z=fa[y], l, r;
        l = (ch[y][1]==x); r = l^1;
        if(y!=root) ch[z][ch[z][1]==y]=x;
        else root = x;
        fa[x]=z; fa[y]=x; fa[ch[x][r]]=y;
        ch[y][l]=ch[x][r]; ch[x][r]=y;
        update(y); update(x);
    }
     
    void Splay(int x, int des_fa) {
        st[++top]=x; for(int i=x; fa[i]!=0; i=fa[i]) st[++top]=fa[i];
        while(top) pushdown(st[top--]);
        while(fa[x] != des_fa) {
            int y=fa[x], z=fa[y];
            if(fa[y] != des_fa) {
                if((x==ch[y][0])^(y==ch[z][0])) rotate(x);
                else rotate(y);
            }
            rotate(x);
        }
    }
     
    void Insert(int x) {
        int p = root, f;
        while(p) { f=p; p=ch[p][1]; }
        ch[f][1] = ++Index; Newnode(ch[f][1], f, x);
        p=ch[f][1]; while(fa[p]) { p=fa[p]; update(p); }
        Splay(ch[f][1], 0);
    }
     
    int query_rank(int rank) {
        int p = root;
        while(1) {
            pushdown(p);
            int rk = siz[ch[p][0]] + 1;
            if(rk == rank) return p;
            if(rank < rk) p = ch[p][0];
            else { rank-=rk; p = ch[p][1]; }
        }
    }
     
    void Replace(int l, int r, int x) {
        int pl = query_rank(l), pr = query_rank(r+2);
        Splay(pl, 0); Splay(pr, pl);
        replace(ch[pr][0], x);
        update(pr); update(pl);
    }
     
    void Reverse(int l, int r) {
        int pl = query_rank(l), pr = query_rank(r+2);
        Splay(pl, 0); Splay(pr, pl);
        reverse(ch[pr][0]);
        update(pr); update(pl);
    }
     
    void Invert(int l, int r) {
        int pl = query_rank(l), pr = query_rank(r+2);
        Splay(pl, 0); Splay(pr, pl);
        invert(ch[pr][0]);
        update(pr); update(pl);
    }
     
    int  Query(int l, int r) {
        int pl = query_rank(l), pr = query_rank(r+2);
        Splay(pl, 0); Splay(pr, pl);
        int p = ch[pr][0]; pushdown(p);
        int a = -yl[p], b = xr[p];
        return ((a+1)/2 + (b+1)/2);
    }
 
} T;
 
int main() {
    n=read(); m=read();
    T.Init();
 
    scanf("%s", s+1);
    for(int i=1; i<=n; i++)
        T.Insert(s[i]=='(' ? 1 : -1);
    T.Insert(0);
     
    while(m--) {
        scanf("%s", opt); int l=read(), r=read();
        if(opt[0] == 'R') {
            scanf("%s", opt);
            T.Replace(l, r, opt[0]=='(' ? 1 : -1);
        }
        if(opt[0] == 'S') T.Reverse(l, r);
        if(opt[0] == 'I') T.Invert(l, r);
        if(opt[0] == 'Q') printf("%d\n", T.Query(l,r));
    }
    return 0;
}

36. bzoj2337

这是概率期望的dp题,涉及到两个套路:
①有位运算时我们要按位来统计对答案的贡献,因为位运算中每一位的贡献是可以拆开的;
②如果图是拓扑图我们就可以dp,如果不是我们就可以列出方程并消元得到dp值。
这里的dp值是指从第i个点到n的最终期望值,等同于最终是1的概率是多少(我们是按位考虑的),则每一位对答案的贡献就为dp[1]*(1<<i)

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 105
#define M 20005
using namespace std;
struct Edge { int nex, to, w; } e[M];
static int head[N], cnt;
static int n, m, deg[N];
static double a[N][N], ans;
static double dp[N];

void Link(int x, int y, int z) {
    e[++cnt].nex = head[x]; head[x] = cnt;
    e[cnt].to = y; e[cnt].w = z;
    deg[y]++;
}

void Guass() {
    for(int i=1; i<n; i++) {
        int id = 0;
        for(int j=i; j<n; j++) if(fabs(a[j][i]) > fabs(a[id][i])) id = j;
        for(int j=i; j<=n+1; j++) swap(a[id][j], a[i][j]);
        for(int j=i+1; j<n; j++) {
            double t = -a[j][i] / a[i][i];
            for(int k=i; k<=n+1; k++)
                a[j][k] += a[i][k] * t;
        }
    }
    for(int i=n-1; i; i--) {
        for(int j=i+1; j<=n; j++)
            a[i][n+1] -= a[i][j] * dp[j];
        dp[i] = a[i][n+1]/a[i][i];
    }
}

void initlaize() {
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++) {
        int x,y,w; scanf("%d%d%d", &x, &y, &w);
        Link(x,y,w); if(x != y) Link(y,x,w);
    }
}

void solve(int i) {
    memset(a, 0, sizeof(a));
    for(int x=1; x<n; x++) {
        a[x][x] = deg[x];
        for(int j=head[x]; j; j=e[j].nex) {
            int y=e[j].to, w=e[j].w;
            if(w & i) a[x][y] += 1.0, a[x][n+1] += 1.0;
            else a[x][y] -= 1.0;
        }
    }
    a[n][n] = a[n][n+1] = 1.0;
    Guass();
}

int main() {
    initlaize();
    for(int i=0; i<30; i++) {
        solve(1<<i);
        ans += dp[1] * (1<<i);
    }
    printf("%.3lf", ans);
    return 0;
}

37. bzoj2338

这道题用了个暴力,比较难卡的暴力,因为勾股点十分有限。
矩形是对角线相等且互相平分的图形,我们把n^2条对角线都提出来,然后把相同的长度且中点相同的归到一组,每一组暴力就好了。因为勾股点十分有限,所以每一组不会很大,然后就这样过了。。。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <algorithm>
using namespace std;
const double eps = 1e-10;
typedef long long ll;
typedef long double ld;
int n, m; ld ans;
struct Node {
    int x, y;
    bool operator < (const Node & rhs) const {
        if(x != rhs.x) return x < rhs.x;
        else return y < rhs.y;
    }
} s[2005];
set<Node> ex;
struct Line {
    int l, r;
    ll len2;
    double x, y;
    
    bool operator == (const Line &rhs) const {
        if(len2 != rhs.len2) return false;
        if(x!=rhs.x || y!=rhs.y) return false;
        return true;
    }
    
} l[4000005];

bool cmp(const Line &a, const Line &b) {
    if(a.len2 != b.len2) return a.len2 < b.len2;
    if(a.x != b.x) return a.x < b.x;
    else return a.y < b.y;
}

void initlaize() {
    scanf("%d", &n); n = m = 0;
    while(scanf("%d%d", &s[0].x, &s[0].y) != EOF) {
        if(ex.find(s[0]) != ex.end()) continue;
        else s[++n] = s[0];
    }
    
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++) {
            l[++m].l = i; l[m].r = j;
            l[m].len2 = (ll)(s[i].x-s[j].x)*(s[i].x-s[j].x) + (ll)(s[i].y-s[j].y)*(s[i].y-s[j].y);
            l[m].x = (double)(s[i].x+s[j].x) / 2; l[m].y = (double)(s[i].y+s[j].y) / 2;
        }
    sort(l+1, l+m+1, cmp);
}

ld calc(int x, int y, int z) {
    ld xz = sqrt((ld)(s[x].x-s[z].x)*(s[x].x-s[z].x) + (ld)(s[x].y-s[z].y)*(s[x].y-s[z].y));
    ld yz = sqrt((ld)(s[y].x-s[z].x)*(s[y].x-s[z].x) + (ld)(s[y].y-s[z].y)*(s[y].y-s[z].y));
    return xz * yz;
}

void solve() {
    ans = 0.0;
    int L, R;
    for(int i=1; i<=m; i=R+1) {
        L = i, R = i;
        while(R<m && l[R+1]==l[R]) R++;
        if(L == R) continue;
        for(int j=L; j<=R; j++)
            for(int k=j+1; k<=R; k++)
                ans = max(ans, calc(l[j].l, l[j].r, l[k].l));
    }
    printf("%.0Lf", ans);
}

int main() {
    initlaize();
    solve();
    return 0;
}

38. bzoj3218 & uoj#77

这真是一道劲题,不过好在颂魔已经给我讲过了线段树优化连边问题。
这道题非常经典(如果数据范围小的话),但是我一开始还是建图建错了,$s \rightarrow i = b_i,\ i\rightarrow t=w_i$这是显然的一个最小割模型,然后就是处理“奇怪的点”的代价,我的做法是对于每个点i新建一个点$i'$然后$s \rightarrow i' = p_i,\ i\rightarrow j=\text{INF},j为满足要求的点$,但是这样就有一个问题,即当点i是白点时我还是有可能会计算它为奇怪的点的代价,然而此时它已不可能为奇怪的点。所以我们只要把$s \rightarrow i' = p_i$这一条边改成$i \rightarrow i' = p_i$就行了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#define N 100005
#define M 5000005
#define INF 1000000000
using namespace std;
const int S = 0, T = 100000;
static int n, m, Index, Ans, X;
struct Edge { int nex, to, w; } e[M];
static int head[N], cnt, ch[N][2], dis[N];
static int root[5005], leaf[5005];
map<int,int> HASH;
struct Node {
    int a, b, w, l, r, p;
} s[5005];

void Link(int x, int y, int z) {
    e[++cnt].nex = head[x]; head[x] = cnt;
    e[cnt].to = y; e[cnt].w = z;
}
void Add(int x, int y, int z) { Link(x, y, z); Link(y, x, 0); }

void initlaize() {
    scanf("%d", &n);
    cnt = m = Ans = 0;
    for(int i=1; i<=n; i++) {
        scanf("%d%d%d", &s[i].a, &s[i].b, &s[i].w);
        scanf("%d%d%d", &s[i].l, &s[i].r, &s[i].p);
        head[++cnt] = s[i].a; head[++cnt] = s[i].l; head[++cnt] = s[i].r;
        Ans += (s[i].b + s[i].w);
    }
    sort(head+1, head+cnt+1); head[0] = -1;
    for(int i=1; i<=cnt; i++)
        if(head[i] != head[i-1]) HASH[head[i]] = ++m;
    for(int i=1; i<=n; i++) {
        s[i].a = HASH[s[i].a];
        s[i].l = HASH[s[i].l];
        s[i].r = HASH[s[i].r];
    }
}

void insert(int &p, int p1, int l, int r, int x) {
    p = ++Index; ch[p][0]=ch[p1][0]; ch[p][1]=ch[p1][1];
    if(l == r) {
        leaf[x] = p;
        if(p1) Add(p, p1, INF);
        return;
    }
    int mid = (l + r) >> 1;
    if(s[x].a <= mid) insert(ch[p][0]=0, ch[p1][0], l, mid, x);
    else insert(ch[p][1]=0, ch[p1][1], mid+1, r, x);
}

void query(int p, int Le, int Re, int l, int r) {
    if(p == 0) return;
    if(Le == l && Re == r) { Add(X, p, INF); return; }
    int mid = (Le + Re) >> 1;
    if(r <= mid) query(ch[p][0], Le, mid, l, r);
    else if(l > mid) query(ch[p][1], mid+1, Re, l, r);
    else {
        query(ch[p][0], Le, mid, l, mid);
        query(ch[p][1], mid+1, Re, mid+1, r);
    }
}

void Build_graph() {
    memset(head, 0, sizeof(head)); cnt = 1;
    memset(ch, 0, sizeof(ch));
    root[0] = Index = 1;
    for(int i=1; i<=n; i++)
        insert(root[i], root[i-1], 1, m, i);
    for(int i=1; i<=Index; i++) {
        if(ch[i][0]) Add(i, ch[i][0], INF);
        if(ch[i][1]) Add(i, ch[i][1], INF);
    }
    for(int i=1; i<=n; i++) Add(leaf[i], Index+n+i, INF);
    for(int i=1; i<=n; i++) {
        Add(S, Index+n+i, s[i].b);
        Add(Index+n+i, T, s[i].w);
    }
    for(int i=2; i<=n; i++) {
        X = i + Index;
        Add(Index+n+i, X, s[i].p);
        query(root[i-1], 1, m, s[i].l, s[i].r);
    }
}

queue<int> Q;
bool bfs() {
    while( !Q.empty()) Q.pop();
    memset(dis, -1, sizeof(dis));
    dis[S] = 0; Q.push(S);
    while( !Q.empty()) {
        int x=Q.front(); Q.pop();
        for(int j=head[x]; j; j=e[j].nex)
            if(e[j].w && dis[e[j].to] < 0) {
                dis[e[j].to] = dis[x] + 1;
                Q.push(e[j].to);
            }
    }
    return dis[T] > 0;
}

int dfs(int p, int minF) {
    if(p == T) return minF;
    int minf = minF;
    for(int j=head[p]; j; j=e[j].nex)
        if(e[j].w && dis[e[j].to]==dis[p]+1) {
            int tmp = dfs(e[j].to, min(minf, e[j].w));
            e[j].w -= tmp; e[j^1].w += tmp;
            minf -= tmp; if( !minf) break;
        }
    return minF - minf;
}

int Dinic() {
    int res = 0;
    while(bfs()) res += dfs(S,INF);
    return res;
}

int main() {
    initlaize();
    Build_graph();
    printf("%d", Ans - Dinic());
    return 0;
}

39. bzoj1064

这道题我想到一种情况就不敢写了。这道题思路还算好,就是把所有的环都找出来,那么颜色种数显然最大是这些环长度的gcd,环可能有重叠,但是dfs都能找到。然后我想得情况就是可能有很多等价的点他们可以在一张无环图上生出一个环,这里用了一个很妙的技巧,就是给边加权,建立负权的反向边,这样就可以巧妙地“抵消”掉等价点的影响了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
#define M 2000005
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
static int n, m, loop, maxl, minl, sum;
struct Edge { int nex,to,w; } e[M];
static int head[N], dis[N], vis[N], cnt;

void Link(int x, int y, int z) {
    e[++cnt].nex = head[x]; head[x] = cnt;
    e[cnt].to = y; e[cnt].w = z;
}

void initlaize() {
    n=read(); m=read();
    for(int i=1; i<=m; i++) {
        int u=read(), v=read();
        Link(u, v, 1); Link(v, u, -1);
    }
}

int gcd(int a, int b) {
    return b ? gcd(b,a%b) : a;
}

void dfs(int x) {
    for(int j=head[x]; j; j=e[j].nex) {
        int y = e[j].to, w = e[j].w;
        if(vis[y]) {
            loop = gcd(loop, dis[x]-dis[y]+w);
            continue;
        }
        vis[y] = true; dis[y] = dis[x] + w;
        maxl = max(maxl, dis[y]);
        minl = min(minl, dis[y]);
        dfs(y);
    }
}

int main() {
    initlaize();
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<=n; i++)
        if( !vis[i]) {
            dis[i] = maxl = minl = 0;
            dfs(i);
            sum += (maxl - minl + 1);
        }
    if(loop < 0) loop *= -1;
    if(loop) {
        if(loop < 3) printf("-1 -1\n");
        else {
            int bd;
            for(bd=3; (bd<loop)&&(loop%bd); bd++);
            printf("%d %d\n", loop, bd);
        }
    }
    else {
        if(sum < 3) printf("-1 -1\n");
        else printf("%d 3\n", sum);
    }
    return 0;
}

40. bzoj1009

写出暴力后就可以矩阵快速幂了。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m, K, k;
char M[25]; int next[25];

struct Matrix {
    int a[25][25];
    Matrix operator * (const Matrix b) const {
        Matrix c; memset(c.a, 0, sizeof(c.a));
        for(int i=0; i<m; i++)
            for(int j=0; j<m; j++)
                for(int k=0; k<m; k++)
                    (c.a[i][j]+=(a[i][k]*b.a[k][j]))%=K;
        return c;
    }
} base, res;

void Build_NEXT() {
    int j = 0; next[1] = 0;
    for(int i=2; i<=m; i++) {
        while(j && (M[j+1]!=M[i])) j = next[j];
        if(M[i] == M[j+1]) j++;
        next[i] = j;
    }
}

void Build_BASE() {
    memset(base.a, 0, sizeof(base.a));
    for(int j=0; j<m; j++)
        for(int i=0; i<=9; i++) {
            int k = j;
            while(k && M[k+1]!=(i+'0')) k = next[k];
            if(M[k+1] == (i+'0')) k++;
            if(k<m) base.a[k][j]++;
        }
}

Matrix Qpow(Matrix &a, int p) {
    if(p == 1) return a;
    Matrix c = Qpow(a,p>>1); c = c*c;
    if(p & 1) return a * c; else return c;
}

int main() {
    scanf("%d%d%d", &n, &m, &K);
    scanf("%s", M+1);
    Build_NEXT(); Build_BASE();
    res = Qpow(base, n);
    int ans = 0;
    for(int i=0; i<m; i++) ans += res.a[i][0];
    printf("%d\n", ans%K);
    return 0;
}

41. bzoj3110

对于每一个询问,我们可以二分一个答案,然后对于小于这个答案的插入操作区间加1,然后这个询问的区间和就是比较答案的依据,然后就可以整体二分了。我一开始线段树写错了一个地方:即查询是Query(R(p), mid+1, Re, mid+1, r)打成了Query(R(p), mid+1, r, mid+1, r),唉代码压行太紧还是不好啊。这里是查询第k大,我偷了个懒把插入的每个数乘-1然后写了查询第k小。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 200005
#define L(a) ((a)<<1)
#define R(a) ((a)<<1|1)
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
static int n, m, ans[50005];
struct OPTION {
    int l, r, k, id, type;
} q[N], q1[N], q2[N];
struct Segment_Tree {
    LL Sum[N*2], Lazy[N*2];
    
    void Init() {
        memset(Sum, 0, sizeof(Sum));
        memset(Lazy, 0, sizeof(Lazy));
    }
    
    void add(int p, int l, int r, int k) {
        Lazy[p] += k; Sum[p] += (k*(r-l+1));
    }
    
    void Pushdown(int p, int l, int r) {
        if(l == r) Lazy[p] = 0; if(Lazy[p] == 0) return;
        int mid = (l + r) >> 1;
        add(L(p), l, mid, Lazy[p]); add(R(p), mid+1, r, Lazy[p]);
        Lazy[p] = 0;
    }
    
    LL  Query(int p, int Le, int Re, int l, int r) {
        Pushdown(p, Le, Re);
        if(Le==l && Re==r) return Sum[p];
        int mid = (Le + Re) >> 1;
        if(r <= mid) return Query(L(p), Le, mid, l, r);
        else if(l > mid) return Query(R(p), mid+1, Re, l, r);
        else return Query(L(p),Le,mid,l,mid) + Query(R(p),mid+1,Re,mid+1,r);
    }
    
    void Modify(int p, int Le, int Re, int l, int r, int k) {
        Pushdown(p, Le, Re);
        if(Le == l && Re == r) { add(p,l,r,k); return; }
        int mid = (Le + Re) >> 1;
        if(r <= mid) Modify(L(p), Le, mid, l, r, k);
        else if(l > mid) Modify(R(p), mid+1, Re, l, r, k);
        else {
            Modify(L(p), Le, mid, l, mid, k);
            Modify(R(p), mid+1, Re, mid+1, r, k);
        }
        Sum[p] = Sum[L(p)] + Sum[R(p)];
    }

} T;

void initlaize() {
    n=read(), m=read();
    for(int i=1; i<=m; i++) {
        int opt = read(), a=read(), b=read(), c=read();
        if(opt == 2) q[i] = (OPTION){a, b, c, ++ans[0], opt};
        else  q[i] = (OPTION){a, b, -c, 0, opt};
    }
    T.Init();
}

void Half_Solve(int ql, int qr, int l, int r) {
    if(l == r) {
        for(int i=ql; i<=qr; i++)
            if(q[i].type==2) ans[q[i].id] = l;
        return;
    }
    int mid=(l+r)>>1; int p1=0, p2=0;
    for(int i=ql; i<=qr; i++) {
        if(q[i].type == 1) {
            if(q[i].k <= mid) {
                T.Modify(1, 1, n, q[i].l, q[i].r, 1);
                q1[p1++] = q[i];
            }
            else q2[p2++] = q[i];
        }
        else {
            LL res = T.Query(1, 1, n, q[i].l, q[i].r);
            if(res >= (LL)q[i].k) q1[p1++] = q[i];
            else { q[i].k-=res; q2[p2++] = q[i]; }
        }
    }
    for(int i=ql; i<=qr; i++)
        if(q[i].type==1 && q[i].k<=mid)
            T.Modify(1, 1, n, q[i].l, q[i].r, -1);
    for(int i=0; i<p1; i++) q[ql+i] = q1[i];
    for(int i=0; i<p2; i++) q[ql+p1+i] = q2[i];
    if(p1) Half_Solve(ql, ql+p1-1, l, mid);
    if(p2) Half_Solve(ql+p1, qr, mid+1, r);
}

int main() {
    initlaize();
    Half_Solve(1, m, -n, n);
    for(int i=1; i<=ans[0]; i++) printf("%d\n", -ans[i]);
    return 0;
}

42. bzoj2434

阿狸的打字机,靠一直以为这种问题要后缀自动机搞,没想到fail树这么神奇。一个串是另一个串的字串,可以是某个后缀的前缀,也可以是某个前缀的后缀。代码是丑一点但好在是1A嘛。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define N 100005
#define L(a) ((a)<<1)
#define R(a) ((a)<<1|1)
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
char ch[N];
int dfn1[N], dfn2[N], Index=1, n=0, tot;
struct QUERY { int x, y, ans; } q[N];
int _pos[N];
vector<int> pos[N];
struct Trie_Node {
    int ch[26], fa, fail, end;
} s[100005];
queue<int> Q;
struct Edge { int nex, to; } e[200005];
int head[N], cnt=0;
inline void Link(int x, int y) {
    e[++cnt].nex = head[x]; head[x] = cnt;
    e[cnt].to = y;
}

void Get_dfn(int p) {
    dfn1[p] = ++Index;
    for(int j=head[p]; j; j=e[j].nex)
        Get_dfn(e[j].to);
    dfn2[p] = Index;
}

void initlaize() {
    scanf("%s", ch+1); int len = strlen(ch+1);
    int p = 1;
    for(int i=1; i<=len; i++) {
        if(ch[i]>='a' && ch[i]<='z') {
            if(s[p].ch[ch[i]-'a'] == 0) {
                s[p].ch[ch[i]-'a'] = ++Index;
                s[Index].fa = p;
            }
            p = s[p].ch[ch[i]-'a'];
        }
        else if(ch[i] == 'P') {
            s[p].end = ++n;
            _pos[n] = p;
        }
        else if(ch[i] == 'B')
            p = s[p].fa;
    }
    for(int i=0; i<26; i++)
        if(s[1].ch[i]) {
            s[s[1].ch[i]].fail = 1;
            Q.push(s[1].ch[i]);
            Link(1, s[1].ch[i]);
        }
    while( !Q.empty()) {
        int x=Q.front(); Q.pop();
        for(int i=0; i<26; i++)
            if(s[x].ch[i]) {
                int p = s[x].fail;
                while(p!=1 && !s[p].ch[i]) p=s[p].fail;
                if(s[p].ch[i]) p = s[p].ch[i];
                s[s[x].ch[i]].fail = p;
                Q.push(s[x].ch[i]);
                Link(p, s[x].ch[i]);
            }
    }
    tot = Index;
    Index = 0; Get_dfn(1);
}

struct Fenwick_Tree {
    int c[N];
    
    inline int lowbit(int x) { return x&-x; }
    
    void Add(int x, int k) {
        for(int i=x; i<=tot; i+=lowbit(i))
            c[i] += k;
    }
    
    int  Sum(int x) {
        int res = 0;
        for(int i=x; i; i-=lowbit(i))
            res += c[i];
        return res;
    }
    
    int Sum(int l, int r) { return Sum(r)-Sum(l-1); }
    
} T;

void dfs(int p) {
    T.Add(dfn1[p], 1);
    if(s[p].end) {
        int y = s[p].end, sz = pos[y].size();
        for(int i=0; i<sz; i++) {
            int x = q[pos[y][i]].x;
            q[pos[y][i]].ans = T.Sum(dfn1[_pos[x]], dfn2[_pos[x]]);
        }
    }
    for(int i=0; i<26; i++)
        if(s[p].ch[i]) dfs(s[p].ch[i]);
    T.Add(dfn1[p], -1);
}

void solve() {
    int m = read();
    for(int i=1; i<=m; i++) {
        q[i].x=read(); q[i].y=read();
        pos[q[i].y].push_back(i);
    }
    
    dfs(1);
    
    for(int i=1; i<=m; i++)
        printf("%d\n", q[i].ans);
}

int main() {
    initlaize();
    solve();
    return 0;
}

43. bzoj3172

比较裸的fail树的应用,一开始开了500万数组MLE了。。。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
static int n, m, cnt[1000005], _pos[205];
char str[1000005];
vector<int> son[1000005];
struct Trie_Node {
    int ch[26], fail, end;
} s[1000005];
queue<int> Q;

void Insert(char *str, int id) {
    int p = 1, len = strlen(str+1);
    for(int i=1; i<=len; i++) {
        if( !s[p].ch[str[i]-'a'])
            s[p].ch[str[i]-'a'] = ++n;
        p = s[p].ch[str[i]-'a'];
        cnt[p]++;
        if(i == len) {
            s[p].end = id;
            _pos[id] = p;
        }
    }
}

void initlaize() {
    scanf("%d", &m); n = 1;
    for(int i=1; i<=m; i++) {
        scanf("%s", str+1);
        Insert(str, i);
    }
    
    for(int i=0; i<26; i++)
        if(s[1].ch[i]) {
            s[s[1].ch[i]].fail = 1;
            Q.push(s[1].ch[i]);
            son[1].push_back(s[1].ch[i]);
        }
        
    while( !Q.empty()) {
        int x=Q.front(); Q.pop();
        for(int i=0; i<26; i++)
            if(s[x].ch[i]) {
                int p = s[x].fail;
                while(p>1 && !s[p].ch[i]) p=s[p].fail;
                if(s[p].ch[i]) p = s[p].ch[i];
                s[s[x].ch[i]].fail = p;
                Q.push(s[x].ch[i]);
                son[p].push_back(s[x].ch[i]);
            }
    }
}

void dfs(int p) {
    for(int i=0; i<son[p].size(); i++) {
        dfs(son[p][i]);
        cnt[p] += cnt[son[p][i]];
    }
}

int main() {
    initlaize();
    dfs(1);
    for(int i=1; i<=m; i++)
        printf("%d\n", cnt[_pos[i]]);
    return 0;
}

44. bzoj4567

满足每个串插入前它的后缀串一定插入即可,这样代价是要比$n^2$小的,所以第一个条件必定不会触发。然后就是如何计算结果了,这可以在fail树上贪心,我们先dfs大小小一些的子树,因为条件中还有一个就是代价为x,即无后缀串的串,这种串的节点直接与根相连。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define N 510005
using namespace std;
int n, tot, Index, TIME;
int _pos[N/5], siz[N], time[N];
char str[N];
long long ans = 0;
struct Trie_Node {
    int ch[26], fail, end;
} s[N];
struct Edge { int nex,to; } e[N];
int head[N], cnt=1;
vector<int> son[N];
inline void Link(int x, int y) { e[++cnt].nex=head[x]; head[x]=cnt; e[cnt].to=y; }

bool cmp(const int a, const int b) { return siz[a] < siz[b]; }

queue<int> Q;

void Insert(char *str, int id) {
    int len = strlen(str+1), p=1;
    for(int i=1; i<=len; i++) {
        int x = str[i]-'a';
        if( !s[p].ch[x]) s[p].ch[x] = ++tot;
        p = s[p].ch[x];
        if(i == len) { s[p].end = id; _pos[id]=p; }
    }
}

void initlaize() {
    scanf("%d", &n); tot = 1;
    for(int i=1; i<=n; i++) {
        scanf("%s", str+1);
        Insert(str, i);
    }

    for(int i=0; i<26; i++)
        if(s[1].ch[i]) { s[s[1].ch[i]].fail=1; Q.push(s[1].ch[i]); }
    
    while( !Q.empty()) {
        int x=Q.front(); Q.pop();
        for(int i=0; i<26; i++)
            if(s[x].ch[i]) {
                int p = s[x].fail;
                while(p && !s[p].ch[i]) p=s[p].fail;
                p = p ? s[p].ch[i] : 1;
                s[s[x].ch[i]].fail = p;
                Q.push(s[x].ch[i]);
            }
    }
    for(int i=1; i<=tot; i++) Link(s[i].fail, i);
}

void Build_tree(int p, int fa) {
    if(s[p].end) { son[fa].push_back(p); fa = p; }
    for(int j=head[p]; j; j=e[j].nex) Build_tree(e[j].to, fa);
}
int  Get_siz(int p) {
    siz[p] = 1; int sz = son[p].size();
    for(int j=0; j<sz; j++) siz[p] += Get_siz(son[p][j]);
    return siz[p];
}

void DFS(int p, int pre) {
    time[p] = ++TIME;
    ans += TIME - time[pre];
    int sz = son[p].size();
    sort(son[p].begin(), son[p].end(), cmp);
    for(int j=0; j<sz; j++) DFS(son[p][j], p);
}

void solve() {
    memset(siz, 0, sizeof(siz));
    Build_tree(1, 1);
    siz[1] = Get_siz(1);
    TIME = -1; DFS(1, 0);    
    printf("%lld\n", ans);
}

int main() {
    initlaize();
    solve();
    return 0;
}

45. bzoj2115

由于异或同一个数两次等于异或0,所以一条从1到n的路径就相当于一条1到n的简单路径加上一堆环,去最大值就好。我一开始把1到n的简单路径的权值加入线性基里一起求,然后发现线性基求的值可以不选1到n的简单路径的权值,WA了一发。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define N 50005
#define M 100005
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, m;
static ll XOR[N], a[70];
bool vis[N];

struct Edge { int nex, to; ll wei; } e[M*2];
static int head[N], cnt;
inline void Link(int x, int y, ll z) {
    e[++cnt].nex=head[x]; head[x]=cnt;
    e[cnt].to=y; e[cnt].wei = z;
}

void Insert(ll x) {
    int i;
    for(i=62; ~i; i--) if(x & (1ll<<i)) x ^= a[i];
    if(x == 0) return;
    for(i=62; ~i; i--) if(x & (1ll<<i)) break;
    a[i] = x;
}

void initlaize() {
    n=read(); m=read();
    for(int i=1; i<=m; i++) {
        int u=read(), v=read(); ll w=read();
        Link(u, v, w); Link(v, u, w);
    }
}

void DFS(int p) {
    vis[p] = true;
    for(int j=head[p]; j; j=e[j].nex) {
        if( !vis[e[j].to]) {
            XOR[e[j].to] = XOR[p] ^ e[j].wei;
            DFS(e[j].to);
        }
        else Insert(XOR[p]^XOR[e[j].to]^e[j].wei);
    }
}

void solve() {
    memset(vis, false, sizeof(vis));
    DFS(1);
    for(int i=62; ~i; i--)
        for(int j=62; ~j; j--)
            if((i!=j) && (a[i]&(1ll<<j)))
                a[i] ^= a[j];
    ll ans = XOR[n];
    for(int i=0; i<=62; i++) ans = max(ans, ans^a[i]);
    printf("%lld\n", ans);
}

int main() {
    initlaize();
    solve();
    return 0;
}

46.bzoj4568

树链剖分强行$O(q\cdot log^2n\cdot log^2w)$,然后T了,为什么别人可以跑过??,其实树上倍增可以达到$O(q\cdot logn\cdot log^2w)$。riteme想出的方法和异或凑数那题一样,即维护线性基中每一位出现的最晚时间,这样一遍dfs预处理再加询问时的合并两个线性基复杂度$O(n\cdot logw + q\cdot log^2w)$,跑得很快,进了第一版。
树链剖分(TLE):

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 20005
#define L(a) ((a)<<1)
#define R(a) ((a)<<1|1)
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, m; ll a[N];
int siz[N], dep[N], fa[N], pos[N], _pos[N], top[N], Index;
struct Edge { int nex,to; } e[N*2];
static int head[N], cnt;
inline void Link(int x,int y) { e[++cnt].nex=head[x]; head[x]=cnt; e[cnt].to=y; }
 
void initlaize() {
    n=read(); m=read();
    for(int i=1; i<=n; i++) a[i]=read();
    for(int i=1; i<n; i++) {
        int u=read(), v=read();
        Link(u,v); Link(v,u);
    }
}
 
void dfs1(int p) {
    siz[p] = 1;
    for(int j=head[p]; j; j=e[j].nex) {
        if(e[j].to == fa[p]) continue;
        dep[e[j].to] = dep[p] + 1;
        fa[e[j].to] = p; dfs1(e[j].to);
        siz[p] = siz[e[j].to];
    }
}
 
void dfs2(int p, int tp) {
    top[p] = tp;
    pos[p] = ++Index; _pos[Index] = p;
    int son = 0;
    for(int j=head[p]; j; j=e[j].nex)
        if(e[j].to!=fa[p]) if(siz[e[j].to] > siz[son]) son = e[j].to;
    if(son) dfs2(son, tp);
     
    for(int j=head[p]; j; j=e[j].nex)
        if(e[j].to!=fa[p] && e[j].to!=son)
            dfs2(e[j].to, e[j].to);
}
 
struct Linear_basis {
    ll x[65];
     
    void Init() { memset(x, 0, sizeof(x)); }
     
    void Insert(ll k) {
        if(k == 0) return;
        for(int i=60; ~i; i--)
            if(k & (1ll<<i)) k ^= x[i];
        if(k == 0) return;
        for(int i=60; ~i; i--)
            if(k & (1ll<<i)) { x[i] = k; break; }
    }
     
    ll  Get_max() {
        ll res = 0;
        for(int i=60; ~i; i--) res = max(res, res^x[i]);
        return res;
    }
    
    void Merge(const Linear_basis & rhs) {
        for(int i=60; ~i; i--) Insert(rhs.x[i]);
    }
     
} res;
 
struct Segment_Tree {
    Linear_basis XOR[N*4];
     
    void Build(int p, int l, int r) {
        if(l == r) {
            XOR[p].Insert(a[_pos[l]]);
            return;
        }
        int mid = (l + r) >> 1;
        Build(L(p), l, mid); Build(R(p), mid+1, r);
        XOR[p].Merge(XOR[L(p)]); XOR[p].Merge(XOR[R(p)]);
    }
     
    void Query(int p, int Le, int Re, int l, int r) {
        if(Le==l && Re==r) { res.Merge(XOR[p]); return; }
        int mid = (Le + Re) >> 1;
        if(r <= mid) Query(L(p), Le, mid, l, r);
        else if(l > mid) Query(R(p), mid+1, Re, l, r);
        else { Query(L(p),Le,mid,l,mid); Query(R(p),mid+1,Re,mid+1,r); }
    }
     
} T;
 
ll Q(int x, int y) {
    res.Init();
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        T.Query(1, 1, n, pos[top[x]], pos[x]);
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) swap(x, y);
    T.Query(1, 1, n, pos[y], pos[x]);
    return res.Get_max();
}
 
void Build_tree() {
    dfs1(1);
    dfs2(1,1);
    T.Build(1, 1, n);
}
 
void solve() {
    while(m--) {
        int x=read(), y=read();
        printf("%lld\n", Q(x,y));
    }
}
 
int main() {
    initlaize();
    Build_tree();
    solve();
    return 0;
}

线性基合并(Tarjan求lca),这里用到了一个很强的黑科技,就是在维护前缀的线性基时我们可以保留每一位的出现的最晚时间,这样就可以再区间查询中贪心,思想就是用最新的不断替换能替换的旧的:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 20005
#define L(a) ((a)<<1)
#define R(a) ((a)<<1|1)
using namespace std;
typedef long long ll;
inline ll read() {
    ll x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, m; ll a[N];
int dep[N], fa[N];
struct Edge { int nex,to; } e[N*2+400005];
static int head[N], cnt, qhead[N];
struct QUES { int x, y, dep; } q[200005];
inline void Link(int x,int y) { e[++cnt].nex=head[x]; head[x]=cnt; e[cnt].to=y; }

struct Linear_basis {
    struct NODE { ll x; int t; } h[61];
    
    void Init() {
        for(int i=60; ~i; i--) h[i].x = 0;
    }
    
    void Insert(ll num, int id) {
        for(int i=60; ~i; i--) {
            if( !(num & (1ll<<i))) continue;
            if( !h[i].x) { h[i].x=num; h[i].t=id; break; }
            if(id>h[i].t) { swap(h[i].x,num); swap(h[i].t,id); }
            num ^= h[i].x;
        }
    }
} s[N], ANS;
 
void initlaize() {
    n=read(); m=read();
    for(int i=1; i<=n; i++) a[i]=read();
    for(int i=1; i<n; i++) {
        int u=read(), v=read();
        Link(u, v); Link(v, u);
    }
}

void dfs(int p) {
    s[p].Insert(a[p], dep[p]);
    for(int j=head[p]; j; j=e[j].nex) {
        if(e[j].to == fa[p]) continue;
        s[e[j].to] = s[p];
        fa[e[j].to] = p; dep[e[j].to] = dep[p]+1;
        dfs(e[j].to);
    }
}

int bin[N]; bool vis[N];

int Find(int x) {
    if(x != bin[x]) bin[x] = Find(bin[x]);
    return bin[x];
}

void Tarjan(int p) {
    bin[p] = p;
    for(int j=head[p]; j; j=e[j].nex) {
        if(e[j].to == fa[p]) continue;
        Tarjan(e[j].to);
        bin[Find(e[j].to)] = Find(p);
    }
    vis[p] = true;
    for(int j=qhead[p]; j; j=e[j].nex) {
        int y = (q[e[j].to].x==p) ? q[e[j].to].y : q[e[j].to].x;
        if(vis[y]) q[e[j].to].dep = dep[Find(y)];
    }
}

void Build_tree() {
    dep[1] = 1; dfs(1);
    for(int i=1; i<=m; i++) {
        q[i].x=read(); q[i].y=read();
        e[++cnt].nex = qhead[q[i].x]; qhead[q[i].x] = cnt;
        e[cnt].to = i;
        e[++cnt].nex = qhead[q[i].y]; qhead[q[i].y] = cnt;
        e[cnt].to = i;
    }
    memset(vis, false, sizeof(vis));
    Tarjan(1);
}

void solve() {
    for(int j=1; j<=m; j++) {
        int x = q[j].x, y = q[j].y;
        int depth = q[j].dep;
        ANS.Init();
        for(int i=60; ~i; i--)
            if(s[x].h[i].t >= depth) ANS.Insert(s[x].h[i].x, 0);
        for(int i=60; ~i; i--)
            if(s[y].h[i].t >= depth) ANS.Insert(s[y].h[i].x, 0);
        
        ll res = 0;
        for(int i=60; ~i; i--)
            res = max(res, res^ANS.h[i].x);
        printf("%lld\n", res);
    }
}

int main() {
    initlaize();
    Build_tree();
    solve();
    return 0;
}

47. bzoj4569

太强了,我想了老半天的线段树优化连边,但是线段树有一个地方不好,就是相等长的两段区间他们最终询问所代表的区间是形态不同的,这就十分麻烦。正解原来是ST表,神了,与线段树有着相似的功能。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
#define MOD 1000000007
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, m, fa[18][N];

inline int Find(int k, int x) {
    if(x != fa[k][x]) fa[k][x] = Find(k, fa[k][x]);
    return fa[k][x];
}

void Merge(int k, int x, int y) {
    int f1 = Find(k, x), f2 = Find(k, y);
    if(f1 == f2) return; else fa[k][f1] = f2;
    if( !k) return;
    Merge(k-1, x, y); Merge(k-1, x+(1<<(k-1)), y+(1<<(k-1)));
}

long long Pow(long long a, int p) {
    if(p<=1) return (!p) ? 1 : a;
    long long c = Pow(a, p>>1); c = c*c % MOD;
    if(p & 1) return (c*a) % MOD;
    else return c;
}

int main() {
    n=read(), m=read();
    if(n == 1) printf("10");
    else {
        for(int k=0; k<17; k++)
            for(int i=1; i<=n; i++)
                fa[k][i] = i;
        for(int i=1; i<=m; i++) {
            int l1=read(), r1=read(), l2=read(), r2=read();
            int k = (int)log2(r1 - l1 + 1);
            Merge(k, l1, l2); Merge(k, r1-(1<<k)+1, r2-(1<<k)+1);
        }
        int ans = 0;
        for(int i=1; i<=n; i++)
            if(fa[0][i] == i) ans++;
        printf("%lld", 9*Pow(10, ans-1) % MOD);
    }
    return 0;
}

48. bzoj4571

黑科技:二进制的Trie树就是主席树,然后就在主席树上找对应的减掉x后的区间中有没有树就好了,可持久化Trie可以用的更灵活了。还有就是可以维护我之前走线段树上的路径,这个可以用一个01串即二进制数表示。一开始主席树的插入写错了,我把叶子节点强行搞成siz值为1,但是这样就不能处理有相同的美味值的情况。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 200005
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
static int n, m;
static int root[N], ch[N*50][2], siz[N*50], Index;

void Insert(int &p, int p1, int Le, int Re, int x) {
    p = ++Index; siz[p] = siz[p1] + 1;
    ch[p][0]=ch[p1][0]; ch[p][1]=ch[p1][1];
    if(Le == Re) return;
    int mid = (Le + Re) >> 1;
    if(x <= mid) Insert(ch[p][0], ch[p1][0], Le, mid, x);
    else Insert(ch[p][1], ch[p1][1], mid+1, Re, x);
}

bool Query(int p, int p1, int Le, int Re, int l, int r) {
    if(Le==l && Re==r) return siz[p]>siz[p1];
    int mid = (Le + Re) >> 1;
    if(r <= mid) return Query(ch[p][0], ch[p1][0], Le, mid, l, r);
    else if(l > mid) return Query(ch[p][1], ch[p1][1], mid+1, Re, l, r);
    else return (Query(ch[p][0],ch[p1][0],Le,mid,l,mid)|Query(ch[p][1],ch[p1][1],mid+1,Re,mid+1,r));
}

void initlaize() {
    n=read(), m=read();
    Index = 0;
    for(int i=1; i<=n; i++) {
        int x = read();
        Insert(root[i], root[i-1], 0, 300000, x);
    }
}

void solve() {
    while(m--) {
        int b=read(), x=read(), l=read(), r=read();
        int a = 0;
        for(int j=17; ~j; j--) {
            if(b & (1<<j)) {
                int L = max(a-x, 0), R = (a|((1<<j)-1))-x;
                if(R<0 || (!Query(root[r], root[l-1], 0, 300000, L, R))) a ^= (1<<j);
            }
            else {
                a ^= (1<<j);
                int L = max(a-x, 0), R = (a|((1<<j)-1))-x;
                if(R<0 || (!Query(root[r], root[l-1], 0, 300000, L, R))) a ^= (1<<j);
            }
        }
        printf("%d\n", a^b);
    }
}

int main() {
    initlaize();
    solve();
    return 0;
}

49. bzoj4034

树链剖分裸题,或者用dfs序的黑科技:每个点访问时和退出时都++Index,就是说每个点在dfs序中出现两次,然后一个点到根节点的路径就可以表示为dfs序的一个前缀,单点修改时入队点+,出对点-,子树修改时打一下标记就好了,即遇到入队点是+,遇到出对点是-。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define N 100005
#define L(a) ((a)<<1)
#define R(a) ((a)<<1|1)
using namespace std;
typedef long long LL;
int n, m, a[N], Index=0;
int dep[N], siz[N], top[N], fa[N], dfn1[N], dfn2[N];
struct Edge { int nex, to; } e[N*2];
static int head[N], cnt;
inline void Link(int x,int y) { e[++cnt]=(Edge){head[x],y}; head[x]=cnt; }

struct Segment_Tree {
    LL Sum[N*5], Lazy[N*5];
    
    void Init() {
        memset(Sum, 0, sizeof(Sum));
        memset(Lazy, 0, sizeof(Lazy));
    }
    
    void add(int p, int l, int r, LL k) {
        Lazy[p] += k; Sum[p] += (k*(LL)(r-l+1));
    }
    
    void Pushdown(int p, int l, int r) {
        if(l == r) Lazy[p] = 0; if(Lazy[p] == 0) return;
        int mid = (l + r) >> 1;
        add(L(p), l, mid, Lazy[p]); add(R(p), mid+1, r, Lazy[p]);
        Lazy[p] = 0;
    }
    
    LL  Query(int p, int Le, int Re, int l, int r) {
        Pushdown(p, Le, Re);
        if(Le==l && Re==r) return Sum[p];
        int mid = (Le + Re) >> 1;
        if(r <= mid) return Query(L(p), Le, mid, l, r);
        else if(l > mid) return Query(R(p), mid+1, Re, l, r);
        else return Query(L(p),Le,mid,l,mid) + Query(R(p),mid+1,Re,mid+1,r);
    }
    LL  sum(int l, int r) { return Query(1, 1, n, l, r); }
    
    void Modify(int p, int Le, int Re, int l, int r, LL k) {
        Pushdown(p, Le, Re);
        if(Le == l && Re == r) { add(p,l,r,k); return; }
        int mid = (Le + Re) >> 1;
        if(r <= mid) Modify(L(p), Le, mid, l, r, k);
        else if(l > mid) Modify(R(p), mid+1, Re, l, r, k);
        else {
            Modify(L(p), Le, mid, l, mid, k);
            Modify(R(p), mid+1, Re, mid+1, r, k);
        }
        Sum[p] = Sum[L(p)] + Sum[R(p)];
    }
    void add(int l, int r, int k) { Modify(1, 1, n, l, r, (LL)k); }

} T;

void dfs1(int p) {
    siz[p] = 1;
    for(int j=head[p]; j; j=e[j].nex) {
        int y = e[j].to;
        if(y == fa[p]) continue;
        fa[y] = p; dep[y] = dep[p]+1;
        dfs1(y);
        siz[p] += siz[y];
    }
}

void dfs2(int p, int tp) {
    dfn1[p] = ++Index; top[p] = tp;
    int son = 0;
    for(int j=head[p]; j; j=e[j].nex)
        if(e[j].to!=fa[p] && siz[e[j].to]>siz[son])
            son = e[j].to;
    if(son) dfs2(son, tp);
    for(int j=head[p]; j; j=e[j].nex)
        if(e[j].to!=fa[p] && e[j].to!=son)
            dfs2(e[j].to, e[j].to);
    dfn2[p] = Index;
}

void initlaize() {
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=1; i<n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        Link(u, v); Link(v, u);
    }
    dep[1]=1; dfs1(1);
    dfs2(1, 1);
    T.Init();
    for(int i=1; i<=n; i++) T.add(dfn1[i], dfn1[i], a[i]);
}

LL  Q(int x, int y) {
    LL res = 0;
    while(top[x] != top[y]) {
        res += T.sum(dfn1[top[x]], dfn1[x]);
        x = fa[top[x]];
    }
    res += T.sum(dfn1[y], dfn1[x]);
    return res;
}

void solve() {
    while(m--) {
        int opt, x, k; scanf("%d", &opt);
        if(opt == 1) {
            scanf("%d%d", &x, &k);
            T.add(dfn1[x], dfn1[x], k);
        }
        if(opt == 2) {
            scanf("%d%d", &x, &k);
            T.add(dfn1[x], dfn2[x], k);
        }
        if(opt == 3) {
            scanf("%d", &x);
            printf("%lld\n", Q(x,1));
        }
    }
}

int main() {
    initlaize();
    solve();
    return 0;
}

50. bzoj3439

fail树上强行线段树合并,或者倒序插入trie加dfs即可
fail树:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n, Index=1;
char ch[1000005];
struct Trie_Node {
    int ch[26], fail;
    vector<int> end;
    int root;
} s[1000005];
struct QUES {
    int k, ans;
} q[100005];
queue<int> Q;
vector<int> fail_son[1000005];

int sIndex = 0;
struct Segment_Tree_Node {
    int ch[2], siz;
} node[10000005];

void Modify(int &p, int Le, int Re, int x, int k) {
    if( !p) p = ++sIndex;
    node[p].siz += k;
    if(Le == Re) return;
    int mid = (Le + Re) >> 1;
    if(x <= mid) Modify(node[p].ch[0], Le, mid, x, k);
    else Modify(node[p].ch[1], mid+1, Re, x, k);
}

int  Query_k(int p, int Le, int Re, int k) {
    if(node[p].siz < k) return -1;
    if(Le == Re) return Le;
    int mid = (Le + Re) >> 1;
    if(k <= node[node[p].ch[0]].siz) return Query_k(node[p].ch[0], Le, mid, k);
    else return Query_k(node[p].ch[1], mid+1, Re, k-node[node[p].ch[0]].siz);
}

int Merge(int x, int y) {
    if( !x) return y;
    if( !y) return x;
    node[x].ch[0] = Merge(node[x].ch[0], node[y].ch[0]);
    node[x].ch[1] = Merge(node[x].ch[1], node[y].ch[1]);
    node[x].siz = node[node[x].ch[0]].siz + node[node[x].ch[1]].siz;
    return x;
}

void Insert(char *str, int id) {
    int len = strlen(str);
    int p = 1;
    for(int i=0; i<len; i++) {
        if( !s[p].ch[str[i]-'a'])
            s[p].ch[str[i]-'a'] = ++Index;
        p = s[p].ch[str[i]-'a'];
        if(i==len-1) s[p].end.push_back(id);
    }
}

void build_fail() {
    while( !Q.empty()) Q.pop();
    
    for(int i=0; i<26; i++)
        if(s[1].ch[i]) {
            s[s[1].ch[i]].fail = 1;
            Q.push(s[1].ch[i]);
            fail_son[1].push_back(s[1].ch[i]);
        }
    
    while( !Q.empty()) {
        int x = Q.front(); Q.pop();
        for(int i=0; i<26; i++)
            if(s[x].ch[i]) {
                int p = s[x].fail;
                while(p>1 && !s[p].ch[i]) p = s[p].fail;
                if(s[p].ch[i]) p = s[p].ch[i];
                s[s[x].ch[i]].fail = p;
                fail_son[p].push_back(s[x].ch[i]);
                Q.push(s[x].ch[i]);
            }
    }
}

void initlaize() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        scanf("%s", ch);
        Insert(ch, i);
    }
    
    for(int i=1; i<=n; i++)
        scanf("%d", &q[i].k);
}

void dfs(int p) {
    int sz = fail_son[p].size();
    for(int i=0; i<sz; i++) {
        dfs(fail_son[p][i]);
        s[p].root = Merge(s[p].root, s[fail_son[p][i]].root);
    }
    
    sz = s[p].end.size();
    for(int i=0; i<sz; i++)
        Modify(s[p].root, 1, n, s[p].end[i], 1);
    
    for(int i=0; i<sz; i++)
        q[s[p].end[i]].ans = Query_k(s[p].root, 1, n, q[s[p].end[i]].k);
}

int main() {
    initlaize();
    build_fail();
    dfs(1);
    for(int i=1; i<=n; i++)
        printf("%d\n", q[i].ans);
    return 0;
}

倒序插入trie:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n, Index = 1;
char ch[1000005];
struct QUES {
    int k, ans;
} q[100005];
struct Trie_Node {
    int ch[26];
    int root;
    vector<int> end;
} s[1000005];
 
void Insert(char *str, int id) {
    int len = strlen(str+1), p = 1;
    for(int i=len; i; i--) {
        if( !s[p].ch[str[i]-'a'])
            s[p].ch[str[i]-'a'] = ++Index;
        p = s[p].ch[str[i]-'a'];
        if(i==1) s[p].end.push_back(id);
    }
}
 
void initlaize() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        scanf("%s", ch+1);
        Insert(ch, i);
    }
    for(int i=1; i<=n; i++)
        scanf("%d", &q[i].k);
}
 
int sIndex = 0;
struct Segment_Node {
    int ch[2], siz;
} node[10000005];
 
void Insert(int &p, int l, int r, int x) {
    if( !p) p = ++sIndex; node[p].siz++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) Insert(node[p].ch[0], l, mid, x);
    else Insert(node[p].ch[1], mid+1, r, x);
}
 
int  Queryk(int p, int l, int r, int k) {
    if(node[p].siz < k) return -1;
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(k <= node[node[p].ch[0]].siz) return Queryk(node[p].ch[0], l, mid, k);
    else return Queryk(node[p].ch[1], mid+1, r, k-node[node[p].ch[0]].siz);
}
 
int Merge(int x, int y) {
    if( !x) return y;
    if( !y) return x;
    node[x].ch[0] = Merge(node[x].ch[0], node[y].ch[0]);
    node[x].ch[1] = Merge(node[x].ch[1], node[y].ch[1]);
    node[x].siz = node[node[x].ch[0]].siz + node[node[x].ch[1]].siz;
    return x;
}
 
void solve(int p) {
    for(int i=0; i<26; i++)
        if(s[p].ch[i]) {
            solve(s[p].ch[i]);
            s[p].root = Merge(s[p].root, s[s[p].ch[i]].root);
        }
     
    int sz = s[p].end.size();
    for(int i=0; i<sz; i++)
        Insert(s[p].root, 1, n, s[p].end[i]);
     
    for(int i=0; i<sz; i++)
        q[s[p].end[i]].ans = Queryk(s[p].root, 1, n, q[s[p].end[i]].k);
}
 
int main() {
    initlaize();
    solve(1);
    for(int i=1; i<=n; i++)
        printf("%d\n", q[i].ans);
    return 0;
}

小总结:

1.贪心
2.dp优化
3.分数规划+前缀和构图
4.半平面交转单调栈
5.$nlog^2n$的线段树或者分块,分块要好想到一些。
6.状压dp,数据范围就不能大一点吗暴力过了诶哥。。。
7.dp,状态的表示
8.利用欧拉定理降幂
9.勾股数两个套路中的一个,给定$r^2$求有多少个满足条件的$(x,y)$,
10/11.SG函数
12.二分答案+主席树验证
13.分类讨论+树状数组(离线)/主席树(在线)
14.网络流限流找路径
15.枚举中心点+数学公式变形递推求和
16.网络流二元组解方程建图
17.网络流打包连边建图
18.dp,转移时细节
19.每条边算贡献
20.dfs序,离线并查集,cdq分治
21.处理只走正向边与只走反向边到某个节点的距离,然后枚举逆向边即可
22.找一下规律就是莫比乌斯函数
23.公式变形+分段求值技巧
24.主席树
25.推式子+树状数组优化查询前缀和,和NOIP2015那个普及组第三题好像
26.推出与非运算的性质然后就是数位dp了。
27.排列组合
28.分类讨论各种性质
29.永无乡
30.神思路+状压dp
31.把数分类后状压dp
32.并查集
33.树链剖分
34.矩乘优化
35.发现要求维护最值前缀和与后缀和,支持一系列操作
36.按位统计+概率dp
37.暴力枚举对角线
38.最小割+主席树优化连边
39.连反向边简化问题
40.矩乘快速幂
41.整体二分
42/43.fail树
44.fail树上贪心
45/46.线性基应用,46有黑科技
47.ST表优化合并
48.主席树替代01串的可持久化Trie树
49.树链剖分
50.fail树强上线段树合并

我计算几何方面一片空白。。。概率dp少的可怜,网络流要补补了。。。