- xuorange 的博客
CF1202D 题解
- 2022-5-28 11:19:51 @
先来找找规律:
数字 | 13337 | 1333337 | 133777 | 111337 |
---|---|---|---|---|
含有1337的个数 | 3 | 10 | 3 |
显然后两种比较简单,于是直接开始试。
#include<iostream>
using namespace std;
int main(){
int q,n;
cin>>q;
while(q--){
cin>>n;
cout<<"133";
while(n--)cout<<"7";
cout<<endl;
}
return 0;
}
然后TLE了(理所当然......
也就是说不能只插入效率低的1和7,应该再来一些3。
数字 | 1337 | 13337 | 133337 | 1333337 | 13333337 | 133333337 |
---|---|---|---|---|---|---|
含有1337个数 | 1 | 3 | 6 | 10 | 15 | 21 |
说明,在有x个3、1个1、1个7时,1337的个数 个
但 这种整数比较罕见(如1、3、6、10等),我们还应该插入一些1或7(在这里我选的是1,你也可以用7)。
所以可以取小于n(题目要求的1337子序列的个数)的第一个 ,再通过插入若干个1补上需要的 个1337即可。
由于我这个解法用了预处理(暴力枚举x(x-1)/2),所以代码很容易理解。
Code(有陷阱,请不要直接抄)
#include<bits\stdc++.h>
using namespace std;
#define ll long long
ll n,C[114514];
int mian(){
int t;
cin>>t;
for(ll i=1;i<=114514;i++) //暴力枚举x(x-1)/2
C[i]=i*(i-1)/2;
while(t--){
scanf("%lld",&n);
ll orange=1;
while(C[orange+1]<=n)orange++;
if(C[orange]==n){ //运气好
cout<<1;
for(int i=1;i<=orange;i++)cout<<3;
cout<<7<<'\n';
cantinue;
}
for(int i=orange;i>=2;i--){
while(n>=C[i]){
n-=C[i];
printf("1");
}
cout<<3;
}
cout<<3; //别落下3
cout<<7<<'\n';
}
}