AtCoder Beginner Contest 237

感觉这场质量还不错。

C - kasaka

给定一个字符串 \(S\) ,问是否可以在开头添加若干个 a 使得串变为回文串。

如果字符串开头 a 的个数比末尾 a 的个数多肯定无解。

否则问题等价于去掉开头和结尾的所有的 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
ll x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 1000007

char s[N];

int main() {
scanf("%s", s + 1);
int n = strlen(s + 1);
int x = 0, y = 0;
for (int i = 1; i <= n; ++i, ++x) if (s[i] != 'a') break;
for (int i = n; i; --i, ++y) if (s[i] != 'a') break;
if (x > y) {puts("No"); return 0;}
int L = x + 1, R = n - y;
for (int i = L; i <= R; ++i)
if (s[i] != s[R - (i - L)]) {puts("No"); return 0;}
puts("Yes");
return 0;
}

D - LR insertion

一个数列,开始只有 \(0\) ,对 \(i=1,2,\cdots,n\) 依次执行:

  • op[i] = L ,将 \(i\) 插入到 \(i-1\) 的左侧。
  • op[i] = R ,将 \(i\) 插入到 \(i-1\) 的右侧。

求最终的数列。

考虑按照 \(i\) 从大到小执行,容易发现操作等价于每次在开头或结尾添加数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 200007
#define pb push_back
#define pf push_front

string s;
deque<int> res;

int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n; cin >> n; res.pb(n);
cin >> s;
for (int i = n - 1; i >= 0; --i)
s[i] == 'L' ? res.pb(i) : res.pf(i);
for (auto x : res) printf("%d ", x);
return 0;
}

E - Skiing

\(n\) 个点每个点有一个点权 \(h_i\) ,以及 \(M\) 条有向边 \((u,v)\) :

  • \(h_u>h_v\) ,边权为 \(-(h_u-h_v)\) ;否则,边权为 \(2(h_u-h_v)\)

\(1\) 号点到所有点的最短路。

负权图不可以跑 Dijkstra ;又很容易构造出网格图卡掉 SPFA 。

一个把负权图变成正权图的方法:

  • 给每个点分配一个势能 \(d_i\) ,对于一条边 \(u\to v\) ,边权增加 \(d_u-d_v\) ,把所有边都变成非负权值。
  • \(s\)\(x\) 的最短路即 \(dis_x+d_x-d_s\)

本题中 \(h_i\) 恰好符合势能的要求,因此修改边权后运行 Dijkstra 即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
ll x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 200007

int n, m, tot, hd[N];

struct edge {int to, nxt, w;} e[N << 1];

inline void add(int u, int v, int w) {
e[++tot].to = v; e[tot].w = w;
e[tot].nxt = hd[u]; hd[u] = tot;
}

ll dis[N], h[N];

bool vis[N];

priority_queue<pair<ll, int> > q;

inline void dij(int u) {
memset(dis, 0x3f, sizeof(dis));
dis[u] = 0; q.push(make_pair(0, u));
while (!q.empty()) {
u = q.top().second; q.pop();
if (vis[u]) continue; vis[u] = 1;
for (int i = hd[u], v; i; i = e[i].nxt)
if (dis[v = e[i].to] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
q.push(make_pair(-dis[v], v));
}
}
}

int main() {
n = rd(); m = rd();
for (int i = 1; i <= n; ++i) h[i] = rd();
for (int i = 1, u, v, w; i <= m; ++i) {
u = rd(); v = rd();
if (h[u] < h[v]) swap(u, v);
add(u, v, 0); add(v, u, h[u] - h[v]);
}
dij(1);
ll ans = 0;
for (int u = 1; u <= n; ++u)
ans = max(ans, -(dis[u] + h[u] - h[1]));
printf("%lld\n", ans);
return 0;
}

F - |LIS| = 3

计数长度为 \(n\ (n\le 1000)\) ,每个位置是 \([1,m]\ (m\le 10)\) 中整数的数列个数,满足 LIS 长度不超过 \(3\)

比较经典的状态机 DP ,设 \(f[i][x][y][z]\) 表示长度为 \(i\) 的数列,长度为 \(1\) 的 LIS 结尾最小是 \(x\) ,长度为 \(2\) 的 LIS 结尾最小是 \(y\) ,长度为 \(3\) 的 LIS 结尾最小是 \(z\) 时的数列个数。

转移直接枚举第 \(i\) 个位置的数字即可,注意不能超过 \(z\) 。复杂度 \(\mathcal{O}(nm^4)\)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 1007
#define mod 998244353

int n, m, f[N][12][12][13];

#define min(x, y) ((x) > (y) ? (y) : (x))

int main() {
cin.tie(nullptr) -> sync_with_stdio(false);

cin >> n >> m;
for (int i = 1; i <= m; ++i) f[1][i][11][12] = 1;

for (int i = 1; i < n; ++i)
for (int a = 1; a <= m; ++a)
for (int b = a + 1; b <= 11; ++b)
for (int c = b + 1; c <= 12; ++c)
for (int j = 1; j <= min(c, m); ++j) {
int tara = min(a, j);
int tarb = (j > a ? min(b, j) : b);
int tarc = (j > b ? min(c, j) : c);
f[i + 1][tara][tarb][tarc] = (f[i + 1][tara][tarb][tarc] + f[i][a][b][c]) % mod;
}
int ans = 0;
for (int i = 1; i <= m; ++i)
for (int j = i + 1; j <= m; ++j)
for (int k = j + 1; k <= m; ++k)
ans = (ans + f[n][i][j][k]) % mod;
cout << ans;
return 0;
}

G - Range Sort Query

一个 \(n\) 的排列,\(q\) 次操作,每次对一个区间升序或降序排序。问 \(x\) 最终的位置。

因为只关心 \(x\) 的位置,所以将小于 \(x\) 的认为是 \(0\) ,大于 \(x\) 的认为是 \(2\) ,将 \(x\) 改为 \(1\)

区间排序就变成统计区间 \(0,1,2\) 的个数,然后进行至多三段的区间赋值,线段树即可。

另解 set 维护区间复杂度正确,每次操作最多带来 \(3\) 个区间,每个区间被遍历后一定会删除(除了两侧至多留下 \(2\) 个)。

注意维护 set 的时候不能查 \(l_i\ge L\) 的区间(第一段有可能找不到),所以要按 \(r_i\) 为第一关键字排序。

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 mt make_tuple
#define lb lower_bound
#define tri tuple<int, int, int>
#define R get<0>
#define L get<1>
#define V get<2>

set<tri> s;

int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, q, k;
cin >> n >> q >> k;
for (int i = 1, x; i <= n; ++i) {
cin >> x;
s.insert(mt(i, i, (x == k) + (x > k) * 2));
}
for (int i = 1, ty, l, r; i <= q; ++i) {
cin >> ty >> l >> r;
auto x = mt(l, 0, 0);
int cnt[3] = {0, 0, 0};
for (auto nw = s.lb(x); nw != s.end(); nw = s.lb(x)) {
auto y = *nw;
if (L(y) > r) break;
cnt[V(y)] += min(r, R(y)) - max(l, L(y)) + 1;
if (L(y) < l) s.insert(mt(l - 1, L(y), V(y)));
if (R(y) > r) s.insert(mt(R(y), r + 1, V(y)));
s.erase(nw);
}
if (ty == 1) {
for (int v = 0; v <= 2; l += cnt[v], ++v)
if (cnt[v]) s.insert(mt(l + cnt[v] - 1, l, v));
} else {
for (int v = 2; v >= 0; l += cnt[v], --v)
if (cnt[v]) s.insert(mt(l + cnt[v] - 1, l, v));
}
}
for (auto x : s)
if (V(x) == 1) {printf("%d\n", R(x)); break;}
return 0;
}

Ex - Hakata

给一个字符串 \(S\ (|S|\le 200)\),问最多能选出多少个回文子串,使得相互不包含。

首先有一个结论是:长度为 \(n\) 的串本质不同的回文子串不超过 \(n\) 个。

接下来回文子串之间的包含关系是一个偏序,根据 Dilworth 定理解最大反链即可。

定理细节和使用方法详见 Dilworth's Theorem - Colin's Blog

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
ll x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 207
#define pb push_back

string str, a[N];

set<string> s;

inline bool substr(int u, int v) {
for (int i = 0; i + a[v].length() <= a[u].length(); ++i) {
bool fl = true;
for (int j = 0; j < a[v].length(); ++j)
if (a[u][i + j] != a[v][j]) {fl = false; break;}
if (fl) return true;
}
return false;
}

vector<int> e[N];

int match[N], vis[N];

bool dfs(int u, int t) {
for (auto v : e[u])
if (vis[v] != t) {
vis[v] = t;
if (!match[v] || dfs(match[v], t)) {match[v] = u; return true;}
}
return false;
}

int main() {
cin >> str;
int n = str.length();
for (int l = 0; l < n; ++l)
for (int r = l; r < n; ++r) {
bool fl = true;
int len = r - l + 1;
for (int i = 1; i <= len; ++i)
if (str[l + i - 1] != str[r - i + 1]) fl = false;
if (fl) s.insert(str.substr(l, len));
}
int m = 0;
for (auto x : s) a[++m] = x;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= m; ++j)
if (i != j && substr(j, i)) e[i].pb(j);
int ans = m;
for (int i = 1; i <= m; ++i) ans -= dfs(i, i);
printf("%d\n", ans);
return 0;
}