2020-2021:teams:legal_string:jxm2001:other:错题集_5
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:other:错题集_5 [2021/03/03 18:41] jxm2001 |
2020-2021:teams:legal_string:jxm2001:other:错题集_5 [2021/08/24 11:25] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 179: | 行 179: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | |||
| + | ===== 2、Trips ===== | ||
| + | |||
| + | [[https://codeforces.com/contest/1037/problem/E|链接]] | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个图，初始时图没有边，接下来每次一个加边操作，然后询问加边后满足所有点度数不小于 $k$ 的最大子图。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 考虑先加入所有边，然后从最后的操作开始向前删边。 | ||
| + | |||
| + | 对每个点，当该点度数小于 $k$ 时直接删去该点和对应边。每个点仅删去一次，每条边最多访问三次，于是总时间复杂度 $O(n+m)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=2e5+5; | ||
| + | struct Edge{ | ||
| + | int u,v; | ||
| + | bool vis; | ||
| + | }edge[MAXN]; | ||
| + | vector<pair<int,int> > g[MAXN]; | ||
| + | int deg[MAXN],ans,k; | ||
| + | bool live[MAXN]; | ||
| + | void update(int u); | ||
| + | void del(int u){ | ||
| + | ans--; | ||
| + | live[u]=false; | ||
| + | _for(i,0,g[u].size()){ | ||
| + | int v=g[u][i].first,edge_id=g[u][i].second; | ||
| + | if(!edge[edge_id].vis){ | ||
| + | edge[edge_id].vis=true; | ||
| + | update(v); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | void update(int u){ | ||
| + | if(live[u]){ | ||
| + | deg[u]--; | ||
| + | if(deg[u]<k) | ||
| + | del(u); | ||
| + | } | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | k=read_int(); | ||
| + | ans=n; | ||
| + | _rep(i,1,n)live[i]=true; | ||
| + | _for(i,0,m){ | ||
| + | int u=read_int(),v=read_int(); | ||
| + | edge[i]=Edge{u,v}; | ||
| + | g[u].push_back(make_pair(v,i)); | ||
| + | g[v].push_back(make_pair(u,i)); | ||
| + | deg[u]++; | ||
| + | deg[v]++; | ||
| + | } | ||
| + | _rep(i,1,n){ | ||
| + | if(live[i]&°[i]<k) | ||
| + | del(i); | ||
| + | } | ||
| + | stack<int>s; | ||
| + | for(int i=m-1;i>=0;i--){ | ||
| + | s.push(ans); | ||
| + | if(edge[i].vis)continue; | ||
| + | edge[i].vis=true; | ||
| + | update(edge[i].u); | ||
| + | update(edge[i].v); | ||
| + | } | ||
| + | while(!s.empty()){ | ||
| + | enter(s.top()); | ||
| + | s.pop(); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== 3、CDN流量调度问题 ===== | ||
| + | |||
| + | [[https://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1003&cid=1029|2021CCPC华为云挑战赛 1003]] | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $n$ 个网络和 $m$ 个额外结点。第 $i$ 个网络初始有一个结点，且最多被分配 $b_i$ 个结点，当被分配 $k$ 个结点时，费用为 $\lceil\frac {a_i}k\rceil$。 | ||
| + | |||
| + | 最小化所有网络的费用和。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 易知使得每个网络的费用发生变化的 $k$ 只有 $O(\sqrt {a_i})$ 个，可以 $O\left(\sum_{i=1}^n a_i\right)$ 暴力预处理。 | ||
| + | |||
| + | 然后设 $\text{dp}(i,j)$ 表示只考虑前 $i$ 个网络花费 $j$ 个额外结点的最小费用，然后状态转移只枚举有效的 $k$。 | ||
| + | |||
| + | 总时间复杂度 $O(nm\sqrt a)$，个人感觉时间复杂度过大，但题目测试数据貌似比较水，所以可以过。 | ||
| + | |||
| + | ps. 本人一开始考虑优先队列，贪心取变化量最大的网络加结点，但实际受取整函数影响，变化量不是单调的，因此假了。 | ||
2020-2021/teams/legal_string/jxm2001/other/错题集_5.1614768074.txt.gz · 最后更改: 2021/03/03 18:41 由 jxm2001
