针对2011 ACM/ICPC 北京赛区9月18日网络赛,本日志汇总网上ACMer们发布的解题报告,方便大家互相学习。欢迎补充和完善本日志。
感谢所有及时发布解题报告,和大家分享知识的各位神牛。
出题报告(转自:http://blog.renren.com/blog/260258127/761163057)
A题 模拟+单纯形 (数据改小了,HIT的队伍dfs+剪枝剪过去了。。FDU用SAP过了。。。orz。。。。)
B题 模拟
C题 三维计算几何
D题 大整数组合数学
E题 北大的题,我不会啊,北大的标程好像是搜
F题 dp,状态转移显然,注意取模
G题 树状数组(MM题@.@)
H题 “水“的计算几何 + 单调队列(hl 大神没过trick啊=.=…一个山峰肿么办?…)
I题 数学
J题 状态dp
K题 概率dp
A Astrolabe (BUPT 211)
http://www.shuizilong.com/house/archives/3233
B Eliminate Witches! (BUPT 212)
http://blog.csdn.net/zxy_snow/article/details/6787704
http://blog.csdn.net/lmyclever/article/details/6787222
http://blog.csdn.net/kk303/article/details/6787956
C Fireworks (BUPT 213)
http://hi.baidu.com/%D0%A1%CE%E4rj/blog/item/0114bb2dcd4cdef78b13991d.html
D FXTZ II (BUPT 235)
本题目公式为:
f[0]=1
f[1]=1/2
f[n]=(n-1)!*2^(n-1)*(f[0]+f[1]+ ……+f[n-1])/(n!*2^n)
公式相应的C++代码参考如下,点击可展开(本题由于高精度,实际需要写大数运算或者改成JAVA,感谢CQU_CFY提供公式以及参考代码)。
#include <cstdlib> #include <cstdio> #include <cstring> #include <cmath> int f[510][2],s[510][2]; int c,n,temp; int gcd(int a,int b) { if (a%b==0)return b; return gcd(b,a%b); } int main() { f[0][0]=1;f[0][1]=1; s[0][0]=1;s[0][1]=1; f[1][0]=1;f[1][1]=2; s[1][0]=3;s[1][1]=2; for (int id=2;id<=500;id++) { temp=s[id-2][1]*f[id-1][1]; f[id][0]=s[id-2][0]*f[id-1][1]+s[id-2][1]*f[id-1][0]; f[id][1]=temp; temp=gcd(f[id][1],f[id][0]); f[id][1]/=temp; f[id][0]/=temp; s[id-1][0]=f[id][0];s[id-1][1]=f[id][1]; f[id][1]*=2*id; temp=gcd(f[id][1],f[id][0]); f[id][1]/=temp; f[id][0]/=temp; } scanf("%d",&c); while(c--) { scanf("%d",&n); printf("%d/%d\n",f[n][0],f[n][1]); } return 0; }
推公式的另一个解题报告:
http://www.cppblog.com/vici/archive/2011/09/19/156153.html
另有观察规律,打表通过的两个解题报告如下:
http://www.blogjava.net/sweetsc/archive/2011/09/18/358920.html
http://blog.csdn.net/xieshimao/article/details/6787863
E GeoDefense (BUPT 215)
http://blog.csdn.net/fp_hzq/article/details/6788049
F Machine scheduling (BUPT 216)
http://www.blogjava.net/sweetsc/archive/2011/09/18/358932.html
http://blog.csdn.net/xieshimao/article/details/6787792
http://hi.baidu.com/aekdycoin/blog/item/69e075f5e200bcf47709d769.html
G Panda (BUPT 217)
http://blog.csdn.net/zxy_snow/article/details/6787695
http://www.blogjava.net/sweetsc/archive/2011/09/18/358921.html
H Raining (BUPT 218)
http://blog.renren.com/blog/260258127/761213407
I Zhuge Liang’s Stone Sentinel Maze (BUPT 219)
http://hi.baidu.com/aekdycoin/blog/item/69e075f5e200bcf47709d769.html
J Tourism Planning (BUPT 220)
http://zhyu.me/acm/boj-220.html
http://blog.csdn.net/jxy859/article/details/6787714
http://www.cnblogs.com/kirk/archive/2011/09/18/2180697.html
K wolf5x (BUPT 221)
http://attiix.com/2011/09/18/solution-of-wolf5x/
http://blog.sina.com.cn/s/blog_4feba2910100tzyq.html
You can follow any responses to this entry through the RSS 2.0 You can leave a response, or trackback.
http://www.shuizilong.com/house/archives/3233
(. 搜搜剪剪无所不能.. .)
http://www.cnblogs.com/kirk/archive/2011/09/18/2180697.html
血泪啊
http://attiix.com/2011/09/18/solution-of-wolf5x/
A怎么用SAP
。根据出题人的说法。。A 题退化后十个一般图的匹配。。用 SAP (建模成二分图)做是不对的。。)
。。似乎还有一种正确的贪心方法。。。)
http://www.cppblog.com/vici/archive/2011/09/19/156153.html
The follows are my idea about problem D.
It is not hard to understand that if the n-th power is shot then the game will be over.
If it is shot at the i-th time, the possibility is (n-i)/n* f(i) * 1/(n-i)*1/2, which is 1/(2n)*f(i)
So f(n) = 1/(2n)*sum( f(i) ), 1<=i f(n)*2n – f(n-1)*2*(n-1) = f(n-1)
=> f(n) = (2n-1)/(2n)*f(n-1) = … = (2n-1)!! / (2n)!! * f(0), where f(0)=1
http://blog.csdn.net/kk303/article/details/6787956
我的B题…感觉很好理解也很简洁…
http://zhyu.me/acm/boj-220.html
我的J的网络流解法 自己感觉还可以… 要是有人指出问题我就更开心了