网址:http://codeforces.com/problemset/problem/1202/D 题意: 输入一个$n$,输出一个只含有$1,3,7$的字符串,字符串中有$n$的子序列$1337$,长度不超过$1e5$。 题解: 首先我们知道$C_{2}^{n}=\frac {n(n
网址:http://codeforces.com/problemset/problem/1202/D
题意:
输入一个$n$,输出一个只含有$1,3,7$的字符串,字符串中有$n$的子序列$1337$,长度不超过$1e5$。
题解:
首先我们知道$C_{2}^{n}=\frac {n(n-1)}{2}$所以如果是满足$n=\frac {x(x-1)}{2}$的,输出$133.....3337$(含有$x$个$3$)即可。这一点是显然的。然后如果不满足呢。这个比赛时真的想不到,后面就想清楚了。首先因为不再满足$n=\frac {x(x-1)}{2}$,我们找到距离$n$最近且小于$n$的$\frac {x(x-1)}{2}$,计算出$rem=n-\frac {x(x-1)}{2}$,然后构造字符串$13377.....7733......337$(含有$rem$个$7$和$k$个$3$)。这个$k$应如何计算呢?又前面构成的子序列含有$rem$个子序列,然后后面含有$C_{k}^{2}个$,前后各取一个$3$的有$2 \cdot k$个,然后再加上前面的$133$和最后的$7$,有$1$个,所以$n=n-\frac {x(x-1)}{2}+C_{k}^{2}+2 \cdot k+1$个,由于$n,x$已知,可计算出$k$。
AC代码:
#include <bits/stdc++.h> using namespace std; long long num[100005]; void init() { for(long long i=1;i<100005;++i) num[i]=i*(i-1)/2; } int main() { init(); int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); int pos; for(pos=1;num[pos]<=n;++pos); pos-=1; if(n-num[pos]) { cout<<"133"; for(int i=0;i<n-num[pos];++i) cout<<‘7‘; for(int i=0;i<pos-2;++i) cout<<‘3‘; cout<<‘7‘; cout<<endl; } else { cout<<‘1‘; for(int i=0;i<pos;++i) cout<<‘3‘; cout<<‘7‘; cout<<endl; } } return 0; }