[HOJ 287][Codeforces #145]Practice

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

可以想像，一開始所有的蘿莉都黏在一起
每比一場比賽，就好像把黏在一起的蘿莉「切開」
而最後的目標是：要把蘿莉切成變一隻一隻的
(好恐怖><)
首先可以知道，最後一定是切剛好N-1刀，每一回合可以切幾刀端看現在有幾團蘿莉
可以發現，如果有任何一回合沒有切開所有團，那麼一定是吃虧
那問題就變成要怎麼讓每一回合蘿莉的團數盡量大
當然就是平分啦(證明呢？想一想，為甚麼XD　提示：可以往二元樹去想)
所以只要寫一個程式模擬切蘿莉的過程，在切每一團蘿莉時都盡量平分，然後記錄下中間結果
最後一次輸出答案即可

code:

#include<cstdio>
#include<vector>
using namespace std;
int N;
vector<int>S[2];
vector<vector<int> >ANS;
int main()
{
    while(scanf("%d",&N)==1)
    {
        S[0].clear(),S[0].push_back(0),S[0].push_back(N);
        ANS.clear();
        int d=0;
        for(;(int)S[d].size()<N+1;d^=1)
        {
            S[d^1].clear();
            vector<int>ans;
            for(int i=0;;i++)
            {
                S[d^1].push_back(S[d][i]);
                if(i+1==(int)S[d].size())break;
                if(S[d][i]+1<S[d][i+1])
                {
                    const int mid=(S[d][i]+S[d][i+1])/2;
                    for(int j=S[d][i];j<mid;j++)ans.push_back(j);
                    S[d^1].push_back(mid);
                }
            }
            ANS.push_back(ans);
        }
        printf("%d\n",(int)ANS.size());
        for(const auto &ans:ANS)
        {
            printf("%d",(int)ans.size());
            for(const int v:ans)printf(" %d",v+1);
            puts("");
        }
        break;
    }
    return 0;
}