最新文章

后缀自动机原理及实现

后缀自动机原理及实现

概述 后缀自动机(Suffix Automaton,简称SAM)是一种用于字符串处理的有限 

[SPOJ-LCS2]Longest Common Substring II 题解

[SPOJ-LCS2]Longest Common Substring II 题解

题目地址:SPOJ:SPOJ.com – Problem LCS2、洛谷:【S 

[BZOJ3091]城市旅行 题解

[BZOJ3091]城市旅行 题解

题目地址:BZOJ:Problem 3091. — 城市旅行

题目描述

travel

输入输出格式

输入格式:
travel

输出格式:
travel

输入输出样例

输入样例#1:

4 5
1 3 2 5
1 2
1 3
2 4
4 2 4
1 2 4
2 3 4
3 1 4 1
4 1 4

输出样例#1:

16/3
6/1

说明

对于所有数据满足 1<=N<=50,000 1<=M<=50,000 1<=Ai<=10^6 1<=D<=100 1<=U,V<=N

题解

参考资料:BZOJ 3091 城市旅行 Link-Cut-Tree – CSDN博客
其实本题是[HAOI2012]高速公路一题扩展到树上的做法。由于树需要动态维护,自然会想到使用LCT。
我们考虑一条树链上的期望应该如何计算,可以求出树链上每个点对期望的分子的贡献,对于a_i,它的贡献是i(n-i+1),即我们要求的分子是\sum_{i=1}^n a_i \cdot i \cdot (n-i+1),我们得想办法在LCT上把这个值维护出来。
于是我们就想到了,能不能先求出子树对应树链的答案,然后再怎么样拼起来呢?
我们观察一下结果吧,假设左子树树链长为4,右子树长为2

想求的东西          1*7*a1 + 2*6*a2 + 3*5*a3 + 4*4*a4 + 5*3*a5 + 6*2*a6 + 7*1*a7
两个子树的答案加起来 1*4*a1 + 2*3*a2 + 3*2*a3 + 4*1*a4 +        + 1*2*a6 + 2*1*a7
上式减下式          1*3*a1 + 2*3*a2 + 3*3*a3 + 4*3*a4 + 5*3*a5 + 5*2*a6 + 5*1*a7

a5是树根处的元素可以单独算,3其实是右子树大小+1,5则是左子树大小+1,我们考虑同时维护一个lsum = \sum_{i=1}^n a_i \cdot i和一个rsum = \sum_{i=1}^n a_i \cdot (n-i+1),就可以借助这些来求整条树链的答案了,即
ans = ans_l + ans_r + (siz_l+1)(siz_r+1)a_{root} + (siz_r+1)(lsum_l) + (siz_l+1)(rsum_r)
而lsum、rsum的合并很简单,只需要把子树元素和乘上另一侧子树的个数+1就好,元素和可以顺便维护一下。
此外,本题还要求一个树链加法标记,如何应用这个加法标记到我们维护的信息上就会是问题。lsum、rsum需要加上add \cdot \sum_{i=1}^n i,比较好办,而期望的分子需要加上add \cdot \sum_{i=1}^n i(n-i+1),这个并不好办,不过我们有数学方法得到这个求和的公式,最后得出的结果是\sum_{i=1}^n i(n-i+1) = \frac{n(n+1)(n+2)}{6}
万事大吉了,剩下的就是把上面的东西码进去。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for (; !isdigit(c); c = fgc()) if (c == '-') neg = -1;
    for (; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 50005;

struct Node {
    int ch[2], fa; LL siz, val, lsum, rsum, sum, exp;
    bool rev; LL add;
} tr[MAXN];

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline bool isroot(int p) {
    return tr[tr[p].fa].ch[0] != p && tr[tr[p].fa].ch[1] != p;
}

inline void update(int p) {
    tr[p].siz = tr[tr[p].ch[0]].siz + tr[tr[p].ch[1]].siz + 1;
    tr[p].sum = tr[tr[p].ch[0]].sum + tr[tr[p].ch[1]].sum + tr[p].val;
    tr[p].lsum = tr[tr[p].ch[0]].lsum + tr[p].val * (tr[tr[p].ch[0]].siz + 1) 
        + tr[tr[p].ch[1]].lsum + tr[tr[p].ch[1]].sum * (tr[tr[p].ch[0]].siz + 1);
    tr[p].rsum = tr[tr[p].ch[0]].rsum + tr[tr[p].ch[0]].sum * (tr[tr[p].ch[1]].siz + 1) 
        + tr[p].val * (tr[tr[p].ch[1]].siz + 1) + tr[tr[p].ch[1]].rsum;
    tr[p].exp = tr[tr[p].ch[0]].exp + tr[tr[p].ch[1]].exp 
        + tr[tr[p].ch[0]].lsum * (tr[tr[p].ch[1]].siz + 1) 
        + tr[tr[p].ch[1]].rsum * (tr[tr[p].ch[0]].siz + 1) 
        + (tr[tr[p].ch[0]].siz + 1) * (tr[tr[p].ch[1]].siz + 1) * tr[p].val;
}

inline void reverse(int p) {
    std::swap(tr[p].ch[0], tr[p].ch[1]);
    std::swap(tr[p].lsum, tr[p].rsum);
    tr[p].rev ^= 1;
}

inline void add(int p, LL v) {
    tr[p].val += v;
    tr[p].sum += v * tr[p].siz;
    tr[p].lsum += v * tr[p].siz * (tr[p].siz + 1) / 2;
    tr[p].rsum += v * tr[p].siz * (tr[p].siz + 1) / 2;
    tr[p].exp += v * tr[p].siz * (tr[p].siz + 1) * (tr[p].siz + 2) / 6;
    tr[p].add += v;
}

inline void pushdown(int p) {
    if(tr[p].rev) {
        if(tr[p].ch[0]) reverse(tr[p].ch[0]);
        if(tr[p].ch[1]) reverse(tr[p].ch[1]);
        tr[p].rev ^= 1;
    }
    if(tr[p].add) {
        if(tr[p].ch[0]) add(tr[p].ch[0], tr[p].add);
        if(tr[p].ch[1]) add(tr[p].ch[1], tr[p].add);
        tr[p].add = 0;
    }
}

int sta[MAXN], stop;

inline void pushto(int p) {
    stop = 0;
    while(!isroot(p)) {
        sta[stop++] = p; p = tr[p].fa;
    }
    sta[stop++] = p;
    while(stop) {
        pushdown(sta[--stop]);
    }
}

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(!isroot(fa)) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[p].ch[!t] = fa; tr[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(int fa = tr[p].fa; !isroot(p); rotate(p), fa = tr[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p);
}

inline void access(int p) {
    for(int q = 0; p; q = p, p = tr[p].fa) {
        splay(p); tr[p].ch[1] = q; update(p);
    }
}

inline void makert(int p) {
    access(p); splay(p); reverse(p);
}

inline int findrt(int p) {
    access(p); splay(p);
    while(tr[p].ch[0]) p = tr[p].ch[0];
    return p;
}

inline void split(int u, int v) {
    makert(u); access(v); splay(v);
}

inline void link(int u, int v) {
    if(findrt(u) == findrt(v)) return;
    split(u, v); tr[u].fa = v;
}

inline void cut(int u, int v) {
    split(u, v);
    if(tr[v].ch[0] != u || tr[u].ch[1]) return;
    tr[u].fa = tr[v].ch[0] = 0; update(v);
}

int n, m;
std::vector<int> gra[MAXN];

inline void dfs(int u, int fa) {
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == fa) continue;
        tr[v].fa = u;
        dfs(v, u);
    }
}

inline LL gcd(LL x, LL y) {
    if(!y) return x;
    return gcd(y, x % y);
}

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        tr[i].val = readint(); update(i);
    }
    for(int i = 1, a, b; i < n; i++) {
        a = readint(); b = readint();
        gra[a].push_back(b); gra[b].push_back(a);
    }
    dfs(1, 0);
    int op, u, v; LL d;
    while(m--) {
        op = readint(); u = readint(); v = readint();
        if(op == 1) {
            cut(u, v);
        } else if(op == 2) {
            link(u, v);
        } else if(op == 3) {
            d = readint(); if(findrt(u) != findrt(v)) continue;
            split(u, v); add(v, d);
        } else {
            if(findrt(u) != findrt(v)) {
                puts("-1"); continue;
            }
            split(u, v);
            LL up = tr[v].exp, down = (tr[v].siz + 1) * tr[v].siz / 2, g = gcd(up, down);
            printf("%lld/%lld\n", up / g, down / g);
        }
    }
    return 0;
}
[BZOJ3561]DZY Loves Math VI 题解

[BZOJ3561]DZY Loves Math VI 题解

题目地址:BZOJ:Problem 3561. — DZY Loves Mat 

[BZOJ3560]DZY Loves Math V 题解

[BZOJ3560]DZY Loves Math V 题解

题目地址:BZOJ:Problem 3560. — DZY Loves Mat 

[BZOJ3563]DZY Loves Chinese 题解

[BZOJ3563]DZY Loves Chinese 题解

题目地址:BZOJ:Problem 3563. — DZY Loves Chinese

题目描述

神校XJ之学霸兮,Dzy皇考曰JC。
摄提贞于孟陬兮,惟庚寅Dzy以降。
纷Dzy既有此内美兮,又重之以修能。
遂降临于OI界,欲以神力而凌♂辱众生。

今Dzy有一魞歄图,其上有N座祭坛,又有M条膴蠁边。
时而Dzy狂WA而怒发冲冠,神力外溢,遂有K条膴蠁边灰飞烟灭。
而后俟其日A50题则又令其复原。(可视为立即复原)
然若有祭坛无法相互到达,Dzy之神力便会大减,于是欲知其是否连通。

题意简述

有一个无向图,每次询问删去若干条边,问图是否连通。强制在线(仮)。

输入输出格式

输入格式:
第一行N,M
接下来M行x,y:表示M条膴蠁边,依次编号
接下来一行Q
接下来Q行:
每行第一个数K而后K个编号c1~cK:表示K条边,编号为c1~cK
为了体现在线,K以及c1~cK均需异或之前回答为连通的个数

输出格式:
对于每个询问输出:连通则为‘Connected’,不连通则为‘Disconnected’(不加引号)

输入输出样例

输入样例#1:

5 10
2 1
3 2
4 2
5 1
5 3
4 1
4 3
5 2
3 1
5 4
5
1 1
2 7 0 3
6 0 7 4 6
1 2 7
0 5 0 2 13

输出样例#1:

Connected
Connected
Connected
Connected
Disconnected

说明

N≤100000 M≤500000 Q≤50000 1≤K≤15
数据保证没有重边与自环
Tip:请学会使用搜索引擎

题解

强制在线个鬼!逗比题一个。
K都异或了,反着异或真实的K,不就得到了这个询问之前有多少询问是连通的嘛,然后反着推一遍,就得到了除了最后一个询问以外的其他询问的答案。
最后一个询问就用并查集随便搞一搞就行。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>

inline bool isendl(char c) {
    return c == '\r' || c == '\n';
}

const int MAXN = 500005;

int n, m, q;

int fa[MAXN];

inline int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

struct Edge {
    int u, v;
} edges[MAXN];

int k, qur[MAXN], ans[MAXN];
bool del[MAXN];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &edges[i].u, &edges[i].v);
    }
    scanf("%d", &q);
    for(int i = 1; i <= q; i++) {
        int cnt = 0;
        scanf("%d", &k);
        while(!isendl(getchar())) {
            scanf("%d", &qur[++cnt]);
        }
        ans[i] = k ^ cnt; k = cnt;
    }
    for(int i = 1; i < q; i++) {
        if(ans[i + 1] - ans[i]) puts("Connected");
        else puts("Disconnected");
    }
    for(int i = 1; i <= k; i++) {
        qur[i] ^= ans[q]; del[qur[i]] = true;
    }
    for(int i = 1; i <= m; i++) {
        if(del[i]) continue;
        int u = edges[i].u, v = edges[i].v, fu = find(u), fv = find(v);
        if(fu == fv) continue;
        fa[fu] = fv;
    }
    int f1 = find(1);
    for(int i = 2; i <= n; i++) {
        if(find(i) != f1) {
            puts("Disconnected");
            return 0;
        }
    }
    puts("Connected");
    return 0;
}
[ZJOI2009]取石子游戏 题解

[ZJOI2009]取石子游戏 题解

题目地址:洛谷:【P2599】[ZJOI2009]取石子游戏 – 洛谷、BZO 

[BJWC2010]取数游戏 题解

[BJWC2010]取数游戏 题解

题目地址:洛谷:【P4411】[BJWC2010]取数游戏 – 洛谷、BZOJ 

[BZOJ3208]花神的秒题计划Ⅰ 题解

[BZOJ3208]花神的秒题计划Ⅰ 题解

题目地址:BZOJ:Problem 3208. — 花神的秒题计划Ⅰ

题目描述

背景【backboard】:
Memphis等一群蒟蒻出题中,花神凑过来秒题……
描述【discribe】:
花花山峰峦起伏,峰顶常年被雪,Memphis打算帮花花山风景区的人员开发一个滑雪项目。
我们可以把风景区看作一个n*n的地图,每个点有它的初始高度,滑雪只能从高处往低处滑【严格大于】。但是由于地势经常变动【比如雪崩、滑坡】,高度经常变化;同时,政府政策规定对于每个区域都要间歇地进行保护,防止环境破坏。现在,滑雪项目的要求是给出每个n*n个点的初始高度,并给出m个命令,C a b c表示坐标为a,b的点的高度改为c;S a b c d表示左上角为a,b右下角为c,d的矩形地区开始进行保护,即不能继续滑雪;B a b c d表示左上角为a b,右下角为c d的矩形地区取消保护,即可以开始滑雪;Q表示询问现在该风景区可以滑雪的最长路径为多少。对于每个Q要作一次回答。
花神一看,这不是超简单!立刻秒出了标算~

题意简述

动态改变点权和点的可用性的滑雪DP。

输入输出格式

输入格式:
第一行n,第二行开始n*n的地图,意义如上;接下来一个m,然后是m个命令,如上

输出格式:
对于每一个Q输出单独一行的回答

输入输出样例

输入样例#1:

5
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25
5
C 1 1 3
Q
S 1 3 5 5
S 3 1 5 5
Q

输出样例#1:

24
3

说明

样例解释:
第一个Q路线为:25->24->23->22….->3->2
第二个Q的路线为:10->9->2
100%的数据:1<=n<=700;1<=m<=1000000;其中Q、S、B操作总和<=100;
题中所有数据不超过2*10^9

题解

动态滑雪。
考虑到QSB操作操作很少,我们是可以接受O(n^3)的复杂度的,因此暴力改,每次全图重新跑记忆化搜索即可。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline bool isop(char c) {
    return c == 'C' || c == 'S' || c == 'B' || c == 'Q';
}

inline char readop() {
    char c;
    while(!isop(c = fgc())) {}
    return c;
}

const int MAXN = 705;
const int fix[2][4] = {{1, -1, 0, 0}, {0, 0, 1, -1}};

int n, m, mmp[MAXN][MAXN], dp[MAXN][MAXN];
bool prot[MAXN][MAXN];

inline int dfs(int x, int y) {
    if(prot[x][y]) return -1e9;
    if(dp[x][y] != -1) return dp[x][y];
    dp[x][y] = 1;
    for(int i = 0; i < 4; i++) {
        int nx = x + fix[0][i], ny = y + fix[1][i];
        if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
        if(mmp[x][y] > mmp[nx][ny]) dp[x][y] = std::max(dp[x][y], dfs(nx, ny) + 1);
    }
    return dp[x][y];
}

char op;
int a, b, c, d;

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            mmp[i][j] = readint();
        }
    }
    m = readint();
    while(m--) {
        op = readop();
        if(op == 'Q') {
            int mx = 0;
            memset(dp, -1, sizeof(dp));
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    mx = std::max(mx, dfs(i, j));
                }
            }
            printf("%d\n", mx);
        } else if(op == 'C') {
            a = readint(); b = readint(); c = readint();
            mmp[a][b] = c;
        } else if(op == 'S') {
            a = readint(); b = readint(); c = readint(); d = readint();
            for(int i = a; i <= c; i++) {
                for(int j = b; j <= d; j++) {
                    prot[i][j] = true;
                }
            }
        } else {
            a = readint(); b = readint(); c = readint(); d = readint();
            for(int i = a; i <= c; i++) {
                for(int j = b; j <= d; j++) {
                    prot[i][j] = false;
                }
            }
        }
    }
    return 0;
}
[BZOJ3551][ONTAK2010]Peaks加强版 题解

[BZOJ3551][ONTAK2010]Peaks加强版 题解

题目地址:BZOJ:Problem 3551. — [ONTAK2010]Pe