[ABC312] 题解 [D~Ex]
D - Count Bracket Sequences
一个括号序列 \(s\) 包含 (, ), ?，? 可以填任意括号，问你填完后有多少种合法序列方式。
这是一个 Classical 的 括号序列 DP，使用这个状态表示可以解决很多括号序列问题：
\(dp[i][j]\) 表示已经摆好了前 \(i\) 个字符，有 \(j\) 个没有匹配的左括号的方案数。
\[dp[i][j] = \left\{\begin{matrix} dp[i - 1][j - 1]&, s[i] = ( \\ dp[i - 1][j + 1]&, s[i] = )\\ dp[i - 1][j - 1] + dp[i - 1][j + 1]&,s[i] = ? \end{matrix}\right. \]if(s[1] == '(') dp[1][1] = 1;
if(s[1] == ')') return cout << 0 << '\n', 0;
if(s[1] == '?') dp[1][1] = 1;
for(int i = 2; i <= n; i ++) {
for(int j = 0; j <= n; j ++) {
if(s[i] == '?') {
if(j > 0) dp[i][j] = dp[i - 1][j - 1];
dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % mod;
}
if(s[i] == ')') dp[i][j] = dp[i - 1][j + 1];
if(s[i] == '(' && j > 0) dp[i][j] = dp[i - 1][j - 1];
}
}
cout << dp[n - 1][0] << '\n';
E - Tangency of Cuboids
观察到 \(M\le 100\rightarrow M^3\le 10^6\)，考虑每一个单位格子。
由于立方体不相交，所以一个单位格子最多属于一个立方体，枚举每一个单位格子的四周，如果有一个单位格子的四周有单位格子属于不同的立方体，那么这两个立方体有相同的面。
所以直接枚举即可，时间复杂度：\(O(N + M^3)\)。
#include <iostream>
#include <set>
using namespace std;
const int N = 100 + 10, M = 1e5 + 10;
set<int> s[M];
int dx[] = {1, 0, 0}, dy[] = {0, 1, 0}, dz[] = {0, 0, 1}, n, a[N][N][N]; // 等价于六个方向
signed main()
{
cin >> n;
for(int y = 1; y <= n; y ++) {
int x1, y1, z1, x2, y2, z2;
cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
for(int i = x1 + 1; i <= x2; i ++)
for(int j = y1 + 1; j <= y2; j ++)
for(int k = z1 + 1; k <= z2; k ++)
a[i][j][k] = y;
}
for(int i = 1; i <= 100; i ++)
for(int j = 1; j <= 100; j ++)
for(int k = 1; k <= 100; k ++)
for(int p = 0; p < 3; p ++)
if(a[i][j][k] && a[i + dx[p]][j + dy[p]][k + dz[p]] && a[i][j][k] != a[i + dx[p]][j + dy[p]][k + dz[p]])
s[a[i][j][k]].insert(a[i + dx[p]][j + dy[p]][k + dz[p]]),
s[a[i + dx[p]][j + dy[p]][k + dz[p]]].insert(a[i][j][k]);
for(int i = 1; i <= n; i ++)
cout << s[i].size() << '\n';
return 0;
}
F - Cans and Openers
首先贪心地把所有免费的 all in，然后尝试用开罐器+普通罐替换最劣的拉环罐，这样枚举一定可以找到最优解，代码丑，不放了。
也可以枚举要用几个开罐器，然后二分能够替换多少个普通罐。
时间复杂度：\(O(N\log N)\)。
G - Avoid Straight Line
第一次正赛切 G。
首先容斥，考虑有多少个三元组在同一条路径上，这种三元组计数问题一般枚举中间点，答案的贡献来源有二：
- 子树内节点与子树外节点组合；
- 不相同子树的两个子节点组合；
第一个乘法原理很好做，第二个情况考虑前缀和，时间复杂度：\(O(N)\)。
// Problem: G - Avoid Straight Line
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-07-29 21:03:34
#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n;
vector<int> g[N];
int sz[N];
int ans;
void dfs(int u, int fa)
{
sz[u] = 1;
for(int v : g[u])
{
if(v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
}
sz[1] = n;
ans -= (sz[u] - 1) * (n - sz[u]);
int sum = 0;
for(int v : g[u])
{
if(v == fa) continue;
ans -= sz[v] * sum;
sum += sz[v];
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1, a, b; i < n; i ++)
{
cin >> a >> b;
g[a].push_back(b), g[b].push_back(a);
}
ans = n * (n - 1) * (n - 2) / 6;
dfs(1, 1);
cout << ans << '\n';
return 0;
}
Ex - snukesnuke
考虑每一个字符串的最小循环节，可以发现，如果两个字符串的最小循环节都不相同，那么无论如何它们两个都不会出现冲突，所以可以把每一种循环节单独处理，对于每一种循环节可以使用一个倍增的数组 \(f\)，\(f_i\) 表示当前循环节，循环了 \(i\) 次的字符串至少需要多少次操作能够合法，遍历的时候直接暴力跳即可，发现计算次数是调和级数，所以时间复杂度为：\(O(n\log n)\)，但是标记每个点是否被选取需要用 std::set，所以实际时间复杂度为：\(O(n\log^2 n)\)。
// Problem: Ex - snukesnuke
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-07-30 19:05:10
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <unordered_map>
// #define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int n, ne[N];
unordered_map<string, int> h;
int idx;
int get(string s) {if(!h.count(s)) h[s] = ++ idx; return h[s];}
vector<PII> cir[N];
string s[N];
int Max[N];
void kmp(int x)
{
int n = s[x].size();
for(int i = 1, j = 0; i < n; i ++) {
while(j && s[x][i] != s[x][j]) j = ne[j - 1];
if(s[x][i] == s[x][j]) j ++;
ne[i] = j;
}
int id = get(s[x].substr(0, ((n % (n - ne[n - 1])) ? n : n - ne[n - 1])));
cir[id].push_back({n, x});
Max[id] = max(Max[id], n);
}
int ans[N], f[N];
set<int> st;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> s[i];
for(int i = 1; i <= n; i ++)
kmp(i);
for(int i = 1; i <= idx; i ++) {
for(int j = 1; j <= Max[i]; j ++)
f[j] = 1;
st.clear();
st.insert(0);
for(auto [len, id] : cir[i]) {
while(st.find(f[len] * len) != st.end()) f[len] ++;
st.insert(f[len] * len), ans[id] = f[len];
}
}
for(int i = 1; i <= n; i ++)
cout << ans[i] << ' ';
cout << '\n';
return 0;
}