水题记录(八)

题目名称 千钧一发 自动刷题机 砝码 Race 粟粟的书架
标签 网络流 二分 进制 点分治 二维主席树
来源 BZOJ 3158 BZOJ 4590 BZOJ 1110 BZOJ 2599 BZOJ 1926

BZOJ 3158

题意

题解

和上一题有点像,都是相互制约的问题,即选了$A$就不能选$B$,选了$B$就不能选$A$,对于这个条件,在网络流中一般是这样连边的,$S-(V_a)->[A]-(inf)->[B]-(V_b)->T$,但要求$A$和$B$分别属于两个集合。

  • 猜出来的正解

因为上面那个相互制约的处理方式只能解决二分图,而题目给出的两个制约条件又特别奇怪,且不难看出,想要找出能够相互制约的数不是一件容易的事,所以我就猜测,这个图建出来之后一定是二分图,所以我就打了染色后的网络流,没想到竟然$AC$了

  • 二分图的证明

对于任意两个偶数,其$gcd$至少为$2$,满足条件二,所以所有的偶数可以被划入一个集合,它们之间不会有任何冲突

对于任意两个奇数,我们不妨设其为$2a+1$和$2b+1$,那么$(2a+1)^2+(2b+1)^2=2*(2a^2+2a+2b^2+2b+1)$显然是$2$乘一个奇数,所以不是$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
105
106
107
108
109
110
111
112
#include <iostream> 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <map>
#include <set>
typedef long long ll;
inline int read() {
int u = 0; bool f = false; char c = getchar();
for (;!isdigit(c); c = getchar()) if (c == '-') f = 1;
for (; isdigit(c); c = getchar()) u = u * 10 + c - 48;
return f ? -u : u;
}
const int maxn = 1e3 + 10; int n;
const int maxm = 1e6 + 10;
const int inf = 1e9;
namespace MaxFlow {
struct edge {
int to, nxt, cap;
edge(int x = 0, int y = 0, int z = 0) {
to = x; nxt = y; cap = z;
}
}e[maxm << 1]; int head[maxn], cnt = 1;
int dep[maxn];
void add(int x, int y, int w) {
e[++cnt] = edge(y, head[x], w); head[x] = cnt;
e[++cnt] = edge(x, head[y], 0); head[y] = cnt;
}
bool bfs(int s, int t) {
std::queue<int>q; q.push(s);
memset(dep, 0, sizeof(dep));
dep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].nxt) {
if (!e[i].cap) continue;
int v = e[i].to;
if (dep[v]) continue;
dep[v] = dep[u] + 1;
if (!dep[t])q.push(v);
}
}
return dep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].nxt) {
if (!e[i].cap) continue;
int v = e[i].to;
if (dep[v] != dep[u] + 1) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
f -= a; e[i].cap -= a; e[i ^ 1].cap += a; r += a;
}
if (!r) dep[u] = 0; return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, inf);
return r;
}
}
int a[maxn], b[maxn], ans;
int gcd(int x, int y) {
return !y ? x : gcd(y, x % y);
}
bool check(int x, int y) {
if (gcd(x, y) != 1) return true;
ll sum = ll(x) * x + ll(y) * y;
ll tmp = sqrt(sum);
if (tmp * tmp != sum) return true;
return false;
}
std::vector<int>G[maxn];
int color[maxn];
void Color(int u, int c) {
color[u] = c;
for (int i = G[u].size() - 1; ~i; i--) {
int v = G[u][i];
if (color[v]) continue;
Color(v, 3 - c);
}
}
int main() {
n = read(); int S = n + 1, T = n + 2;
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= n; i++) ans += (b[i] = read());
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (!check(a[i], a[j]))
G[i].push_back(j), G[j].push_back(i);
for (int i = 1; i <= n; i++) {
if (!color[i]) Color(i, 1);
if (color[i] == 1)
MaxFlow::add(S, i, b[i]);
else
MaxFlow::add(i, T, b[i]);
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (!check(a[i], a[j])) {
int x = i, y = j;
if (color[x] == 2) std::swap(x, y);
MaxFlow::add(x, y, inf);
}
printf("%d\n", ans - MaxFlow::dinic(S, T));
}

BZOJ 4590

题意

曾经发明了信号增幅仪的发明家SHTSC又公开了他的新发明:自动刷题机–一种可以自动AC题目的神秘装置。自动
刷题机刷题的方式非常简单:首先会瞬间得出题目的正确做法,然后开始写程序,每秒,自动刷题机的代码生成模
块会有两种可能的结果:
A.写了x行代码。
B.心情不好,删掉了之前写的y行代码。(如果y大于当前代码长度则相当于全部删除。)
对于每个OJ所有题目,存在某个固定的长度n>0。一旦自动刷题机在某秒结束时积累了大于等于n行的代码,它就会
自动提交并AC此题,然后新建一个文件开始写下一题。SHTSC在某个OJ上跑了一天的自动刷题机,得到了很多条关
于写代码的日志信息。他突然发现自己没有记录这个OJ的n究竟是多少。所幸他通过自己在OJ上的Rank知道了机一
共切了k道题。希望你计算n可能的最小值和最大值。

题解

傻逼二分,毁我青春,注意他那个题意有点问题,只要不存在最大值或者最小值中的一个就要输出$-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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;
ll a[maxn], n, m;
int check(ll x) {
ll r = 0, now = 0;
for (int i = 1; i <= n; i++) {
now = max(0ll, now + a[i]);
if (now >= x) r++, now = 0;
}return r;
}
int main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lld", a + i);
ll l = 1, r = 1e18;
while (l < r) {
ll mid = l + r >> 1;
ll tmp = check(mid);
if (tmp == m) r = mid;
else if (tmp < m) r = mid - 1;
else if (tmp > m) l = mid + 1;
}
ll lll = l;
l = 1, r = 1e18;
while (l < r) {
ll mid = (l + r >> 1) + 1;
ll tmp = check(mid);
if (tmp == m) l = mid;
else if (tmp < m) r = mid - 1;
else if (tmp > m) l = mid + 1;
}
ll rrr = r;
if (check(lll) != m || check(rrr) != m) return 0 * puts("-1");
cout << lll << ' ' << rrr << endl;
}

BZOJ 1110

题意

在byteotian公司搬家的时候,他们发现他们的大量的精密砝码的搬运是一件恼人的工作。公司有一些固定容量的容器可以装这些砝码。他们想装尽量多的砝码以便搬运,并且丢弃剩下的砝码。每个容器可以装的砝码数量有限制,但是他们能够装的总重量不能超过每个容器的限制。一个容器也可以不装任何东西。任何两个砝码都有一个特征,他们的中总有一个的重量是另外一个的整数倍,当然他们也可能相等。

题解

复制个黄学长的题解。。。
砝码两两互为倍数关系,从小到大排个序,可以发现不同的砝码种类数是log(10^9)级别的,只有30左右。
根据贪心的思想,砝码从小到大依次装入一定是最优的
把每个容器的容量写成砝码大小的进制表示,比如当有3,9,18,54这些种类的砝码时,133的容量可以写成254+118+09+23+1,末尾的+1永远用不上,可以舍弃,那么各位从低到高分别是(2,0,1,2)。
把所有容器都写成这种表示,并把同一位上全部累加。比如说我们还有一个容器(0,1,2,0),那么两个容器累加的结果就是(2,1,3,2)。
当我们正在放大小为3的砝码时,就使用最低位上的容量。比如我们只有1个大小为3的砝码,那么塞入以后剩余容量为(1,1,3,2)。接下来要放大小为9的砝码,最低位上的那个1就永远用不上了。假如我们有2个9,而第二位上只有1的容量,那么就往高位借一个18拆成两个9,变成(2,3,2,2),然后塞入后剩余(2,1,2,2)。以此类推。
当剩余容量不够再放入时即停止,当前已放入的砝码个数即为最优答案。

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
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10; int ans;
int a[maxn], b[maxn], c[maxn], d[maxn], e[maxn];
bool check(int p) {
if (e[p]) return e[p]--;
int q = p;
while (!e[q] && q <= c[0]) q++;
if (q > c[0]) return false;
for (int i = q - 1; i >= p; i--)
e[i + 1]--, e[i] += c[i + 1] / c[i];
return e[p]--;
}
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) scanf("%d", &b[i]), c[i] = b[i];
sort(c + 1, c + 1 + m);
c[0] = unique(c + 1, c + 1 + m) - c - 1;
for (int i = 1; i <= m; i++)
d[lower_bound(c + 1, c + 1 + c[0], b[i]) - c]++;
for (int i = 1; i <= n; i++)
for (int j = c[0]; j; j--)
e[j] += a[i] / c[j], a[i] %= c[j];
for (int j = 1; j <= c[0]; j++){
int tmp = min(d[j], e[j]);
ans += tmp; e[j] -= tmp; d[j] -= tmp;
while (d[j]--)
if (check(j)) ans++;
else return 0 * printf("%d", ans);
}
return 0 * printf("%d", m);
}

BZOJ 2599

题意

给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.N <= 200000, K <= 1000000

题解

考虑点分治,我们找到树的重心之后,用一个$set$维护曾经存在过的距离及其边数,每次在里面二分距离为$k - d$的元素即可,注意点的编号从零开始

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
#include <iostream> 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
const int maxn = 2e5 + 10;
struct edge {
int to, dis;
edge(){}
edge(int to, int dis) : to(to), dis(dis) {}
};
vector<edge>G[maxn];
int n, k;
int size[maxn], center, maxs[maxn];
bool vis[maxn];
void getcenter(int u, int f, int all) {
size[u] = 1; maxs[u] = 0;
for (int i = G[u].size() - 1; ~i; i--) {
edge &e = G[u][i];
if (vis[e.to] || e.to == f) continue;
getcenter(e.to, u, all);
maxs[u] = max(maxs[u], size[e.to]);
size[u] = size[u] + size[e.to];
}
maxs[u] = max(maxs[u], all - size[u]);
if (maxs[u] < maxs[center]) center = u;
}
set<pair<int,int> >dis, tmp; int ans = -1;
void checkdis(int u, int f, int d, int h) {
if (d > k || (ans != -1 && h > ans)) return;
set<pair<int,int> >::iterator now = dis.lower_bound(make_pair(k - d, 0));
if (now != dis.end() && now->first == k - d)
ans = (ans == -1 || h + now->second < ans) ? h + now->second : ans;
tmp.insert(make_pair(d, h));
for (int i = G[u].size() - 1; ~i; i--) {
edge &e = G[u][i];
if (vis[e.to] || e.to == f) continue;
checkdis(e.to, u, d + e.dis, h + 1);
}
}
void solve(int u) {
vis[u] = true; dis.clear();
dis.insert(make_pair(0, 0));
for (int i = G[u].size() - 1; ~i; i--) {
edge &e = G[u][i];
if (vis[e.to]) continue;
checkdis(e.to, u, e.dis, 1);
for (set<pair<int,int> >::iterator it = tmp.begin(); it != tmp.end(); it++)
dis.insert(*it); tmp.clear();
}
for (int i = G[u].size() - 1; ~i; i--) {
edge &e = G[u][i];
if (vis[e.to]) continue;
maxs[center = n + 1] = size[e.to] << 1;
getcenter(e.to, u, size[e.to]);
solve(center);
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i < n; i++) {
int x, y, z; scanf("%d%d%d", &x, &y, &z);
G[x].push_back(edge(y, z));
G[y].push_back(edge(x, z));
}
maxs[center = n + 1] = n << 1;
getcenter(0, 0, n);
solve(center);
printf("%d", ans);
}
/*
15 10
1 2 1
1 3 2
2 4 3
2 5 4
3 6 5
3 7 1
4 8 2
4 9 3
5 10 4
5 11 5
6 12 1
6 13 2
7 14 3
7 0 4
*/

BZOJ 1926

题意

幸福幼儿园 B29 班的粟粟是一个聪明机灵、乖巧可爱的小朋友,她的爱好是画画和读书,尤其喜欢 Thomas H. Cormen 的文章。粟粟家中有一个 R行C 列的巨型书架,书架的每一个位置都摆有一本书,上数第i 行、左数第j 列摆放的书有Pi,j页厚。粟粟每天除了读书之外,还有一件必不可少的工作就是摘苹果,她每天必须摘取一个指定的苹果。粟粟家果树上的苹果有的高、有的低,但无论如何凭粟粟自己的个头都难以摘到。不过她发现, 如果在脚下放上几本书,就可以够着苹果;她同时注意到,对于第 i 天指定的那个苹果,只要她脚下放置书的总页数之和不低于Hi,就一定能够摘到。由于书架内的书过多,父母担心粟粟一天内就把所有书看完而耽误了上幼儿园,于是每天只允许粟粟在一个特定区域内拿书。这个区域是一个矩形,第 i 天给定区域的左上角是上数第 x1i行的左数第 y1i本书,右下角是上数第 x2i行的左数第y2i本书。换句话说,粟粟在这一天,只能在这﹙x2i-x1i+1﹚×﹙y2i-y1i+1﹚本书中挑选若干本垫在脚下,摘取苹果。粟粟每次取书时都能及时放回原位,并且她的书架不会再撤下书目或换上新书,摘苹果的任务会一直持续 M天。给出每本书籍的页数和每天的区域限制及采摘要求,请你告诉粟粟,她每天至少拿取多少本书,就可以摘到当天指定的苹果。

题解

简单说,就是查询矩形内,最少选择几个元素使得和大于一个给定的值,考虑二维前缀和 + 主席树,只要我们能建出每个点的前缀值域线段树,那么就没有任何问题了,注意到如果一行行地建树,会爆空间,所以我就用了那么一个启发式建树乱搞搞,好像省了不少空间,就过掉了。。。

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
#include <iostream> 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;

const int maxn = 5e5 + 10;
struct node {
int sum, ls, rs, cnt;
};
vector<int>root[500];
vector<int>mxt[500];
namespace HJT {
node T[maxn * 60]; int coc;
void insert(int &p, int l, int r, int v) {
T[++coc] = T[p]; p = coc;
if (l == r) {
T[p].sum += v; T[p].cnt++; return;
}
int mid = (l + r) >> 1;
if (v > mid) insert(T[p].rs, mid + 1, r, v);
else insert(T[p].ls, l, mid, v);
T[p].cnt = T[T[p].ls].cnt + T[T[p].rs].cnt;
T[p].sum = T[T[p].ls].sum + T[T[p].rs].sum;
}
int query(int p1, int p2, int m1, int m2, int l, int r, int h) {
int sum = T[p1].sum - T[m1].sum + T[p2].sum - T[m2].sum;
if (sum < h) return -1;
if (l == r) return (h + l - 1) / l;
int mid = (l + r) >> 1;
int rst = query(T[p1].rs, T[p2].rs, T[m1].rs, T[m2].rs, mid + 1, r, h);
if (rst != -1) return rst;
h -= T[T[p1].rs].sum - T[T[m1].rs].sum + T[T[p2].rs].sum - T[T[m2].rs].sum;
rst = T[T[p1].rs].cnt - T[T[m1].rs].cnt + T[T[p2].rs].cnt - T[T[m2].rs].cnt;
return query(T[p1].ls, T[p2].ls, T[m1].ls, T[m2].ls, l, mid, h) + rst;
}
}

inline int read(){
int r = 0; char c = getchar();
for(;!isdigit(c); c = getchar());
for(; isdigit(c); c = getchar()) r = (r << 1) + (r << 3) + c - '0';
return r;
}
int main() {
//cerr << sizeof (HJT::T) / 1024 / 1024 << endl;
int n = read(), m = read(), q = read();
for (int i = 0; i <= m; i++) root[0].push_back(0);
for (int i = 1; i <= n; i++) {
mxt[i].push_back(0); root[i].push_back(0);
for (int j = 1; j <= m; j++) {
int x = read();
mxt[i].push_back(x);
if (i <= j) {
root[i].push_back(root[i][j - 1]);
for (int k = 1; k < i; k++)
HJT::insert(root[i][j], 1, 1000, mxt[k][j]);
}else {
root[i].push_back(root[i - 1][j]);
for (int k = 1; k < j; k++)
HJT::insert(root[i][j], 1, 1000, mxt[i][k]);
}
HJT::insert(root[i][j], 1, 1000, mxt[i][j]);
}
}
while (q--) {
int x1 = read(), y1 = read(), x2 = read(), y2 = read(), h = read();
int p1 = root[x1 - 1][y1 - 1], p2 = root[x2][y2];
int m1 = root[x1 - 1][y2], m2 = root[x2][y1 - 1];
int rst = HJT::query(p1, p2, m1, m2, 1, 1000, h);
if (rst == -1) printf("Poor QLW\n");
else printf("%d\n", rst);
}
return 0;
}