ZOJ 3768 Continuous Login（找规律+哈希）

系统管理员 2022-06-03 08:59 94阅读 0赞

Pierre is recently obsessed with an online game. To encourage users to log in, this game will give users a continuous login reward. The mechanism of continuous login reward is as follows: If you have not logged in on a certain day, the reward of that day is 0, otherwise the reward is the previous day's plus 1.

On the other hand, Pierre is very fond of the number N. He wants to get exactly Npoints reward with the least possible interruption of continuous login.

Input

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:

There is one integer N (1 <= N <= 123456789).

Output

For each test case, output the days of continuous login, separated by a space.

This problem is special judged so any correct answer will be accepted.

Sample Input

4
    20
    19
    6
    9

<h4< dd="">

Sample Output

4 4
    3 4 2
    3
    2 3

Hint

20 = (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4)

19 = (1 + 2 + 3) + (1 + 2 + 3 + 4) + (1 + 2)

6 = (1 + 2 + 3)

9 = (1 + 2) + (1 + 2 + 3)

Some problem has a simple, fast and correct solution.

题解：

列几组数据可以发现最多有3组组成一个数字，然后就打表，用map记录下该数字下是加到几的结果，然后分三种情况：第一种是一个数字就可以组成，这个直接哈希判断就好，第二种是两个数字组成，这个用枚举第一个数字+第二个哈希判断就好了，第三种是三个数字组成，枚举前两个第三个数字用哈希判断

代码：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<queue>
    #include<stack>
    #include<math.h>
    #include<vector>
    #include<map>
    #include<set>
    #include<stdlib.h>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    #define ll long long
    map<int,int>M;
    int a[15750];
    void init()
    {
        int i,j,s=0;
        for(i=1;i<=15720;i++)
        {
            s+=i;
            M[s]=i;
            a[i]=s;
        }
    }
    int main()
    {
        int i,j,k,n,test,tag;
        init();
        while(scanf("%d",&test)!=EOF)
        {
            while(test--)
            {
                scanf("%d",&n);
                if(M[n])
                {
                    printf("%d\n",M[n]);
                }
                else
                {
                    tag=0;
                    for(i=1;a[i]<n;i++)
                    {
                        if(M[n-a[i]])
                        {
                            printf("%d %d\n",i,M[n-a[i]]);
                            tag=1;
                            break;
                        }
                    }
                    if(!tag)
                    {
                        for(i=1;a[i]<n;i++)
                        {
                            for(j=1;a[i]+a[j]<n;j++)
                            {
                                if(M[n-a[i]-a[j]])
                                {
                                    printf("%d %d %d\n",i,j,M[n-a[i]-a[j]]);
                                    goto loop;
                                }
                            }
                        }
                        loop:;
                    }
                }
            }
        }
        return 0;
    }