2011 ACM/ICPC 北京赛区网络赛解题报告汇总

九月 18th, 2011 | Posted by diaorui in ICPC 2011 亚洲区 | 解题报告
欢迎转载,转载请注明出处。




针对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.

9 Responses



留言给 vici 取消留言

电子邮件地址不会被公开。 必填项已用*标注