cf-edu-round72

还行。

E Sum Queries? 线段树 观察

根据观察可以看出,首先只有一个数的时候肯定符合,当两个数相加时,如果其中一个数的某一位为0,这一位符合要求,反之不行。

经过观察可以看出因为进位,所以当某一位不符合要求时,之后无论再加什么数都不会使这一位重新变为符合要求,详细证明看题解。这就为线段树创造条件。

因为原题要求不符合要求时最小的子集中各数的和,所以维护一段区间,用node储存,best为答案,mx[i]为集合中所有数中第i位不为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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const int inf = 2e9;
struct node {
int mx[10];
int best;
node() {
best = inf;
for(int i = 0; i < 10; ++i)
mx[i] = inf;
}
int& operator[](size_t N) { return mx[N]; }
};

node b[maxn << 2];
int a[maxn];

void insert(node& a, int val) {
int d = val;
for(int i = 0; i < 10 && d; ++i) {
if(d % 10)
a[i] = min(a[i], val);
d /= 10;
}
}

node Merge(node &a, node &b) {
node c;
c.best = min(a.best, b.best);
for(int i = 0; i < 10; ++i) {
c[i] = min(a[i], b[i]);
if(a[i] < inf && b[i] < inf)
c.best = min(c.best, a[i] + b[i]);
}
return c;
}

void build(int o, int l, int r) {
if(r == l) {
insert(b[o], a[l]);
return;
}
int mid = (l + r) >> 1;
build(o*2, l ,mid);
build(o*2 + 1,mid + 1, r);
b[o] = Merge(b[o*2], b[o*2+1]);
}

void upda(int o, int l, int r, int qp, int val) {
if(r == l) {
b[o] = node();
insert(b[o], val);
return;
}
int mid = (l + r) >> 1;
if(qp <= mid)
upda(o*2, l, mid, qp, val);
else
upda(o*2 + 1, mid + 1, r, qp, val);
b[o] = Merge(b[o*2], b[o*2+1]);
}

node query(int o, int l, int r, int L, int R) {
if(l >= L && r <= R)
return b[o];
int mid = (l + r) >> 1;
node ql, qr;
if(L <= mid)
ql = query(o*2, l, mid, L, R);
if(R > mid)
qr = query(o*2 + 1, mid + 1, r, L, R);
return Merge(ql, qr);
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n,m; cin>>n>>m;
for(int i = 1; i <= n; ++i) {
cin>>a[i];
}
build(1, 1, n);
while(m--) {
int opt, x, y;
cin>>opt>>x>>y;
if(opt == 1) {
upda(1, 1, n, x, y);
} else {
int ans = query(1, 1, n, x, y).best;
if(ans == inf)
cout<<"-1\n";
else
cout<<ans<<endl;
}
}
}

D Coloring Edges 思维

给定一个有向图,对m条边染色使得不存在一个所有边颜色相同的圈,求满足条件的最少染色数。

可以通过dfs找圈的想法来构造一种染色方法,假设dfs一个圈,按照节点dfs序给节点编号,肯定会访问到一条指向之前还在栈中的节点的边(back edge),每个圈都由这种边和圈中剩下的其它边构成,所以把它染色为2,其它的染为1。注意当这个节点dfs完成后要做个标记,因为有可能有若干张连通图,且当其它点访问到它后因为之前已经染色完成,直接跳过就好。

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const int inf = 2e9;

vector<pair<int,int>> G[5050];
int n,m;
int col[5050];
bool cycle;
bool vis[5050];
bool in[5050];
void dfs(int u) {
in[u] = 1;
for(auto d : G[u]) {
int v = d.first, id = d.second;
if(vis[v]) {
col[id] = 1;
} else if(!in[v]) {
col[id] = 1;
dfs(v);
} else {
cycle = 1;
col[id] = 2;
}
}
in[u] = 0;
vis[u] = 1;
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i = 1; i <= m; ++i) {
int u,v; cin>>u>>v;
G[u].push_back({v,i});
}
for(int i = 1; i <= n; ++i) {
if(!vis[i]) {
dfs(i);
}
}
if(!cycle) {
cout<<"1\n";
for(int i = 1; i <= m; ++i)
cout<<"1 ";
cout<<endl;
} else {
cout<<"2\n";
for(int i = 1; i <= m; ++i)
cout<<col[i]<<" ";
cout<<endl;
}

}

C The Number Of Good Substrings 枚举

给定一个01串,如果任意一段转化为十进制后等于该段长度,则该段为good。找出所有为good的子串数量。所有字符串长度总和<= 2e5。

因为log2(2e5) = 20左右,所以直接暴力,枚举任意段20位看看是否符合条件。但是直接暴力是不对的,有一个特例,当某一段转化为10进制 > 该段长度时,它可以看看前面是否有0,有的话可以用0补足长度。假设5 = (101),如果前面有两个0就会成立(00101)。所以可能有一段加上若干个0之后长度就会>20,但是有效位长度肯定永远<=20。

所以要先统计这一位前从上一个1开始的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
42
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
const int inf = 2e9;

int nxt[maxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin>>n;
while(n--) {
string s;
s.clear();
cin>>s;
int ans = 0;
for(int i = 0; i < s.length(); ++i) {
nxt[i] = (i > 0 && s[i - 1] == '0') ? (nxt[i - 1] + 1) : 0;
}
for(int i = 0; i < s.length(); ++i) {
int val = 0;
for(int j = 0; j < 21 && i - j >= 0; j += nxt[i - j] + 1) {
val = val + ((s[i - j] - '0') << j);
if(val == j + 1)
++ans;
else if(val > j + 1 && val <= j + 1 + nxt[i - j])
++ans;
}
}
cout<<ans<<endl;
}
}

B Zmei Gorynich 贪心

一个有x个头的怪物,有很多种砍头方式,第i种方式砍掉min(di,x)个头,如果砍完后还有头,就会再长出hi个头,否则怪物被干掉。每次尝试可以任选砍头方法,问如何能用最少的砍头次数干掉怪物,

简单贪心。

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

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t; cin>>t;
while(t--) {
ll n, x;
cin>>n>>x;
set<ll> s;
priority_queue<ll> q; //按照从大到小排序
ll maxd = -1;
for(int i = 1; i <= n; ++i) {
ll d, h; cin>>d>>h;
s.insert(d);
q.push(d - h);
maxd = max(maxd, d);
}
ll ans = 0;
while(1) {
if(x <= 0) break;
if(s.lower_bound(x) != s.end()) {++ans; break;} //如果存在一种方法可以将当前的头全部砍掉,则用该种方法,退出
if(q.top() <= 0) {//如果没有能使当前头数减少的方法,说明无解
ans = -1;
break;
} else {
ans += (x - maxd + q.top() - 1) / q.top() + 1; //否则当前头数>任意一种砍头方法的d,选择能使当前头减少的最多的方法,将头砍至d的最大值
break;
}
};
cout<<ans<<endl;
}
}

A

给定a,b,c,求出将c一部分加到a上,另一部分加到b上之后a>b的方案数。

一元一次方程,注意边界。

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

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <bitset>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
using namespace std;
typedef long long ll;

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t; cin>>t;
while(t--) {
int a, b, e;
cin>>a>>b>>e;
cout<<max(min((a - b + e + 1) / 2, e + 1),0)<<endl;
}
}