闲话
编▇▇则
4．选手程序中只允许通过▇▇▇▇▇读写▇▇▇▇▇指定库函数▇▇▇▇▇▇▇▇▇▇的方式与外部环境通信。在程序中严禁▇▇▇▇▇
试图▇▇▇▇▇
使用▇▇▇▇▇生成函数
想到之前有个外围叫凿子啥的（
黑条艺术（
bgf 的 exp 咋写啊？
构造不出来咋办？
我现在只会 \(O(n^3 \log n)\) 了
咋我自己都不知道我提交数 666 别人先知道了？
不懂的
今日推歌：Telecaster B-boy - すりぃ feat. 鏡音连
洗脑至极（
模拟赛题解
again? again!
T1 后浪
签到题。直接预处理第 \(i\) 个串里 \(c\) 的个数 \(\text{cnt}(i, c)\)，并枚举切换 \(0\to 1\) 的串 \(k\)，得到其前 \(i\) 个字符中 \(0\) 的个数 \(\text{pref}(i)\) 和后 \(i\) 个字符中 \(1\) 的个数 \(\text{suff}(i)\)，答案就是
\[\max_k \left\{ \max_i \left\{ \text{pref}(i) + \text{suff}(i + 1) \right\} + \sum_{i \neq k} \max\{\text{cnt}(i, 0), \text{cnt}(i, 1) \} \right\} \]可以 \(O(\sum s)\) 地得到。
T2 脑力
神犇 \(\color{black}{i}\color{red}{x35}\) 被 Brain Power 洗脑了。
考虑用容斥原理刻画 Trie 上的节点。
记 \(S_i\) 是第 \(i\) 个串所有前缀组成的集合，则 \(\lvert S_i\cap S_j\rvert\) 就是串 \(i,j\) 的 \(\text{lcp}\)。
由于期望是线性的，可以知道 Trie 上节点数（不算根）就是
直接 \(O(2^n)\) 枚举 \(S\)，对每个集合计算 \(\left\lvert \bigcap_{i \in S} S_i \right\rvert\) 即可。这计算是简便的，我们只需要枚举当前 \(\text{lcp}\) 的长度并计算其可能的大小即可，也就是每种长度的概率。这在过程中计数有多少个 ? 并考虑他们都相同的概率即可。
总时间复杂度 \(O(nm2^n)\)。
code
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
int n, m, cnt[30], ans;
char str[15][1005];
int calc(int s) {
int len = 0, p = 1;
rep(j,1,m) {
char ch = 0;
rep(i,1,n) if (s >> (i - 1) & 1) {
if (!ch) {
ch = str[i][j];
if (ch == '?') muli(p, inv(26));
} else {
if (ch == '?') {
if (str[i][j] == '?') muli(p, inv(26));
else ch = str[i][j];
} else {
if (str[i][j] == '?') muli(p, inv(26));
else if (ch != str[i][j]) return len;
}
}
}
if (ch == '?') muli(p, 26);
addi(len, p);
} return len;
}
signed main() {
cin >> n >> m;
rep(i,1,n) cin >> str[i] + 1;
for (int i = 1; i < (1 << n); ++ i) {
if (__builtin_popcount(i) & 1) addi(ans, calc(i));
else subi(ans, calc(i));
} cout << add(ans, 1) << '\n';
}
T3 道路
看到二叉树就要想到二进制大数表示一个位置。
首先考虑用一个二进制数来表示一个位置，第 \(i\) 位的 01 性表示这一步是否向右儿子走。
向左右儿子走和向父亲走都好说，只用加入/删除最后一位。平行向左/右走等价于翻转最后的一众 0/1，这也就等价于减/加。
这可以在扫到时 lazy 地作操作，过程中需要向父亲走时再进位即可。最终从低到高扫一遍就能得到我们需要的二进制数，深度也可以随之确定。
然后问题转化为在如图的树上行走使得步数最小。
首先贪心地让更深的位置向根跳，随后可以枚举一个层数，满足两个位置在这一层相遇最优。这也可以在一同向根跳的过程中计算，只需要维护之间距离和跳的次数即可。
最后记得加更深的位置跳的次数。
总时间复杂度 \(O(n)\)。
code
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
const int N = 1e6 + 10;
int lga, a[N];
int lgb, b[N];
char str[N];
inline void upd(int idx[], int i) {
idx[i - 1] += idx[i] / 2 - (idx[i] % 2 == -1);
idx[i] = abs(idx[i]) % 2;
}
inline void init(int idx[], int& lgv) {
cin >> str + 1;
int n = strlen(str + 1);
idx[0] = lgv = 1;
rep(i,1,n) {
if (str[i] == '1') idx[lgv++] = 0;
if (str[i] == '2') idx[lgv++] = 1;
if (str[i] == 'L') --idx[lgv - 1];
if (str[i] == 'R') ++idx[lgv - 1];
if (str[i] == 'U') upd(idx, --lgv);
} pre(i, lgv - 1, 1) upd(idx, i);
}
int main() {
init(a, lga), init(b, lgb);
int lgv = min(lga, lgb), ans = 1e9, dis = 0;
for (int i = 0; i < lgv and dis < (1 << 20); ++i) {
dis = dis * 2 + a[i] - b[i];
ans = min(ans, abs(dis) + 2 * (lgv - i - 1));
} cout << ans + abs(lga - lgb) << '\n';
}
T4 光学实验室
一个很显然的条件就是最终局面中肯定没有环。
这就导出了计树做法。
我们将原图看做 \((n + 1)\times (m + 1)\) 的点集，并黑白染色，满足黑白点内部不四联通。只有同色点可以连边。
然后可以发现的是，最终答案一定是黑点/白点的一棵生成树，这时另一些点只有一种连法。
因此用并查集缩点，最终的联通块数一定是 \(O(k)\) 的。
随后加可能的边，矩阵树定理计算答案即可。
总时间复杂度 \(O(nm\alpha(nm) + k^3)\)。
标签：25,##_,idx,int,闲话,23.2,str,text,lgv From： https://www.cnblogs.com/joke3579/p/chitchat230225.html