这场没打，后续补的时候发现题其实都很trivial~
C
题目大意：目前有 $n$ 篇博客，在第 $i$ 篇博客中提到的用户分别为 $a_{i,1},\ldots,a_{i,l_i}$ 。
现在要修改这 $n$ 篇博客的发布顺序，给定一个序列 $Q$ ，当某篇未发布的博客发布的时候，依次遍历它提到的用户，当遍历到用户 $x$ 时，若它不在 $Q$ 中，则提到 $Q$ 的最前面，反之则删除它本来在的地方并提到 $Q$ 的最前面。
现在，请你求出字典序最小的 $Q$ 。
数据范围： $1 \leq n \leq 3000, 1\leq l_i \leq 3000, 1 \leq sum(n) \leq 3000, 1 \leq \sum\limits_{i=1}^{n}l_i \leq 3000$ 。
思路：这个贪心其实蛮难的，首先容易注意到应该从各个博客的结尾出发倒序遍历，越小的记号越晚出现最好。
随后，考虑从前到后遍历，由于我们可以接受 $O(n^2)$ 的复杂度，因此直接考虑在当前取完的博客的前提下，应该取怎样的下一篇博客，从而慢慢从局部最优到全局最优，这是一个很有启发性的思路。
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
|
void solve() {
int n;
cin >> n;
vi l(n);
vvi a(n);
rep(i, 0, n - 1) {
cin >> l[i];
a[i].resize(l[i]);
rep(j, 0, l[i] - 1) cin >> a[i][j];
}
vi res;
set<int> s;
deque<int> d;
vector<bool> vis(n, false);
rep(i, 0, n - 1) {
vi tem;
vi tem2;
int idx = -1;
rep(j, 0, n - 1) {
if (vis[j]) continue;
tem.clear();
set<int> s1;
frep(v, sz(a[j]) - 1, 0) {
if (s.count(a[j][v]) || s1.count(a[j][v])) continue;
tem.push_back(a[j][v]);
s1.insert(a[j][v]);
}
if (tem.empty()) continue;
if (tem2.empty() || tem < tem2) {
tem2 = tem;
idx = j;
}
}
if (idx == -1) break;
vis[idx] = true;
rep(j, 0, sz(tem2) - 1) {
if (!s.count(tem2[j])) {
d.push_back(tem2[j]);
s.insert(tem2[j]);
}
}
}
while (!d.empty()) {
auto node = d.front();
d.pop_front();
res.push_back(node);
}
for (int& p : res) cout << p << ' ';
cout << endl;
return;
}
|
D
题目大意：给定一个长度为 $n$ 的排列 $a$ ，我们定义具有以下性质的数组 $b$ 为酷数组，如果不存在 $b_i=\mathrm{max}(b_{i-1},b_i,b_{i+1})$ 。
现在对于 $a$ ，如果存在 $a_i=\mathrm{max}(a_{i-1},a_i,a_{i+1})$ ，则可以删除 $a_{i-1}$ 或者 $a_{i+1}$ ，求要变为酷数组所需要的最少步数。
数据范围： $3 \leq n \leq 5 \cdot 10^5$ 。
思路：下面我们先介绍一种叫做笛卡尔树的数据结构，它可以成为我们在完成单调栈题目时的轮椅。
这棵树的每个节点有两个属性，一个是它在原数组中的下标，一个是它的值。
同时，这棵树关于原数组的下标形成一棵BST，因此它的中序遍历结果就是原数组，且这棵树的每棵子树都关于值形成大根堆/小根堆，于是它的左子树就是往左边延伸小于/大于它的值，右边亦然。
是不是想到了接雨水、最大矩形等题目？是的，它对单调栈贡献法的题目有奇效，哈哈，非常神奇吧~
回到原题，这玩意到底有什么用？
首先观察到一个性质，就是最大的数一定要移到最左边或者最右边，于是对于笛卡尔树，就要舍弃当前节点的左子树或者右子树，以此类推，最后剩下的元素就是从根节点到叶子节点的节点数。
于是，要使剩下的节点数最大，那么就是树的深度，因此答案为 $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
|
// 笛卡尔树，默认为大根堆
template <class T, typename Compare = std::greater<T>>
struct CartesianTree {
T inf = std::numeric_limits<T>::max();
struct Node {
int idx; // 原数组下标
T val; // 权值
int par, siz; // 父节点索引，子树大小
std::array<T, 2> son; // 左儿子，右儿子
Node(int idx = 0, T val = 0, int par = 0, int siz = 0) : idx(idx), val(val), par(par), siz(siz), son{} {}
};
std::vector<Node> t;
CartesianTree() { init(); }
void init(Compare comp = Compare()) {
t.assign(1, {0, 0, 0});
t[0].son.fill(0);
if (comp(-inf, inf))
t[0].val = -inf;
else
t[0].val = inf;
} // 自动建立虚拟节点
void add(int idx, T val, int par = 0) { t.emplace_back(idx, val, par); } // 负责把元素加进末尾，需要使用1-based
int work(Compare comp = Compare()) {
for (int i = 1; i < t.size(); i++) {
int k = i - 1;
while (comp(t[i].val, t[k].val)) k = t[k].par;
t[i].son[0] = t[k].son[1];
t[k].son[1] = i;
t[i].par = k;
t[t[i].son[0]].par = i;
} // 遍历，砍树枝
auto dfs = [&](auto&& dfs, int u) -> void {
if (!u) return;
t[u].siz = 1;
dfs(dfs, ls(u));
dfs(dfs, rs(u));
t[u].siz += t[ls(u)].siz + t[rs(u)].siz;
}; // 进行一个dfs
dfs(dfs, t[0].son[1]);
return t[0].son[1];
}
int depth() {
int ans = 0;
auto dfs = [&](auto&& dfs, int u, int d) -> void {
if (!u) return;
ans = max(ans, d);
dfs(dfs, ls(u), d + 1);
dfs(dfs, rs(u), d + 1);
return;
};
dfs(dfs, t[0].son[1], 1);
return ans;
}
int Left(int p) { return p - size(ls(p)); } // 左边最远
int Right(int p) { return p + size(rs(p)); } // 右边最远
int size(int p) { return t[p].siz; }
int ls(int p) { return t[p].son[0]; }
int rs(int p) { return t[p].son[1]; }
int par(int p) { return t[p].par; }
};
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
CartesianTree<int> tree;
int ans = 0;
rep(i, 0, n - 1) { tree.add(i + 1, a[i]); }
int root = tree.work();
cout << n - tree.depth() << endl;
return;
}
|
当然，此处还有一种参考朋友的做法，显而易见的是最后的数组必然形成先递减后递增的结构（如果只有递减或者只有递增，则视为退化后的）。
于是，可以进行前后缀分解，枚举当前谷底，并取最值。
但是，这里要注意的是，某一端的贡献必须使用单调栈来做而不是 LIS ，因为可以从题目读出，这里采用的是两个小数吃掉一个大数的机制。
Kita3’s submission
E
题目大意：给定一个大小为 $m$ 的数组 $a$ ，现在需要对它进行一次以下操作：
将它划分为若干个子段，然后每个子段分别反转。
现在给定一个数组 $T$ ，问能通过上述操作转变为 $T$ 的数组个数，并模998244353。
数据范围： $1 \leq n \leq 8000, 1 \leq T_i \leq 8000$ 。
思路：看到这个题目马上就想到可能是DP，哈哈哈。
随后，对于重复计数问题，最关键的就是要找到怎么样才是重复的，通过画图发现如果 $[l1,r1] \cup [r1+1,r2]$ 翻转后的效果与 $[l1,r2]$ 一样，则 $[l1,r2]$ 的 border 长度必然大于0。
于是，显然需要使用 KMP 算法在 $O(n^2)$ 复杂度下求出任意子串的border ，然后使用 $O(n^2)$ 的DP，如果当前子串的 border 长度大于0则不发生转移，结束了。
非常trivial的一道题，体感比D简单~
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
|
const int MOD = 998244353;
vector<int> kmp(const vi& pattern) {
int m = pattern.size();
vector<int> pi(m);
int cnt = 0;
for (int i = 1; i < m; i++) {
int b = pattern[i];
while (cnt && pattern[cnt] != b) cnt = pi[cnt - 1];
if (pattern[cnt] == b) cnt++;
pi[i] = cnt;
}
return pi;
}
void solve() {
int n;
cin >> n;
vi a(n);
vvi border(n + 1);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) {
vi tem(a.begin() + i, a.end());
auto tem2 = kmp(tem);
border[i + 1] = tem2;
}
vi dp(n + 1);
dp[0] = 1;
rep(i, 1, n) {
rep(j, 0, i - 1) {
if (border[j + 1][i - j - 1])
continue;
else {
dp[i] += dp[j] % MOD;
dp[i] %= MOD;
}
}
}
cout << dp[n] << endl;
return;
}
|
