【JZOJ4935】【NOIP2017GDKOI模拟1.12】b

Description

Data Constraint

Solution

這道題本來我是會的，隻因為我在考場上開了半個小時的車，然後就……

我們發現，對于一個節點，他假如有兩個兒子，這兩個兒子的size分别為x,y,那麼對答案的貢獻為(x+1)* (y+1)，他假如有一個兒子，這兩個兒子的size為x,那麼對答案的貢獻為x+1。是以我們可以這樣做：當目前n為奇數時，我們将目前點連出一個兒子，并将光标移向最後一個兒子；當目前n為偶數時，我們将目前點連出的兒子數量為它是2的次幂數+1，并将光标移向最後一個兒子。

Code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=; 
int n,i,t,j,k,l,x,y,num,ans[maxn][];
int main(){
    freopen("b.in","r",stdin);freopen("b.out","w",stdout);
    while (scanf("%d",&n)!=EOF){
        num=;x=;
        while (n>){
            if (!(n%)){
                while (!(n%)) ans[num][]=x,ans[num][]=++num,n/=;
                if (n>){
                    ans[num][]=x,ans[num][]=++num;
                    n--;x=num;
                }
            }else{
                ans[num][]=x,ans[num][]=++num;
                n--;x=num;
            }
        }
        printf("%d\n",num);
        for (i=;i<num;i++)
            printf("%d %d\n",ans[i][],ans[i][]);
    }
}