Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

翻车笔记 ZKY 学长的杂题 [杂题, 清奇脑回路]

Posted on Edited on In

给大家拜个晚年 祝大家狗年快乐

计数器:

19

上学了...还是学校舒服...里面个个都是人才...说话又好听...

zky学长来讲课啦! zky学长好帅啊!

简单题

bitset优化一下背包就行了, 比手写的好用多了...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**************************************************************
    Problem: 3687
    User: Cansult
    Language: C++
    Result: Accepted
    Time:2640 ms
    Memory:1948 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <bitset>
#define MAXN (2000000 + 5)
#define pii pair<int, int>
#define LL unsigned long long
using namespace std;
int n;
LL ans;
bitset<MAXN> f;
int main() {
    scanf("%d", &n);
    for (int i = 1, srx; i <= n; i++) {
        scanf("%d", &srx);
        f[0] = 1;
        f ^= (f << srx);
    }
    for (int i = 1; i < MAXN; i++)
        if (f[i])
            ans ^= i;
    printf("%lld", ans);
    return 0;
}

Preprefix sum

维护前缀和然后区间修改区间查询就完事了

当然也可以推一波式子...和树状数组维护区间的感觉差不多...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**************************************************************
    Problem: 3155
    User: Cansult
    Language: C++
    Result: Accepted
    Time:672 ms
    Memory:11840 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#define LS(dq) ((dq) << 1)
#define RS(dq) (LS(dq) + 1)
#define MAXN (100000 + 5)
#define LL long long
using namespace std;
struct node {
    int le, ri;
    LL zh, lazy;
} b[MAXN << 2];
int n, a[MAXN];
LL f[MAXN];
void js(int dq, int le, int ri) {
    b[dq].le = le, b[dq].ri = ri, b[dq].zh = f[le];
    if (le == ri) return ;
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi), js(RS(dq), mi + 1, ri);
    b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
}
void push_down(int dq) {
    LL zh = b[dq].lazy;
    b[LS(dq)].lazy += zh, b[RS(dq)].lazy += zh;
    b[LS(dq)].zh += (b[LS(dq)].ri - b[LS(dq)].le + 1) * zh;
    b[RS(dq)].zh += (b[RS(dq)].ri - b[RS(dq)].le + 1) * zh;
    b[dq].lazy = 0;
}
void xg(int dq, int le, int ri, int zh) {
    if (b[dq].le == le && b[dq].ri == ri) {
        b[dq].zh += (LL)(ri - le + 1) * zh;
        b[dq].lazy += zh;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (b[dq].lazy) push_down(dq);
    if (le > mi) xg(RS(dq), le, ri, zh);
    else if (ri <= mi) xg(LS(dq), le, ri, zh);
    else xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
    b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
}
LL cx(int dq, int le, int ri) {
    if (b[dq].le == le && b[dq].ri == ri)
        return b[dq].zh;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (b[dq].lazy) push_down(dq);
    if (le > mi) return cx(RS(dq), le, ri);
    else if (ri <= mi) return cx(LS(dq), le, ri);
    else return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
}
int main() {
    int q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), f[i] = f[i - 1] + a[i];
    js(1, 1, n);
    char srs[10 + 5];
    for (int i = 1, srx, sry; i <= q; i++) {
        scanf("%s", srs);
        if (srs[0] == 'Q') scanf("%d", &srx), printf("%lld\n", cx(1, 1, srx));
        else scanf("%d%d", &srx, &sry), xg(1, srx, n, sry - a[srx]), a[srx] = sry;
    }
    return 0;
}

[JSOI2009]等差数列

这题...呕...

一看到是等差 显然要对区间差分 我一看等差数列差分完不就都相等了吗 那不就是求区间颜色个数吗

写写写...这答案怎么都比标准答案...似乎...大了一倍?

后来才发现首项的问题...才发现这题真相在哪...

就是合并的时候注意是否可能前一个区间的最后一个数是后一个区间的首项 然后就完事了

至于转移为什么维护4个值...就是你写着写着发现维护少了写不出来...

那四个值的含义其实就是对于当前区间 可以去掉两边的值后的答案(去掉的那个值就给旁边的区间当首项了)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/**************************************************************
    Problem: 1558
    User: Cansult
    Language: C++
    Result: Accepted
    Time:3520 ms
    Memory:15744 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN (100000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (LS(dq) | 1)
using namespace std;
struct node {
    int le, ri, lc, rc, ans[4], lazy; // 0: l和r都不在等差数列中; 1: l在等差数列中; 2: r在等差数列中; 3: l和r都在等差数列中
} b[MAXN << 2];
int a[MAXN], n;
node push_up(node le, node ri) {
    node re;
    re.lazy = 0;
    re.le = le.le, re.ri = ri.ri;
    re.lc = le.lc, re.rc = ri.rc;
 
    re.ans[0] = le.ans[2] + ri.ans[1] - (le.rc == ri.lc);
    re.ans[0] = min(re.ans[0], le.ans[0] + ri.ans[1]);
    re.ans[0] = min(re.ans[0], le.ans[2] + ri.ans[0]);
 
    re.ans[1] = le.ans[3] + ri.ans[1] - (le.rc == ri.lc);
    re.ans[1] = min(re.ans[1], le.ans[1] + ri.ans[1]);
    re.ans[1] = min(re.ans[1], le.ans[3] + ri.ans[0]);
 
    re.ans[2] = le.ans[2] + ri.ans[3] - (le.rc == ri.lc);
    re.ans[2] = min(re.ans[2], le.ans[0] + ri.ans[3]);
    re.ans[2] = min(re.ans[2], le.ans[2] + ri.ans[2]);
 
    re.ans[3] = le.ans[3] + ri.ans[3] - (le.rc == ri.lc);
    re.ans[3] = min(re.ans[3], le.ans[3] + ri.ans[2]);
    re.ans[3] = min(re.ans[3], le.ans[1] + ri.ans[3]);
 
    return re;
}
void js(int dq, int le, int ri) {
    b[dq].le = le, b[dq].ri = ri, b[dq].lazy = 0, b[dq].lc = b[dq].rc = a[le];
    b[dq].ans[3] = b[dq].ans[2] = b[dq].ans[1] = 1;
    b[dq].ans[0] = 0;
    if (le == ri) return ;
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi), js(RS(dq), mi + 1, ri);
    b[dq] = push_up(b[LS(dq)], b[RS(dq)]);
}
void push_down(int dq) {
    int zh = b[dq].lazy;
    b[LS(dq)].lazy += zh, b[LS(dq)].lc += zh, b[LS(dq)].rc += zh;
    b[RS(dq)].lazy += zh, b[RS(dq)].lc += zh, b[RS(dq)].rc += zh;
    b[dq].lazy = 0;
}
void xg(int dq, int le, int ri, int zh) {
    le = max(le, 1), ri = min(ri, n - 1);
    if (le > ri) return ;
    if (b[dq].le == le && b[dq].ri == ri) {
        b[dq].lc += zh, b[dq].rc += zh;
        b[dq].lazy += zh;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (b[dq].lazy) push_down(dq);
    if (le > mi) xg(RS(dq), le, ri, zh);
    else if (ri <= mi) xg(LS(dq), le, ri, zh);
    else xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
    b[dq] = push_up(b[LS(dq)], b[RS(dq)]);
}
node cx(int dq, int le, int ri) {
    if (b[dq].le == le && b[dq].ri == ri)
        return b[dq];
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (b[dq].lazy) push_down(dq);
    if (le > mi) return cx(RS(dq), le, ri);
    else if (ri <= mi) return cx(LS(dq), le, ri);
    else return push_up(cx(LS(dq), le, mi), cx(RS(dq), mi + 1, ri));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i < n; i++) a[i] = a[i + 1] - a[i];
    js(1, 1, n - 1);
    int q;
    scanf("%d", &q);
    char srs[10 + 5];
    for (int i = 1, srx, sry, sra, srb; i <= q; i++) {
        scanf("%s", srs);
        if (srs[0] == 'A') {
            scanf("%d%d%d%d", &srx, &sry, &sra, &srb);
            xg(1, srx - 1, srx - 1, sra);
            xg(1, srx, sry - 1, srb);
            xg(1, sry, sry, -sra - (sry - srx) * srb);
        }
        else
            scanf("%d%d", &srx, &sry), printf("%d\n", (srx == sry) ? 1 : cx(1, srx, sry - 1).ans[3]);
    }
    return 0;
}

[Poi2010]Intelligence test

这题...众(不包括我)所周知这种一个数(\(n\))特别大的情况, 就尽量只扫一遍\(n\)

然后...就扫一遍\(n\)....就完事了....

(可以体会一下注释中的代码和AC代码的微妙区别)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**************************************************************
    Problem: 2083
    User: Cansult
    Language: C++
    Result: Accepted
    Time:7444 ms
    Memory:52752 kb
****************************************************************/
 
#include <cstdio>
#include <vector>
#define MAXN (1000000 + 5)
using namespace std;
int n, m, a[MAXN], len[MAXN];
bool ans[MAXN];
vector<int> b[MAXN], nex[MAXN];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int m;
    scanf("%d", &m);
    for (int i = 1, dqn; i <= m; i++) {
        scanf("%d", &dqn);
        for (int j = 1, srx; j <= dqn; j++)
            scanf("%d", &srx), b[i].push_back(srx);
        nex[b[i][0]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        vector<int> bk = nex[a[i]];
        nex[a[i]].clear();
        for (int j = 0; j < bk.size(); j++) {
            int wz = bk[j];
            ++len[wz];
            if (len[wz] >= b[wz].size()) ans[wz] = true;
            else nex[b[wz][len[wz]]].push_back(wz);
        }
    }
    for (int i = 1; i <= m; i++)
        puts(ans[i] ? "TAK" : "NIE");
    return 0;
}

/*
#include <cstdio>
#include <vector>
#define MAXN (1000000 + 5)
using namespace std;
int n, m, a[MAXN], len[MAXN];
bool ans[MAXN];
vector<int> b[MAXN], nex[MAXN];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int m;
	scanf("%d", &m);
	for (int i = 1, dqn; i <= m; i++) {
		scanf("%d", &dqn);
		for (int j = 1, srx; j <= dqn; j++)
			scanf("%d", &srx), b[i].push_back(srx);
		nex[b[i][0]].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		vector<int> bk = nex[a[i]];
		nex[a[i]].clear();
		for (int j = 0; j < bk.size(); j++) {
			int wz = bk[j];
			if (len[wz] >= b[wz].size() - 1) continue;
			nex[b[wz][++len[wz]]].push_back(wz);
			if (len[wz] >= b[wz].size() - 1) ans[wz] = true; //这个地方可能只是把下一位push进了vector, 而还没有在a[]中出现过, 所以可能造成有些NIE变成TAK
		}
	}
	for (int i = 1; i <= m; i++)
		puts(ans[i] ? "TAK" : "NIE");
	return 0;
}
*/

Count

根据影魔的套路 我们发现所谓的好区间就是一个数和他的premax, nexmax

然后就是在给定的区间里看有多少个这样的区间 二维数点 用树套树即可

发现这题没修改 直接用主席树也就做完了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**************************************************************
    Problem: 3956
    User: Cansult
    Language: C++
    Result: Accepted
    Time:3872 ms
    Memory:204608 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#define MAXN (300000 + 5)
#define INF (0x7fffffff)
#define pii pair<int, int>
using namespace std;
struct node {
    int ls, rs, zh, le, ri;
} b[MAXN << 5];
int a[MAXN], n, root[MAXN], cntb, bh[MAXN], cntr;
vector<pii> pa;
stack<pii> Gary;
void ins(int pre, int& dq, int le, int ri, int zh) {
    if (!dq) dq = ++cntb, b[dq].le = le, b[dq].ri = ri, b[dq].ls = b[dq].rs = 0, b[dq].zh = b[pre].zh;
    if (le == ri) { ++b[dq].zh; return ; }
    int mi = (le + ri) >> 1;
    if (zh <= mi) b[dq].rs = (b[dq].rs ? b[dq].rs : b[pre].rs), ins(b[pre].ls, b[dq].ls, le, mi, zh);
    else b[dq].ls = (b[dq].ls ? b[dq].ls : b[pre].ls), ins(b[pre].rs, b[dq].rs, mi + 1, ri, zh);
    b[dq].zh = b[b[dq].ls].zh + b[b[dq].rs].zh;
}
int cx(int dq, int le, int ri) {
    if (!dq) return 0;
    if (b[dq].le == le && b[dq].ri == ri) return b[dq].zh;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi) return cx(b[dq].rs, le, ri);
    else if (ri <= mi) return cx(b[dq].ls, le, ri);
    else return cx(b[dq].ls, le, mi) + cx(b[dq].rs, mi + 1, ri);
}
void init() {
    Gary.push(make_pair(INF, 0));
    for (int i = 1; i <= n; i++) {
        while (Gary.top().first < a[i]) Gary.pop();
        pa.push_back(make_pair(Gary.top().second, i));
        Gary.push(make_pair(a[i], i));
    }
    while (!Gary.empty()) Gary.pop();
    Gary.push(make_pair(INF, n + 1));
    for (int i = n; i >= 1; i--) {
        while (Gary.top().first < a[i]) Gary.pop();
        pa.push_back(make_pair(i, Gary.top().second));
        Gary.push(make_pair(a[i], i));
    }
    sort(pa.begin(), pa.end());
    vector<pii>::iterator te = unique(pa.begin(), pa.end());
    pa.erase(te, pa.end());
    int dq = 0;
    for (int i = 0; i < pa.size(); i++) {
        if (pa[i].first < 1 || pa[i].second > n || pa[i].second - pa[i].first <= 1) continue;
        while (dq < pa[i].first - 1) bh[++dq] = cntr;
        ++cntr;
        ins(root[cntr - 1], root[cntr], 1, n, pa[i].second);
    }
    while (dq < n) bh[++dq] = cntr;
}
int main() {
    int ty, q;
    scanf("%d%d%d", &n, &q, &ty);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    init();
    for (int i = 1, lastans = 0, srx, sry; i <= q; i++) {
        scanf("%d%d", &srx, &sry);
        if (ty) {
            srx = (srx + lastans - 1) % n + 1, sry = (sry + lastans - 1) % n + 1;
            if (srx > sry) swap(srx, sry);
        }
        lastans = cx(root[bh[n]], 1, sry) - cx(root[bh[srx - 1]], 1, sry) + sry - srx;
        printf("%d\n", lastans);
    }
    return 0;
}

罗马游戏

可并对板子

忘了在合并的时候判断他们是否已经在一个堆里了 丢人

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**************************************************************
    Problem: 1455
    User: Cansult
    Language: C++
    Result: Accepted
    Time:2208 ms
    Memory:42308 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN (2000000 + 5)
#define INF (0x7fffffff)
using namespace std;
struct node {
    int ls, rs, zh, dis, fa;
} b[MAXN];
int n;
bool hsdie[MAXN];
int merge(int x, int y) {
    if (x == y) return x;
    if (!x || !y) return x + y;
    if (b[x].zh > b[y].zh) swap(x, y);
    b[b[x].rs = merge(b[x].rs, y)].fa = b[b[x].ls].fa = x;
    if (b[b[x].ls].dis < b[b[x].rs].dis) swap(b[x].ls, b[x].rs);
    b[x].dis = b[b[x].rs].dis + 1;
    return x;
}
int find(int x) {
    while (b[x].fa != x) x = b[x].fa; 
    return x;
}
void uni(int fx, int fy) {
    if (b[fx].zh > b[fy].zh) b[fy].fa = fy;
    else b[fx].fa = fx;
    merge(fx, fy);
}
void del(int x) {
    int fx = find(x);
    b[fx].zh = 0;
    uni(b[fx].ls, b[fx].rs);
    b[fx].ls = b[fx].rs = 0;
    hsdie[fx] = true;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i].zh), b[i].fa = i;
    b[0].zh = INF;
    int q;
    scanf("%d", &q);
    char srs[5];
    for (int i = 1, srx, sry; i <= q; i++) {
        scanf("%s", srs);
        if (srs[0] == 'M') {
            scanf("%d%d", &srx, &sry);
            if (hsdie[srx] || hsdie[sry]) continue;
            uni(find(srx), find(sry));
        }
        else {
            scanf("%d", &srx);
            if (hsdie[srx]) puts("0");
            else { 
                int fx = find(srx);
                printf("%d\n", b[fx].zh), del(fx);
            }
        }
    }
    return 0;
}

tjoi2012 桥

众所周知boss在的边肯定在最短路的那条链上

联想一下这个题, 考虑枚举边 更新在最短路链上删除边后的收益

对于每一条边, 可以更新的区间是 [起点在以\(s\)为根的最短路树上与\(t\)的LCA, 终点在以\(t\)为根的最短路树上与\(s\)的LCA]

之所以要这么更新 主要是因为我们不知道在是否会删掉这条边后会经过我们枚举的边 所以我们要对这个区间用[经过我们枚举的边的最短路的长度]来取\(\min\)

然后最后在最短路链上找值最大的边 就是要删掉的边, 最大值的数量就是方案数

注意特判有两条没有公共边的最短路的情况 这时候无论删掉哪条边答案都不变 方案数要输出总边数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/**************************************************************
    Problem: 4400
    User: Cansult
    Language: C++
    Result: Accepted
    Time:2348 ms
    Memory:15380 kb
****************************************************************/
 
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (100000 + 5)
#define MAXM (200000 + 5)
#define INF (0x7ffffff)
#define pii pair<int, int>
#define LS(dq) ((dq) << 1)
#define RS(dq) (LS(dq) | 1)
#define rev(i) (((i - 1) ^ 1) + 1)
using namespace std;
struct edg {
    int from, to, next, cost;
} tb[MAXM << 1];
struct node {
    int le, ri, lazy;
} b[MAXN << 2];
struct cmp {
    bool operator () (const pii x, const pii y) { return x.second > y.second; }
};
int n, m, pre[2][MAXN], g[MAXN], cntb, dis[2][MAXN], ats[MAXN], att[MAXN];
// pre: 最短路树; ats: 这个点从s为根的最短路树上往上爬能达到的编号; att: 从以t为...的编号
bool chosen[MAXM << 1];
void dijk(int s, int* disx, int* prex) {
    bool vis[MAXN];
    memset(vis, false, sizeof(vis));
    priority_queue<pii, vector<pii>, cmp> q;
    q.push(make_pair(s, 0));
    for (int i = 1; i <= n; i++) disx[i] =  INF;
    disx[s] = 0;
    while (!q.empty()) {
        int dq = q.top().first;
        q.pop();
        if (vis[dq]) continue;
        vis[dq] = true;
        for (int i = g[dq]; i; i = tb[i].next)
            if (disx[tb[i].to] > disx[dq] + tb[i].cost) {
                disx[tb[i].to] = disx[dq] + tb[i].cost;
                prex[tb[i].to] = i;
                q.push(make_pair(tb[i].to, disx[tb[i].to]));
            }
    }
}
void js(int dq, int le, int ri) {
    b[dq].le = le, b[dq].ri = ri, b[dq].lazy = INF;
    if (le == ri) return ;
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi), js(RS(dq), mi + 1, ri);
}
void xg(int dq, int le, int ri, int zh) {
    if (le > ri) return ;
    if (b[dq].le == le && b[dq].ri == ri) {
        b[dq].lazy = min(b[dq].lazy, zh);
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (ri <= mi) xg(LS(dq), le, ri, zh);
    else if (le > mi) xg(RS(dq), le, ri, zh);
    else xg(LS(dq), le, mi, zh), xg(RS(dq), mi + 1, ri, zh);
}
int cx(int dq, int wz) {
    if (b[dq].le == b[dq].ri) return b[dq].lazy;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (wz <= mi) return min(b[dq].lazy, cx(LS(dq), wz));
    else return min(b[dq].lazy, cx(RS(dq), wz));
}
int dfs(int dq, int* prex, int* at) {
    if (at[dq]) return at[dq];
    return (at[dq] = dfs(tb[prex[dq]].from, prex, at));
}
void init() {
    int cnta = 0;
    for (int i = 1; i; i = tb[pre[1][i]].from) ats[i] = att[i] = ++cnta, chosen[pre[1][i]] = chosen[rev(pre[1][i])] = true;
    for (int i = 2; i < n; i++) 
        if (!ats[i])
            ats[i] = dfs(i, pre[0], ats);
    for (int i = 2; i < n; i++)
        if (!att[i])
            att[i] = dfs(i, pre[1], att);
    js(1, 1, cnta - 1);
}
void solve() {
    for (int i = 1; i <= cntb; i += 2)
        if (!chosen[i]) {
            int u = tb[i].from, v = tb[i].to;
            if (dis[0][u] > dis[0][v]) swap(u, v);
            xg(1, ats[u], att[v] - 1, dis[0][u] + dis[1][v] + tb[i].cost);
        }
    int ans = 0, cnt = 0;
    for (int i = 1; i < att[n]; i++)
        ans = max(ans, cx(1, i));
    for (int i = 1; i < att[n]; i++)
        if (ans == cx(1, i))
            ++cnt;
    printf("%d %d", ans, (ans == dis[0][n]) ? m : cnt);
}
void adn(int from, int to, int cost) {
    tb[++cntb].next = g[from];
    tb[cntb].from = from, tb[cntb].to = to, tb[cntb].cost = cost;
    g[from] = cntb;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, srx, sry, src; i <= m; i++)
        scanf("%d%d%d", &srx, &sry, &src), adn(srx, sry, src), adn(sry, srx, src);
    dijk(1, dis[0], pre[0]), dijk(n, dis[1], pre[1]);
    init();
    solve();
    return 0;
}

[Poi2012]Warehouse Store

我一开始想二分最大能连续选的商品价值 后来发现剩下的没法处理

考虑有一道类似的题...就是删除之前选过的东西

所以...这题我们发现可以...遇到一个不能选的点 看看他的前面能否去掉一个b[x]更大的x, 然后让这个点加入

一定要记得什么类型就用什么输出 我被输出锤自闭了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**************************************************************
    Problem: 2802
    User: Cansult
    Language: C++
    Result: Accepted
    Time:1144 ms
    Memory:6840 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define LL long long
#define MAXN (250000 + 5)
#define pii pair<int, int>
using namespace std;
struct cmp {
    bool operator () (const pii x, const pii y) {
        return x < y;
    }
};
int n, a[MAXN], b[MAXN];
vector<int> outp;
priority_queue<pii, vector<pii> > q;
main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    LL dq = 0;
    for (int i = 1; i <= n; i++) {
        dq += a[i];
        if (dq >= b[i]) q.push(make_pair(b[i], i)), dq -= b[i];
        else if (!q.empty() && q.top().first > b[i]) {
                dq += q.top().first - b[i];
                q.pop();
                q.push(make_pair(b[i], i));
        }
    }
    printf("%d\n", q.size()); // 这个地方用lld输出就会出问题
    while (!q.empty()) outp.push_back(q.top().second), q.pop();
    sort(outp.begin(), outp.end());
    for (int i = 0; i < outp.size(); i++)
        printf("%d ", outp[i]);
    return 0;
}

[POI2018]Prawnicy

我们可以枚举答案区间的左端点

然后让左端点在答案区间左边的区间中 右端点尽量靠右就完事了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**************************************************************
    Problem: 2802
    User: Cansult
    Language: C++
    Result: Accepted
    Time:1144 ms
    Memory:6840 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define LL long long
#define MAXN (250000 + 5)
#define pii pair<int, int>
using namespace std;
struct cmp {
    bool operator () (const pii x, const pii y) {
        return x < y;
    }
};
int n, a[MAXN], b[MAXN];
vector<int> outp;
priority_queue<pii, vector<pii> > q;
main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    LL dq = 0;
    for (int i = 1; i <= n; i++) {
        dq += a[i];
        if (dq >= b[i]) q.push(make_pair(b[i], i)), dq -= b[i];
        else if (!q.empty() && q.top().first > b[i]) {
                dq += q.top().first - b[i];
                q.pop();
                q.push(make_pair(b[i], i));
        }
    }
    printf("%d\n", q.size());
    while (!q.empty()) outp.push_back(q.top().second), q.pop();
    sort(outp.begin(), outp.end());
    for (int i = 0; i < outp.size(); i++)
        printf("%d ", outp[i]);
    return 0;
}

[Noi2002]Savage

首先你要知道 这题数据水的和鳖一样\(\mathrm O(m n^2\lg \mathrm {maxint})\)可过

然后我们可以列式子: 他们如果遇见了 是在什么时候 然后解出来时间之后再和他们的寿命比较一下

然后我发现我似乎之前exGCD都写假了 最小整数解要\(\mod \frac{b}{gcd}\)很真实

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**************************************************************
    Problem: 1407
    User: Cansult
    Language: C++
    Result: Accepted
    Time:1280 ms
    Memory:1288 kb
****************************************************************/
 
// c[i] + p[i] * x % m == c[j] + p[j] * x % m
// (p[i] - p[j]) * x == c[j] - c[i] && x <= hp
 
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN (15 + 5)
using namespace std;
void exgcd(int a, int b, int& x, int& y) { // ax + by == gcd
    if (!b) {
        x = 1, y = 0;
        return ;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
    return ;
}
int gcd(int x, int y) { return (!y) ? x : gcd(y, x % y); }
bool solve(int a, int b, int m, int hp) { // ax == b (mod m) => ax + my == b
    a = (a % m + m) % m, b = (b % m + m) % m; // 注意处理负数
    int qaq = gcd(a, m), x, y;
    if (b % qaq) return true;
    exgcd(a, m, x, y);
    x *= b / qaq;
    x %= (m / qaq);
    if (x < 0) x += m / qaq;
    return hp < x;
}
int n, c[MAXN], p[MAXN], l[MAXN];
bool solve(int m) {
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if (!solve(p[i] - p[j], c[j] - c[i], m, min(l[i], l[j])))
                return false;
    return true;
}
int main() {
    scanf("%d", &n);
    int minans = n;
    for (int i = 1; i <= n; i++) 
        scanf("%d%d%d", &c[i], &p[i], &l[i]), minans = max(minans, c[i]);
    for (int i = minans; i <= 1000000; i++)
        if (solve(i)) {
            printf("%d", i);
            return 0;
        }
    return 0;
}

DZY Loves Chinese II

这题很有意思

建出dfs树, 对于所有的非树边 随机一个权值, 然后将这个非树边在树上的一段区间全部异或上这个权值, 最后得出树边的权值, 这样 对于一次询问 我们只需要判断出这些边是否能异或出0(树边和覆盖ta的非树边都被删掉了)

一开始我想写32棵标记永久化的线段树 然后对每次询问的非树边区间修改 树边单点查询

后来发现直接对这些边建线性基就能看出来是否能异或出0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/**************************************************************
    Problem: 3569
    User: Cansult
    Language: C++
    Result: Accepted
    Time:3368 ms
    Memory:30736 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define pii pair<int, int>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define MAXL (32 + 5)
#define MAXK (15 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (LS(dq) | 1)
using namespace std;
struct edg {
    int from, to, next, bh;
} tb[MAXN], eb[MAXM << 1];
struct tnode {
    int fa, deep, top, hs, size;
} ta[MAXN];
int n, m, q, tg[MAXN], eg[MAXN], cntt, cnte, cost[MAXM], lazy[MAXN], b[MAXL], dqk[MAXK];
bool ist[MAXM], vis[MAXN];
pii pb[MAXM];
void adn(edg* bx, int* gx, int& cntx, int from, int to, int bh) {
    bx[++cntx].next = gx[from];
    bx[cntx].from = from, bx[cntx].to = to, bx[cntx].bh = bh;
    gx[from] = cntx;
}
void init(int dq) {
    ta[dq].size = 1;
    vis[dq] = true;
    for (int i = eg[dq]; i; i = eb[i].next)
        if (!vis[eb[i].to]) {
            ta[eb[i].to].deep = ta[dq].deep + 1;
            ta[eb[i].to].fa = dq;
            adn(tb, tg, cntt, dq, eb[i].to, eb[i].bh);
            ist[eb[i].bh] = true;
            init(eb[i].to);
            ta[dq].size += ta[eb[i].to].size;
            if (ta[eb[i].to].size > ta[ta[dq].hs].size) ta[dq].hs = eb[i].to;
        }
}
void dfs(int dq) {
    if (ta[dq].hs) ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs);
    for (int i = tg[dq]; i; i = tb[i].next)
        if (tb[i].to != ta[dq].hs && tb[i].to != ta[dq].fa)
            ta[tb[i].to].top = tb[i].to, dfs(tb[i].to);
}
int lca(int x, int y) {
    while (ta[x].top != ta[y].top) {
        if (ta[ta[x].top].deep < ta[ta[y].top].deep) swap(x, y);
        x = ta[ta[x].top].fa;
    }
    if (ta[x].deep > ta[y].deep) swap(x, y);
    return x;
}
void xg(int dq) {
    for (int i = tg[dq]; i; i = tb[i].next) {
        xg(tb[i].to);
        lazy[dq] ^= (cost[tb[i].bh] = lazy[tb[i].to]);
    }
}
bool ins(int x) {
    for (int i = MAXL - 1; i >= 0; i--)
        if ((1ll << i) & x) {
            if (b[i]) x ^= b[i];
            else {
                b[i] = x;
                return true;
            }
        }
    return false;
}
int main() {
    srand(20020522);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &pb[i].first, &pb[i].second), adn(eb, eg, cnte, pb[i].first, pb[i].second, i), adn(eb, eg, cnte, pb[i].second, pb[i].first, i);
    ta[1].fa = ta[1].top = 1;
    init(1), dfs(1);
    for (int i = 1; i <= m; i++)
        if (!ist[i]) {
            cost[i] = rand();
            int lcaxy = lca(pb[i].first, pb[i].second);
            lazy[pb[i].first] ^= cost[i], lazy[pb[i].second] ^= cost[i];
            if (lcaxy != pb[i].first && lcaxy != pb[i].second) lazy[lcaxy] ^= cost[i];
        }
    xg(1);
    scanf("%d", &q);
    for (int i = 1, sumans = 0; i <= q; i++) {
        scanf("%d", &dqk[0]);
        for (int j = 1; j <= dqk[0]; j++)
            scanf("%d", &dqk[j]);
        memset(b, 0, sizeof(b));
        bool ok = true;
        for (int j = 1, srx; j <= dqk[0]; j++) {
            srx = dqk[j], srx ^= sumans;
            if (!ins(cost[srx])) {
                puts("Disconnected");
                ok = false;
                break;
            }
        }
        if (ok)
            puts("Connected"), ++sumans;
    }
    return 0;
}

[cqoi2013]新Nim游戏

首先我们知道 对于普通Nim游戏 所有的石子数量异或起来如果是0就先手必败

也就是说我们要让第二个人拿完几堆之后 异或和不为0

考虑线性基插入的时候 不能插入的数 就是异或和为0的子集的"关键元素"(没了他就异或不出0来)

所以我们只需要把这些不能插入线性基的数删掉就好了

因为答案要求尽量小 所以我们把数从小到大插入即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**************************************************************
    Problem: 3105
    User: Cansult
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:1292 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100 + 5)
#define MAXL (32 + 5)
#define LL long long
using namespace std;
LL ans = 0;
int a[MAXN], n, b[MAXL];
void ins(int x) {
    int dans = x;
    for (int i = MAXL - 1; i >= 0; i--)
        if ((1ll << i) & x) {
            if (b[i]) x ^= b[i];
            else {
                b[i] = x;
                return ;
            }
        }
    ans += dans;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for (int i = n; i >= 1; i--)
        ins(a[i]);
    printf("%lld", ans);
    return 0;
}

4269: 再见Xor

放在这里记录一个结论 线性基能异或出的次大值就是不异或最后一个基底的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**************************************************************
    Problem: 4269
    User: Cansult
    Language: C++
    Result: Accepted
    Time:252 ms
    Memory:1288 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXL (35)
using namespace std;
int b[MAXL], n;
void ins(int x) {
    for (int i = MAXL - 1; i >= 0; i--)
        if (x & (1ll << i)) {
            if (b[i]) x ^= b[i];
            else {
                b[i] = x;
                return ;
            }
        }
}
int main() {
    scanf("%d", &n);
    for (int i = 1, srx; i <= n; i++)
        scanf("%d", &srx), ins(srx);
    int ans = 0;
    for (int i = MAXL - 1; i >= 0; i--)
        ans = max(ans, ans ^ b[i]);
    printf("%d ", ans);
    for (int i = 0; i < MAXL; i++)
        if (b[i]) {
            ans ^= b[i];
            break;
        }
    printf("%d", ans);
    return 0;
}

[Poi2003]Sums

这题很有意思

先说结论: 把\(\{a\}\)从小到大排序 对于\(x \in [0, a_1 - 1]\)中的每一个\(x\)计算出[最小的模\(a_1\)后等于\(x\)的数\(dis_x\)], 然后对于每一个询问\(b_i\), 如果\(dis_{b_i \% a_1} > b_i\)就是NIE, 否则就是TAK

首先 一个很显然的结论就是 如果\(b_x\)能被凑出来 那么\(b_x + na_y\)也可以被凑出来

所以如果\(b\%a_1\)能凑出来 \(b\)就也一定能凑出来

那么为什么\(b \% a_1\)大于\(b\)就凑不出来呢? 废话这个都大于\(b\)了还怎么往上面加数

那么为什么只用试一个\(a_1\)呢? 基本和上面的理由一样 因为其他的\(a\)无非就是看上去多了几个\(dis\), 然而这些\(dis\)在刚才的做法里也是有的(算到\(\mod a_1\)之后的下标上了), 所以根据上面的那一条 较小的\(a_1\)都凑不出来 其他的\(a\)就也一定凑不出来

据说存边会炸空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**************************************************************
    Problem: 2612
    User: Cansult
    Language: C++
    Result: Accepted
    Time:384 ms
    Memory:2068 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (50000 + 5)
#define INF (0x7ffffffffffffll)
#define LL long long
#define pii pair<int, LL>
using namespace std;
struct cmp {
    bool operator () (const pii x, const pii y) {
        return x.second > y.second;
    }
};
int n, a[MAXN];
LL dis[MAXN];
void dijk() {
    bool vis[MAXN];
    memset(vis, false, sizeof(vis));
    memset(dis, 0x7f, sizeof(dis));
    priority_queue<pii, vector<pii>, cmp> q;
    q.push(make_pair(0, dis[0] = 0));
    while (!q.empty()) {
        int dq = q.top().first;
        q.pop();
        if (vis[dq]) continue;
        vis[dq] = true;
        for (int i = 1; i <= n; i++) 
            if (dis[dq] + a[i] < dis[(dq + a[i]) % a[1]])
                q.push(make_pair((dq + a[i]) % a[1], dis[(dq + a[i]) % a[1]] = dis[dq] + a[i]));
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    dijk();
    int q;
    scanf("%d", &q);
    for (int i = 1, srx; i <= q; i++)
        scanf("%d", &srx), puts(dis[srx % a[1]] <= srx ? "TAK" : "NIE");
    return 0;
}

[HNOI2012]矿场搭建

我怎么老是记得我好像写过这题... = =

这题我已经不想说啥了... 先是Tarjan求割点写了个假板子...然后统计有几个联通块连着几个割点的时候又自闭了

后来直接大力set<int> []终于过了...哦对了我中间还忘清数组了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**************************************************************
    Problem: 2730
    User: Cansult
    Language: C++
    Result: Accepted
    Time:44 ms
    Memory:1632 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#define MAXN (5000 + 5)
#define LL long long
using namespace std;
struct edg {
    int from, to, next;
} b[MAXN << 1];
int g[MAXN], cntb, n, m, dfn[MAXN], low[MAXN], cntdfn, size[MAXN], fa[MAXN];
bool isc[MAXN];
set<int> fuck[MAXN];
vector<int> cpoint;
LL ans1, ans2;
void adn(int from, int to) {
    b[++cntb].next = g[from];
    b[cntb].from = from, b[cntb].to = to;
    g[from] = cntb;
}
void tarjan(int dq, bool isroot) {
    low[dq] = dfn[dq] = ++cntdfn;
    int cntc = 0;
    bool ok = false;
    for (int i = g[dq]; i; i = b[i].next)
        if (b[i].to != fa[dq]) {
            if (dfn[b[i].to]) low[dq] = min(low[dq], dfn[b[i].to]);
            else fa[b[i].to] = dq, ++cntc, tarjan(b[i].to, false), low[dq] = min(low[dq], low[b[i].to]), ok |= (low[b[i].to] >= dfn[dq] && !isroot);
        }
    if ((isroot && cntc > 1) || ok)
        isc[dq] = true, cpoint.push_back(dq);
}
void dfs(int dq) {
    size[dq] = 1;
    for (int i = g[dq]; i; i = b[i].next)
        if (!size[b[i].to] && !isc[b[i].to]) {
            dfs(b[i].to);
            size[dq] += size[b[i].to];
            fuck[dq].insert(fuck[b[i].to].begin(), fuck[b[i].to].end());
        }
        else if (isc[b[i].to])
            fuck[dq].insert(b[i].to);
 
}
void solve(int casei) {
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            fa[i] = i, tarjan(i, true);
    if (!cpoint.size()) {
        printf("Case %d: 2 %d\n" ,casei, n * (n - 1) / 2);
        return ;
    }
    for (int i = 1; i <= n; i++)
        if (!size[i] && !isc[i]) {
            dfs(i);
            if (fuck[i].size() == 1)
                ++ans1, ans2 *= size[i];
        }
    printf("Case %d: %lld %lld\n", casei, ans1, ans2);
}
int main() {
    int cntc = 0;
    while (true) {
        memset(isc, false, sizeof(isc));
        memset(g, 0, sizeof(g));
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(size, 0, sizeof(size));
        memset(fa, 0, sizeof(fa));
        cpoint.clear();
        cntb = n = m = cntdfn = 0;
        ans1 = 0, ans2 = 1;
        scanf("%d", &m);
        if (!m) break;
        for (int i = 1, srx, sry; i <= m; i++)
            scanf("%d%d", &srx, &sry), adn(srx, sry), adn(sry, srx), n = max(n, max(srx, sry));
        for (int i = 1; i <= n; i++) fuck[i].clear();
        solve(++cntc);
    }
    return 0;
}

PA2010 Riddle

Emmmmm...显然是个2SAT 然后我们发现这个玩意处理同一个郡内的关系的时候边数爆炸了

联想一下这题的标签 我们发现这个东西就是对于每一个点都要找一个点 连向这个郡内出了当前的点的所有点的反点

我们又发现 刨去这个点\(city_x\)后, 郡被分成了两个区间 \([1, city_x - 1] \cup [city_x + 1, city_0]\)

我们又发现 这个东西是个前缀和的样子 于是 我们就对每个点 新建一个点连向两边的前缀/后缀区间所代表的点即可

本机会爆栈... = = b站上28s卡过去的...很真实

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**************************************************************
    Problem: 3495
    User: Cansult
    Language: C++
    Result: Accepted
    Time:28460 ms
    Memory:346760 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#define MAXN (10000000 + 5)
#define bh(i) (1000000 + (i))
#define jbh(i) (2000000 + (i))
using namespace std;
struct edg {
    int from, to, next;
} b[MAXN];
int g[MAXN], n, m, k, cntb, belong[MAXN], low[MAXN], dfn[MAXN], cntdfn, city[MAXN];
bool ins[MAXN];
stack<int> gary;
void adn(int from, int to) {
    b[++cntb].next = g[from];
    b[cntb].from = from, b[cntb].to = to;
    g[from] = cntb;
}
void tarjan(int dq) {
    low[dq] = dfn[dq] = ++cntdfn;
    belong[dq] = dq;
    gary.push(dq);
    ins[dq] = true;
    for (int i = g[dq]; i; i = b[i].next)
        if (!dfn[b[i].to]) tarjan(b[i].to), low[dq] = min(low[dq], low[b[i].to]); 
        else if (ins[b[i].to]) low[dq] = min(low[dq], dfn[b[i].to]);
    if (low[dq] == dfn[dq]) {
        while (!gary.empty() && gary.top() != dq) ins[gary.top()] = false, belong[gary.top()] = dq, gary.pop();
        if (!gary.empty())
            gary.pop();
        ins[dq] = false;
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, srx, sry; i <= m; i++)
        scanf("%d%d", &srx, &sry), adn(bh(srx), sry), adn(bh(sry), srx);
    for (int i = 1, cntc = 0; i <= k; i++) {
        scanf("%d", &city[0]);
        for (int j = 1; j <= city[0]; j++) scanf("%d", &city[j]);
        adn(jbh(++cntc), bh(city[1]));
        for (int j = 2; j <= city[0]; j++) adn(jbh(++cntc), bh(city[j])), adn(jbh(cntc), jbh(cntc - 1)), adn(city[j], jbh(cntc - 1));
        adn(jbh(++cntc), bh(city[city[0]]));
        for (int j = city[0] - 1; j >= 1; j--) adn(jbh(++cntc), bh(city[j])), adn(jbh(cntc), jbh(cntc - 1)), adn(city[j], jbh(cntc - 1));
    }
    for (int i = 1; i < MAXN; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i++)
        if (belong[i] == belong[bh(i)]) {
            puts("NIE");
            return 0;
        }
    puts("TAK");
    return 0;
}

[TJOI2018]xor

树链剖分套可持久化trie

一开始想第一问启发式合并然后第二问在树上建可持久化trie

然后没过一会就真香了... = =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**************************************************************
    Problem: 5338
    User: Cansult
    Language: C++
    Result: Accepted
    Time:4584 ms
    Memory:94188 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define int LL
#define MAXN (100000 + 5)
#define MAXL (30 + 1)
#define LS(dq) ((dq) << 1)
#define RS(dq) (LS(dq) | 1)
using namespace std;
struct node {
    int ch[2], zh;
} b[MAXN << 5];
struct edg {
    int from, to, next;
} tb[MAXN << 1];
struct tnode {
    int begin, end, top, fa, size, hs, deep;
} ta[MAXN];
int tg[MAXN], cntt, cntb, n, root[MAXN], cnta, a[MAXN], zh[MAXN];
void adn(int from, int to) {
    tb[++cntt].next = tg[from];
    tb[cntt].from = from, tb[cntt].to = to;
    tg[from] = cntt;
}
void init(int dq) {
    ta[dq].size = 1;
    ta[dq].deep = ta[ta[dq].fa].deep + 1;
    for (int i = tg[dq]; i; i = tb[i].next)
        if (tb[i].to != ta[dq].fa)
            ta[tb[i].to].fa = dq, init(tb[i].to), ta[dq].size += ta[tb[i].to].size, ta[dq].hs = (ta[ta[dq].hs].size > ta[tb[i].to].size) ? ta[dq].hs : tb[i].to;
}
void dfs(int dq) {
    a[ta[dq].begin = ++cnta] = dq;
    if (ta[dq].hs) ta[ta[dq].hs].top = ta[dq].top, dfs(ta[dq].hs);
    for (int i = tg[dq]; i; i = tb[i].next)
        if (tb[i].to != ta[dq].fa && tb[i].to != ta[dq].hs)
            ta[tb[i].to].top = tb[i].to, dfs(tb[i].to);
    ta[dq].end = cnta;
}
int newnode() { return ++cntb; }
void ins(int pre, int dq, int x) {
    for (int i = 30; i >= 0; i--) {
        bool isright = (x & (1ll << i)) != 0;
        b[dq].ch[isright] = newnode();
        b[b[dq].ch[isright]].zh = b[b[pre].ch[isright]].zh + 1;
        b[dq].ch[!isright] = b[pre].ch[!isright];
        dq = b[dq].ch[isright], pre = b[pre].ch[isright];
    }
}
int cx(int pre, int dq, int x) {
    int re = 0;
    for (int i = 30; i >= 0; i--) {
        bool isright = (x & (1ll << i)) == 0;
        if (b[b[dq].ch[isright]].zh - b[b[pre].ch[isright]].zh) re |= (1ll << i), dq = b[dq].ch[isright], pre = b[pre].ch[isright];
        else dq = b[dq].ch[!isright], pre = b[pre].ch[!isright];
    }
    return re;
}
int solve(int x, int y) { return cx(root[ta[x].begin - 1], root[ta[x].end], y); }
int solve(int x, int y, int z) {
    int re = 0;
    while (ta[x].top != ta[y].top) {
        if (ta[ta[x].top].deep < ta[ta[y].top].deep) swap(x, y);
        re = max(re, cx(root[ta[ta[x].top].begin - 1], root[ta[x].begin], z));
        x = ta[ta[x].top].fa;
    }
    if (ta[x].deep > ta[y].deep) swap(x, y);
    re = max(re, cx(root[ta[x].begin - 1], root[ta[y].begin], z));
    return re;
}
main() {
    int q;
    scanf("%lld%lld", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &zh[i]);
    for (int i = 1, srx, sry; i < n; i++) scanf("%lld%lld", &srx, &sry), adn(srx, sry), adn(sry, srx);
    ta[1].fa = ta[1].top = 1;
    init(1), dfs(1);
    for (int i = 1; i <= n; i++) ins(root[i - 1], root[i] = newnode(), zh[a[i]]);
    for (int i = 1, sre, srx, sry, srz; i <= q; i++) {
        scanf("%lld", &sre);
        if (sre == 1) scanf("%lld%lld", &srx, &sry), printf("%lld\n", solve(srx, sry));
        else scanf("%lld%lld%lld", &srx, &sry, &srz), printf("%lld\n", solve(srx, sry, srz));
    }
    return 0;
}

[HNOI2015]菜肴制作

这题挺有意思...一开始以为是直接正着拓扑排序 把队列换成堆就行了

后来发现题目要求的是"编号小的尽量靠前" 而不是 "字典序最小"

这两个玩意是有区别的:

字典序最小是要让第一位尽量小 然后再让第二位尽量小...

编号小的靠前是宁愿让第一位大一些 也要把编号小的挪到前面去

搞清楚这两个的区别就很好理(意)解(会)为什么要建反图了(因为编号大的数为了凑字典序都跑到后面取了) (估计这题在当时会坑不少人?)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**************************************************************
    Problem: 4010
    User: Cansult
    Language: C++
    Result: Accepted
    Time:1060 ms
    Memory:4276 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (100000 + 5)
using namespace std;
struct edg {
    int from, to, next;
} b[MAXN];
struct cmp {
    bool operator () (const int x, const int y) { return x < y; }
};
int g[MAXN], cntb, n, m, du[MAXN];
vector<int> outp;
void adn(int from, int to) {
    b[++cntb].next = g[from];
    b[cntb].from = from, b[cntb].to = to;
    g[from] = cntb;
}
void solve() {
    priority_queue<int, vector<int>, cmp> q;
    for (int i = 1; i <= n; i++) if (!du[i]) q.push(i);
    while (!q.empty()) {
        int dq = q.top();
        q.pop();
        outp.push_back(dq);
        for (int i = g[dq]; i; i = b[i].next) {
            --du[b[i].to];
            if (!du[b[i].to])
                q.push(b[i].to);
        }
    }
    if (outp.size() != n) puts("Impossible!");
    else {
        for (int i = n - 1; i >= 0; i--) printf("%d ", outp[i]);
        puts("");
    }
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        memset(du, 0, sizeof(du));
        memset(g, 0, sizeof(g));
        cntb = 0;
        outp.clear();
        for (int i = 1, srx, sry; i <= m; i++)
            scanf("%d%d", &srx, &sry), adn(sry, srx), ++du[srx];
        solve();
    }
    return 0;
}

树上三角形

这题也挺有意思的 当时我熬夜肝For Honor所以上课昏昏沉沉的 然后就听学长说 "你倒过来想一下 这个路径不能构成三角形是什么情况"

我一想 不能构成三角形最少不就是个斐波那契数列吗 这个说爆int很快啊

于是我们发现斐波那契数列到第\(50\)项左右就爆int了...

所以我们对于点数大于\(50\)的路径直接输出Y就行

当然节点数小于\(50\)的就可以直接暴力算了...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**************************************************************
    Problem: 3251
    User: Cansult
    Language: C++
    Result: Accepted
    Time:1004 ms
    Memory:50956 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (100000 + 5)
#define MAXL (50 + 5)
#define LL long long
#define int LL 
using namespace std;
struct edg {
    int from, to, next;
} b[MAXN];
int g[MAXN], cntb, n, deep[MAXN], zh[MAXN], d[MAXN][MAXL];
void adn(int from, int to) {
    b[++cntb].next = g[from];
    b[cntb].from = from, b[cntb].to = to;
    g[from] = cntb;
}
void dfs(int dq) {
    deep[dq] = deep[d[dq][0]] + 1;
    for (int i = 1; i < MAXL; i++) d[dq][i] = d[d[dq][i - 1]][i - 1];
    for (int i = g[dq]; i; i = b[i].next) dfs(b[i].to);
}
int lca(int x, int y) {
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = MAXL - 1; i >= 0; i--)
        if (deep[d[x][i]] >= deep[y])
            x = d[x][i];
    if (x == y) return x;
    for (int i = MAXL - 1; i >= 0; i--)
        if (d[x][i] != d[y][i])
            x = d[x][i], y = d[y][i];
    return d[x][0];
}
main() {
    int q;
    scanf("%lld%lld", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &zh[i]);
    for (int i = 1, srx, sry; i < n; i++) scanf("%lld%lld", &srx, &sry), adn(srx, sry), d[sry][0] = srx;
    d[1][0] = 1;
    dfs(1);
    for (int i = 1, sre, srx, sry; i <= q; i++) {
        scanf("%lld%lld%lld", &sre, &srx, &sry);
        if (sre) zh[srx] = sry;
        else {
            int lcaxy = lca(srx, sry);
            if (deep[sry] + deep[srx] - 2 * deep[lcaxy] > MAXL) puts("Y");
            else {
                vector<int> dq;
                while (srx != lcaxy) dq.push_back(zh[srx]), srx = d[srx][0];
                while (sry != lcaxy) dq.push_back(zh[sry]), sry = d[sry][0];
                dq.push_back(zh[lcaxy]);
                sort(dq.begin(), dq.end());
                if (dq.size() < 3) puts("N");
                else {
                    bool ok = false;
                    for (int i = 2; i < dq.size(); i++) 
                        if (dq[i] < dq[i - 1] + dq[i - 2]) {
                            ok = true;
                            puts("Y");
                            break;
                        }
                    if (!ok) puts("N");
                }
            }
        }
    }
    return 0;
}

By 准备退役旅游的 Cansult