水题笔记_ ZJOI + HNOI刷水计划

还有一周了…开始刷水…

刷水题 上day榜

23333好不容易到个第一页求不D

我太菜了

AuFun: 原来Day榜还有人看啊 我一不小心就rank1了(Orzzzzzzzz)

1003: [ZJOI2006] 物流运输

扯淡的 题解

看了题解

最近状态太差了 太差了 太差了 智商一天比一天低了是smg啊

见鬼…

想着记录每一天的最短路 然后发现推不出式子 因为不知道是否能够转移

然后居然没有想到记录一段时间的最短路

我怎么这么菜啊 完了这个状态去R1肯定一轮退役啊…

$f[i] = \min(dis[1][i][n], f[j] + dis[j +1][i][n] \cdot (i - j) + k)\,\,\, (j \in [0, i - 1])$

沙茶的 代码

注: 因为一些奇奇怪怪的原因在某谷开氧气优化会挂掉

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
/**************************************************************
Problem: 1003
User: Cansult
Language: C++
Result: Accepted
Time:80 ms
Memory:2372 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN (20 + 5)
#define MAXD (100 + 5)
#define INF (0x7ffffff)
#define pii pair<int, int>
using namespace std;
int g[MAXN][MAXN], n, m, d, k, f[MAXN], dis[MAXD][MAXD][MAXN];
vector<int> ct[MAXD];
void dijk(int del, int from, int to)
{
int *x = dis[from][to];
bool v[MAXN];
memset(dis[from][to], 0x7f, sizeof(dis[from][to]));
memset(v, false, sizeof(v));
x[1] = 0;
for (int i = 1; i <= n; i++)
{
int kc = 0, maxf = INF;
for (int j = 1; j <= n; j++)
if (x[j] < INF && !v[j] && x[j] < maxf && !(del & (1 << j)))
maxf = x[j], kc = j;
if (!kc) break;
v[kc] = true;
for (int j = 1; j <= n; j++)
if (g[kc][j] < INF && x[j] > x[kc] + g[kc][j] && !v[j] && !(del & (1 << j)))
x[j] = x[kc] + g[kc][j];
}
}
void init()
{
for (int i = 1; i <= d; i++)
{
int del = 0;
for (int j = i; j <= d; j++)
{
for (int kc = 0; kc < ct[j].size(); kc++)
del |= (1 << ct[j][kc]);
dijk(del, i, j);
}
}
}
void dp()
{
for (int i = 1; i <= d; i++)
{
if (dis[1][i][n] < INF)
f[i] = dis[1][i][n] * i;
else
f[i] = INF;
for (int j = 1; j < i; j++)
if (dis[j + 1][i][n] < INF && f[j] < INF)
f[i] = min(f[i], f[j] + dis[j + 1][i][n] * (i - j) + k);
}
}
int main()
{
memset(g, 0x7f, sizeof(g));
scanf("%d%d%d%d", &d, &n, &k, &m);
for (int i = 1; i <= m; i++)
{
int srx, sry, srz;
scanf("%d%d%d", &srx, &sry, &srz);
g[sry][srx] = g[srx][sry] = srz;
}
int dn;
scanf("%d", &dn);
for (int i = 1; i <= dn; i++)
{
int srx, sry, srz;
scanf("%d%d%d", &srz, &srx, &sry);
for (int j = srx; j <= sry; j++)
ct[j].push_back(srz);
}
init();
dp();
printf("%d", f[d]);
return 0;
}

1036: [ZJOI2008]树的统计

扯淡的 题解

链剖, 注意节点值可能为负

沙茶的 代码

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
/**************************************************************
Problem: 1036
User: Cansult
Language: C++
Result: Accepted
Time:2888 ms
Memory:57000 kb
****************************************************************/

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (300000 + 5)
#define INF (5000000)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
const int root = 1;
using namespace std;
struct edg
{
int from, to, next;
}tb[MAXN];
int tg[MAXN << 1], cntt;
struct tnode
{
int deep, top, hs, size, zh, start, end, fa;
}ta[MAXN];
struct node
{
int zh, maxz, le, ri;
}b[MAXN << 3];
int a[MAXN], cnta;
node push_up(node ls, node rs)
{
node re;
re.le = ls.le, re.ri = rs.ri;
re.maxz = max(ls.maxz, rs.maxz);
re.zh = ls.zh + rs.zh;
return re;
}
void js(int dq, int le, int ri)
{
if (le == ri)
{
b[dq].le = le, b[dq].ri = ri;
b[dq].zh = b[dq].maxz = a[le];
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 xg(int dq, int wz, int zh)
{
if (b[dq].le == b[dq].ri)
{
b[dq].maxz = b[dq].zh = zh;
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz <= mi)
xg(LS(dq), wz, zh);
else if (wz > mi)
xg(RS(dq), wz, 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 (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));
}
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, int deep)
{
ta[dq].deep = deep;
ta[dq].size = 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, deep + 1);
ta[dq].size += ta[tb[i].to].size;
if (ta[tb[i].to].size > ta[ta[dq].hs].size)
ta[dq].hs = tb[i].to;
}
}
}
void dfs(int dq)
{
ta[dq].start = ++cnta;
a[cnta] = ta[dq].zh;
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;
}
node solve(int x, int y)
{
node re;
re.maxz = -INF;
re.zh = re.le = re.ri = 0;
while (ta[x].top != ta[y].top)
{
if (ta[ta[x].top].deep < ta[ta[y].top].deep)
swap(x, y);
re = push_up(re, cx(1, ta[ta[x].top].start, ta[x].start));
x = ta[ta[x].top].fa;
}
if (ta[x].deep > ta[y].deep)
swap(x, y);
re = push_up(re, cx(1, ta[x].start, ta[y].start));
return re;
}
int main()
{
b[0].maxz = -INF;
b[0].zh = 0;
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
int srx, sry;
scanf("%d%d", &srx, &sry);
adn(srx, sry);
adn(sry, srx);
}
for (int i = 1; i <= n; i++)
scanf("%d", &ta[i].zh);
ta[root].fa = ta[root].top = 1;
init(root, 1);
dfs(root);
js(1, 1, n);
int q;
scanf("%d", &q);
for (int i = 1; i <= q; i++)
{
char sre[20];
int srx, sry;
scanf("%s%d%d", sre, &srx, &sry);
if (sre[0] == 'C')
xg(1, ta[srx].start, sry);
else
printf("%d\n", (sre[1] == 'M' ? solve(srx, sry).maxz : solve(srx, sry).zh));
}
return 0;
}

/*
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
*/

1191: [HNOI2006]超级英雄Hero

扯淡的 题解

枚举能做几道题, 然后连边跑二分图, 看是否满流即可

扯淡的 题解

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
/**************************************************************
Problem: 1191
User: Cansult
Language: C++
Result: Accepted
Time:264 ms
Memory:41152 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define INF (0x7ffffff)
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define MAXQ (2000)
#define pii pair<int, int>
#define bh(a) ((a) + MAXQ)
#define rev(a) ((((a) - 1) ^ 1) + 1)
using namespace std;
const int s = 0, t = MAXN - 1;
pii a[MAXQ];
struct edg
{
int from, to, next, cap, flow;
edg() {}
edg(int fr, int dqt, int ne, int ca): from(fr), to(dqt), next(ne), cap(ca), flow(0) {}
} b[MAXM << 2];
int g[MAXN], cntb, n, m, dis[MAXN];
int dinic(int dq, int maxf)
{
if (dq == t || !maxf)
return maxf;
int re = 0;
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
{
int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
b[i].flow += zl;
b[rev(i)].flow -= zl;
maxf -= zl;
re += zl;
}
}
return re;
}
int bfs()
{
queue<int> q;
q.push(s);
memset(dis, 0, sizeof(dis));
dis[s] = 1;
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
if (b[i].cap > b[i].flow && !dis[b[i].to])
dis[b[i].to] = dis[dq] + 1, q.push(b[i].to);
}
return dis[t];
}
void adn(int from, int to, int cap)
{
b[++cntb] = edg(from, to, g[from], cap);
g[from] = cntb;
}
void solve()
{
int ans = 0;
for (int i = 1; i <= m; i++)
{
adn(a[i].first, bh(i), 1);
adn(bh(i), a[i].first, 0);
adn(a[i].second, bh(i), 1);
adn(bh(i), a[i].second, 0);
adn(bh(i), t, 1);
adn(t, bh(i), 0);
while (bfs())
ans += dinic(s, INF);
if (ans != i)
{
printf("%d", i - 1);
return ;
}
}
printf("%d", m);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
adn(s, i, 1), adn(i, s, 0);
for (int i = 1; i <= m; i++)
{
int srx, sry;
scanf("%d%d", &srx, &sry);
++srx, ++sry;
a[i].first = srx, a[i].second = sry;
}
solve();
return 0;
}

/*
5 6
3 2
2 0
0 3
0 4
3 2
3 2
*/

1588: [HNOI2002]营业额统计

扯淡的 题解

早上起来写sb数据结构醒脑

直接上spaly splay, 资瓷插入和查询前驱后继即可
注意函数返回的是节点的编号还是节点的值, 以及注意rotate函数有没有把左右儿子搞反

沙茶的 代码

似乎跑的挺快?

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
/**************************************************************
Problem: 1588
User: Cansult
Language: C++
Result: Accepted
Time:212 ms
Memory:2572 kb
****************************************************************/

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAXN (32767 + 5)
#define null (0)
#define INF (0X7FFFFFFF)
using namespace std;
struct node
{
int ch[2], zh, fa, cnt;
}b[MAXN << 1];
int cnt, root = null;
inline int mabs(const int x)
{ return (x > 0 ? x : (-x)); }
bool isLeft(int x)
{ return (x == b[b[x].fa].ch[1]); }
void qinDing(int fa, int son, bool ls)
{
b[fa].ch[ls] = son;
b[son].fa = fa;
}
void rotate(int dq)
{
int fa = b[dq].fa, gr = b[fa].fa;
bool ls = isLeft(dq);
qinDing(gr, dq, isLeft(fa));
qinDing(fa, b[dq].ch[ls ^ 1], ls);
qinDing(dq, fa, ls ^ 1);
}
int splay(int dq)
{
for (int fa; (fa = b[dq].fa) != null; rotate(dq))
if (b[fa].fa != null)
rotate(isLeft(fa) == isLeft(dq) ? fa : dq);
return (root = dq);
}
inline int newnode(int zh, int fa)
{
++cnt;
b[cnt].fa = fa, b[cnt].zh = zh, b[cnt].ch[0] = b[cnt].ch[1] = null, b[cnt].cnt = 1;
return cnt;
}
int ins(int& dq, int zh, int fa)
{
if (dq == null)
return (dq = newnode(zh, fa));
if (b[dq].zh == zh)
{
++b[dq].cnt;
return dq;
}
return ins(b[dq].ch[zh > b[dq].zh], zh, dq);
}
int cxner(int dq, bool ls)
{
dq = b[dq].ch[ls];
while (b[dq].ch[ls ^ 1] != null)
dq = b[dq].ch[ls ^ 1];
return b[dq].zh;
}
int main()
{
int n, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int srx, dqans = INF;
scanf("%d", &srx);
splay(ins(root, srx, null));
if (b[root].cnt > 1)
continue;
if (b[root].ch[0] == null && b[root].ch[1] == null)
{
ans += srx;
continue;
}
if (b[root].ch[0] != null)
dqans = min(dqans, mabs(srx - cxner(root, 0)));
if (b[root].ch[1] != null)
dqans = min(dqans , mabs(srx - cxner(root, 1)));
ans += dqans;
}
printf("%d", ans);
return 0;
}
/*
6
5
1
2
5
4
6
*/

[HNOI2005]狡猾的商人

扯淡的 题解

翻车了翻车了…

一开始抱着玩玩的心态写了个最短路 + 最长路…然后蜜汁RE了…不知道是写残了还是思路有问题…今晚搞一搞这个玩意…

写的时候脑子不怎么清醒…然后就看了CA爷爷的一句话题解才不是抄题解呢

行吧 加权并查集…

写了10mins蜜汁$RE$…我$^{TM}$写个并查集你$RE$是算怎么回事…

然后就扔了一天…我会告诉你那天我颓的可开心了?

今天脑子清醒了再一看…woc我是沙茶嘛…这不是众所周知的事实?

先是合并的时候父亲和儿子写错了一个…大概就递归爆栈了…

然后发现我写的权也有问题啊…

按照加权并查集的一般套路 一个节点的权值是他到他父亲之间的代价这样才好合并啊压缩啊…

我想的时候是这么想的来着…写的时候就沙茶了…

底下的权值 = fa.second - son.second + cost写成了fa.second + cost…看上去没啥问题…因为我觉得既然是并查集的根了, second肯定是0啊…

然后我没有考虑到他这个并查集从底下find的时候会把整个路径上的权值都加起来…然后就$gg$了…

总之 意思就是要减去要合并的节点到根的路径上的权值对合并时权值的影响…Emmmmm差不多就是这样吧…

沙茶的 代码

AuFun太强了Orz

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
/**************************************************************
Problem: 1202
User: Cansult
Language: C++
Result: Accepted
Time:272 ms
Memory:1288 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100 + 5)
#define MAXM (1000 + 5)
#define pii pair<int, int>
using namespace std;
pii fa[MAXN];
int n, m;
pii find(int);
bool uni(int, int, int); // fa <- son
int main()
{
// freopen("in.in", "r", stdin);
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
for (int i = 0; i <= n + 1; i++)
fa[i].first = i, fa[i].second = 0;
bool ans = true;
for (int i = 1; i <= m; i++)
{
int srx, sry, srz;
scanf("%d%d%d", &srx, &sry, &srz);
++srx, ++sry;
if (!uni(srx - 1, sry, srz))
{
ans = false;
break;
}
}
puts(ans ? "true" : "false");
}
return 0;
}
pii find(int x)
{
if (fa[x].first == x)
return fa[x];
else
{
pii re = find(fa[x].first);
return (fa[x] = make_pair(re.first, re.second + fa[x].second));
}
}
bool uni(int x, int y, int cost)
{
pii fx = find(x), fy = find(y);
if (fx.first == fy.first)
return (fx.second == fy.second - cost);
else
fa[fy.first] = make_pair(fx.first, fx.second - fy.second + cost);
return true;
}

/*
2
3 3
1 2 10
1 3 -5
3 3 -15
5 3
1 5 100
3 5 50
1 2 51
*/

[HNOI2006]鬼谷子的钱袋

扯淡的 题解

绝世好水

我是很久以前就猜了一个结论是都按照二进制分…主要是根据电脑也是根据二进制存的…所以我就按照二进制算的…然后好像就A了…

其实好像是数据太水…我输入一个4输出2的程序居然能A….

怕不是RP全耗在这上面了

改了一下…至少不会输出2了…然后还是A了…我真的很想吐槽这个绝世水题…题目水也就算了…数据还水…Emmmmmmmm

沙茶的 代码

假的. 可以随便Hack随便艹

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <cstdio>
using namespace std;
int n, re;
int main()
{
scanf("%d", &n);
for (; (1 << re) <= n; re++)
{}
printf("%d", re);
return 0;
}

By 完蛋的 Cansult