专栏文章

长训day2

DDFbd
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio0n132
此快照首次捕获于
2025/12/02 11:25
3 个月前
此快照最后确认于
2025/12/02 11:25
3 个月前
查看原文
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与当前节点和 fafa 节点组成路径。
选择2
没错，就长这样。
我们在当前节点直接断开路径，子树1、2、3均变为情况1，而且这时也只能用选择1，很好理解。
至此，我们讨论完了所有情况，现在就很容易设计状态了。
fi,0/1/2f_{i, 0/1/2}，表示根为 ii 的子树的情况数，0表示情况1，1表示情况2，2表示情况1且只能用选择1。
接下来，我们分情况开始转移。
令当前节点为 xx，子节点集合为 ss。

情况1

选择1
这时可以更新 fx,2f_{x, 2}，最后再把 fx,2f_{x, 2} 加到 fx,0f_{x, 0} 里。
fx,2=∑i∈s∑j∈sj>ifi,1×fj,1×∏k∈sk≠ik≠jfk,0f_{x, 2} = \sum_{i \in s} \sum_{\substack{j \in s\\j > i}} f_{i,1} \times f_{j,1} \times \prod_{\substack{k \in s\\k \ne i\\k \ne j}} f_{k, 0}
暴力求会变成 O(n3)O(n^3)，显然会T，所以我们事先把 ∏k∈sfk,0\prod_{k \in s} f_{k, 0} 和 ∑j∈sfj,1fj,0\sum_{j \in s} \frac{f_{j,1}}{f_{j,0}} 求出来，然后枚举 ii，乘上求出的两个数和 fi,1fi,0\frac{f_{i,1}}{f_{i,0}}。
由于有取模，需要写个快速幂求逆元。
选择2
这时更新 fx,0f_{x, 0}。
fx,0=∏i∈sfi,2+fx,0f_{x, 0} = \prod_{i \in s} f_{i, 2} + f_{x, 0}
选择3
这时也更新 fx,0f_{x, 0}
fx,0=∑i∈sfi,1×∏j∈sj≠ifj,2+fx,0f_{x, 0} = \sum_{i \in s} f_{i,1} \times \prod_{\substack{j \in s\\j \ne i}} f_{j, 2} + f_{x, 0}
同样的，我们也不能暴力求，所以我们要事先把 ∏j∈sfj,2\prod_{j \in s} f_{j, 2} 求出来，然后枚举 ii，乘上求出的数和 fi,1fi,2\frac{f_{i,1}}{f_{i,2}}。
但是 fj,2f_{j, 2} 可能等于0，所以我们要特殊处理，当 fj,2=0f_{j, 2} = 0 时，我们不将其乘入，将计数器 sumsum 加1。
当 sum>1sum > 1 时，该选择情况数为0。
当 sum=1sum = 1 时，只有 fi,2=0f_{i, 2} = 0 时会更新答案，fx,0=fi,1×∏j∈sj≠ifj,2+fx,0f_{x, 0} = f_{i,1} \times \prod_{\substack{j \in s\\j \ne i}} f_{j, 2} + f_{x, 0}。
当 sum=0sum = 0 时，无需考虑有0的情况。

情况2

接下来更新 fi,1f_{i, 1}。
选择1
和情况1选择3很像。
fx,1=∑i∈sfi,1×∏j∈sj≠ifj,0+fx,1f_{x, 1} = \sum_{i \in s} f_{i,1} \times \prod_{\substack{j \in s\\j \ne i}} f_{j, 0} + f_{x, 1}
处理方法也一样，只不过不需要考虑0。
而且这里要提前求的 ∏j∈sfj,0\prod_{j \in s} f_{j, 0} 在情况1选择1也求了。
选择2
和情况1选择2一模一样。
至此，我们的转移也写完了。
最后答案为 f1,0f_{1, 0}，时间复杂度 O(nlog⁡n)O(n \log n)。
CPP
#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) 做法：
我的 O(nlogn)O(n log n) 做法：
haokee的 O(n3)O(n^3) 做法：

T2

不会，打暴力。
暴力很好打，直接枚举 mm 一个个算，时间复杂度 O(nm)O(nm)，20pts走人。
CPP
#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，没有金币卡直接每个都单价买，写完走人。
CPP
#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)O(RCQ) 暴力，每次操作找连通块，直接染色，10pts到手。
CPP
#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;
}
R=1R = 1 的就变成一个一维数组，好像是线段树，我不会，走人。

总结

这次真是尽力了，会拿的暴力都拿了，T1屎山也堆出来了，没有挂分。
需要注意的是，我依然不会线段树，这导致150 -> 135。
我真得好好学学线段树了。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...