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;
}