2015 Multi-University Training Contest 4 hdu 5334 Virtual Participation
HDU 2015 multi Virtual Contest Training University
2023-09-11 14:15:28 时间
Virtual Participation
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 705 Accepted Submission(s): 202
Special 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 K, she needs to come up with an sequence of integers A satisfying that the number of different continuous subsequence of A is equal to k.
Two continuous subsequences a, b are different if and only if one of the following conditions is satisfied:
1. The length of a is not equal to the length of b.
2. There is at least one t that at≠bt, where at means the t-th element of a and bt means the t-th element of b.
Unfortunately, it is too difficult for Rikka. Can you help her?
Given an integer K, she needs to come up with an sequence of integers A satisfying that the number of different continuous subsequence of A is equal to k.
Two continuous subsequences a, b are different if and only if one of the following conditions is satisfied:
1. The length of a is not equal to the length of b.
2. There is at least one t that at≠bt, where at means the t-th element of a and bt means the t-th element of b.
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 K (1≤K≤109)
Output
For each testcase print two lines.
The first line contains one integers n (n≤min(K,105)).
The second line contains n space-separated integer Ai (1≤Ai≤n) - the sequence you find.
The first line contains one integers n (n≤min(K,105)).
The second line contains n space-separated integer Ai (1≤Ai≤n) - the sequence you find.
Sample Input
10
Sample Output
4
1 2 3 4
Author
XJZX
Source
解题：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int calc(int k) { 4 int ret = 1; 5 while(ret*(ret+1)/2 < k) ++ret; 6 return ret; 7 } 8 int calc2(int x) { 9 int ret = 1; 10 while(ret*(ret-1)/2 <= x) ++ret; 11 return ret-1; 12 } 13 int main() { 14 int k; 15 while(~scanf("%d",&k)) { 16 if(k <= 100000) { 17 printf("%d\n",k); 18 for(int i = 1; i < k; ++i) 19 printf("1 "); 20 puts("1"); 21 continue; 22 23 } 24 int n = calc(k); 25 int b = n*(n+1)/2 - k; 26 int cnt = 0,d = 1; 27 printf("%d\n",n); 28 while(b > 0) { 29 int e = calc2(b); 30 for(int i = 0; i < e; ++i) { 31 printf("%d%c",d,cnt+1==n?'\n':' '); 32 cnt++; 33 } 34 b -= e * (e - 1) / 2; 35 d++; 36 } 37 for(; cnt < n; ++cnt) 38 printf("%d%c",d++,cnt+1==n?'\n':' '); 39 } 40 return 0; 41 }