Day-7 模拟赛题解
T1
数据点 3 - 5
- 枚举每一个问号对应的字母
- Kmp，把 s 当作模式串匹配 T
- \(O(26^k|T|)\)，k 是 ？ 的个数
代码（我也不知道为啥 T 了，鸽着）
正解
- 有种被诈骗了的感觉
- 根据期望的可加性，答案等于各个字符串出现次数的期望的和
- 于是，各个字符串出现在哪里相互没有关联
- 于是，枚举每个字符串出现的位置，单独计算期望，累加
- 设字符串 S = T[i, j] 中有 \(k_0\) 个 ？，则他的期望 = \(\frac{26^{(k - k_0)}}{26^k}\)
- 复杂度 \(O(n^2)\)
- \(\sum len_s \le 3e5\)，所以枚举起点 \(O(n)\)，每个起点每个 S 都访问一次 \(O(n)\)，相乘
- 这是一个均摊复杂度
- 注：string 超级慢！！ 用 char 不容易被卡
代码
# include <bits/stdc++.h>
# define int long long
# define double long double
using namespace std;
const int MOD = 998244353;
const int N = (int)5e3 + 10;
int q, n;
int poww[N];
char s[N], t[N];
int Q_pow(int a, int b){
int ans = 1, p = a;
while(b){
if(b & 1){
ans = (ans * p) % MOD;
}
b >>= 1;
p = (p * p) % MOD;
}
return ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int up = 5000;
poww[0] = 1;
for(int i = 1; i <= up; i++){
poww[i] = poww[i - 1] * 26 % MOD;
}
cin >> q;
while(q--){
cin >> t >> n;
int k = 0;
for(auto i : t){
if(i == '?'){
k++;
}
}
int len = strlen(t), ans = 0;
for(int i = 1; i <= n; i++){
cin >> s;
int lenn = strlen(s), up = len - lenn + 1;
for(int j = 0; j < up; j++){
bool f = 1;
int temp = k;
for(int k = 0; k < lenn; k++){
if(t[j + k] != '?' && s[k] != t[j + k]){
f = 0;
break;
}
if(t[j + k] == '?'){
temp--;
}
}
if(f == 1){
ans = (ans + poww[temp]) % MOD;
}
}
}
ans = ans * Q_pow(poww[k], MOD - 2) % MOD;
cout << ans << "\n";
}
}
T2
-
均摊时间复杂度坑爹啊！
- 每组数字只会被加进去 && 删除 1 次，均摊 \(O(n)\)
- 而我费尽心思线段树 + 二分加上去两个 log
-
设原来拼成的数字是 c （考虑操作带来的影响）
- 加入：\(c -> c * 10 ^ x + y_0\)
- 删除：\(c -> c - 10^{(len - x)} * y_0\)
- len 为 c 的长度，\(y_0\) 为 x 个 y 构成的数
-
如何求 \(y_0\)
- 小学奥数
- \(y * 10 ^ 0 + y * 10 ^ 1 + ... + y * 10 ^ {n - 1} = y_0\)
- \(y * 10 ^ 1 + y * 10 ^ 2 + ... + y * 10 ^ n = 10 * y_0\)
- \(9 * y_0 = y * (10 ^ n - 1)\)
- \(y_0 = \frac{y*(10^n - 1)}{9}\)
-
对于 \(10 ^ n\)，常规方法是快速幂，但是 5e6 带 log 跑不过
- 光速幂
光速幂
-
能做到单次询问 \(O(1)\)
-
对于 \(a^b\)，设 \(b = p * q + r, r \le q\)
-
则 \(a^b = (a^p)^q * a^r\)
-
我们要做的就是预处理 \(a^p, a^r\)
- 当 \(p = sqrt(mod)\) 时预处理为\(O(sqrt(n))\)，时间复杂度最小
- 预处理出 \(r = 1 到 sqrt(mod), q = 1 到 sqrt(mod)\) 时的 \(a^k\)，在 1e4 - 1e5 级别
-
根据欧拉定理 \(a ^ b ≡ a^{b \% \phi(mod)}(\% mod)\)，这可以缩小 b 的范围到 [0, mod] 中
-
完事！
代码
- 出题人卡我输入输出！！
- 不过快读是真快！！
# include <bits/stdc++.h>
# define int long long
# define double long double
using namespace std;
const int INV = 443664157; // INV 9
const int MOD = 998244353;
const int N = (int)1e7 + 10;
int n;
int opt, x, y;
struct Node{
int x, y;
}a[N];
int l, r, val, len;
int read(){
int sum=0,f=1;char st=getchar();
while(st<'0'||st>'9'){
if(st=='-')f=-1;
st=getchar();
}
while('0'<=st&&st<='9'){
sum=(sum<<3)+(sum<<1)+st-'0';
st=getchar();
}
return sum*f;
}
int p, phi, base = 10, pw[N][2];
int Phi(int x){
int ans = x;
for(int i = 2; i * i <= x; i++){
if(x % i == 0){
ans = ans / i * (i - 1);
while(x % i == 0){
x /= i;
}
}
}
if(x > 1){
ans = ans / x * (x - 1);
}
return ans;
}
void Init(){
phi = Phi(MOD);
p = sqrt(MOD);
pw[0][0] = pw[0][1] = 1;
for(int i = 1; i <= p; i++){
pw[i][0] = pw[i - 1][0] * base % MOD;
}
for(int i = 1; i <= p; i++){
pw[i][1] = pw[i - 1][1] * pw[p][0] % MOD;
}
}
int Query(int b){
b %= phi;
return pw[b % p][0] * pw[b / p][1] % MOD;
}
signed main(){
n = read();
Init();
l = r = val = len = 1;
a[1] = {1, 1};
for(int i = 1; i <= n; i++){
opt = read();
if(opt == 1){
x = read(), y = read();
a[++r] = {x, y};
len += x;
val = (val * Query(x) % MOD + y * (Query(x) + MOD - 1) % MOD * INV % MOD) % MOD;
}else if(opt == 2){
x = read();
while(x){
if(x >= a[l].x){
val = val + MOD - a[l].y * (Query(a[l].x) + MOD - 1) % MOD * INV % MOD * Query(len - a[l].x) % MOD;
val %= MOD;
x -= a[l].x;
len -= a[l].x;
l++;
}else{
val = val + MOD - a[l].y * (Query(x) + MOD - 1) % MOD * INV % MOD * Query(len - x) % MOD;
val %= MOD;
a[l].x -= x;
len -= x;
x = 0;
}
}
}else{
printf("%lld\n", val);
}
}
}
T3
- 只写 60 分做法，满分做法太阴间了，鸽了
- 设 dp[i][j] 表示 i 节点及其子树原来无色，强行染成 j 色后还需要几步达到题目要求
- 对于节点 i，\(mini = min(\sum_{i = [0, n]} dp[son][i])\)
- 如果 \(\sum_{i = [0, n]} dp[son][i] == mini\)，dp[i][j] = mini
- 否则，dp[i][j] = mini + 1
- 即：先用 1 步把 i 及其子树染成 j，再一股脑染成 mini 对应的颜色
- 这样比 mini 多用 1 步
- 注：全局定义的数组在递归中调用时要注意
- 不要 i 调用了又在 \(son_i\) 调用（除非需要这么做）
代码
# include <bits/stdc++.h>
# define int long long
# define double long double
using namespace std;
const int N = 5e3 + 10;
int n;
int fa, a[N];
int maxc, sumc[N], dp[N][N];
vector <int> e[N];
void Dfs(int x){
if(a[x] != 0){
for(int i = 0; i <= maxc; i++){
dp[x][i] = (a[x] != i);
}
}else{
for(auto i : e[x]){
Dfs(i);
}
for(int i = 0; i <= maxc; i++){
sumc[i] = 0;
}
for(auto i : e[x]){
for(int j = 0; j <= maxc; j++){
sumc[j] += dp[i][j];
}
}
int mini = (int)1e18;
for(int i = 0; i <= maxc; i++){
mini = min(mini, sumc[i]);
}
for(int i = 0; i <= maxc; i++){
if(sumc[i] == mini){
dp[x][i] = mini;
}else{
dp[x][i] = mini + 1;
}
}
}
}
signed main(){
cin >> n;
for(int i = 2; i <= n; i++){
cin >> fa;
e[fa].push_back(i);
}
for(int i = 1; i <= n; i++){
cin >> a[i];
maxc = max(maxc, a[i]);
}
Dfs(1);
cout << dp[1][0] << "\n";
}
T4
- 鸽了