P00573. 冲锋

2023-11-27 07:53:09

Description

J将军正在组织他手下的士兵攻击敌人。J将军发现不能让所有的士兵一次性压上。而是应该分成若干个梯队，这些梯队的人数最好形成连续的正整数。例如当他手下有15个士兵时。他应该有以下几种分法

15=1+2+3+4+5

15=4+5+6

15=7+8

但他同时也发现如果手上只有4个士兵时，则无法进行这样的分解。现在给出J将军手下的士兵人数N，请问他能不能进行分解

Format

Input

一行给出数字N

Output

如果能分解就输出“YES”，否则输出"NO"

Samples

输入数据 1

输出数据 1

YES

Limitation

1s, 1024KiB for each test case.

题解

题意简化：询问一个数能否分解成2个及以上的连续自然数之和

暴力：

枚举开始点i，结束点j，求和即可

#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
    char c=getchar();int f=0;x=0;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
    if(f==-1)x=-x;
}
int main()
{
    int n;
    read(n);
    for(int i=1;i<=n/2;i++)
    for(int j=i+1;j<=n;j++)
    {
        int ans=(i+j)*(j-i+1);
        if(ans==2*n)
        {
            printf("YES");
            return 0;
        }
    }
    printf("NO");
    return 0;
}

这样的话复杂度到了O(n^2)

本蒟蒻刚开始是这样写的，还很烦看不到数据，但是我看到可以看到数据的大小，一看10bytes，瞬间人傻了，竟然到了10^10

优化

我们假设输入的数为w，数列的开始点为i，结束点为j

那么(i+j)(j-i+1)/2=w

所以我们可以解得j=sqrt(2*n+i*i-i+0.25)-0.5;(简单的一元二次，刚开始公式法写爆了，*用配方法)

所以我们只要枚举i，判断j是否是整数，而i最大取到n/2，所以我们就可以降低复杂度到O(n/2)，但对于10^10，可能是数据原因，用了384ms

话不多说，上代码

ps：十年OI一场空，不开long long见祖宗

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll n;
    cin>>n;
    for(ll i=1;i<=n/2;i++)
    {
        double j=sqrt(2*n+i*i-i+0.25)-0.5;
        if((ll)j==j&&i<j)
        {
            printf("YES");
            return 0;
        }
    }
    printf("NO"); 
    return 0;
}