简单构造,设数列为1,1,…,1,2,2,…,2,3,3,….,3
设有x 个1,y 个 2, z 个 3,枚举x,,y即可。
不同的连续子序列有x + y + z + x*y + y*z + x*z。。。。
因为事实上K<=10^9时,最小的合法的 x 也不超过100.。。
所以复杂度远远没有想象中那么高。。。。。
Virtual ParticipationTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 237Accepted Submission(s): 56Special Judge
Problem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he asks rikka to have some practice on codeforces. Then she opens the problem B:Given an integer, she needs to come up with an sequence of integerssatisfying that the number of different continuous subsequence ofis equal to.Two continuous subsequencesare different if and only if one of the following conditions is satisfied:1. The length ofis not equal to the length of.2. There is at least one, wheremeans the-th element ofmeans the-th element of.Unfortunately, it is too difficult for Rikka. Can you help her?
Input
There are at most 20 testcases,each testcase only contains a single integer
Output
For each testcase print two lines.The first line contains one integers.The second line containsspace-separated integer- the sequence you find.
Sample Input
10
Sample Output
41 2 3 4
Author
XJZX
Source
#include <bits/stdc++.h>using namespace std;#define prt(k) cerr<<#k" = "<<k<<endlconst int N = 100000;int main(){int K;while (scanf("%d", &K)==1) {if (K<=2){if (K==1) puts("1\n1");if (K==2) puts("2\n1 1");continue;}bool f = 1;for (int x=0;f && x<=1e5;x++) {for (int y=0;x+y<=1e5&&x+y+x*y<=K&&y<=sqrt(K+0.5);y++){int t = K – x – y – x * y;if (t % (x+y+1)==0) {int z = t / (x + y + 1);if (z < 0 || x+y+z>min(N, K)) continue;assert(x+y+z+x*y+y*z+x*z==K);int n = x + y + z;printf("%d\n", n);for (int i=1;i<=n;i++) {int c;if (i<=x) c=1;else {if (i<=x+y) c = 2;else c = 3;}printf("%d%c", c, i==n ? 10 : ' ' );}f =false;break;}}}assert(!f);}}
版权声明:本文为博主原创文章,未经博主允许不得转载。
再长的路,一步步也能走完,再短的路,不迈开双脚也无法到达。