【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][]);
    }
}