C. Monsters And Spells
怪兽会在第K秒出现，血量是H，任务是在它出现的时候消灭它。上一秒如果没有使用过魔法，那么这一秒只能施展1的魔法；如果上一秒使用过x的魔法，这一秒可以使用x+1的魔法。若魔法x>=H，则怪兽可以被消灭。使用x的魔法就会消耗x的魔力，问最少消耗魔力是多少。
直接从前往后遍历一遍是不可以的，存在H [ i ] > H [ i - 1 ] + K [ i ] - K [ i - 1 ]，为了避免这种情况，可以先dp消除这种情况，再从前往后遍历一遍就好了。
还有一种写法简单些，是区间合并，在时间轴上弄出所有的区间然后以左端点排个序，开始合并就好了。
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#include<bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5, mod = 1e9 + 7; int k[N], h[N]; signed main () { int tt; cin >> tt; while(tt--){ int n; cin >> n; for (int i = 1; i <= n; i++) cin >> k[i]; for (int i = 1; i <= n; i++) cin >> h[i]; for (int i = n - 1; i >= 1; i--) h[i] = max(h[i], h[i + 1] - (k[i + 1] - k[i])); int ans = 0; int last = 0; for (int i = 1; i <= n; i++){ if (last + k[i] - k[i - 1] >= h[i]){ if (k[i] - k[i - 1] >= h[i]){ ans += h[i] * (h[i] + 1) / 2; last = h[i]; } else { ans += (last + 1 + last + k[i] - k[i - 1]) * (k[i] - k[i - 1]) / 2; last += k[i] - k[i - 1]; } } } cout << ans << endl; } 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#include<bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5, mod = 1e9 + 7; int k[N], h[N]; struct node{ int l, r; bool operator < (const node &k) const{ if (l != k.l) return l < k.l; else return r < k.r; } } a[N]; signed main () { int tt; cin >> tt; while(tt--){ int n; cin >> n; for (int i = 1; i <= n; i++) cin >> k[i]; for (int i = 1; i <= n; i++) cin >> h[i]; for (int i = 1; i <= n; i++){ a[i].l = k[i] - h[i] + 1; a[i].r = k[i]; } sort(a + 1, a + 1 + n); int ans = 0; int l = a[1].l, r = a[1].r; for (int i = 2; i <= n; i++){ if (a[i].l <= r) { r = max(r, a[i].r); //相交 更新右端点 } else { ans += (1 + r - l + 1) * (r - l + 1) / 2; //不想交 统计答案 l = a[i].l; r = a[i].r; } } ans += (1 + r - l + 1) * (r - l + 1) / 2; cout << ans << endl; } return 0; }
鸡哥的 AI 驾驶
很久以前的一道二分题了。寒假闲来没事干，突然想到以前这题二分一下时间然后check好像可写。但是水平不够还是调了很久。。有一个bug不拿别人AC程序对拍是真想不到。。最后用并查集+二分过得。细节真的很重要啊。
思路：枚举时间，然后得到车子的新的位置，怎样判断车子有没有相撞呢？用并查集，相邻的车子只要型号相同，就并在一起。得到新的位置后排个序就知道和原来的相对位置有没有发生改变了，如果变了那就一定撞车了，反之则没有。
我的wa点：
1.二分区间枚举的太大了，太依赖1e18这个大数字，导致更新位置的时候炸long long。
2.如果好几辆车新的位置是相同的，如果又恰好最开始他们的相对位置有相邻在一起，我的排序排完后也还是把他们排到了一起，没有打乱顺序，导致答案错误。只要在cmp函数里加一行判断相等的时候的情况就好了。
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#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 5, mod = 1e9 + 7; struct node{ int p, v, t; bool operator < (const node &k) const { if (p != k.p) return p < k.p; return v > k.v; } } a[N], b[N]; int fa[N]; int n, k; int getf(int k) { if (k == fa[k]) return k; else return fa[k] = getf(fa[k]); } int check(int mid) { for (int i = 1; i <= n; i++){ b[i].p = a[i].p + a[i].v * mid; b[i].v = i; b[i].t = getf(i); } sort(b + 1, b + 1 + n); for (int i = 1; i <= n; i++){ if (b[i].t != getf(i)) return 1; } return 0; } signed main() { // freopen("data.in","r",stdin); // freopen("data.out","w",stdout); cin >> n >> k; for (int i = 1; i <= n; i++) { scanf("%lld%lld%lld", &a[i].p, &a[i].v, &a[i].t); } sort(a + 1, a + 1 + n); for (int i = 1; i <= n; i++) { fa[i] = i; if (a[i].t == a[i - 1].t) fa[i] = i - 1; } for (int i = 1; i <= n; i++) getf(i); int l = 1, r = 5e9; while(l < r){ int mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid + 1; } if (check(l)) cout << l - 1; else cout << -1; return 0; }
C. Strange Test
给定整数a,b，可以执行三种操作：
a++,b++,a|=b
求使得a==b的最小操作次数。
推式子，设a自增一些次数后变x，b自增一些后变y，那么ans=x-a+y-x+(x|y)-y+1。化简后得x+(x|y)-a-b+1。那么只要从a开始顺序枚举，然后构造出y，使得x|y尽量小，更新ans就好了。
由|操作的性质不难构造Y，就四种情况。
看到网上还有一些其他的方法，直接从a开始枚举，如果(i|b) == b，那么ans = min(ans, i - a + 1)；然后再从b开始枚举，如果(a | i ) = = i，那么ans = min(ans, i - b +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#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e6 + 5, mod = 1e9 + 7; signed main() { int tt; cin >> tt; while(tt--){ int a, b; cin >> a >> b; int ans = b - a; for (int i = a; i <= b; i++){ int x = 0; for (int j = 32; j >= 0; j--){ if ((b>>j) & 1) x += (1ll << j); else if ((i >> j) & 1) { x += (1ll << j); break; } } ans = min(i + (i|x) - a - b + 1, ans); } cout << ans << endl; } return 0; }
B. Range and Partition
好题，一个数组和一个区间[x,y]。让数组其分成k块，每一块都满足：每一块中在区间[x,y]内的数的数量为cnt1，不在的为cnt2，要求cnt1>cnt2。题目要求求出这个区间[x,y]，使得y - x最小。
思路：一小块中在区间内的有cnt1个，这一块长度为len，则cnt1 > len - cnt1，即2 * cnt1 - len >= 1；所有块都满足这个条件，那么合并所有的不等式，就有了 2 * cnt1 - n >= k。
给数组排个序，枚举数组中的每个数为x，然后就能O（logn）或者O（1）的求出y。
O（logn）：直接二分枚举，判断上面的不等式是否满足即可。
O（1）：由不等式可得，cnt1 >= (n + k) / 2，因为是大于号，所以向上取整，所以cnt1 = (n + k + 1) / 2，此时就可以O（1）的求出y了。
求出x和y后，下面的输出怎么划分很简单，不必细说。
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#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e6 + 5, mod = 1e9 + 7; int a[N], b[N]; int n, k; int sum[N]; int bsh(int x, int l, int r) { while(l < r){ int mid = (l + r) / 2; if (2*(mid - x + 1)-n>=k) r = mid; else l = mid + 1; } if (2 * (l - x + 1) - n >= k) return l; else return -1; } signed main() { int tt; cin >> tt; while(tt--){ cin >> n >> k; for (int i = 1; i <= n; i++) { b[i] = a[i] = 0; cin >> a[i]; b[i] = a[i]; } sort(b + 1, b + 1 + n); int x = 1, y = n; for (int i = 1; i <= n; i++){ int pos = bsh(i, i, n); if (pos == -1) continue; if (b[pos] - b[i] < y - x) x = b[i], y = b[pos]; } cout << x << " " << y << endl; for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1]; if (a[i] >= x && a[i] <= y) sum[i]++; } int last = 0, cnt = 0; for (int i = 1; i <= n; i++) { int cnt1 = 2 * (sum[i] - sum[last]) - (i - last); int cnt2 = 2 * (sum[n] - sum[i]) - (n - i); if (cnt1 > 0 && cnt2 > 0){ if (cnt + 1 < k){ printf("%lld %lldn", last + 1, i); last = i; cnt++; } } else if (cnt1 > 0 && cnt + 1 == k) { printf("%lld %lldn", last + 1, n); break; } } } return 0; }
C. Road Optimization
题意有点不好说。。上一张题目带的图吧。
Total time is 3⋅5+1⋅8+4⋅3+2⋅6=47 minutes.
然后删除一些路标，求新的最小的时间。
简单dp，cf难度1700的dp好像也不是很难，不过这题主要是确定了状态后，转移的方程式就很好写了。
定义f[i][j]为至以第i个路标结尾，删了j个路标的最小时间。
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#include<bits/stdc++.h> using namespace std; #define int long long const int N = 500 + 5, mod = 1e9 + 7; int f[N][N], d[N], a[N]; signed main () { int n, l, k; cin >> n >> l >> k; for (int i = 1; i <= n; i++){ cin >> d[i]; } d[n + 1] = l; for (int i = 1; i <= n; i++){ cin >> a[i]; } memset(f, 0x3f3f3f3f, sizeof f); f[1][0] = 0; int ans = 1e18; for (int i = 1; i <= n + 1; i++){ for (int j = 0; j <= min(k, i - 2); j++){ for (int k = i - j - 1, p = 0; k <= i - 1; k++, p++){ f[i][j] = min(f[i][j], f[k][p] + a[k] * (d[i] - d[k])); } if (i == n + 1) ans = min(ans, f[i][j]); } } cout << ans; return 0; }
最后
以上就是微笑小松鼠最近收集整理的关于寒假cf补题的全部内容，更多相关寒假cf补题内容请搜索靠谱客的其他文章。
发表评论 取消回复