首页 > 代码库 > hdu4982 Goffi and Squary Partition （DFS解法）
hdu4982 Goffi and Squary Partition （DFS解法）
BestCoder Round #6 B
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 24 222 4 Sample Output NOYESYES Source BestCoder Round #6 Recommend heyang | We have carefully selected several similar problems for you: 4984 4983 4981 4980 4979 |
题意：给出n和k，求k个不同的正整数，使其中k-1个数能组成平方数，k个数的和为n。有解输出YES，无解输出NO。
题解：从大到小枚举小于n的平方数，剪枝搜索是否有解。
先判一下是不是1~k这最小的k个数加起来都超过n，这种情况肯定不可能，真去搜一遍的话太费时间了，还是特判掉比较好。
if((1+k)*k/2>n)return 0;
枚举平方数，进入搜索：
1 t=sqrt(1.0*n);2 if(t*t==n)t--;3 for(i=t; i>=1; i--) {4 int lost=i*i;5 Remove(n-lost);6 if(dfs(lost,2,R[n]))return 1;7 Resume(n-lost);8 }
↑（这个在函数里，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代码：
1 bool dfs(const int &lost,const int &x,const int &now) { 2 if(x>k) { 3 if(lost==0) 4 return 1; 5 else return 0; 6 } 7 if(lost<=0)return 0; 8 if(x!=k) { 9 int maxi=((lost+lost)/(k-x+1)-(k-x))/2;///剩下的大于i的最小的(k-x+1)个数加起来超的话就跳10 maxi=min(maxi,n-1);11 for(int i=now; i<=maxi; i=R[i]) {12 Remove(i);13 if(dfs(lost-i,x+1,R[i]))return 1;14 Resume(i);15 }16 } else {17 if(L[R[lost]]==lost) {18 Remove(lost);19 if(dfs(0,x+1,R[lost]))return 1;20 Resume(lost);21 }22 }23 return 0;24 }
（这题的正解好像是各种情况都考虑一下，直接几个if就判出来了……我是不太懂）（还有官方题解说平方数只用枚举最大的那个就行，可是8 2这组数据，最大的平方数是4，然后就逗乐啊……虽然好像只有这一组数据有问题）
全代码：
1 //#pragma comment(linker, "/STACK:102400000,102400000") 2 #include<cstdio> 3 #include<cmath> 4 #include<iostream> 5 #include<cstring> 6 #include<algorithm> 7 #include<cmath> 8 #include<map> 9 #include<set> 10 #include<stack> 11 #include<queue> 12 using namespace std; 13 #define ll long long 14 #define usll unsigned ll 15 #define mz(array) memset(array, 0, sizeof(array)) 16 #define minf(array) memset(array, 0x3f, sizeof(array)) 17 #define REP(i,n) for(i=0;i<(n);i++) 18 #define FOR(i,x,n) for(i=(x);i<=(n);i++) 19 #define RD(x) scanf("%d",&x) 20 #define RD2(x,y) scanf("%d%d",&x,&y) 21 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z) 22 #define WN(x) prllf("%d\n",x); 23 #define RE freopen("D.in","r",stdin) 24 #define WE freopen("1biao.out","w",stdout) 25 #define mp make_pair 26 #define pb push_back 27 28 const int maxn=222222; 29 int L[maxn],R[maxn]; 30 inline void Remove(int x) { 31 L[R[x]]=L[x]; 32 R[L[x]]=R[x]; 33 } 34 35 inline void Resume(int x) { 36 L[R[x]]=x; 37 R[L[x]]=x; 38 } 39 40 int n,k; 41 42 bool dfs(const int &lost,const int &x,const int &now) { 43 if(x>k) { 44 if(lost==0) 45 return 1; 46 else return 0; 47 } 48 if(lost<=0)return 0; 49 if(x!=k) { 50 int maxi=((lost+lost)/(k-x+1)-(k-x))/2;///剩下的大于i的最小的(k-x+1)个数加起来超的话就跳 51 maxi=min(maxi,n-1); 52 for(int i=now; i<=maxi; i=R[i]) { 53 Remove(i); 54 if(dfs(lost-i,x+1,R[i]))return 1; 55 Resume(i); 56 } 57 } else { 58 if(L[R[lost]]==lost) { 59 Remove(lost); 60 if(dfs(0,x+1,R[lost]))return 1; 61 Resume(lost); 62 } 63 } 64 return 0; 65 } 66 67 bool farm(int _n,int _k) { 68 int t; 69 int i,j; 70 n=_n; 71 k=_k; 72 if((1+k)*k/2>n)return 0; 73 for(i=2; i<=n; i++) { 74 L[i]=i-1; 75 R[i-1]=i; 76 } 77 L[1]=n; 78 R[n]=1; 79 t=sqrt(1.0*n); 80 if(t*t==n)t--; 81 for(i=t; i>=1; i--) { 82 int lost=i*i; 83 Remove(n-lost); 84 if(dfs(lost,2,R[n]))return 1; 85 Resume(n-lost); 86 } 87 return 0; 88 } 89 90 int main() { 91 int i; 92 int n,k; 93 while(scanf("%d%d",&n,&k)!=EOF) { 94 if(farm(n,k))printf("YES\n"); 95 else printf("NO\n"); 96 // for(i=0;i<r;i++) 97 // printf("%d ",b[i]); 98 // puts(""); 99 }100 return 0;101 }
hdu4982 Goffi and Squary Partition （DFS解法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。