2020-2021:teams:wangzai_milk:cf贪心练习
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:cf贪心练习 [2020/08/07 12:59] wzx27 创建 |
2020-2021:teams:wangzai_milk:cf贪心练习 [2020/08/07 13:03] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 69: | 行 69: | ||
| } | } | ||
| </code> </hidden> | </code> </hidden> | ||
| + | \\ | ||
| + | |||
| + | ==== CF1385F ==== | ||
| + | |||
| + | 给一棵树，每次选 $k$ 个叶子删掉，问最多能操作多少次。 | ||
| + | |||
| + | 每次找儿子叶子最多的一直删即可，关键是要维护每个点的儿子叶子的个数。可以用线段树或者 $\text{set}$ 维护。 | ||
| + | |||
| + | <hidden code> <code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ALL(x) (x).begin(),(x).end() | ||
| + | #define ll long long | ||
| + | #define db double | ||
| + | #define ull unsigned long long | ||
| + | #define pii_ pair<int,int> | ||
| + | #define mp_ make_pair | ||
| + | #define pb push_back | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define rep(i,a,b) for(int i=(a);i<=(b);i++) | ||
| + | #define per(i,a,b) for(int i=(a);i>=(b);i--) | ||
| + | #define show1(a) cout<<#a<<" = "<<a<<endl | ||
| + | #define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl | ||
| + | using namespace std; | ||
| + | const ll INF = 1LL<<60; | ||
| + | const int inf = 1<<30; | ||
| + | const int maxn = 2e5+5; | ||
| + | inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);} | ||
| + | int cnt[maxn],n,k; | ||
| + | vector<int> g[maxn]; | ||
| + | set<int> sg[maxn]; | ||
| + | struct node | ||
| + | { | ||
| + | int id,num; | ||
| + | bool operator < (const node e) const | ||
| + | { | ||
| + | if(num != e.num) return num < e.num; | ||
| + | return id < e.id; | ||
| + | } | ||
| + | }tr[maxn<<2]; | ||
| + | void dfs(int u,int f) | ||
| + | { | ||
| + | cnt[u] = 0; | ||
| + | for(int v:g[u])if(v!=f){ | ||
| + | dfs(v,u); | ||
| + | if(g[v].size()==1) cnt[u]++; | ||
| + | } | ||
| + | } | ||
| + | void push_up(int id) | ||
| + | { | ||
| + | tr[id] = max(tr[id<<1],tr[id<<1|1]); | ||
| + | } | ||
| + | void build(int id,int l,int r) | ||
| + | { | ||
| + | if(l==r){ | ||
| + | tr[id] = (node){l,cnt[l]}; | ||
| + | return ; | ||
| + | } | ||
| + | int mid = (l+r)>>1; | ||
| + | build(id<<1,l,mid);build(id<<1|1,mid+1,r); | ||
| + | push_up(id); | ||
| + | } | ||
| + | void update(int id,int stl,int str,int pos,int flag) | ||
| + | { | ||
| + | if(stl==str){ | ||
| + | if(!flag) tr[id].num %= k; | ||
| + | else tr[id].num++; | ||
| + | return ; | ||
| + | } | ||
| + | int mid = (stl+str)>>1; | ||
| + | if(pos<=mid) update(id<<1,stl,mid,pos,flag); | ||
| + | else update(id<<1|1,mid+1,str,pos,flag); | ||
| + | push_up(id); | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | fastio(); | ||
| + | int _; | ||
| + | for(cin>>_;_;_--){ | ||
| + | cin>>n>>k; | ||
| + | rep(i,1,n) g[i].clear(),sg[i].clear(); | ||
| + | rep(i,1,n-1){ int u,v; | ||
| + | cin>>u>>v; | ||
| + | g[u].pb(v); | ||
| + | g[v].pb(u); | ||
| + | } | ||
| + | if(k==1){ | ||
| + | cout<<n-1<<endl;continue; | ||
| + | } | ||
| + | rep(i,1,n){ | ||
| + | if(g[i].size()!=1) {dfs(i,0);break;} | ||
| + | } | ||
| + | rep(u,1,n){ | ||
| + | for(int v:g[u]) if(g[v].size() > 1) sg[u].insert(v); | ||
| + | } | ||
| + | build(1,1,n); | ||
| + | int ans = 0; | ||
| + | while(1){ | ||
| + | node tmp = tr[1]; | ||
| + | if(tmp.num < k) break; | ||
| + | int num = tmp.num / k; | ||
| + | ans += num; | ||
| + | update(1,1,n,tmp.id,0); | ||
| + | cnt[tmp.id] -= num*k; | ||
| + | if(cnt[tmp.id]==0 && sg[tmp.id].size()==1){ | ||
| + | int f = *sg[tmp.id].begin(); | ||
| + | sg[f].erase(sg[f].find(tmp.id)); | ||
| + | cnt[f]++; | ||
| + | update(1,1,n,f,1); | ||
| + | } | ||
| + | } | ||
| + | cout<<ans<<endl; | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </hidden> </code> | ||
2020-2021/teams/wangzai_milk/cf贪心练习.1596776367.txt.gz · 最后更改: 2020/08/07 12:59 由 wzx27
