英文原题 中文题译
题目大意:
给定N,求将集合{i|1<=i<=N}划分为两个元素和相等的子集的方案的个数。如,N=3时,{1,2}{3}共一个解。
1-N的数的和为(N+1)N/2,则如果此数为奇数,一定无解。若为偶数,则一定可构造出解。
如果直接暴力求解,粗略估计搜索空间为(n/2)!,不过可以快速剪枝。关键是从最大的数开始搜,每次增加一个未搜索的最大数,直到得到既定的和,或者超过和则剪枝。例如N=7,(7+1)*7/4=14,即每个集合的和为14。最大数7必然在某个集合中,这个数不用搜索。可从6开始,得1。5开始,得2。4开始,得3,继续搜索得2,1。3开始,就不用搜了,因为从3开始最大可得(3+1)*2/2=6<7。
这样搜索在第五个测试点(36)时超时(比NOCOW上说的第四个点31超时好,呵呵),而整个测试长度为39,故需要另想办法。打印出n=8时搜索求解的结果如下:
8 7 3
8 7 2 1
8 6 4
8 6 3 1
8 5 4 1
8 5 3 2
8 4 3 2 1
注意到其中的重复性,如yu'xyu'xiyu'xia余数为3时有两种方案3,21。这种重复方案导致整个搜索呈指数复杂度。对这种具有重复子问题的求解,自然应该想到动态规划了,于是定义:a[i][j]= 以小于等于i的数求和得到j的个数。则自然有a[i][j]= a[i-1][j-i]+a[i-1][j](表示是否选择i-1)。结合之前的分析,a[N][(N+1]*N/4]即为答案。同时我们可以在此表的基础上重构出所有的解来。
在标程中有一个用一维DP的,其实是把上述的2维DP线性化。
PS:求解之初曾想过直接对N做DP,查了半天数据没找到可行的合适方案。
题目大意:
给定N,求将集合{i|1<=i<=N}划分为两个元素和相等的子集的方案的个数。如,N=3时,{1,2}{3}共一个解。
1-N的数的和为(N+1)N/2,则如果此数为奇数,一定无解。若为偶数,则一定可构造出解。
如果直接暴力求解,粗略估计搜索空间为(n/2)!,不过可以快速剪枝。关键是从最大的数开始搜,每次增加一个未搜索的最大数,直到得到既定的和,或者超过和则剪枝。例如N=7,(7+1)*7/4=14,即每个集合的和为14。最大数7必然在某个集合中,这个数不用搜索。可从6开始,得1。5开始,得2。4开始,得3,继续搜索得2,1。3开始,就不用搜了,因为从3开始最大可得(3+1)*2/2=6<7。
/* ID: blackco3 TASK: subset LANG: C++ */ #include <iostream> using namespace std; int n_part=0 ; void get_subset( int cur_num , int remain ) { if( remain<=0 ) n_part += (remain==0); else for( int i=min(cur_num-1,remain); remain<=((i*(i+1))>>1) && i>=1; i-- ) get_subset( i, remain-i ); } int main() { freopen("subset.in", "r", stdin); freopen("subset.out", "w", stdout); int num ; cin >> num ; int part_sum = (num * (num + 1) ) >> 1 ; if( part_sum & 1 ){ cout << 0 << endl ; return 0 ; } get_subset(num, (part_sum>>1)-num ); cout << n_part << endl ; return 0; }
这样搜索在第五个测试点(36)时超时(比NOCOW上说的第四个点31超时好,呵呵),而整个测试长度为39,故需要另想办法。打印出n=8时搜索求解的结果如下:
8 7 3
8 7 2 1
8 6 4
8 6 3 1
8 5 4 1
8 5 3 2
8 4 3 2 1
注意到其中的重复性,如yu'xyu'xiyu'xia余数为3时有两种方案3,21。这种重复方案导致整个搜索呈指数复杂度。对这种具有重复子问题的求解,自然应该想到动态规划了,于是定义:a[i][j]= 以小于等于i的数求和得到j的个数。则自然有a[i][j]= a[i-1][j-i]+a[i-1][j](表示是否选择i-1)。结合之前的分析,a[N][(N+1]*N/4]即为答案。同时我们可以在此表的基础上重构出所有的解来。
在标程中有一个用一维DP的,其实是把上述的2维DP线性化。
/* ID: blackco3 TASK: subset LANG: C++ */ #include <iostream> #include <memory.h> using namespace std; #define _max_ 40 int main() { freopen("subset.in", "r", stdin); freopen("subset.out", "w", stdout); int num ; cin >> num ; int part_sum = (num * (num + 1) ) >> 1 ; if( part_sum & 1 ){ cout << 0 << endl ; return 0 ; } part_sum = part_sum>>1 ; int sum_num[_max_][((_max_*(_max_+1))>>2)+1] ; memset(sum_num, 0, sizeof(sum_num)); sum_num[1][1]=1 ; for( int i=2; i<=num; i++ ){ for(int j=1; j<=part_sum; j++ ){ sum_num[i][j] += i-1>=1 ? sum_num[i-1][j] + ( j-i>=1 ? sum_num[i-1][j-i] : 0 ) : 0 ; } } cout << sum_num[num][part_sum] << endl ; return 0; }
PS:求解之初曾想过直接对N做DP,查了半天数据没找到可行的合适方案。
发表评论
-
USACO Training Section 4.2 Cowcycles
2010-01-31 21:11 882英文原题 中文题译 ... -
USACO Training Section 4.2 Job Processing
2010-01-30 17:31 1130英文原题 中文题译 大意: 有N个工件,每个工件要经 ... -
USACO Training Section 4.2 Drainage Ditches ISAP非递归和多路增广递归
2010-01-29 19:39 1845郁闷。不小心覆盖了重 ... -
USACO Training Section 4.2 The Perfect Stall 匈牙利算法的递归和非递归实现
2010-01-28 21:21 1642英文原题 中文题译 ... -
USACO Training Section 4.1 Cryptcowgraphy 奶牛密码
2010-01-27 20:58 1195英文原题 中文题译 大意: 奶牛们要从农场逃跑 ... -
USACO Training Section 4.1 Beef McNuggets
2010-01-26 21:37 966英文原题 中文题译 大意: 给定N个正整数, ... -
USACO Training Section 4.1 Fence Loops
2010-01-24 20:14 1062英文原题 大意: 农夫布朗的牧场上的篱笆已经失 ... -
USACO Training Section 3.4 Closed Fences
2010-01-23 17:50 1401英文原题 题意 一个 ... -
USACO Training Section 3.4 American Heritage
2010-01-21 23:19 771英文原题 大意:有一个由最多26个大写字母构成的二叉树 ... -
USACO Training Section 3.4 Raucous Rockers
2010-01-21 23:09 796英文原题 大意:有S首歌,要放到D个CD里。每首歌有一个 ... -
USACO Training Section 3.4 Electric Fence
2010-01-21 12:57 969英文原题 大意:给定一个三角形(0,0),(m,n),( ... -
USACO Training Section 3.3 Riding the Fences
2010-01-20 23:38 1204英文原题 中文题译 经典的求欧拉路径:给定最多两个奇 ... -
USACO Training Section 3.3 Shopping Offers
2010-01-19 22:18 912英文原题 中文题译 这是个与日常生活相关的题。商场促销 ... -
USACO Training Section 3.3 A Game
2010-01-19 20:54 1092英文原题 有如下一个双人游戏:N(2 <= N & ... -
USACO Training Section 3.3 Home on the Range
2010-01-19 19:36 771英文原题 中文题译 大意:给定一个01矩阵,计算其中全为 ... -
USACO Training Section 3.3 Camelot
2010-01-19 03:39 1229英文原题 中文题译 ... -
USACO Training Section 3.2 Sweet Butter
2010-01-19 00:10 1043英文原题 中文题译 大意:农场之间有路构成稀疏无向图,若 ... -
USACO Training Section 3.2 Magic Squares
2010-01-18 23:11 929英文原题 中文题译 大意:有人发明了一种有8个块三种变换 ... -
USACO Training Section 3.2 Feed Ratios
2010-01-18 20:52 1304英文原题 中文题译 大意:给出整数a[i][j]和 ... -
USACO Training Section 3.2 Spinning Wheels
2010-01-18 19:37 866英文原题 中文题译 大意:有五个纺车飞轮,每个都有最多五 ...
相关推荐
ACM----USACO Training(解题博客网),提供了USACO Training解题的代码,可以参考一下
自己写的usaco_training带代码。供参考,有一道题是cheat的。自己看吧。
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
usaco解题报告,就是usaco.training.gateway上面的题目全解
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
[USACO 1.1.4]破碎的项链.cpp
2.2 Section 2.2 2.3 Section 2.3 2.4 Section 2.4 3 Chapter3 3.1 Section 3.1 3.2 Section 3.2 3.3 Section 3.3 3.4 Section 3.4 4 Chapter4 4.1 Section 4.1 4.2 Section 4.2 4.3 Section 4.3 4.4 Section 4.4 5 ...
USACO全部译题 USACO Training Program Gateway
USACO_培训USACO_培训Ride.java-> Gift1.java->
USACO training 教程翻译合集(清晰明确)
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始
One of the answer of the USACO training exercises.
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
usaco历年测试数据
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
USACO题集及答案
某些USACO题目的答案,很详细,代码清晰结构良好,算法高效易于调试
usaco的总结和心得 包括了对题目的分了和总结 以及对题目的解法概括
USACO培训网站 我为章节解决方案。 每个文件的多行USACO标识信息注释 第1章全部的解决方案 第2章全部的解决方案