2016年1月15日 星期五

[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;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原