Goffi and Squary Partition

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1171    Accepted Submission(s): 402

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−1 numbers sums up to a square of integer.

[/ol]
For example, a set {1, 5, 6, 10} is a squary partition of 22 because 1 + 5 + 6 + 10 = 22 and 1 + 5 + 10 = 16 = 4 × 4.

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 10000). 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
2 2
4 2
22 4
 
Sample Output
NO
YES
YES
 
Source
 
构造数组出来,真的难想到,无比佩服能够想到的大牛。。分析都在代码里。。
/**
题意:给你k个数(各不相同的正整数),它们的和是n,问是否存在k-1个数的和是某个数的平方?
分析:我们假设其中k-1个数个数的平方为 m , m 应该不小于 k*(k-1)/2,不然就会有重复的 。
我们可以通过构造一个序列来判断是否满足条件。
*/
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
typedef long long LL; int n,k;
bool judge(int m){
int t = n-m, sum = (k-)*k/;
if(sum>m) return false; ///k-1项最小都要 sum
int count=,x=;
for(int i=;i<k-;i++){ ///构造出一个序列包含剩下的序列中的 k - 2 项
x++;
if(t==x) x++;
count+=x;
}
int lastnum = n-count-t; ///剩下的序列中的第 k-1 个数
if(lastnum<=x) return false; ///如果最后一个数小于 x ,那么之前肯定存在过了
x++;
if(t==x||t==x+){ ///如果 t == x 或者 t==x+1 那么当 第k-1个数等于t 的时候我们无法通过改变前k-2
///项的值令 lastnum != t 了,如果t更大一些,我们是可以通过改变 k-1这个序列的值
///来让 lastnum != t 的.
if(lastnum==t) return false;
}
return true;
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF){
bool flag = false;
for(int i=;i*i<n;i++){
int m = i*i;
if(judge(m)){
flag = true;
break;
}
}
if(flag) printf("YES\n");
else printf("NO\n");
}
return ;
}

最新文章

  1. class-dump获取iOS私有api
  2. Linux 多线程编程 实例 2
  3. 通通的最后一篇博客(附自制html5平面射击小游戏一枚)
  4. 【转发】构建高可伸缩性的WEB交互式系统(上)
  5. Android开发优化
  6. poj 1664 放苹果_整数拆分
  7. python实现刷博器(适用于新浪、搜狐)
  8. Sql CE 数据库编程
  9. 120. Triangle(中等)
  10. selenium-确认进入了预期页面
  11. C语言 &#183; 8皇后问题
  12. 《OKR工作法》读书笔记(转)
  13. (原创)PouchDB 图片本地存储(web离线应用)
  14. Django+Uwsgi+Nginx项目部署文档
  15. 降阶法计算行列式方法有个地方有Bug(原文也已更正,此为更正后部分)
  16. 『PyTorch』第九弹_前馈网络简化写法
  17. lua闭包与简易迭代器实现
  18. remote link Centos6.6 Horrible Slow
  19. 扩展-Easyui Datagrid相同连续列合并扩展(一)
  20. java多线程以及Android多线程

热门文章

  1. A1025 PAT Ranking (25)(25 分)
  2. HBase(0.94.5)的Compact和Split源码分析
  3. Django--源码安装
  4. 如何使用DroidPlugin——DroidPlugin初体验
  5. HDU 5657 CA Loves Math 状压DP + 枚举
  6. SSH进阶之路
  7. IOS开发---菜鸟学习之路--(二十二)-近期感想以及我的IOS学习之路
  8. 聊聊、Java 命令 第二篇
  9. Linux编程之变量
  10. 贪吃蛇—C—基于easyx图形库(上):基本控制函数实现 画图程序