赛前模拟1-20250825(总结)

· · 个人记录

Part 1 赛时

T1

首先我们可以发现测试点分为两类：

T2

看看这数据规模与约定： 测试点编号 n m a_i=1 b_i=a_i+1 分支不超过 3
1 \le 5 =1 否 否 是
2 \le 10 \le n-1 否 是 是
3 \le 15 \le n-1 是 否 否
4 \le 10^3 =1 否 否 是
5 \le 3\times 10^4 =1 是 否 否
6 \le 3\times 10^4 =1 否 否 否
7 \le 3\times 10^4 \le n-1 是 否 否
8 \le 5\times 10^4 \le n-1 是 否 否
9 \le 10^3 \le n-1 否 是 是
10 \le 3\times 10^4 \le n-1 否 是 是
11 \le 5\times 10^4 \le n-1 否 是 是
12 \le 50 \le n-1 否 否 是
13 \le 50 \le n-1 否 否 是
14 \le 200 \le n-1 否 否 是
15 \le 200 \le n-1 否 否 是
16 \le 10^3 \le n-1 否 否 是
17 \le 10^3 \le n-1 否 否 否
18 \le 3\times 10^4 \le n-1 否 否 否
19 \le 3\times 10^4 \le n-1 否 否 否
20 \le 5\times 10^4 \le n-1 否 否 否

简单的数了一下，如果把所有特殊点加上，可以拿到\color {green} 80tps，太值了，于是我完成了(3/4) -> 前三个，于是，我们来一个一个分析：

  1. m=1，这个十分明显，m=1代表只用出现一条赛道，如果要让这条赛道的长度最长，这条赛道其实就是这个树的直径，十分简单
  2. ai=1，这是一个菊花图：

对于这种情况，我们发现每一条赛道至多为2条边，如果m*2\le n，很明显我们直接曲最大的2*m个，一大一小进行匹配，但是如果m*2>n呢，我们可以加入若干条连接1的边，且其边为0，补全至第一种。

  1. ai=bi+1这是一条链，我们可以使用二分，每一次依次加边，直到>=mid,看能不能全部分配够。

T3

我在考场上，看到了这个：

测试点编号 \text{type} n = m=
1,2 A3 10
3,4 C3 10
5,6 A3 100
7 C3 100
8,9 A3 2\times 10^3
10,11 C3 2\times 10^3
12,13 A1 10^5
14, 15, 16 A2 10^5
17 A3 10^5
18,19 B1 10^5
20,21 C1 10^5
22 C2 10^5
23, 24, 25 C3 10^5

于是我先写了所有A的骗分，但时间复杂度算错了，只拿了\color {red} 24tps

T4

暴力

\color {red} 20tps

Part 2 赛后

T1

赛后我很快发现暴力断边的时间复杂度 5000*5000 完全可以啊,于是就\color{green} Accepted。

T2

肉眼可得: 我们可以使用二分答案，check的内容为长度大于等于mid是否能超过m个。

这道题我们可以发现每一个赛道可以分解为两条链，我们记录一下沿着每一个当前节点的子节点向下的最长链，为了满足要求，我们应当选择两条链使其最接近mid，如果剩下一些链没写，传上去。

（当然，如果一条链就大于mid了，便直接ans++）

这一段可以使用set实现，但我用的是数组。

for(int i=1;i<cnt;i++){
    if(vis[i]) continue;
    int it=lower_bound(a+i+1,a+cnt+1,mid-a[i])-a;
        if(it==cnt+1) continue;
        while(vis[it]&&it<cnt) it++;
        if(!vis[it]&&a[i]+a[it]>=mid)
            ans++,vis[i]=vis[it]=1;
    }

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=5e4+5;
int n,m;
int ans,mid;
int a[N],b[N],vis[N];
int tot,head[N],ver[N<<1],nxt[N<<1],edg[N<<1];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void add(int a,int b,int c){
    ver[++tot]=b,edg[tot]=c;
    nxt[tot]=head[a],head[a]=tot;
}
void dfs(int x,int fa){
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa) continue;
        dfs(y,x);
    }
    int cnt=0;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i],w=edg[i];
        if(y==fa) continue;
        if(b[y]+w>=mid) ans++;
        else a[++cnt]=b[y]+w;
    }
    sort(a+1,a+cnt+1);
    for(int i=1;i<=cnt;i++)
        vis[i]=0;
    for(int i=1;i<cnt;i++){
        if(vis[i]) continue;
        int it=lower_bound(a+i+1,a+cnt+1,mid-a[i])-a;
        if(it==cnt+1) continue;
        while(vis[it]&&it<cnt) it++;
        if(!vis[it]&&a[i]+a[it]>=mid)
            ans++,vis[i]=vis[it]=1;
    }
    b[x]=0;
    for(int i=1;i<=cnt;i++)
        if(vis[i]==0)
            b[x]=a[i];
}
bool check(int x){
    ans=0;
    dfs(1,0);
    return ans>=m;
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int a,b,l;cin>>a>>b>>l;
        add(a,b,l),add(b,a,l);
    }
    int l=0,r=1e17;
    while(l<r){
        mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<'\n';
    return 0;
}

by __H_J_M__

by huangjieming0703