终于更新到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:有一个人在q[1..k]这k个位置各放了1个照相机,只有当照相机拍满y分钟的视频之后才会满足条件。满足条件之后就不架了。
- 事件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个数。
标签:sz,int,ACM,son,散题,maxn,习题,mx,dp From: https://www.cnblogs.com/guanjinquan/p/16909234.html