ACM散题习题库5【持续更新】

终于更新到5了，但是发现并不是做过的题仍然记得，所以现在应该着重记录一些相对简单且模板的题目了。

501. H - Clock HDU - 6551【环上点覆盖 问题】

题意：给你一个环[0,N-1]，和一个起始点S，同时还有n个在环上的点，请你求出最短的时间从S出发，去覆盖这n个点。

解决这个环问题的关键在于拆环。拆环的关键在于确定拆环的点，然后把这个点当作原点O。然后就可以从序列的角度去写for循环了，对我来说这样容易理解。

定义\(s\)到第\(i\)个点的顺时针距离为\(d_i\)，我们把n个点根据\(d\)排序，就可以得到一个序列啦！然后就枚举\(i\)和\(i+1\)这两个点作为两个端点，\(s\)到\(i\)的距离就是\(d_{i}\)，到\(i+1\)的距离是\(N-d_{i+1}\)。那么答案就是: \(2 * min(d_{i}, N-d_{i+1}) + max(d_{i}, N-d_{i+1})\)。然后记得特判一下首尾就行了。

502. J - Tangram HDU - 6553【小学奥数 + 切蛋糕题目】

题意：自己看。

目标是跟更多的边相交。

503. 2019CCPC女生赛-Union【搜索计数】

题目给定了7个条件，直接考虑这些条件确实不好计数。

504. 2019CCPC女生赛-String【贪心 + DP】

空间复杂度有点大？\(O(n*26*10)\), 其中\(n=10^5\)。

505. 2022年SCUT-新生杯B题 - AC! 【区间DP / 反悔贪心】

题意：给你一个串S，只包含a、c、p三种字符，有两种操作，每次你可以选择一种操作来执行：

• 你选择S中的子串 'ac' ，然后删掉它。
• 你选择S中的子串 'cp'， 然后删掉它。

每次删掉两个字符，串都会重新拼接起来。你的任务是将整个串删空，但是直接删可能无法将整个串删空，所以你可以在字符串S的任意一个地方插入一个任意的字符。现在问你最少插入多少个字符，使得整个串被删掉。原题\(n=300\)，但是实际上贪心可以\(O(n)\)通过。

（方法1：区间DP）

初始状态：\begin{align*}dp[i][j] = \{\begin{matrix}0 & i > j \\ 1 & i = j \\ inf  & i<j\end{matrix}\end{align*}.

转移方程：有两种转移方式

• 如果\(s[i]+s[j]=='ac'/'cp'\) 可以有 \(dp[i][j] = min(dp[i][j],  dp[i+1][j-1])\)
• 然后都要进行区间DP的转移方式：\(dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]\)

（方法2：反悔贪心）

506. E.Master of Subgraph【点分治优化 + bitset表示状态的DP】【查看聚聚的题解】

这道题一点头绪都没有。。。主要是连搜索都不会写，然后DP的状态根本想不出来。【这题数据范围n=3000，但是数据中边集好像出现了大于3000的点，开成6000就能过了】

考虑一个\(O(n^2)\)的暴力，我们枚举每一个点作为连通块的必过点Root(连通块必须包含这个节点)。定义`bitset<100000> dp[x]`表示dfs到x节点(以及一部分x的孙子节点)的时候，包含Root和x的联通块的权值。【这个"dfs到x节点"的说法有点巧妙，之前都没见过这样的】

那么从x再dfs到某个儿子节点v的时候，dp[x]应该转移给dp[v]，所以`dp[v] = dp[x] << w[v]`。如果v是一个叶子节点的话，dp[v]就直接是v节点的答案了。那么现在从v退栈到x，应该让`dp[x]|=dp[v]`。这样的话，就不需要做很多次背包/卷积了。因为在枚举x的下一个儿子节点`nxt_v`的时候，就会有`dp[nxt_v]=dp[x]<<w[nxt_v]`，就达到了背包的组合效果（x， 感觉很神奇。

现在复杂度是\(O(\dfrac{n^2*100000}{64})\)，实际上我们枚举了很多重复的状态（很多重复的连通块）。

所以我们考虑一个Root被选了之后，就把它的所有子树单独求解，这样就不会重复计算了。然后想到这里应该能想到点分治优化这个分治过程。最后复杂度就是\(O(\dfrac{nlogn*100000}{64})。

#include <bits/stdc++.h>
using namespace std;
#define ios_fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

const int maxn = 3e3 + 11;

// 输入信息
int n, m, w[maxn], head[maxn], etop;
bitset<100005> dp[maxn], ans;
vector<vector<int>> e;

// 点分治信息
int root, mx_son_sz[maxn], sz[maxn], vis[maxn];

void addEdge(int x, int y) {
  e[++etop] = {y, head[x]}, head[x] = etop;
  e[++etop] = {x, head[y]}, head[y] = etop;
}

void find_root(int x, int p, int tot_sz) {  // totsz不可以加引用
  mx_son_sz[x] = 0, sz[x] = 1;
  for (const int & v : e[x]) {
    if (vis[v] || v == p) continue;
    find_root(v, x, tot_sz);
    sz[x] += sz[v];
    if (mx_son_sz[x] < sz[v]) mx_son_sz[x] = sz[v];
  }
  mx_son_sz[x] = max(mx_son_sz[x], tot_sz - sz[x]);
  if (root == -1 || mx_son_sz[x] < mx_son_sz[root]) root = x;
}

void dfs(int x, int p) {
  sz[x] = 1;  // 这里重新计算sz也行，不算也行，不算的话，只有父节点的sz是错误的，但是也不影响复杂度.[跳到line-51:①]
  dp[x] = dp[p] << w[x];
  for (const int & v : e[x]) {
    if (vis[v] || v == p) continue;
    dfs(v, x);
    sz[x] += sz[v];
    dp[x] |= dp[v];
  }
}

void Work(int x, int tot_sz) {
  root = -1;
  find_root(x, 0, tot_sz);
  vis[root] = true;
  dfs(root, 0);
  ans |= dp[root];
  x = root;  // 注意赋值记录root
  for (const int & v : e[x]) {
    if (!vis[v]) Work(v, sz[v]); // 这里①：如果上面不算，只有x的父节点的sz是错的
  }
}

void solve() {
  cin >> n >> m;
  e.assign(2 * n + 1, vector<int>());
  for (int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    e[x].push_back(y);
    e[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    dp[i].reset();
    vis[i] = false;
  }
  dp[0].reset();
  ans.reset();
  dp[0][0] = 1;  // 初始化特例
  Work(1, n);
  assert(m <= 100000);
  for (int i = 1; i <= m; i++) cout << ans[i];
  cout << "\n";
}

int main() {
  ios_fast;
  int T;
  cin >> T;
  while (T--) solve();
}

507. I. Incoming Asteroids【经典：三个点的权值之和大于x + 势能思想】【提交记录】

题意大致如下：有n个位置可以假设照相机，然后有m个时间发生。

1. 事件1：有一个人在q[1..k]这k个位置各放了1个照相机，只有当照相机拍满y分钟的视频之后才会满足条件。满足条件之后就不架了。
2. 事件2：在位置x出现了长达y分钟的事件，在位置x架设的照相机可以拍到y分钟的视频。

每个事件2之后输出满足条件的事件1的ID。要求强制在线。

如果不要求强制在线，可以离线用二分来做，也是\(O(nlognlogn*k)\)。

如果一个事件1要拍y分钟，那么一定存在一个位置拍了\(\lceil\dfrac{y}{k}\rceil\)分钟及以上的。我们把这个时间戳放进一个堆里面，当一个位置x加了y的时候，检查一下x节点的堆是否有事件1的时间戳被满足。

这样不停减\(\frac{1}{3}\)直到变成0。所以整体复杂度为\(n*logn*log_{\frac{2}{3}}n\)

508. 2019香港-E. Erasing Numbers【贪心 + 思维 + 结论】

题意：给你n=2000的一个序列（保证任意两个数互不相同），每次可以选择连续的3个数，然后保留其中的中位数，删掉剩下两个数。请你判断是否能通过一系列操作最后只剩第i个数。