长训day2

DFbd · 2025-09-04 16:33:57 · 个人记录

China（中国）

一个唯一稀有度的DFbd被dmy击败了

不过堆屎山堆出了T1😋

CSP-S2024：100 + 100 + 20 + 0

CSP模拟d2：100 + 20 + 5 + 10

dmy我爱你🥰

contest

T1

思维难度：2000

代码难度：1e9 + 7

看题目很容易想到dp，但是这里有一堆情况，我们一个个讨论。

情况1

这时，我们有3种选择：

选择1

红色线表示一条路径。

此时子树2变成情况1，子树1、3变成下面的情况2。

同理，也可以是子树1、2或2、3与当前节点组成路径。

选择2

红色圆圈表示该点单独成为一条路径。

此时子树1、2、3均为情况一，但是只能用选择1，否则选出的路径将会与当前节点组成一条路径，不符题意。

选择3

此时子树1变成下面的情况2，子树2、3为情况1。

同样的，子树2、3也只能用选择1，否则会与当前选出的路径组成一条更长的路经，不符题意。

同理，也可以是子树2或3与当前节点组成路径。

情况2

此时有2种选择：

选择1

此时子树1变为情况2，子树2、3变为情况1。

同理，也可以是子树2或3与当前节点和 fa 节点组成路径。

选择2

没错，就长这样。

我们在当前节点直接断开路径，子树1、2、3均变为情况1，而且这时也只能用选择1，很好理解。

至此，我们讨论完了所有情况，现在就很容易设计状态了。

同样的，我们也不能暴力求，所以我们要事先把 \prod_{j \in s} f_{j, 2} 求出来，然后枚举 i，乘上求出的数和 \frac{f_{i,1}}{f_{i,2}}。

但是 f_{j, 2} 可能等于0，所以我们要特殊处理，当 f_{j, 2} = 0 时，我们不将其乘入，将计数器 sum 加1。

当 sum > 1 时，该选择情况数为0。

当 sum = 1 时，只有 f_{i, 2} = 0 时会更新答案，f_{x, 0} = f_{i,1} \times \prod_{\substack{j \in s\\j \ne i}} f_{j, 2} + f_{x, 0}。

当 sum = 0 时，无需考虑有0的情况。

情况2

接下来更新 f_{i, 1}。

选择1

和情况1选择3很像。

处理方法也一样，只不过不需要考虑0。

而且这里要提前求的 \prod_{j \in s} f_{j, 0} 在情况1选择1也求了。

选择2

和情况1选择2一模一样。

至此，我们的转移也写完了。

最后答案为 f_{1, 0}，时间复杂度 O(n \log n)。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll kMaxN = 1e5 + 5, p = 1e9 + 7;

ll n, f[kMaxN][3];
vector<int> e[kMaxN];

ll fpow(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b & 1)
      res = res * a % p;
    a = a * a % p;
    b >>= 1;
  }
  return res;
}

void dfs(int x, int fa) {
  ll tot1 = 1, tot2 = 1, tot3 = 0, sum = 0;
  for (int i = 0; i < e[x].size(); i++) {
    if (fa == e[x][i])
      continue;
    dfs(e[x][i], x);
    tot2 = (f[e[x][i]][0] * tot2) % p;
    tot3 = (f[e[x][i]][1] * fpow(f[e[x][i]][0], p - 2) % p + tot3) % p;
    if (f[e[x][i]][2])
      tot1 = (f[e[x][i]][2] * tot1) % p;
    else
      sum++;
  }
  for (int i = 0; i < e[x].size(); i++) {
    if (fa == e[x][i])
      continue;
    ll tmp = f[e[x][i]][1] * tot2 % p * fpow(f[e[x][i]][0], p - 2) % p;
    f[x][1] = (tmp + f[x][1]) % p;
    f[x][2] = (tmp * ((tot3 - f[e[x][i]][1] * fpow(f[e[x][i]][0], p - 2) % p + p) % p) % p + f[x][2]) % p;
    if (sum == 1 && !f[e[x][i]][2])
      f[x][0] = (tot1 * f[e[x][i]][1] % p + f[x][0]) % p;
    if (!sum)
      f[x][0] = (f[x][0] + tot1 * f[e[x][i]][1] % p * fpow(f[e[x][i]][2], p - 2) % p) % p;
  } 
  f[x][2] = f[x][2] * fpow(2, p - 2) % p;
  if (!sum) {
    f[x][1] = (tot1 + f[x][1]) % p;
    f[x][0] = (tot1 + f[x][0]) % p;
  }
  f[x][0] = (f[x][2] + f[x][0]) % p;
}

int main() {
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1, 0);
  cout << f[1][0];
  return 0;
}

小剧场：

xbc的 O(n) 做法：

我的 O(n log n) 做法：

haokee的 O(n^3) 做法：

T2

不会，打暴力。

暴力很好打，直接枚举 m 一个个算，时间复杂度 O(nm)，20pts走人。

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 5e5 + 5;

int n, a[kMaxN], b[kMaxN], m[kMaxN], maxn, maxm, ans;

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
    maxm = max(maxm, max(a[i], b[i]));
  }
  if (n * maxm <= 4e8) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= maxm + 1; j++) {
        if (a[i] % j < b[i] % j) {
          m[j]++;
          maxn = max(maxn, m[j]);
        }
      }
    }
    cout << maxn << ' ';
    if (m[maxm + 1] == maxn) 
      cout << -1;
    else {
      for (int i = 1; i <= maxm; i++)
        ans += (m[i] == maxn) * i;
      cout << ans;
    }
  }
  return 0;
}

T3

这个也不会，还只会5pts，没有金币卡直接每个都单价买，写完走人。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int kMaxN = 1e5 + 5;

ll m, n, t, a[kMaxN], ans;

int main() {
  cin >> m >> n >> t;
  for (int i = 1; i <= m; i++)
    cin >> a[i];
  if (!n) {
    for (int i = 1; i <= m; i++)
      ans += a[i] * t;
    cout << ans;
  }
  return 0;
}

T4

这个也不会，先打一个 O(RCQ) 暴力，每次操作找连通块，直接染色，10pts到手。

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int kMaxN = 2e3 + 5;

int r, c, q, vis[kMaxN][kMaxN], a[kMaxN][kMaxN], dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

void bfs(int x, int y, int z, int s) {
  for (int i = 1; i <= r; i++) 
    for (int j = 1; j <= c; j++)
      vis[i][j] = 0;
  queue<pii> q;
  q.push({x, y});
  vis[x][y] = 1;
  while (q.size()) {
    pii t = q.front();
    q.pop();
    a[t.first][t.second] = z;
    for (int i = 0; i < 4; i++) {
      int nx = t.first + dx[i], ny = t.second + dy[i];
      if (nx < 1 || nx > r || ny < 1 || ny > c || a[nx][ny] != s || vis[nx][ny])
        continue;
      q.push({nx, ny});
      vis[nx][ny] = 1;
    }
  }
}

int main() {
  cin >> r >> c;
  for (int i = 1; i <= r; i++) 
    for (int j = 1; j <= c; j++)
      cin >> a[i][j];
  for (cin >> q; q; q--) {
    int x, y, z;
    cin >> x >> y >> z;
    bfs(x, y, z, a[x][y]);
  }
  for (int i = 1; i <= r; i++) {
    for (int j = 1; j <= c; j++)
      cout << a[i][j] << " ";
    cout << '\n';
  }
  return 0;
}