专栏文章

题解：CF2162G Beautiful Tree

MMagallan_forever
CF2162G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mindjnga
此快照首次捕获于
2025/12/02 00:39
3 个月前
此快照最后确认于
2025/12/02 00:39
3 个月前
查看原文

简要说明题意：

给出 nn，构造一棵含 nn 个节点的树。一条边 (u,v)(u,v) 的权为 uvuv，要求树的边权之和是一个完全平方数。

题目分析：

想构造的方便一点，那我们构造的值最好是一个和 nn 有关的东西。由于 1+3+5+⋯+(2n−1)=n21+3+5+\dots+(2n-1)=n^2，所以想到把奇数和偶数分成两堆，大于 22 的偶数和 11 连接，大于 11 的奇数和 22 连接。
至于为什么不是奇数和 11，偶数和 22，我一开始也是这么构造的，式子会麻烦一些。 :(
nn 为偶数时，奇数偶数个数相等，nn 为奇数时，奇数比偶数多 11，式子会不一样，分开讨论。
偶数
记 n=2kn=2k，这个森林的和是 3k2+k−43k^2+k-4。
那我们连接 (k−1,k)(k-1,k)（还可以把两棵树连起来），配凑一个 k∗(k−1)k*(k-1)，得到 4k2−44k^2-4，再将 (1,4)(1,4) 改为 (2,4)(2,4)，得到了一个和为 4k2=n24k^2=n^2 的构造。
奇数
记 n=2k−1n=2k-1，和为 3k2−k−43k^2-k-4。
连接 (k,k+1)(k,k+1) 得到 4k2−44k^2-4，同理将 (1,4)(1,4) 改为 (2,4)(2,4)，得到一个和为 4k2=(n+1)24k^2=(n+1)^2 的构造。
然后注意一下 corner case。
偶数
n=2n=2 应该是 -1。
k=2,3k=2,3，即 n=4,6n=4,6 时，(k−1,k)(k-1,k) 会和 (2,3)(2,3) 重复。
k=4,5k=4,5，即 n=8,10n=8,10 时，(k−1,k),(2,4),(2,k)/(2,k−1)(k-1,k),(2,4),(2,k)/(2,k-1) 会成环。
奇数
同理，需要单独构造一下 n=3,5,7n=3,5,7。
梳理后感觉构造过程并不复杂，可是半夜做题让我多花了很多时间计算和查错。:(
代码如下：
CPP
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int T,n;
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>T;
    while(T--){
        cin>>n;
        if(n==2){
            cout<<"-1\n";
            continue;
        }
        if(n==6){
            cout<<"1 2\n";
            cout<<"1 3\n";
            cout<<"1 5\n";
            cout<<"1 6\n";
            cout<<"4 5\n";
            continue;
        }
        if(n==8){
            cout<<"1 2\n";
            cout<<"1 3\n";
            cout<<"1 4\n";
            cout<<"1 5\n";
            cout<<"1 6\n";
            cout<<"1 8\n";
            cout<<"3 7\n";
            continue;
        }
        if(n==10){
            cout<<"1 2\n";
            cout<<"1 3\n";
            cout<<"1 4\n";
            cout<<"1 5\n";
            cout<<"1 6\n";
            cout<<"1 7\n";
            cout<<"1 8\n";
            cout<<"1 9\n";
            cout<<"2 10\n";
            continue;
        }
        if(!(n&1)){
            cout<<(n>>1)-1<<' '<<(n>>1)<<'\n';
            cout<<"2 4\n";
            for(int i=6;i<=n;i+=2) cout<<"1 "<<i<<'\n';
            for(int i=3;i<=n;i+=2) cout<<"2 "<<i<<'\n';
            continue;
        }
        if(n==3){
            cout<<"1 3\n";
            cout<<"2 3\n";
            continue;
        }
        if(n==5){
            cout<<"1 3\n";
            cout<<"2 3\n";
            cout<<"3 4\n";
            cout<<"3 5\n";
            continue;
        }
        if(n==7){
            cout<<"1 2\n";
            cout<<"1 4\n";
            cout<<"1 5\n";
            cout<<"1 6\n";
            cout<<"1 7\n";
            cout<<"3 4\n";
            continue;
        }
        if(n&1){
            cout<<((n+1)>>1)<<' '<<((n+1)>>1)+1<<'\n';
            cout<<"2 4\n";
            for(int i=6;i<=n;i+=2) cout<<"1 "<<i<<'\n';
            for(int i=3;i<=n;i+=2) cout<<"2 "<<i<<'\n';
            continue;
        }
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...