JZTXT

普及模拟3

发布时间 2023-08-22 14:39:31作者: The_Shadow_Dragon

普及模拟3

\(T1\) 最大生成树 \(100pts\)

  • 简化题意：给定一个 \(n\) 个点的完全图，给定各点的点权 \(a_i(1 \le i \le n)\) ，两点间的边权为 \(|a_i-a_j|\) ，求该图的最大生成树。
  • 正解：贪心，考虑到一个点对答案产生的贡献为 \(\max(a_i-\min\limits_{j=1}^{n} a_j,\max\limits_{j=1}^{n} a_j-a_i)\) ，又因为是完全图，易证得连边后一定是符合题意的解。
    ll a[100001];
int main()
{
    ll n,i,ans=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(i=1;i<=n-1;i++)//只需要n-1条边
    {
        ans+=max(a[n]-a[i],a[i]-a[1]);
    }
    cout<<ans<<endl;
    return 0;
}

\(T2\) 红黑树 \(80pts\)

  • 简化题意：

\(T3\) 校门外的树 \(0pts\)

  • 简化题意：
  • 部分分：
    • \(30pts\) ：\(n^2\) 暴力枚举。
    • \(20pts\) ：考虑到没有修改操作，维护一下即可。
  • 正解：建一棵线段树，

\(T4\) 种树 \(0pts\)

  • 简化题意：

总结

  • \(T1、T3、T4\)打到 \(8:30\) ，\(9:30\) 打完 \(T2\) 后就去打高斯消元了，导致没有看见 \(T3\) 的对 \(2^{64}\) 取模（打成了 \(2^{60}\) ）。
  • \(T4\) 没有再多想想，没骗到计数类型的 \(DP\) 分。