http://acm.hdu.edu.cn/showproblem.php?pid=4982
Goffi and Squary PartitionTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 308 Accepted Submission(s): 106Problem 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]
Input
Input contains multiple test cases (less than 10000). For each test case, there's one line containing two integers \(n\) and \(k\) (\(2 \le n \le 200000, 2 \le k \le 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
Recommend
|
题意：给出n和k，求k个不同的正整数，使其中k-1个数能组成平方数，k个数的和为n。有解输出YES，无解输出NO。
题解：从大到小枚举小于n的平方数，剪枝搜索是否有解。
先判一下是不是1~k这最小的k个数加起来都超过n，这种情况肯定不可能，真去搜一遍的话太费时间了，还是特判掉比较好。
if((+k)*k/>n)return ;
枚举平方数，进入搜索：
t=sqrt(1.0*n);
if(t*t==n)t--;
for(i=t; i>=; i--) {
int lost=i*i;
Remove(n-lost);
if(dfs(lost,,R[n]))return ;
Resume(n-lost);
}
↑（这个在函数里，return 1是有解。）
这题每个数只用一次，所以枚举一个数，下个数可以从这个数+1开始枚举。我使用了DancingLinks那种超碉的结构，不过其实只用一个used[]就好了……
比赛的时候这样就能过了，因为n大的时候很容易就找到解，dfs不耗多长时间。不过今天一看居然加强了数据，会TLE，所以我们来加个剪枝：
当枚举第x个数时，剩下(k-x+1)个数，枚举i为当前的数，如果i+ (i+1)+(i+2)+...+(i+k-x)这以i开头的最小的k-x+1个数都大于剩下的数了，就不用继续枚举i了。
等差数列求和，(i + i+(k-x))*(k-x+1)/2 > lost，搞一搞可以把 i 移出来，得到i的最大值。
DFS代码：
bool dfs(const int &lost,const int &x,const int &now) {
if(x>k) {
if(lost==)
return ;
else return ;
}
if(lost<=)return ;
if(x!=k) {
int maxi=((lost+lost)/(k-x+)-(k-x))/;///剩下的大于i的最小的(k-x+1)个数加起来超的话就跳
maxi=min(maxi,n-);
for(int i=now; i<=maxi; i=R[i]) {
Remove(i);
if(dfs(lost-i,x+,R[i]))return ;
Resume(i);
}
} else {
if(L[R[lost]]==lost) {
Remove(lost);
if(dfs(,x+,R[lost]))return ;
Resume(lost);
}
}
return ;
}
（这题的正解好像是各种情况都考虑一下，直接几个if就判出来了……我是不太懂）（还有官方题解说平方数只用枚举最大的那个就行，可是8 2这组数据，最大的平方数是4，然后就逗乐啊……虽然好像只有这一组数据有问题）
全代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) prllf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout)
#define mp make_pair
#define pb push_back const int maxn=;
int L[maxn],R[maxn];
inline void Remove(int x) {
L[R[x]]=L[x];
R[L[x]]=R[x];
} inline void Resume(int x) {
L[R[x]]=x;
R[L[x]]=x;
} int n,k; bool dfs(const int &lost,const int &x,const int &now) {
if(x>k) {
if(lost==)
return ;
else return ;
}
if(lost<=)return ;
if(x!=k) {
int maxi=((lost+lost)/(k-x+)-(k-x))/;///剩下的大于i的最小的(k-x+1)个数加起来超的话就跳
maxi=min(maxi,n-);
for(int i=now; i<=maxi; i=R[i]) {
Remove(i);
if(dfs(lost-i,x+,R[i]))return ;
Resume(i);
}
} else {
if(L[R[lost]]==lost) {
Remove(lost);
if(dfs(,x+,R[lost]))return ;
Resume(lost);
}
}
return ;
} bool farm(int _n,int _k) {
int t;
int i,j;
n=_n;
k=_k;
if((+k)*k/>n)return ;
for(i=; i<=n; i++) {
L[i]=i-;
R[i-]=i;
}
L[]=n;
R[n]=;
t=sqrt(1.0*n);
if(t*t==n)t--;
for(i=t; i>=; i--) {
int lost=i*i;
Remove(n-lost);
if(dfs(lost,,R[n]))return ;
Resume(n-lost);
}
return ;
} int main() {
int i;
int n,k;
while(scanf("%d%d",&n,&k)!=EOF) {
if(farm(n,k))printf("YES\n");
else printf("NO\n");
// for(i=0;i<r;i++)
// printf("%d ",b[i]);
// puts("");
}
return ;
}