CatVirus

In the cat country, any cat family can be regarded as a rooted tree. As we all know, a kind of zombie virus hides in all the cats' bodies. Therefore, a cat family may consist of cats and zombies. When a cat is born, it may become a zombie. If a cat becomes a zombie, all of its offspring will also become zombies.

Now given an integer $K$ , you should construct a cat family with exactly $K$ ways to mark the identities (cat or zombie) of members of this family. Two ways are considered different if and only if there is at least one member that is marked as a cat in one way and marked as a zombie in the other way.

Formally, the vertices in a rooted tree will be marked black or white, and if a vertex is marked black, all the vertices in its subtree should also be marked black. Given a rooted tree, it's easy to calculate the number of possible valid ways to mark the vertices in the tree. Your task is to construct a rooted tree with exactly $K$ ways to mark your tree's vertices. Two ways are considered different if and only if there is at least one vertex such that in one way is marked black and marked white in the other way.

Let's denote the number of vertices of the tree you construct as $n$ , and label the vertices from $K$ to $n$ where vertex $K$ is the root.

The output should contain $n$ lines. In the first line, print one integer $n$ $(1 \le n \le 10^5)$ . In the each of the next $n-1$ lines, print two integers $u,v$ $(1 \le u, v \le n, u \neq v)$ describing an edge in your rooted tree.

It is guaranteed that at least one solution exists. If there are several possible valid solutions, you can print any of them.

#include<stdio.h> typedef long long ll; struct YPO {ll u,v; }gg[500050]; ll ci=1; int main() { ll n,k=1; scanf("%lld",&n); n-=1; while(n>1) { if(n&1!=0) { gg[ci].u=k; gg[ci].v=ci+1; k=ci+1; ci++; } gg[ci].u=k; gg[ci].v=ci+1; ci++; n>>=1; } printf("%lld\n",ci); for(int i=1;i<ci;i++) printf("%lld %lld\n",gg[i].u,gg[i].v); }

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll a[1]; int main(){ ll n,t=1,x=1; cin>>n; n--; while(n!=1){ if(n&1){ a[t]=x; x=++t; } a[t++]=x; n/=2; } cout<<t<<endl; for(int i=1;i<t;i++) cout<<a[i]<<" "<<i+1<<'\n'; }

详情