题解

3 条题解

  • 1
    @ 2023-07-11 10:52:30
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int MAXN = 5e4 + 5, MAXM = MAXN << 1;
    const int INF = 0x7fffffff;
    
    int head[MAXM], nxt[MAXM], v[MAXM], w[MAXM], cnt;
    
    int n, m;
    int root;
    
    inline void Addline(int x, int y, int z)
    {
        v[cnt] = y, w[cnt] = z;
        nxt[cnt] = head[x], head[x] = cnt++;
    
        return;
    }
    
    int dp[MAXN], tag[MAXN];//dp是向上贡献的最长链长度,也就是上面说的点权
    int que[MAXN], tail;
    int res;//还需要的赛道数
    
    inline void DFS(int x, int from, int lim)
    {
        for (int i = head[x]; ~i; i = nxt[i])
            if (v[i] != from)
                DFS(v[i], x, lim);//先下去DP一边,这样就不需要多开数组做后面的贪心了
    
        tail = 0;
        for (int i = head[x]; ~i; i = nxt[i])
            if (v[i] != from)
                que[++tail] = dp[v[i]] + w[i];//把几条链加进队列
    
        sort(que + 1, que + tail + 1);//排序
    
        for (int i = tail; i >= 1 && que[i] >= lim; i--)
            tail--, res--;//先把已经能变成赛道的边直接去掉,他们不需要两两匹配
    
        for (int i = 1; i <= tail; i++)
            if (tag[i] != x)//这个链没有被选过
            //这里的tag不再存True和False,而是存当前点的编号,这样就不用多次清空数组,而且可以保证不会重复(每个点只访问一次)
            {
                int l = i + 1, r = tail, pst = tail + 1;//二分另外一条链使得能刚好组成赛道
                while (l <= r)
                {
                    int mid = ((l + r) >> 1);
                    if (que[i] + que[mid] >= lim)
                        pst = mid, r = mid - 1;
                    else
                        l = mid + 1;
                }
    
                while (tag[pst] == x && pst <= tail)//因为有可能当前二分到的是已经被选过的链,那么我们贪心往后找一条链,可以证明这样是最优的
                    pst++;
    
                if (pst <= tail)//如果有观察上面的代码,可以发现tail+1是我们的溢出区,这里判断一下
                    tag[i] = tag[pst] = x, res--;
            }
    
        dp[x] = 0;
        for (int i = tail; i >= 1; i--)//找到当前没有选过的最长链,向上传递(其实也就是把链看成是当前点对上面点的贡献)
            if (tag[i] != x)
            {
                dp[x] = que[i];
                break;
            }
    
        return;
    }
    
    signed main(void)
    {
        memset(head, -1, sizeof head);
    
        cin >> n >> m;
        for (int i = 1, x, y, z; i < n; i++)
        {
            scanf("%d %d %d", &x, &y, &z);
            Addline(x, y, z), Addline(y, x, z);
        }
    
        root = rand() % n + 1;//随机选根
    
        int l = 0, r = INF, ans = 0;
        while (l <= r)//二分答案
        {
            int mid = ((l + r) >> 1);
            res = m;
    
            memset(tag, false, sizeof tag);
    
            DFS(root, 0, mid);
            if (res <= 0)
                ans = mid, l = mid + 1;
            else
                r = mid - 1;
        }
    
        cout << ans << endl;
    
        return 0;
    }
    
    
  • 0
    @ 2021-02-26 08:50:42
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    const int MAXN = 5e4 + 5, MAXM = MAXN << 1;
    const int INF = 0x7fffffff;
    
    int head[MAXM], nxt[MAXM], v[MAXM], w[MAXM], cnt;
    
    int n, m;
    int root;
    
    inline void Addline(int x, int y, int z)
    {
        v[cnt] = y, w[cnt] = z;
        nxt[cnt] = head[x], head[x] = cnt++;
    
        return;
    }
    
    int dp[MAXN], tag[MAXN];//dp是向上贡献的最长链长度,也就是上面说的点权
    int que[MAXN], tail;
    int res;//还需要的赛道数
    
    inline void DFS(int x, int from, int lim)
    {
        for (int i = head[x]; ~i; i = nxt[i])
            if (v[i] != from)
                DFS(v[i], x, lim);//先下去DP一边,这样就不需要多开数组做后面的贪心了
    
        tail = 0;
        for (int i = head[x]; ~i; i = nxt[i])
            if (v[i] != from)
                que[++tail] = dp[v[i]] + w[i];//把几条链加进队列
    
        sort(que + 1, que + tail + 1);//排序
    
        for (int i = tail; i >= 1 && que[i] >= lim; i--)
            tail--, res--;//先把已经能变成赛道的边直接去掉,他们不需要两两匹配
    
        for (int i = 1; i <= tail; i++)
            if (tag[i] != x)//这个链没有被选过
            //这里的tag不再存True和False,而是存当前点的编号,这样就不用多次清空数组,而且可以保证不会重复(每个点只访问一次)
            {
                int l = i + 1, r = tail, pst = tail + 1;//二分另外一条链使得能刚好组成赛道
                while (l <= r)
                {
                    int mid = ((l + r) >> 1);
                    if (que[i] + que[mid] >= lim)
                        pst = mid, r = mid - 1;
                    else
                        l = mid + 1;
                }
    
                while (tag[pst] == x && pst <= tail)//因为有可能当前二分到的是已经被选过的链,那么我们贪心往后找一条链,可以证明这样是最优的
                    pst++;
    
                if (pst <= tail)//如果有观察上面的代码,可以发现tail+1是我们的溢出区,这里判断一下
                    tag[i] = tag[pst] = x, res--;
            }
    
        dp[x] = 0;
        for (int i = tail; i >= 1; i--)//找到当前没有选过的最长链,向上传递(其实也就是把链看成是当前点对上面点的贡献)
            if (tag[i] != x)
            {
                dp[x] = que[i];
                break;
            }
    
        return;
    }
    
    signed main(void)
    {
        memset(head, -1, sizeof head);
    
        cin >> n >> m;
        for (int i = 1, x, y, z; i < n; i++)
        {
            scanf("%d %d %d", &x, &y, &z);
            Addline(x, y, z), Addline(y, x, z);
        }
    
        root = rand() % n + 1;//随机选根
    
        int l = 0, r = INF, ans = 0;
        while (l <= r)//二分答案
        {
            int mid = ((l + r) >> 1);
            res = m;
    
            memset(tag, false, sizeof tag);
    
            DFS(root, 0, mid);
            if (res <= 0)
                ans = mid, l = mid + 1;
            else
                r = mid - 1;
        }
    
        cout << ans << endl;
    
        return 0;
    }
    
  • 0
    @ 2020-04-30 17:33:48

    考场上打了一个 vectorvector 解法,因为我当时不会 multisetmultiset

    好吧,我来讲一讲今年的 \text{tgD1T3}tgD1T3

    首先,这题 5555 分是不难想的。

    1、 b_i=a_i+1b
    i
    ​ =a
    i
    ​ +1 的情况(一条链)
    解法:把所有边权记录下来,这种情况等价于将序列分割成 mm 段,使 mm 段区间和的最小值最大。

    那么二分 mm 段区间和的最小值,然后 O(n)O(n) 贪心扫一遍,时间复杂度 O(n\log n)O(nlogn)

    namespace subtask1{
    int a[maxn];
    void dfs(int x,int fa){
    for(int i=head[x],y;i;i=e[i].next){
    y=e[i].to;
    if(y==fa) continue;
    dfs(y,x);
    a[x]=e[i].val;
    }
    }
    int check(int k){
    int t=0,now=0;
    for(int i=1;i<n;i++){
    if(now+a[i]>=k){
    now=0;
    t++;
    }
    else now+=a[i];
    }
    return t>=m;
    }
    void solve(){
    dfs(1,0);
    int l=1,r=sum,mid;
    while(l<r){
    mid=l+r+1>>1;
    if(check(mid)) l=mid;
    else r=mid-1;
    }
    printf("%d\n",l);
    return ;
    }
    }
    2、 m=1m=1 的情况(树的直径)
    解法:取一条最长链,即为树的直径问题,记录一下最大值和次大值,每次把最大 值传到它的父亲,时间复杂度 O(n)O(n)
    namespace subtask2{
    int dfs(int x,int fa){
    int sum1=0,sum2=0;
    for(int i=head[x],y;i;i=e[i].next){
    y=e[i].to;
    if(y==fa) continue;
    sum2=max(sum2,dfs(y,x)+e[i].val);
    if(sum2>sum1) swap(sum1,sum2);
    }
    ans=max(ans,sum1+sum2);
    return sum1;
    }
    void solve(){
    dfs(1,0);
    printf("%d\n",ans);
    return ;
    }
    }
    3、a_i=1a
    i
    ​ =1的情况(菊花图)
    解法:把所有边权记录下来,从大到小排序。设边权为 ww,答案即为 w_1+w_{2m-1},w_2+w_{2m-2},...,w_m+w_{m+1}w
    1
    ​ +w
    2m−1
    ​ ,w
    2
    ​ +w
    2m−2
    ​ ,...,w
    m
    ​ +w
    m+1
    ​ 的最小值,时间复杂度 O(nlogn)O(nlogn)
    namespace subtask3{
    int a[maxn];
    bool cmp(int a,int b){
    return a>b;
    }
    void solve(){
    for(int i=head[1],y;i;i=e[i].next){
    y=e[i].to;
    a[y-1]=e[i].val;
    }
    sort(a+1,a+n,cmp);
    int ans=inf;
    for(int i=1;i<=m;i++)
    ans=min(ans,a[i]+a[2*m-i+1]);
    printf("%d\n",ans);
    }
    }
    分支不超过 33 的话其实就是正解的弱化版。

    看到题意描述第一反应就是先二分那个修建的 mm 条赛道中长度最小的赛道的长度 kk ,然后 O(n)O(n) 或 O(n\log n)O(nlogn) 判断。

    那么怎么判断呢?

    对于每个结点,把所有传上来的值 valval 放进一个 multisetmultiset ,其实这些值对答案有贡献就两种情况:

    val\geq kval≥k
    val_a+val_b\geq kval
    a
    ​ +val
    b
    ​ ≥k
    那么第一种情况可以不用放进 multisetmultiset,直接答案 +1+1 就好了。第二种情况就可以对于每一个最小的元素,在 multisetmultiset 中找到第一个 \geq k≥k 的数,将两个数同时删去,最后把剩下最大的值传到那个结点的父亲

    我出考场后想为什么这种解法是正确的,有没有可能对于有些情况直接传最大的数会使答案更大?

    当然不会。这个数即使很大也只能对答案贡献加 11,在其没传上去的时候可以跟原来结点的值配对,也只能对答案贡献加 11。

    multisetmultiset 版:

    int dfs(int x,int fa,int k){
    s[x].clear();
    int val;
    for(int i=head[x],y;i;i=e[i].next){
    y=e[i].to;
    if(y==fa) continue;
    val=dfs(y,x,k)+e[i].val;
    if(val>=k) ans++;
    //直接处理第一种情况
    else {
    s[x].insert(val);
    }
    }
    int Max=0;
    while(!s[x].empty()){
    if(s[x].size()==1){
    return max(Max,*s[x].begin());
    }
    //把最大的给传上去
    it=s[x].lower_bound(k-*s[x].begin());
    //二分到那个值
    if(it==s[x].begin()&&s[x].count(*it)==1) it++;
    //若找到的就是它自己且当前值的count==1,迭代器++
    if(it==s[x].end()){
    Max=max(Max,*s[x].begin());
    s[x].erase(s[x].find(*s[x].begin()));
    }
    //若没有找到比k-*s[x].begin()大的,就取个最大值,把*s[x].begin()删掉
    else {
    ans++;
    s[x].erase(s[x].find(*it));
    s[x].erase(s[x].find(*s[x].begin()));
    }
    //处理第二种情况
    }
    return Max;
    //把最大值传上去
    }
    vectorvector 版:

    while(!s[x].empty()){
    if(s[x].size()==1){
    return max(Max,*s[x].begin());
    }
    it=lower_bound(s[x].begin(),s[x].end(),k-*s[x].begin());
    if(it==s[x].begin()) it++;
    if(it==s[x].end()){
    Max=max(Max,*s[x].begin());
    s[x].erase(s[x].begin());
    }
    else {
    ans++;
    s[x].erase(it);
    s[x].erase(s[x].begin());
    }
    }
    return Max;
    multisetmultiset 版:时间复杂度 O(n\log^2 n)O(nlog
    2
    n)
    vectorvector 版:时间复杂度 O(n^2\log n)O(n
    2
    logn)
    备注:如果数据是随机的,vectorvector 的写法会很快,但菊花图可以把它卡掉。

    然后 tgD1T3tgD1T3 就被我们解决了。

    还有就是那个二分上界可以换成树的直径。

    Code\ Below:Code Below:
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=50000+10;
    int n,m,head[maxn],tot,ans,up;

    struct node{
    int to,next,val;
    }e[maxn<<1];

    multiset<int> s[maxn];
    multiset<int>::iterator it;

    inline int read(){
    register int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return (f==1)?x:-x;
    }

    inline void add(int x,int y,int w){
    e[++tot].to=y;
    e[tot].val=w;
    e[tot].next=head[x];
    head[x]=tot;
    }

    int dfs(int x,int fa,int k){
    s[x].clear();
    int val;
    for(int i=head[x],y;i;i=e[i].next){
    y=e[i].to;
    if(y==fa) continue;
    val=dfs(y,x,k)+e[i].val;
    if(val>=k) ans++;
    else {
    s[x].insert(val);
    }
    }
    int Max=0;
    while(!s[x].empty()){
    if(s[x].size()==1){
    return max(Max,*s[x].begin());
    }
    it=s[x].lower_bound(k-*s[x].begin());
    if(it==s[x].begin()&&s[x].count(*it)==1) it++;
    if(it==s[x].end()){
    Max=max(Max,*s[x].begin());
    s[x].erase(s[x].find(*s[x].begin()));
    }
    else {
    ans++;
    s[x].erase(s[x].find(*it));
    s[x].erase(s[x].find(*s[x].begin()));
    }
    }
    return Max;
    }

    int check(int k){
    ans=0;
    dfs(1,0,k);
    if(ans>=m) return 1;
    return 0;
    }

    int dfs1(int x,int fa){
    int sum1=0,sum2=0;
    for(int i=head[x],y;i;i=e[i].next){
    y=e[i].to;
    if(y==fa) continue;
    sum2=max(sum2,dfs1(y,x)+e[i].val);
    if(sum1<sum2) swap(sum1,sum2);
    }
    up=max(up,sum1+sum2);
    return sum1;
    }

    int main()
    {
    n=read(),m=read();
    int x,y,w;
    for(int i=1;i<n;i++){
    x=read(),y=read(),w=read();
    add(x,y,w);add(y,x,w);
    }
    dfs1(1,0);
    int l=1,r=up,mid;
    while(l<r){
    mid=l+r+1>>1;
    if(check(mid)) l=mid;
    else r=mid-1;
    }
    printf("%d\n",l);
    return 0;
    }

  • 1

信息

ID
2060
难度
1
分类
(无)
标签
递交数
30
已通过
24
通过率
80%
上传者