返回信息流发信人: dragonflywww (龙飞), 信区: ACM_ICPC
标 题: 题目分析
发信站: 珞珈山水 (2004年04月26日11:05:44 星期一), 站内信件
先看一下做题情况：
提交次数/第一次做对的时间/通过的队数
A 252/9/61
B 16/--/0
C 95/--/0
D 54/75/4
E 169/154/3
F 139/34/7
A 模拟
送分题，没什么好说的
//本来出这个题的想法是让所有的队都过的，结果只有61个，刚刚及格：（
B 计算几何＋图论
先算出球面坐标：
X=x*2*R*R/(d+R*R)
Y=y*2*R*R/(d+R*R)
Z=R*(d-R*R)/(d+R*R)
(d=x*x+y*y)
//据说复变函数有这个公式，其实解方程也很快
然后算出球面距：
aftermath用内积：D=R*acos(innerproduct/R/R);
我的数学只有高中水平：D=R*2*asin(d/2/R)（d为空间距离）
再用一个floyd求最短路。
/*这个题本来是当简单题出的，但是比赛的时候居然没有队过
可能是题目意思太难懂了：），还有处理输入比较麻烦
*/
C 组合数学＋动态规划＋高精度计算
原问题：x1+x2+x3+...xm=n ( 0 <= x(i+1)-xi <= k,x1<=k )
利用共扼ferrers图像把原问题转化为：
1*x1+2*x2+...m*xm=n (0 <= xi <= k)
m k
然后用母函数 ∏ ∑ x^(i*j) 求解
i=1 j=0
另外结果很大，要用高精度计算。
/*O（mnk）的算法，可能还有其他做法的
这个题的结果有20多位
比赛的时候居然都是用搜索做的（而且没有高精）
天哪，就是用非确定机来算也要几百年
*/
D 贪心＋枚举
在同一行或列上最多只要操作一次就行了
先枚举行操作，然后列就独立了，每列找个最大值加起来
E 数论
可以证明大于等于(a-1)*(b-1)的数都能表示as＋bt
//这个证明就留给aftermath了：）
这样搜索空间就很小了
/*aftermath自己认为的难题
结果还是有3个队做出来了
他认为的简单题B却没有队过：）
*/
F
推个公式就可以了：(n+1)*(n*n-n+6)/6
第n次切时最多增加的数目是前n-1刀把第n次的切面分成的最大平面数
实在不行的话，找4个最简单的情况，待定系数法解一下就可以了
/*本来想改成n维空间的，后来怕没简单题了
这个题要用到long long(int64)
估计这个卡了很多人
*/
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #832同步于 2006/4/13
ACM_ICPC机器人发帖
今天武大比赛的解题报告
dby
2006/4/13镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。