题目目录：1006 1003 1007
1006题 Cute Tree
题目大意：给出一段建树过程的伪代码，最后要求树中的结点个数tot。

思路：伪代码给的花里胡哨的，其实就是调用一次BuildTree()就tot++。本质是求递归次数，和数组A中的元素等于多少没有任何关系。当区间L==R，停止递归；当R-L=1，对区间二分再递归，即递归次数+2；当R-L≥2，对区间三分再递归，即递归次数+3。这道题的答案只与数组长度有关，拿样例解释：当n==7时，total=0，BuildTree(A,root,1,7)，对【1,7】三分得到【1,2】【3,4】【5,7】，total+=3。对【1,2】【3,4】进行二分，【5,7】进行三分，total+=2+2+3。最后别忘了加上第一次调用，total++。所以最后答案为11。读者可以思考，为何不能将total初始化为1，而是在最后加上1。因为如果total初始化为1，每次调用BuildTree()时会多加一个1。

#include <bits/stdc++.h>
using namespace std;
int a[200005];
int solve(int n){
    int num=0;
    if(n==1) num=num;
    else if(n==2) num+=2;
    else{
        num+=3;
        if(n%3==0) num+=3*solve(n/3);
        else if(n%3==1) num+=2*solve(n/3)+solve(n/3+1);
        else num+=solve(n/3)+2*solve(n/3+1);
    }
    return num;
}
int main(){
    int t,n,ans;
        std::ios::sync_with_stdio(false);//不用这个就会TEL
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        ans=solve(n);
        cout<<ans+1<<endl;
    }
    return 0;
}

另外给出标准程序std，用的是线段树的思想：

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
struct segment{
    int a[3];
}t[N<<2];
int n,cnt,x,T;
inline void build(int x,int l,int r){
    if(l==r) return;
    if(r==l+1){
         build(t[x].a[0]=++cnt,l,l);
         build(t[x].a[1]=++cnt,r,r);
         return;
     }
    int len=(r-l)/3+1;
    int a=l+len-1,b=a+r>>1;
    build(t[x].a[0]=++cnt,l,a);
    build(t[x].a[1]=++cnt,a+1,b);
    build(t[x].a[2]=++cnt,b+1,r);
}
int main(){
    scanf("%d",&T);
    while(T--){
        cnt=1;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)scanf("%d",&x);
        build(1,1,n);
        printf("%d\n",cnt);
    }
}

1003题 VC Is All You Need
题目大意：在示例中，不管点是蓝色或红色，你都可以在二维平面上找一条线来分隔这三个点，以保持相同颜色的点位于同一侧。但是在k维实欧氏空间R^k中，你能找到n个点满足在2^n个着色方案中的任何一个中总是存在一个k-1维超平面来分离它们吗？（其实笔者感觉题目有点漏洞，比如三个点在同一条线上的时候，红蓝红或者蓝红蓝排列就无法找到这样的线，但是题目好像没考虑这样的情况，或者说点组成的图形必须恰是k维空间的图形吧）

思路：k-1维超平面可以这么理解，立体的超平面是面，面的超平面是线，线的超平面是点。在k维空间中，最少只需要k个点就可以确定一个k-1维超平面，如果有2个点在k-1维超平面的两侧，那么必然存在至少一种情况，使得怎样也不可能用一个k-1维超平面将这k+2个点的颜***分开，并且当n大于k+2时也存在这样的结论（因为可以包含n==k+1的情形）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
ll t,n,k;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        if(n-2>=k) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
}

1007题 Banzhuan
题目大意：给出一个n×n×n的三维空间以及任意个1×1×1的立方体。要求摆出一个立体图形，使得它的三视图都是n×n的正方形。规定平面xOy代表地面，z轴描述高度。立方体是受重力的。即，当一个立方体下面是空的，这个立方体会下落直到它下面有另一个立方体或者接触地面。将立方体放在一个整数坐标(x，y，z)上，价格为xy^2z。输出最小成本和最大成本。

思路：最大成本是为放置n^3个立方体，并且都从z==n的高度释放使它下落，这样的花费一定是最大的。要计算最小的成本，只需要对z==1上的立方体进行分析，其他层数的花费都是这一层的2-n倍，所以只要第一层花费最小，其他层数照样往上垒n-1层即可。例举n==3，n==4，n==5的情况，可以知道z==1时，建造第一行和第一列（注意扣掉x==1&&y==1方块）的成本是最省的。这样我们就得到了计算最小成本的方法，只需要推出公式即可。但是在代码实现的过程中由于n≤10^18，如果计算组合数或者多个n相乘时数据肯定会爆的。由于我们知道a/b%c==((a%c)/b)%c,所以我们应该不停的对乘数的结果取模来保证数据不爆，并且这里采用了unsigned long long来储存。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int mod=1e9+7;
ll t,n;
ll kpow2(ll a,ll b){
    if(b==0) return 1;
    if(b%2==1) return a*kpow2(a,b-1)%mod;
    else {
        ll t=kpow2(a,b/2);
        return t*t%mod;                                                                                                                                     
    }
}
ll cc(ll a,ll b){
    ll ans=1;
    for(int i=1;i<=b;i++){
        ans=ans*(a-b+i)%mod;
        ans=ans*kpow2(i,mod-2)%mod;
    }
    return ans;
}
//这里用了一个计算大数据组合数的Lucas定理，不用这个其实也可以解决
ll l(ll a,ll b){
    if(b==0) return 1;
    return cc(a%mod,b%mod)*l(a/mod,b/mod)%mod;
}

int main(){
    cin>>t;
    while(t--){
        cin>>n;
        ll a1=l(n+1,2);
        ll a2=a1-1;
        ll b1=l(n+2,3)+l(n+1,3);
        cout<<(((a1+b1-2)%mod)*a2+a1*b1)%mod<<endl;   
        cout<<((((n%mod)*(n%mod))%mod)*((a1*b1)%mod))%mod<<endl;   
    }
}