noip模拟53
题解
Task 1 ZYB和售货机
并不知道自己的代码哪里错了，但是既然有更简单的方法就上吧
易得：有些物品的购买顺序构成了一个环，而环上的答案一定是取不全的，因此必须要断一条边。
如何断边？因为要让答案最大，所以选的边一定是最大的，要让损失最小，就把最大值最小的边换成第二小的（统计最大的边时都是比较从当前点向前连的边来保证换边后可以断环）
注意还要更新边权小于最大值但大于当前次大值的情况
Task 1 ZYB和售货机
然后进行DFS，走最大值的边，边DFS边统计答案，存储一下每个点属于哪个环，当dfs到已访问过且属于当前环时就把答案减去最小的(最大值-次大值)，若访问到不属于当前环的点就 return
代码
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
|
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 100010;
template <typename LDXIN>
LDXIN read() {
LDXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int n, ans;
// nxt cost sellPrice cnt
int f[maxn], c[maxn], d[maxn], a[maxn], w[maxn];
int mx[maxn], mmx[maxn];
int vis[maxn], cnt;
int dlt;
void dfs(int id) {
if (vis[id]) {
if (vis[id] == cnt) {
ans -= dlt;
return;
} else {
return;
}
}
vis[id] = cnt;
if (!mx[id]) return;
ans += 1ll * w[mx[id]] * a[id];
dlt = min(dlt, w[mx[id]] - w[mmx[id]]);
if (mx[id] != id) dfs(mx[id]);
}
int main() {
n = read<int>();
For(i, 1, n) {
f[i] = read<int>();
c[i] = read<int>();
d[i] = read<int>();
a[i] = read<int>();
}
For(i, 1, n) {
w[i] = d[f[i]] - c[i];
if (w[i] > w[mx[f[i]]]) {
mmx[f[i]] = mx[f[i]];
mx[f[i]] = i;
} else {
if (w[i] > w[mmx[f[i]]]) mmx[f[i]] = i;
}
}
For(i, 1, n) {
if (!vis[i]) {
dlt = 0x3f3f3f3f, cnt++;
dfs(i);
}
}
cout << ans << endl;
return 0;
}
|
Task2 ZYB玩字符串
注意：
用string时不要直接复制，会导致size和length变为0，建议使用push_back
Task2 ZYB玩字符串
先说暴力：
操作就是枚举每一个字串，暴力查找，暴力删除，但与查找顺序有关
正着查找能拿30分，倒着查找能拿50分。比如说 ababaa 这个串，正着查删完会变成 baa 显然不对。这个串反过来又可以干灭倒着查找的方法，所以朴素的暴力不对。
Task2 ZYB玩字符串
正解:
统计原串中每个字母出现的次数，然后和暴力一样先枚举长度，长度一定是原串长的约数（优化×1）再用每个字母出现的次数除以长度得出可能的子串中各字母的个数（优化×2，不能整除，优化×3，跳过字母个数不满足要求的字串），然后用一个dp来确定这个字串是否合法。因为尽管子串（它组成了原串）可能被断成若干节，但夹在其中的每一段都是可以消掉的。
Task2 ZYB玩字符串
DP:
用$f_{i, j}$表示**原串**的区间$[i, j]$是否合法，如果$j - i + 1$为$len$的倍数，就表示能否消掉。若有剩余，则剩余的一定需要是子串的前缀。
转移
考虑第j个字符，分两种情况
$f_{i, j}|=f_{i, j-1}&[a_j=prefix(j - i) % len+1]$
$f_{i, j}|=f_{i, j-k*len}&f_{i-k*len+1, j}(k*len<length(子串))$
代码
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
|
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 1001;
template <typename LDXIN>
LDXIN read() {
LDXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
using namespace std;
map<string, int> vis;
char a[maxn], sb[maxn];
int f[maxn][maxn], bukkit[26], bkt[26], cnt[26], sl, len;
int chk(int llen) {
for (int i = 1; i <= sl; i++) f[i][i] = (sb[1] == a[i]);
for (int len = 2; len <= sl; len++) {
char c = sb[(len - 1) % llen + 1];
for (int l = 1; l <= sl - len + 1; l++) {
int r = l + len - 1;
f[l][r] = f[l][r - 1] & (a[r] == c);
for (int k = 1; k * llen <= len && !f[l][r]; k++)
f[l][r] |= (f[l][r - k * llen] & f[r - k * llen + 1][r]);
}
}
return f[1][sl];
}
string ans;
int main() {
freopen("string.in", "r", stdin);
int T;
T = read<int>();
while (T--) {
scanf("%s", a + 1);
Set(bkt, 0);
vis.clear();
sl = strlen(a + 1);
For(i, 1, sl) bkt[a[i] - 'a']++;
|
代码
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
|
for (len = 1; len <= sl; len++) {
if (sl % len) continue;
memcpy(bukkit, bkt, sizeof(bkt));
int num = sl / len, ok = 1;
For(i, 0, 25) {
if (bukkit[i] % num) {
ok = 0;
break;
}
}
if (!ok) continue;
For(i, 0, 25) bukkit[i] /= num;
bool getAns = 0;
for (int i = 1; i <= sl - len + 1; i++) {
memcpy(cnt, bukkit, sizeof(bukkit));
ok = 1;
Set(sb, 0);
for (int k = 0; k < len; k++) {
sb[k + 1] = a[i + k];
if (cnt[sb[k + 1] - 'a'] - 1 < 0) {
ok = 0;
break;
} else {
cnt[sb[k + 1] - 'a']--;
}
}
if (!ok) continue;
string cur = (string)(sb + 1);
if (vis[cur]) continue;
vis[cur];
if (chk(len)) {
if (!getAns) {
ans = cur;
getAns = 1;
} else {
if (cur < ans) {
ans = cur;
}
}
}
}
if (getAns) break;
}
cout << ans << endl;
}
}
|
Task 3 午餐
这道题是个最短路……
考场上码了164行，把没学会的尽量往前放，把学会了的尽量往后放，喜提10分高分。为什么错？
因为一定是越早学会越好（就能越早教给后面的人），按我考场上的操作来的话可能有的人原本能学会却没有时间学会（例子，小A的区间是[5, 7]，小B的区间是[4, 6]，让小A在第7天恰饭导致原本能学会的小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
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
155
156
157
158
159
160
161
162
163
164
|
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 10010;
template <typename LDXIN>
LDXIN read() {
LDXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
struct INFO {
int with, l, r, id;
};
vector<INFO> p[maxn];
vector<int> unknown;
bool used[maxn];
int known[maxn], occu[maxn];
int type[maxn], ans[maxn];
int n, m, nowday;
int main() {
freopen("lunch.in", "r", stdin);
freopen("lunch.out", "w", stdout);
n = read<int>();
m = read<int>();
For(i, 1, m) {
int a, b, x, y;
a = read<int>();
b = read<int>();
x = read<int>();
y = read<int>();
p[a].push_back((INFO){b, x, y, i});
p[b].push_back((INFO){a, x, y, i});
}
For(i, 1, n) {
type[i] = read<int>();
if (type[i] == 1) {
if (known[i] < 0) {
cout << "Impossible" << endl;
return 0;
}
known[i] = 1;
bool fnd = 0;
for (auto fk : p[i]) {
if (!used[fk.id]) {
known[fk.with] = 1;
Fordown(d, fk.r, fk.l) {
if (occu[d] == 0 || occu[d] == 1) {
occu[d] = 1;
ans[fk.id] = d;
fnd = 1;
break;
}
}
if (!fnd) {
cout << "Impossible" << endl;
}
used[fk.id] = 1;
}
}
} else {
if (type[i] == -1) {
if (known[i] > 0) {
cout << "Impossible" << endl;
return 0;
}
known[i] = -1;
for (auto fk : p[i]) {
if (!used[fk.id]) {
known[fk.with] = -1;
bool fnd = 0;
For(d, fk.l, fk.r) {
if (occu[d] == 0 || occu[d] == -1) {
occu[d] = -1;
fnd = 1;
ans[fk.id] = d;
break;
}
}
if (!fnd) {
cout << "Impossible" << endl;
return 0;
}
used[fk.id] = 1;
}
}
} else {
if (known[i] == 0) unknown.push_back(i);
}
}
}
for (auto i : unknown) {
cout << "UKN: " << i << endl;
bool ha = 0;
for (auto fk : p[i]) {
if (!used[fk.id]) {
if (known[fk.with] != 0) {
known[i] = known[fk.with];
For(d, fk.l, fk.r) {
if (occu[d] == known[i] || occu[d] == 0) {
occu[d] = known[i];
ans[fk.id] = d;
}
}
ha = 1;
break;
}
}
}
if (!ha) {
int nt = 3;
for (auto fk : p[i]) {
if (!used[fk.id]) {
int type = 0;
For(d, fk.l, fk.r) {
if (occu[d] == 0 || type == 3) {
type = 3;
break;
}
if (occu[d] == -1) {
type |= 1;
}
if (occu[d] == 1) {
type |= 2;
}
}
if (type & nt == 0) {
cout << "Impossible" << endl;
return 0;
} else {
nt = nt & type;
}
}
if (nt == 1)
known[i] = -1;
else
known[i] = 1;
for (auto fk : p[i]) {
For(d, fk.l, fk.r) {
if (occu[d] == 0 || occu[d] == known[i]) {
known[fk.with] = known[i];
ans[fk.id] = d;
}
}
}
}
}
cout << known[3] << ' ' << known[4] << endl;
}
For(i, 1, m) { cout << ans[i] << endl; }
return 0;
}
|
Task 3 午餐
如何保证可行性？
开一个$low$数组表示某个人最早在什么时间能学会，对于一条边而言（起点from，终点to），如果$low[from] \gt r$，则表明在当前区间内$from$这个人还没学会，所以$low[to]$只能是$l + 1$。如果$low[from] \le r$那么吃饭的时间可以安排在$r$，不限制$to$让$to$教$from$。所以把所有不会的人的初值都赋为0x3f，然后跑最长路。
再开一个数组$tme$表示一个点何时可以学会，点1的值为0。接着跑最短路，每个点在$L, tme[from], low[to]$之间取$max$，并保证最大值小于$R$
代码
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
|
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 201001;
template <typename LDXIN>
LDXIN read() {
LDXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
struct EDGE {
int to, nxt, l, r, from;
} edge[maxn * 2];
int head[maxn], tote;
void addEdge(int from, int to, int l, int r) {
edge[++tote].to = to;
edge[tote].from = from;
edge[tote].nxt = head[from];
edge[tote].l = l;
edge[tote].r = r;
head[from] = tote;
}
int n, m;
int known[maxn], low[maxn], tme[maxn];
struct knode {
int id, dis;
bool operator<(knode k) const { return dis > k.dis; }
};
struct uknode {
int id, dis;
bool operator<(uknode k) const { return dis < k.dis; }
};
priority_queue<knode> kq;
priority_queue<uknode> ukq;
int u[maxn], v[maxn], l[maxn], r[maxn];
int main() {
freopen("lunch.in", "r", stdin);
freopen("lunch.out", "w", stdout);
n = read<int>();
m = read<int>();
For(i, 1, m) {
u[i] = read<int>();
v[i] = read<int>();
l[i] = read<int>();
r[i] = read<int>();
addEdge(u[i], v[i], l[i], r[i]);
addEdge(v[i], u[i], l[i], r[i]);
}
For(i, 1, n) { known[i] = read<int>(); }
|
代码
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
|
For(i, 1, n) {
if (known[i] == -1) {
low[i] = 0x3f3f3f3f;
ukq.push((uknode){i, low[i]});
}
}
// LP
while (!ukq.empty()) {
auto fnt = ukq.top();
ukq.pop();
int id = fnt.id;
int dis = fnt.dis;
for (int i = head[id]; i; i = edge[i].nxt) {
int to = edge[i].to;
if (dis > edge[i].r && edge[i].l + 1 > low[to]) {
low[to] = edge[i].l + 1;
ukq.push((uknode){to, low[to]});
}
}
}
if (low[1]) {
puts("Impossible");
return 0;
}
Set(tme, 0x3f);
tme[1] = 0;
kq.push((knode){1, 0});
// SP
while (!kq.empty()) {
auto fnt = kq.top();
kq.pop();
int id = fnt.id;
int dis = fnt.dis;
for (int i = head[id]; i; i = edge[i].nxt) {
int to = edge[i].to;
int mx = max(edge[i].l, max(dis, low[to]));
if (mx < tme[to] && mx <= edge[i].r)
tme[to] = mx, kq.push(knode{to, tme[to]});
}
}
For(i, 1, n) {
if (known[i] == 1 && tme[i] == 0x3f3f3f3f) {
puts("Impossible");
return 0;
}
}
for (int i = head[1]; i; i = edge[i].nxt) {
int to = edge[i].to;
if (known[to] == -1) {
puts("Impossible");
return 0;
}
}
For(i, 1, m) {
int ans = (max(tme[u[i]], tme[v[i]]) > r[i])
? l[i]
: max(l[i], max(tme[u[i]], tme[v[i]]));
printf("%d\n", ans);
}
return 0;
}
|
Task 4 计数
设$dp[i][j]$表示前续遍历编号为$[i, j]$的点能构成的子树种类数，直接枚举$i, j$再枚举$k$, $i \leq k \leq j$，如果满足要求则$dp[i][j]+=dp[i + 1][k]*dp[k + 1][j]$
要求：
-
$[i+1,k]$的任何一个点中序遍历都不能在$[k+1,j]$ 以后
-
$[i+1,k]$的任何一个点中序遍历都不能在$i$以后
-
$i$的中序遍历都不能在$[k+1,j]$以后
然后算个2维前缀和，如果非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
|
For(i, 1, m) {
q[i].u = read<int>();
q[i].v = read<int>();
hv[q[i].u][q[i].v] = 1;
}
For(i, 1, n) {
For(j, 1, n) {
mat[i][j] =
hv[i][j] + mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
}
}
For(i, 1, n) { dp[i][i] = 1; }
For(sz, 1, n) {
for (int i = 1; i + sz <= n; i++) {
int j = i + sz;
if (!getSum(i, i + 1, i, j)) dp[i][j] += dp[i + 1][j];
if (!getSum(i + 1, i, j, i)) dp[i][j] += dp[i + 1][j];
For(k, i, j) {
if (!getSum(k + 1, i + 1, j, k) && !getSum(k + 1, i, j, i) &&
!getSum(i, i + 1, i, k)) {
dp[i][j] += dp[i + 1][k] * dp[k + 1][j];
}
dp[i][j] %= mod;
}
}
}
|