## 密文板
#贪心 #构造
这题看起来就很像贪心构造答案。
首先我们把可以匹配的左右括号都先匹配上，具体思路是从左往右枚举，对于每个右括号，如果左边有还没有匹配的左括号，那么就匹配上。
接下来考虑一个问号和一个括号匹配。一种是问号和右括号匹配。由于和上面进行初始匹配一样都需要枚举右括号，所以可以一起处理。然后是左括号和问号匹配，正着或反着枚举均可，但是正着枚举必须选大于当前下标的最小下标的问号，反着则不需要。
由于我们有些左括号已经在之前跟右括号匹配了，而这里和问号匹配当然是越靠左越好。所以最开始我们找和右括号匹配的左括号需要优先选下标更大的（栈实现），这样才使得在可以留下左括号的情况下，左括号都尽量靠左，可以与更多右边的问号匹配。
最后是剩下的问号自己和自己匹配。按照下标从小到大的顺序一左一右即可。
维护所有的问号我是用了 set。可以快速找小于/大于某个下标的问号，并且支持删除。时间复杂度 $\mathcal O(n\log_2 n)$。
```cpp
#include <fstream>
#include <stack>
#include <set>
using namespace std;
const int kMaxN = 1e5 + 5;
ifstream cin("cipher.in");
ofstream cout("cipher.out");
int f[kMaxN], t, n;
set<int> s;
stack<int> q;
char a[kMaxN];
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n >> a;
for (int i = n; i >= 1; i--) {
a[i] = a[i - 1];
}
fill(f + 1, f + n + 1, 0);
for (; q.size(); q.pop()) { }
s.clear();
int ans = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == '?') {
s.insert(i);
}
}
for (int i = 1; i <= n; i++) {
if (a[i] == '(') {
q.push(i);
} else if (a[i] == ')') {
if (q.size()) {
f[q.top()] = f[i] = 1;
q.pop();
ans++;
continue;
}
auto p = s.lower_bound(i);
if (p != s.begin()) {
p--;
f[*p] = f[i] = 1;
a[*p] = '(';
s.erase(p);
ans++;
}
}
}
for (int i = n; i >= 1; i--) {
if (a[i] == '(' && !f[i]) {
auto p = s.upper_bound(i);
if (p != s.end()) {
s.erase(p);
a[*p] = ')';
ans++;
}
}
}
bool b = 1;
for (int i : s) {
a[i] = b ? '(' : ')';
ans += !b;
b ^= 1;
}
cout << n - 2 * ans << '\n' << (a + 1) << '\n';
}
return 0;
}
```
## 括号序列
#状压dp #二分 #前缀和
首先看到 $n\le 20$，这很有可能是状压的题目。然后再看到括号序列，那我们就可以构建一个前缀和数组，左括号减一右括号加一，对于一段前缀和都不小于 $0$ 的前缀，有多少个 $0$ 就代表着有多少个合法括号串前缀。
然后我就设计出了状态：$dp_{i,j}$ 表示若 $n$ 个串的已选状态为 $i$，最后的前缀值为 $j$ 所能获得的最大答案。当时我觉得这个状态会炸，因为 $j$ 的取值特别多，但是实际上 $j$ 只有一种取值，即 $i$ 包含的所有 $s_i$ 的前缀和值相加的和。不过我赛时还是写了个 `map` 就是了。
枚举已选状态 $i$ 之后，再枚举新的要选的 $j$。如何判断拼上 $j$ 了之后是否存在一段前缀和小于 $0$ 呢？可以对每个串的前缀和值再做一个前缀 $\min$，这样就可以快速判断整个串。如果整个串拼上来不会导致有小于 $0$ 的，那么就可以直接转移 dp。
对于有小于 $0$ 的，拼完这一段继续拼任何东西都不会有任何加成了。所以我们通过那个前缀 $\min$ 的数组做二分，找到最大的 $p$ 使得前 $p$ 个数都不会导致前缀值变到负数。二分完我们还需要求一个前缀当中有多少个指定的数。每个字符串开 $2\times|s_i|+1$ 个 `vector` 存前缀值所对应的下标（要加偏移量应对负数），在下标 `vector` 上二分即可。
时间复杂度 $\mathcal O\left(2^n\left(n+\sum\limits_{i=1}^n\log|s_i|\right)\right)$。当然我瞎写了 `map` 常数较大。
- [!] 注意查询一定要判越界，这就是我在初测是挂 $60$ 分的原因。
- [c] 一个悲伤的故事是，由于我把 `<fstream>` 的 `f` 写成了大写 `F` 直接导致我这题在 Linux 上 CE 保灵。**警钟长鸣🔔**
```cpp
#include <fstream> // 不要写成 Fstream
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int kMaxN = 21;
ifstream cin("seq.in");
ofstream cout("seq.out");
int n, ans;
string s[kMaxN];
vector<int> p[kMaxN], m[kMaxN];
vector<vector<int>> v[kMaxN];
map<int, int> dp[1 << kMaxN];
vector<int> &get(int i, int j) {
static vector<int> empty;
if (j + s[i].size() < 0 || j + s[i].size() >= v[i].size()) { // 越界
return empty;
}
return v[i][j + s[i].size()];
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
int pre = 0, mn = 1e9;
p[i].reserve(s[i].size());
m[i].reserve(s[i].size());
v[i].resize(2 * s[i].size() + 1);
for (int j = 0; j < s[i].size(); j++) {
pre += (s[i][j] == '(' ? 1 : -1);
mn = min(mn, pre);
p[i].push_back(pre);
m[i].push_back(mn);
get(i, pre).push_back(j);
}
}
dp[0][0] = 0;
for (int i = 0; i < (1 << n); i++) {
for (const auto &j : dp[i]) {
for (int k = 1; k <= n; k++) {
if (i & (1 << (k - 1))) {
continue;
}
if (j.first + m[k].back() >= 0) {
int &x = dp[i | (1 << (k - 1))][j.first + p[k].back()];
int val = j.second + get(k, -j.first).size();
x = max(x, val);
ans = max(ans, val);
continue;
}
int p = -1;
for (int l = 0, r = s[k].size() - 1; l <= r; ) {
int mid = (l + r) / 2;
if (j.first + m[k][mid] >= 0) {
p = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (p != -1) {
auto x = get(k, -j.first);
int val = upper_bound(x.begin(), x.end(), p) - x.begin();
ans = max<int>(ans, j.second + val);
}
}
}
}
cout << ans << '\n';
return 0;
}
```
## 法国
#暴力 #数学
记 $a=att,b=hp,A=Att,B=Hp$.
首先我们看到这个式子 $\sum\limits_{i=1}^k\left\lceil\cfrac{b_i}{A_q}\right\rceil a_i\ge B_q$。我靠，怎么这么复杂，而且随着 ${} q$ 的增大，$A_q$ 会增大，这个分数会变小这也太难维护了吧？但是仔细想想，分子 $b_i$ 是固定的，分母单调递增，而一个数 $x$ 除以任意正数（上或下取整均可），不同的答案它的量级貌似是 $\mathcal O\left(\sqrt x\right)$ 级别的（实测 ${} x=3\times 10^5 {}$ 时大约有 $1000$ 个），所以我们只需要在分数 $\left\lceil\cfrac{b_i}{A_q}\right\rceil$ 的值发生变化是重新计算贡献即可。这样子时间复杂度就是 $\mathcal O(n\sqrt V)$ 的了，完全可行。
现在我们考虑当 $A_q$ 增大到多少的时候分数值会发生改变，即解关于 $x$ 的方程 $\left\lceil\cfrac{a}{x}\right\rceil<b$。根据赤石的推导，可以得到 ${} x\ge\left\lceil\cfrac{a}{b-1}\right\rceil {}$，这里 $a=b_i,b=\left\lceil\cfrac{b_i}{A_q}\right\rceil$。所以当到后面最小的满足 $A_q\ge x$ 的地方，分数值才会改变。
由于本题值域只有 $3\times 10^5$，所以我们直接把 $x$ 当下标，将 $i$ 的值存到 `vector` 里面。再维护一个指针 $k$ 用来遍历重构，每次把 $k$ 移动到 $\le A_q$ 的所有值上，从 `vector` 里面取出下标重新计算贡献，计算完之后再算出下一次重算贡献需要的 $A_q$ 值。由于每个元素重算贡献的时间复杂度为 $\sqrt V$，所以复杂度满足要求。
注意当分数值已经等于 $1$ 的时候就不要放进 `vector` 里面了，一个是它的值不会改变（一直都是 $1$），一个是计算需要除以它 $-1$ 的值，直接导致 RE。
```cpp
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
using LL = long long;
const LL kMaxN = 3e5 + 5;
ifstream cin("france.in");
ofstream cout("france.out");
LL a1[kMaxN], b1[kMaxN], a2[kMaxN], b2[kMaxN], f[kMaxN], n, m, v, sum;
vector<int> vct[kMaxN];
priority_queue<pair<LL, LL>, vector<pair<LL, LL>>, greater<>> q;
LL ceil(LL a, LL b) {
return (a + b - 1) / b;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> v;
for (LL i = 1; i <= n; i++) {
cin >> a1[i] >> b1[i];
}
for (LL i = 1; i <= m; i++) {
cin >> a2[i] >> b2[i];
}
for (LL i = 1, j = 1, k = 1; i <= m; i++) {
for (; k <= a2[i]; k++) {
for (int j : vct[k]) {
sum -= f[j];
LL x = ceil(b1[j], a2[i]);
sum += x * a1[j];
f[j] = x * a1[j];
if (x > 1) {
vct[ceil(b1[j], x - 1)].push_back(j);
}
}
vct[k].clear();
vct[k].shrink_to_fit(); // 清内存
}
for (; j <= n && sum < b2[i]; j++) {
LL x = ceil(b1[j], a2[i]);
sum += x * a1[j];
f[j] = x * a1[j];
if (x > 1) {
vct[ceil(b1[j], x - 1)].push_back(j); // 大于它 整除值就会改变
}
}
cout << (sum >= b2[i] ? j - 1 : -1) << '\n';
}
return 0;
}
```
## 酒杯
#组合数学 #概率与期望
赛时我两种暴力都 WA 了，都没有调出来，太悲惨了。
首先是对于 $n,m\le 500$，考虑 $nm^2$ 的 DP。设 $dp_{i,j}$ 表示前 $i$ 层已经有了 $j$ 个 AC，那么枚举下一层有了 $k$ 个 AC 计算概率转移即可。注意答案需要额外乘上 $m!$ 因为 $m$ 个 AC 位置可以互换。
对于 $n\le 20$ 但 $m$ 特别大的数据，考虑枚举有哪几层没有任何一个 AC，计算概率后加起来，再用 $1$ 减去他们，得到任意一层都有 AC 的概率。