趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
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]);
}
|