[NC20650] 可爱の星空

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

“当你看向她时，有细碎星辰落入你的眼睛，真好。”——小可爱

在一个繁星闪烁的夜晚，卿念和清宇一起躺在郊外的草地上，仰望星空。

星语心愿，他们，想把这片星空的星星，连成一棵漂亮的树，将这美好的景色记录下来。

现在，天上共有n颗星星，编号分别为1,2…..n，一开始任何两个点之间都没有边连接。

之后，他们两个想在在(u,v)之间连无向边，需要付出|u联通块大小-v联通块大小|的代价。

他们两个想用最少的代价来使这n个点联通，所以他们想知道最小代价是多少。

(多组数据

输入描述:

1
2
3
第一行一个正整数，表示数据组数T

接下来T行每行一个正整数，表示询问的n

输出描述:

1
T行，每行一个数表示答案

输入

1
2
1
5

输出

1
2

说明

1
2
3
1,2....5五个点，连边顺序为(1,2),(3,4),(1,5),(5,3),代价为0,0,1,1，总代价为2，是n=5的时候最优答案。

虽然(1,2),(2,3),(3,4),(4,5)也可以，但是代价为0,1,2,3，总代价为6，比2大。

备注:

1
2
3
4
5
6
7
对于20%的数据，T<=2,n<=10

对于40%的数据，T<=10,n<=1000

对于60%的数据，T<=100000,n<=100000

对于另外40%的数据，T=1,n<=1000000000000

题解:

题目解析:

一开始并没有理解什么是|u联通块大小-v联通块大小|,后来才看懂这个连通块大小是连到这个节点的顶点个数+它本身.

题目使用递归解决,显然开dp扫数组肯定炸:1000000000000这么大的数据.一开始并不知道怎么做,后来看了别人的题解:

  • 就示例输出为例:

    1
    2
    3
           5
       2       3
    1     1 1     2

    5是由这种构造方式组成的,使用对半分的方式显然可以得到最佳结果,也就是最少的代价,但是我证明不出来.

于是我们就可以构造递推了,代码如下:

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
typedef long long ll;

ll solve(ll n){
    if(n == 1 || n == 2){
        return 0;
    }
    if(n&1) {
        return solve(n >> 1) + solve((n >> 1) + 1) + 1;
    }
    return solve(n >> 1) * 2;
}

int main(){
    ll n;
    int T;
    cin >> T;
    while(T--){
        cin >> n;
        cout << solve(n) << endl;
    }
    return 0;
}

吐槽+小技巧

我刚刚从别人那边学到了个判断是否是偶数的方式:

1
n&1

如果是奇数则返回1,如果是偶数则返回0.

写这个代码的时候我真没想到solve函数也能爆int,于是WA了一个测试点= =