查看: 946|回復: 0

[TIOJ] [遞推]1020 F.Number Insertion

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-2-12 11:21
  • 簽到天數: 2 天

    [LV.1]初來乍到

    18

    主題

    31

    帖子

    211

    積分

    好好學生

    Rank: 3Rank: 3

    積分
    211
    發表於 2014-9-23 08:03:51 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    原題:http://tioj.ck.tp.edu.tw/problems/1020
    測試結果:http://tioj.ck.tp.edu.tw/submissions/2492


    經觀察可以發現,一個K-合法序列是由K-1-合法序列加上K所形成的,經紙筆推演可發現答案增長的速度似乎不是很快,而且測資有限,於是我們可以離線計算後直接輸出答案

    如果這篇code在哪看過了,就當作是個秘密吧!

    [C++] 純文本查看 復制代碼
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    bool cmp(const vector<int> &a,const vector<int> &b)
    {
    	int i=0;
    	while(true){
    		if(a[i]!=b[i])
    			return a[i]>b[i];
    		++i;
    	}
    	return false;
    }
    int main()
    {
    	vector<vector<int>> D[32];
    	vector<int> tmp;
    	D[1].push_back({0,1});
    	for(int i=2;i<=31;++i)
    	{
    		for(const auto &d : D[i-1])
    		{
    			for(int j=0;j<d.size()-1;++j)
    			{
    				if(i%(d[j]+d[j+1])==0)
    				{
    					tmp=d;
    					tmp.insert(tmp.begin()+j+1,i);
    					D[i].push_back(tmp);
    				}
    			}
    		}
    		sort(D[i].begin(),D[i].end(),cmp);
    		cout<<"\"";
    		cout<<D[i].size()<<"\\n";
    		for(auto j:D[i][0])
    			cout<<j<<' ';
    		cout<<"\\n\","<<endl;;
    	}
    	return 0;
    }
    


    [C++] 純文本查看 復制代碼
    #include<cstdio>
    char ans[][1000]={
    "",
    "1\n0 1\n",
    "1\n0 2 1\n",//2
    "1\n0 2 3 1\n",
    "2\n0 4 2 3 1\n",
    "3\n0 4 2 5 3 1\n",
    "4\n0 6 2 5 3 4 1\n",
    "6\n0 6 2 7 5 3 4 1\n",
    "12\n0 8 4 6 2 7 5 3 1\n",
    "12\n0 8 4 6 2 9 7 5 3 1\n",
    "23\n0 10 2 3 4 9 5 6 7 8 1\n",
    "33\n0 10 2 3 4 9 5 11 6 7 8 1\n",
    "65\n0 12 6 8 10 2 11 9 7 5 3 4 1\n",
    "87\n0 12 6 8 10 2 13 11 9 7 5 3 4 1\n",
    "200\n0 14 2 12 10 13 3 4 9 5 11 6 7 8 1\n",
    "226\n0 14 2 15 3 4 5 6 13 7 8 9 10 11 12 1\n",
    "460\n0 16 8 12 4 14 10 6 2 15 13 11 9 7 5 3 1\n",
    "614\n0 16 8 12 4 14 10 6 2 17 15 13 11 9 7 5 3 1\n",
    "1247\n0 18 6 16 2 17 15 13 11 9 7 12 5 8 3 14 4 10 1\n",
    "1548\n0 18 6 16 2 19 17 15 13 11 9 7 12 5 8 3 14 4 10 1\n",
    "3032\n0 20 10 12 14 16 18 2 19 17 15 3 4 13 9 5 11 6 7 8 1\n",
    "3721\n0 20 10 12 14 16 18 2 21 19 17 15 3 4 13 9 5 11 6 7 8 1\n",
    "8035\n0 22 2 20 18 16 14 12 10 3 21 4 9 5 11 17 6 19 13 7 15 8 1\n",
    "12195\n0 22 2 20 23 3 21 4 18 5 6 7 8 17 9 19 10 11 12 13 14 15 16 1\n",
    "21696\n0 24 12 18 6 22 16 2 23 21 19 17 15 13 11 20 9 7 5 8 3 14 4 10 1\n",
    "26492\n0 24 12 18 6 22 16 2 25 23 21 19 17 15 13 11 20 9 7 5 8 3 14 4 10 1\n",
    "53504\n0 26 2 25 3 24 21 4 5 22 6 7 8 9 10 11 23 12 13 14 15 16 17 18 19 20 1\n",
    "71264\n0 26 2 27 25 3 24 21 4 5 22 6 7 8 9 10 11 23 12 13 14 15 16 17 18 19 20 1\n",
    "147392\n0 28 14 16 18 20 22 24 26 2 27 25 23 21 19 17 15 3 4 5 6 13 7 8 9 10 11 12 1\n",
    "216653\n0 28 14 16 18 20 22 24 26 2 29 27 25 23 21 19 17 15 3 4 5 6 13 7 8 9 10 11 12 1\n",
    "372984\n0 30 10 22 12 28 2 29 27 25 3 24 21 4 26 9 23 14 19 5 16 11 17 6 13 20 7 15 8 18 1\n",
    "365437\n0 30 10 22 12 28 2 31 29 27 25 3 24 21 4 26 9 23 14 19 5 16 11 17 6 13 20 7 15 8 18 1\n",};
    
    int main()
    {
    	int p;
    	scanf("%d",&p);
    	printf(ans[p]);
    }
    

    評分

    參與人數 1金幣 +3 收起 理由
    Sylveon + 3

    查看全部評分

    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表