2024/10/14 模拟赛总结

\(0+100+40+0=140\)，怎么都会 T3 啊

#A. char

令 \(dp_{i,j}\) 为已经考虑了文本串前 \(i\) 位且将所有 * 填入了字符，匹配了模式串的前 \(j\) 位的方案总数

转移显然，若第 \(i\) 位不是 *，则只有这一位和模式串相等才会有答案，即 \(dp_{i,j}=\begin{cases}dp_{i-1,j-1} & s_i=t_k\\0 & \text{else}\end{cases}\)

否则当前位可以填任意字符，则 \(dp_{i,j}=\sum dp_{i-1,j}\)

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxM = 1e3 + 5, kMaxN = 5e4 + 5;
const int kP = 998244853;

int n, m, sz[kMaxN];
LL dp[kMaxN][kMaxM], pre[kMaxN][kMaxM], ans;
string s, t[kMaxN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("char.in", "r", stdin), freopen("char.out", "w", stdout);
  cin >> n >> m >> s;
  for (int i = 1; i <= m; i++) {
    cin >> t[i], sz[i] = t[i].size();
    for (int j = 1; j <= n; j++) {
      fill(dp[j], dp[j] + sz[i] + 2, 0), fill(pre[j], pre[j] + sz[i] + 2, 0);
      if (s[j - 1] != '*') {
        for (int k = 1; k <= sz[i]; k++) {
          if (s[j - 1] == t[i][k - 1]) {
            (dp[j][k] += dp[j - 1][k - 1] + (k == 1)) %= kP;
          }
          pre[j][k] = pre[j][k - 1] + dp[j][k] % kP;
        }
      } else {
        dp[j][0] = dp[j - 1][0] + 1;
        for (int k = 1; k <= sz[i]; k++) {
          (dp[j][k] += (dp[j - 1][0] + pre[j - 1][k] + 1) % kP) %= kP;
          pre[j][k] = pre[j][k - 1] + dp[j][k] % kP;
        }
      }
    }
    for (int j = 1; j <= n; j++) {
      (ans += dp[j][sz[i]]) %= kP;
    }
  }
  cout << ans << '\n';
  return 0;
}

#B. tree

感觉很像原题啊找到原题了

引入那个 T2 的概念：影响域

由于最多改变一个颜色且 \(n \le 3000\)，可以想到枚举修改的点

对于每条边，求出其左右两边的影响域，答案即为左边白点乘右边黑点加左边黑点乘右边白点，枚举修改的点，对于每条边修改影响域中黑白点的数量，直接计算比大小即可

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 3e3 + 5;

vector<pair<int, LL>> g[kMaxN];
int n, c[kMaxN], u[kMaxN], v[kMaxN];
LL ans = 1e18, calc, cnt1[2][kMaxN], cnt2[2][kMaxN], w[kMaxN];  // cnt1 : white   cnt2 : black
unordered_map<int, bool> mp[2][kMaxN];

void DFS(int u, int fa, LL lt, int ae, bool flag) {
  (c[u] == 0 ? cnt1[flag][ae] : cnt2[flag][ae])++, mp[flag][ae][u] = 1;
  for (pair<int, LL> i : g[u]) {
    int v = i.first;
    LL w = i.second;
    if (v != fa) {
      if (w < lt) {
        DFS(v, u, lt, ae, flag);
      }
    }
  }
}
LL Calc(int x, LL ret = calc) {
  for (int i = 1; i < n; i++) {
    if (mp[0][i].count(x)) {
      ret -= w[i] * (cnt1[0][i] * cnt2[1][i] + cnt1[1][i] * cnt2[0][i]);
      (c[x] == 1) ? (cnt1[0][i]++, cnt2[0][i]--) : (cnt1[0][i]--, cnt2[0][i]++);
      ret += w[i] * (cnt1[0][i] * cnt2[1][i] + cnt1[1][i] * cnt2[0][i]);
      (c[x] == 1) ? (cnt1[0][i]--, cnt2[0][i]++) : (cnt1[0][i]++, cnt2[0][i]--);
    } else if (mp[1][i].count(x)) {
      ret -= w[i] * (cnt1[0][i] * cnt2[1][i] + cnt1[1][i] * cnt2[0][i]);
      (c[x] == 1) ? (cnt1[1][i]++, cnt2[1][i]--) : (cnt1[1][i]--, cnt2[1][i]++);
      ret += w[i] * (cnt1[0][i] * cnt2[1][i] + cnt1[1][i] * cnt2[0][i]);
      (c[x] == 1) ? (cnt1[1][i]--, cnt2[1][i]++) : (cnt1[1][i]++, cnt2[1][i]--);
    }
  }
  return ret;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("tree.in", "r", stdin), freopen("tree.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
  }
  for (int i = 1; i < n; i++) {
    cin >> u[i] >> v[i] >> w[i], g[u[i]].push_back({v[i], w[i]}), g[v[i]].push_back({u[i], w[i]});
  }
  for (int i = 1; i < n; i++) {
    DFS(u[i], v[i], w[i], i, 0), DFS(v[i], u[i], w[i], i, 1), calc += w[i] * (cnt1[0][i] * cnt2[1][i] + cnt1[1][i] * cnt2[0][i]);
  }
  ans = calc;
  for (int i = 1; i <= n; i++) {
    ans = max(ans, Calc(i));
  }
  cout << ans << '\n';
  return 0;
}

#C. wooden

考虑容斥，所有的情况为 \(\mathrm{C}_{\lceil\frac{x}{2}\rceil}^{3}\)

令选的长度为 \(x < u < v < w \le 4x\)，那么不满足条件的条件为 \(x+u \le v \le w-u \le 4x-u\)

先想 \(O(n)\) 做法，我们枚举 \(u\)，那么对于每一个 \(u\) 其他方案数为 \(\mathrm{C}_{3x-2u+1}^{2}\)，把这些式子拆开裂项合并就可以求出最终的式子：\(n^3-\frac{\lceil\frac{x}{2}\rceil\times (\lceil\frac{x}{2}\rceil+1)\times(2\lceil\frac{x}{2}\rceil+1)}{6}+[n\bmod 2=0]\times \lceil\frac{x}{2}\rceil^2\)

按照式子直接算即可

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const LL kP = 1e9 + 7, iv = 166666668;

LL n, ans, cnt, in;

int main() {
  freopen("wooden.in", "r", stdin), freopen("wooden.out", "w", stdout);
  cin >> in, n = (in + 1) >> 1, n %= kP, ans = ((in * 3 % kP) * ((in * 3 % kP) - 1) % kP) * ((in * 3 % kP) - 2) % kP, (ans *= iv) %= kP;
  cnt = (((n % kP) * n % kP) * n % kP) - ((((n % kP) * ((n + 1) % kP) % kP) * ((n + n + 1) % kP) % kP) * iv % kP) % kP, (cnt += kP) %= kP;
  (in & 1 ^ 1) && ((cnt += (n % kP) * (n % kP) % kP) %= kP);
  cout << (((ans - cnt) % kP) + kP) % kP << '\n';
  return 0;
}

#D. stars

人机期望，以后再写