10月15日复盘

xueyuhui917 · 2023-10-16 22:13:51 · 生活·游记

A

本来，这道题是老师用来诈骗我们的

结果，我们发现这道题有线段树做法，反倒是我被骗了 -- by teacher

然而我们还是被骗了。我们一开始以为是数据的问题，直到我们发现 #1 测试点的树，四个点编号不是1、2、3、4，也不是0、1、2、3，而是1、2、3、8！

一道不折不扣的诈骗题，正解是倒着往前推，线段树类似做法（如分块和ODT）+离散化也可行。

B

字符串模拟。

我写的时候采用了类似字典树的写法，比如说下面这堆文件：

CCF/CSP/RP/plus/plus
IOI/AK/me
CCF/NOIP/RP/plus/plus
CCF/CSP/J
CCF/CSP/S

则我会构造这么一个玩意：

根目录上要处理一下，毕竟原题是没有根目录这个玩意的。

以及让一个文件既隐藏又显示是什么意思

C

结论题：答案为两倍的树边长总和减去直径长度。

方法是：两个人走到直径，然后往两边散开。

大致是类似于下面这个图：

D

并查集乱搞。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+100;
struct eg
{
    int u,v,w;
    bool friend operator <(const eg &x,const eg&y)
    {
        return x.w>y.w;
    }
 };
 eg e[N];
 int p[N],f[N];
 int F(int x){return x==f[x]?x:f[x]=F(f[x]); }
 signed main()
 {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=0;
        f[i]=i;
     }
     for(int i=1;i<=m;i++)
     {
        int u,v,w;cin>>u>>v>>w;
        e[i]={u,v,w};
     }
     sort(e+1,e+m+1);
     long long as=0;
     for(int i=1;i<=m;i++)
     {
        int u=F(e[i].u),v=F(e[i].v),w=e[i].w;
        if(u==v)
        {
            if(!p[u])
            {
                p[u]=w;
             }
             else as+=w+p[u],p[u]=0;
         }
         else
         {
            f[v]=u;
            if(!p[u]&&!p[v])p[u]=w;
            else if(!p[u]||!p[v])as+=w+p[u]+p[v],p[u]=0;
            else as+=w+max(p[u],p[v]),p[u]=min(p[u],p[v]);
         }
     }
     cout<<as;
 }