题解 - Vijos

1

12322132131231 (褚战) LV 10 @ 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

RP++ (贪吃蛇) LV 8 @ 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

j18tm01 LV 10 @ 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;
}

题解

3 条题解

赛道修建

信息

状态

开发

支持

题解

3 条题解

赛道修建

信息

状态

开发

支持

还没有账户？

登录