T1 购买板凳
有 $n$ 条信息，每条信息包含 $x$ 个人，这 $x$ 个人会在 $A$ 时间到达，$B$ 时间离开，每个人到达后会占用一个板凳，求至少要准备多少个板凳。
题解
这个题我看完就直接扫描线了，把时间换算成分钟，然后 $A$ 时间 $+x$，$B$ 时间 $-x$，排序后累加即可。
注意处理边界，即重复的时刻要先累加再更新答案
时间复杂度 $O(n \log n)$。
当然这个题也可以直接差分做到 $O(n)$。
代码
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
|
#include <bits/stdc++.h>
namespace IO {
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}
template <typename T>
inline bool read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return false;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig ? x = -x : 0;
return true;
}
inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}
inline int read(char *buf) {
register int s = 0;
register char c;
while (c = read(), isspace(c) && c != -1)
;
if (c == -1) {
*buf = 0;
return -1;
}
do
buf[s++] = c;
while (c = read(), !isspace(c) && c != -1);
buf[s] = 0;
return s;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
x < 0 ? (print('-'), x = -x) : 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void print(const char *s) {
for (; *s; s++) print(*s);
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
struct InputOutputStream {
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
~InputOutputStream() { flush(); }
} io;
}
namespace {
using IO::io;
const int MAXN = 100000;
struct Node {
int x, val;
inline bool operator<(const Node &p) const { return x < p.x; }
Node(int x = 0, int val = 0) : x(x), val(val) {}
} data[MAXN * 2 + 5];
int cnt;
inline void solve() {
register int n;
io >> n;
for (register int i = 1, x, a, b, c, d; i <= n; i++) {
io >> x >> a >> b >> c >> d;
data[++cnt] = Node(a * 60 + b, x);
data[++cnt] = Node(c * 60 + d, -x);
}
std::sort(data + 1, data + cnt + 1);
register int max = 0, now = 0;
for (register int i = 1; i <= cnt; i++) {
now += data[i].val;
while (i + 1 <= cnt && data[i].x == data[i + 1].x)
i++, now += data[i].val;
max = std::max(max, now);
}
io << max;
}
}
int main() {
solve();
return 0;
}
|
T2 新排序
定义不和谐的数字满足：这个数字严格小于它左边的一个数字或大于它右边的一个数字，每次选出所有不和谐的数字删去，直到没有不和谐的数字存在，求最后的序列。
题解
一开始想了个 std::list 套 std::list，后来感觉一个 std::list 似乎就可以，然后发现自己算了假的复杂度，用一个链表可以通过先单调递增后单调递减的数据卡到 $O(n ^ 2)$ 级别。
考虑 std::list 套 std::list，我们可以把序列划分成很多上升的子串，每次会删除子串相交处的数，我们用双向链表维护这些子串，每次 $O(1)$ 删除每个不和谐的数，然后再依次合并子串，时间复杂度 $O(n)$。
注意 std::list::splice 复杂度的问题：
1
2
| void splice( const_iterator pos, list& other );
void splice( const_iterator pos, list& other, const_iterator it );
|
复杂度 $O(1)$
1
| void splice( const_iterator pos, list& other, const_iterator first, const_iterator last);
|
若 &other == this，复杂度 $O(1)$，否则为 std::distance(first, last)
代码
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
|
#include <bits/stdc++.h>
namespace IO {
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}
template <typename T>
inline bool read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return false;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig ? x = -x : 0;
return true;
}
inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}
inline int read(char *buf) {
register int s = 0;
register char c;
while (c = read(), isspace(c) && c != -1)
;
if (c == -1) {
*buf = 0;
return -1;
}
do
buf[s++] = c;
while (c = read(), !isspace(c) && c != -1);
buf[s] = 0;
return s;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
x < 0 ? (print('-'), x = -x) : 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void print(const char *s) {
for (; *s; s++) print(*s);
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
struct InputOutputStream {
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
~InputOutputStream() { flush(); }
} io;
}
namespace {
using IO::io;
typedef std::list<std::list<int> > List;
List list;
inline void solveCase() {
list.clear();
register int n;
static std::list<int> now;
io >> n, now.clear();
for (register int i = 1, v, last = -1; i <= n; i++) {
io >> v;
if (v < last) list.push_back(now), now.clear();
last = v, now.push_back(v);
}
if (!now.empty()) list.push_back(now);
while (list.begin() != --list.end()) {
for (register List::iterator it = list.begin(); it != list.end();
it++) {
if (it != list.begin()) it->pop_front();
if (!it->empty() && it != --list.end()) it->pop_back();
}
while (!list.empty() && list.begin()->empty()) list.pop_front();
for (register List::iterator it = list.begin(), next; it != list.end();
it++) {
while (++(next = it) != list.end()) {
if (next->empty() || next->front() >= it->back())
it->splice(it->end(), *next), list.erase(next);
else
break;
}
}
}
if (!list.empty()) {
io << list.begin()->size() << '\n';
for (register std::list<int>::iterator it = list.begin()->begin();
it != list.begin()->end(); it++)
io << *it << ' ';
io << '\n';
} else {
io << "0\n\n";
}
}
inline void solve() {
register int T;
io >> T;
while (T--) solveCase();
}
}
int main() {
solve();
return 0;
}
|
T3 豆豆游戏
有 $01$ 两个数，每次可以向任意一个位置插入一个数，若连在一起的相同的数达到三个及以上，就会被消除，可以连锁消除，求最小的消除次数。
题解
先考虑前 $% 30$ 的数据，这个题 $% 30$ 的数据可能需要一些高超的搜索技巧，用链表维护这串数，然后先贪心选择相同数多的位置进行搜索，然后以当前状态最坏次数 $/ 5$ 为估价函数搜索（$/ 6$ 及以上可能会 T）。
然后是正解，考虑区间 DP，首先数相同的一块肯定是一起消除的，所以我们可以把相邻的相同的点合在一起，令 $num[i]$ 表示其个数。
$dp[l][r]$ 表示 $[l, r]$ 内全部消除的最小次数，我们显然有以下转移：
$$\begin{cases}3 - num[l] & l = r \\
dp[l][k] + dp[k + 1][r] & l \leq k \lt r \\
dp[l + 1][r - 1] + \max\{0, \ \ 3 - num[l] - num[r]\} & c[l] = c[r]\end{cases}$$
然而还有一种转移：
$$dp[l + 1][k - 1] + dp[k + 1][r - 1], c[l] = c[r] = c[k], num[l] + num[r] \lt 4, num[k] = 1$$
如 $110010011$ 和 $10011001$ 消去任意一段 $0$ 后并上的 $1$ 就 $\geq 3$。
然后记忆化搜索就好了，时间复杂度 $O(n ^ 3)$
代码
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
|
#include <bits/stdc++.h>
namespace IO {
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}
template <typename T>
inline bool read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return false;
c == '-' ? iosig = true : 0;
}
for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
iosig ? x = -x : 0;
return true;
}
inline void read(char &c) {
while (c = read(), isspace(c) && c != -1)
;
}
inline int read(char *buf) {
register int s = 0;
register char c;
while (c = read(), isspace(c) && c != -1)
;
if (c == -1) {
*buf = 0;
return -1;
}
do
buf[s++] = c;
while (c = read(), !isspace(c) && c != -1);
buf[s] = 0;
return s;
}
const int OUT_LEN = 1000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
*oh++ = c;
}
template <typename T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
} else {
x < 0 ? (print('-'), x = -x) : 0;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void print(const char *s) {
for (; *s; s++) print(*s);
}
inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
struct InputOutputStream {
template <typename T>
inline InputOutputStream &operator>>(T &x) {
read(x);
return *this;
}
template <typename T>
inline InputOutputStream &operator<<(const T &x) {
print(x);
return *this;
}
~InputOutputStream() { flush(); }
} io;
}
namespace {
using IO::io;
const int MAXN = 200;
int f[MAXN + 1][MAXN + 1], num[MAXN + 1];
bool vis[MAXN + 1][MAXN + 1];
char s[MAXN + 1], ch[MAXN + 1];
int dp(int l, int r) {
register int &ret = f[l][r];
if (vis[l][r]) return ret;
vis[l][r] = true;
if (l == r) return ret = 3 - num[l];
if (ch[l] == ch[r]) {
ret = dp(l + 1, r - 1) + std::max(0, 3 - num[l] - num[r]);
if (num[l] + num[r] < 4) {
for (register int k = l + 2; k < r; k += 2) {
if (num[k] == 1) {
ret = std::min(ret, dp(l + 1, k - 1) + dp(k + 1, r - 1));
}
}
}
}
for (register int k = l; k < r; k++)
ret = std::min(ret, dp(l, k) + dp(k + 1, r));
return ret;
}
inline void solveCase() {
register int n = IO::read(s + 1);
register int cnt = 0;
memset(num, 0, sizeof(int) * (n + 1));
for (register int i = 1; i <= n; i++) {
if (s[i] != s[i - 1])
ch[++cnt] = s[i], num[cnt] = 1;
else
num[cnt]++;
}
for (register int i = 0; i <= cnt; i++) {
memset(f[i], 0x3f, sizeof(int) * (cnt + 1));
memset(vis[i], 0, sizeof(bool) * (cnt + 1));
}
io << dp(1, cnt) << '\n';
}
inline void solve() {
register int T;
io >> T;
while (T--) solveCase();
}
}
int main() {
solve();
return 0;
}
|
