hdu 4982 Goffi and Squary Partition

Goffi and Squary Partition

Time Limit: / MS (Java/Others)    Memory Limit: / K (Java/Others)
Total Submission(s): Accepted Submission(s): Problem Description
Recently, Goffi is interested in squary partition of integers. A set X of k distinct positive integers is called squary partition of n if and only if it satisfies the following conditions:
[ol]
the sum of k positive integers is equal to n
one of the subsets of X containing k− numbers sums up to a square of integer.
[/ol]
For example, a set {, , , } is a squary partition of because + + + = and + + = = × . Goffi wants to know, for some integers n and k, whether there exists a squary partition of n to k distinct positive integers. Input
Input contains multiple test cases (less than ). For each test case, there's one line containing two integers n and k (2≤n≤200000,2≤k≤30). Output
For each case, if there exists a squary partition of n to k distinct positive integers, output "YES" in a line. Otherwise, output "NO". Sample Input Sample Output
NO
YES
YES

题意:输入整数n和k,要求把n分成k个数之和的形式,其中存在k-1个数之和为一个完全平方数,而且这k个数各不相同。
分析: 我们尝试枚举那个完全平方数 S,然后看能否将他拆分为 K-1 个数,并且不用到N-S 这一步可以用贪心+一次调整来搞定。为了保证 K-1 个数都不同,我们尝试尽量

用 1,2,3...这些连续自然数来构造,如果 N-S 出现在这些数中,那么将 N-S 移除,再新加一个数。最后一个数由S-sum(1~k-2)(包括调整过的)来得到。

  • 1.如果sum值大于S值,可以分成两种情况来看

1.1 前k-2个数中不存在N-S,那么原数列为1,2,3,....,k-2,其中的和大于等于S值,且最小的数为1,没有剩余的空间减少这k-2个数的和

1.2 前k-2个数中存在N-S,设x等于N-S那么原数列为1,2,....x-1,x+1,.....,k-1,其中多出来的空间为避免N-S,同样不存在剩余空间减少和

  • 2.如果倒数最后一个数在前面k-2个数中出现,由上面结论可知,必定存在冲突,且无法调整
  • 3.如果倒数最后一个数与N-S相等,那么可以使得倒数第一个数-1和倒数第二个数+1,这样的调整代价是最小的,如果这样的处理方式仍存在冲突,就为错
#include <cstdio>
using namespace std;
int pnt[],top;
int n,k;
bool check(int x)
{
int sum=,top=;
int r=n-x,cc=,cnt=;
pnt[top++]=;
for(int i=; i<k-; i++)
{
cc++;
if(cc==r) cc++;
pnt[top++]=cc;
sum+=cc;
}
if(sum>=x) return false;
pnt[top]=x-sum;
if(pnt[top]<=pnt[top-]) return false;
if(pnt[top]==r)
{
if(pnt[top-]+>=pnt[top]-) return false;
}
return true;
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
int flag=;
for(int i=; i<=; i++)
{
if(i*i>=n) break;
if(check(i*i))
{
printf("%d\n",i*i);
printf("YES\n");
flag=;
break;
}
}
if(flag) continue;
printf("NO\n");
}
return ;
}
上一篇:收集一些java相关的文章


下一篇:【摘】Chrome解决高版本Stable Beta扩展程序强制停用问题