HDU 5334 Virtual Participation（2015多校第四场）

 

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?

 

Input

 

There are at most 20 testcases，each testcase only contains a single integer K (1≤K≤10⁹)

 

Output

 

For each testcase print two lines.

The first line contains one integers n (n≤min(K,10⁵)).

The second line contains n space-separated integer A_i (1≤A_i≤n) - the sequence you find.

 

Sample Input

 

10

 

Sample Output

 

4

1 2 3 4

 

 

题意：给一个整数k，输出一个长度为n的数列。要求这个数列的所有不为空且不相同的连续子序列的个数为k。

 

 

题解：当数列元素都为1时，数列子序列个数为k。所以当k小于等于10⁵时，可以直接输出k个1。

 

当k大于10⁵时，对于一个1到n的数列，该数列的子序列个数m为n(n+1)/2。如果我们将某个不与1相邻的数替换为1， 那么其m值就会减1；如果是从2的位置开始连续将x个数变为1，其m值减少x(x+1)/2。比如 1 2 3 4 5 6 7 8将3个数变为1后为 1 1 1 1 5 6 4 8，m值减少了6。

 

对于给定的k，我们可以先找到一个子序列个数大于等于k且最接近的数列n，则这个数列的长度就是我们所要求的数列的长度。当m>k时，求出连续1的个数和不连续1的个数， 将相应位置的数替换成1。

 

 

 

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int pos[45000];  //存储数列的子序列的个数
void F()
{
    for (int i=1; i<44730; i++)
        pos[i] = (i * i + i) / 2;
}
int main()
{
    F();
    int k;
    while (~scanf("%d", &k)){
        if (k <= 100000){
            printf("%d
", k);
            for (int i=1; i<k; i++)
                printf("1 ");
            printf("1
");
        }
        else{
            int x;
            //找到子序列个数大于k的数列n
            for (int i=1; i<44730; i++)
                if (pos[i] >= k && pos[i-1] < k){
                    x = i;
                    break;
                }
            //数列n中不与1相邻元素所要替换成1的个数
            int y = pos[x] - k;
            printf("%d
", x);
            int temp;
            //找到连续1的个数
            for (int i=1; i<44730; i++)
                if (pos[i] <= y && pos[i+1] > y){
                    temp = i;
                    break;
                }
            printf("1");
            for (int i=1; i<=temp; i++)
                printf(" 1");
            //不与1相邻元素所要替换成1的个数
            y = y - pos[temp];
            int ans = 1;
            for (int i=temp+2; i<=x; i++){
                ans++;
                 if (ans % 2 && y > 0){
                    printf(" 1");
                    y--;
                 }
                 else
                    printf(" %d", i);
            }
            printf("
");
        }
    }
    return 0;
}