hdu 5334 Virtual Participation 构造 Virtual Participation

63 阅读 0 评论 42 点赞

我是靠谱客的博主还单身小白菜，最近开发中收集的这篇文章主要介绍hdu 5334 Virtual Participation 构造 Virtual Participation，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Virtual Participation

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 639 Accepted Submission(s): 180
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?

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.

Sample Input

Sample Output

Author

XJZX

Source

2015 Multi-University Training Contest 4

题意：

给一个k，求出一个长度小于10^5的序列，该序列的不同子串的个数为k

分析：

求出第一个满足 n*（n+1)/2 >= k 的数字

然后对于F = n*(n+1)/2 - k，求出一些数，满足x1*(x1-1)+x2*(x2-1) ...... = F

第二个函数是有解的。bestcoder上有一题的题解说，任意数字，最少可以由3个三角数构成。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
int main(){
    ll k;
    while(scanf("%I64d",&k)!=EOF){
        if(k <= 100){
            printf("%I64dn",k);
            for(int i = 0;i < k; i++){
                if(i == 0)printf("1");
                else printf(" 1");
            }
            printf("n");
            continue;
        }
        vector<ll> head;
        ll n = 0;
        for(n = 0;;n++){
            if(n*(n+1)/2>=k) break;
        }
        ll su = n*(n+1)-2*k;
        while(su > 0){
            ll x = 0;
            for(x=0;;x++){
                if(x*(x+1) > su ) break;
            }
            head.push_back(x);
            su -= x*(x-1);
        }
        printf("%I64dn",n);
        int flag = 0,cnt = 1,L=0;
        for(int i = 0;i < head.size(); i++){
            for(int j= 0;j < head[i]; j++){
                if(flag) printf(" ");
                printf("%d",cnt);
                flag = 1;
            }
            L+=head[i];
            cnt++;
        }
        while(L<n){
            if(flag) printf(" ");
            printf("%d",cnt);
            cnt++;
            L++;
        }
        printf("n");
    }
    return 0;
}