一般构造题就是
1、先找到规律
2、然后确定算法
3、最后代码模拟生成。
代码
#include<stdio.h> #include<algorithm> #include<set> #include<vector> using namespace std; const int maxn = 100010; typedef long long ll; int K; ll table[maxn]; int ans[maxn]; int len; void init() { for(int i=1;i<maxn;i++) table[i]=table[i-1]+i; } void ok() { int cnt=0; for(int i=1;i<=len;i++) { set<vector<int> >SET; for(int l=1;l+i-1<=len;l++) { int r = l+i-1; vector<int>tp; for(int j=l;j<=r;j++) tp.push_back(ans[j]); if(!SET.count(tp)) { cnt++; SET.insert(tp); } } } if(cnt==K) puts("YES"); else puts("NO"); } void solve() { if(K<=1e5) { printf("%d\n",K); for(int i=1;i<=K;i++) printf("1%c",i==K?'\n':' '); return; } len = lower_bound(table,table+maxn,K)-table; int sheng = table[len]-K; for(int i=1;i<=len;i++) ans[i]=i; int p=len; while(sheng) { int k = upper_bound(table,table+maxn,sheng)-table; sheng-=table[k-1]; for(int i=p;p-i+1<=k;i--) ans[i]=p; p-=k; } printf("%d\n",len); for(int i=1;i<=len;i++) printf("%d%c",ans[i],i==len?'\n':' '); //ok(); } int main() { init(); while(scanf("%d",&K)==1) solve(); return 0; }