BestCoder Round 92

Contents
  1. 1. 1001 Skip the Class
  2. 2. 1002 Count the Sheep
  3. 3. 1003 Girls Love 233
  4. 4. 1004 Game Arrangement

好久没写题解了。。感觉还是经常写点文字。题解勉强算是吧(雾

1001 Skip the Class

直接对于每种课程维护最大值和次大值即可

1002 Count the Sheep

题意:
$给定N\le 10^5个男羊,M\le 10^5个女羊,K\le 10^5个朋友关系$
$问满足A-B、B-C、C-D是朋友关系且A、B、C、D各不相同的,A-B-C-D这样序列的方案数$

分析:
$直接枚举B-C边,然后统计下两边的度就好了,别忘了减去自己$

1003 Girls Love 233

题意:
$给定长度N\le 100的由字符’2’和’3’构成的字符串$
$有\lfloor{M\over 2}\rfloor次操作次数,每次可以交换2个相邻的字符$
$最多能使这个字符串中有多少个子串”233”呢$

分析:
$官方题解给了一个很妙的dp$
$可以发现答案其实只跟’2’有关,即’3’和’3’换是毫无意义的$
$于是我们可以抠出来所有’2’的位置,那么只对’2’有交换的花费$
$接下来考虑dp,f[i][j][k][3]:=$
$选取了i个’2’,j个’3’,使用了k次交换,状态是s的最多子串数$
$s状态显然有i\in [0,3):’2’后面有i个’3’,如果有第一次有2个’3’显然答案+1$
$最终ans=\displaystyle\max_{k, s}\{ f[c2][c3][k][s]\}$

代码:

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
//
// Created by TaoSama on 2017-02-27
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cerr << #x << " = " << x << " "
#define prln(x) cerr << #x << " = " << x << endl
const int N = 1e2 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m;
char s[N];
int f[N][N][N / 2][3];
void getMax(int& x, int y) {
if(x < y) x = y;
}
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int t; scanf("%d", &t);
while(t--) {
vector<int> p(1, 0);
scanf("%d%d%s", &n, &m, s + 1); m >>= 1;
for(int i = 1; i <= n; ++i) if(s[i] == '2') p.push_back(i);
int c2 = p.size() - 1, c3 = n - c2;
for(int i = 0; i <= c2; ++i)
for(int j = 0; j <= c3; ++j)
for(int k = 0; k <= m; ++k)
for(int z = 0; z < 3; ++z)
f[i][j][k][z] = -INF;
f[0][0][0][2] = 0;
for(int i = 0; i <= c2; ++i) {
for(int j = 0; j <= c3; ++j) {
for(int k = 0; k <= m; ++k) {
for(int z = 0; z < 3; ++z) {
if(f[i][j][k][z] < 0) continue;
if(i < c2) {
int nk = k + abs(i + j + 1 - p[i + 1]);
if(nk <= m) getMax(f[i + 1][j][nk][0], f[i][j][k][z]);
}
if(j < c3) {
int nz = z, one = 0;
if(nz != 2) {
if(++nz == 2) ++one;
}
getMax(f[i][j + 1][k][nz], f[i][j][k][z] + one);
}
}
}
}
}
int ans = 0;
for(int k = 0; k <= m; ++k)
for(int z = 0; z < 3; ++z)
getMax(ans, f[c2][c3][k][z]);
printf("%d\n", ans);
}
return 0;
}

1004 Game Arrangement

题意:
$给定N\le 10^4段空闲时间[L_i, R_i],1\le L_i\le R_i\le 10^9$
$给定M\le 10^4个游戏的感兴趣时段[l_i, r_i],1\le l_i\le r_i\le 10^9,并且需要持续时间1\le d_i\le 10^9$
$对于i类游戏只能全在它的感兴趣时段,以及某段空闲时段才可以玩$
$问最多能玩游戏的次数$

分析:
$如果数据范围不是10^9的话,显然可以按时间来dp,就不多说了$
$可以考虑贪心,因为物品的价值都是1,就可以贪心了$
$对于当前时间,对某个游戏肯定选择持续短的,就可以用堆或者set来贪心了$
$首先把空闲时间和游戏按照起始时间排序$
$考虑枚举每一段空闲时间,首先把当前能玩的游戏全部加进去堆里$
$再把一把都玩不了的都删了,然后取出第一个能玩的$
$当前这个游戏能玩多久由三个东西限制,一个是空闲时间,一个是感兴趣时间$
$还有下一个游戏的开始时间来限制$
$肯定尝试下取整个是一定可以的$
$然后你以为就对了??显然不是,我还可以后延续到下一个游戏的时间$
$所以就考虑再玩一个,但是只是尝试,所以拆成两半,一个是现在玩一些$
$剩下的时间成为一个新的游戏塞进去,之后直接尝试下一个游戏就可以了$
$这样贪心就对了$
$注意一下边界的细节,时间复杂度是O(nlogn)$
$感谢bc大佬的代码$

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
//
// Created by TaoSama on 2017-02-27
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cerr << #x << " = " << x << " "
#define prln(x) cerr << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m;
struct Node {
int l, r, d;
bool operator<(const Node& r) const {
return d > r.d;
}
void see() {
pr(l); pr(r); prln(d);
}
};
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
vector<Node> a, b;
a.reserve(n); b.reserve(m);
for(int i = 1; i <= n; ++i) {
int l, r; scanf("%d%d", &l, &r);
if(a.size() && a.back().r + 1 == l)
a.back().r = r;
else a.push_back({l, r, 0});
}
for(int i = 1; i <= m; ++i) {
int l, r, d; scanf("%d%d%d", &l, &r, &d);
b.push_back({l, r, d});
}
b.push_back({INF, -1, -1});
sort(b.begin(), b.end(), [](const Node & a, const Node & b) {
return a.l < b.l;
});
int ans = 0;
priority_queue<Node> q;
for(int i = 0, j = 0; i < a.size(); ++i) {
int cur = a[i].l;
for(; cur <= a[i].r;) {
for(; b[j].l <= cur; ++j) q.push(b[j]); //insert
while(q.size() && q.top().r - q.top().d + 1 < cur) q.pop(); //delete
if(!q.size()) {cur = b[j].l; continue;}
Node tp = q.top();
int r = min(a[i].r, tp.r);
int cnt = (min(r, b[j].l - 1) - cur + 1) / tp.d;
ans += cnt;
cur += cnt * tp.d;
if(!cnt) {
int nxt = cur + tp.d - 1;
if(nxt <= r) q.push({b[j].l, nxt, nxt - b[j].l + 1});
cur = b[j].l;
}
}
}
printf("%d\n", ans);
}
return 0;
}

1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到