dreamangel

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  14 随笔 :: 0 文章 :: 0 评论 :: 0 Trackbacks

地址:http://acm.fjnu.edu.cn/showcontest?contest_id=1100
A:Accept
枚举4个点,判断是垂直,一个O(n^4)就能过
B:Choose ACMer
模拟题,注意09级比08级年轻,应该排在前面,,还有在计算最优的前n-2个分数时,要直接用加的,不要用总的n个的和减去最差的2个,这样会造成精度问题。。
C:Heroes General Assembly
数论题。
题目即求a^b = 1 (mod c)中,b的最小值。
设b的最小值为e, 根据欧拉定理有,e | phi(c),其中phi(c)为欧拉函数,但是反过来并不成立,即不是充要条件。
所以我们先求出c的欧拉函数,然后对其分解素因子,再暴力枚举所有c的因子(不一定为素因子),取符合a^b = 1 (mod c)的最小值即可。
D:Largest Group
线段树。
E:Magic String
找规律题。
F:Put Coin Game
博弈题。试放所有位置的圆,求出每个table的SG值,再将所有的table的SG值求异或即可
G:Rotate rotate and rotate
几何题。直接一个体积公式解决。注意PI要取acos(-1.0)。
H:Try
图论题,正解是拆点套用网络流。
I:Number Cutting Game
DP题。定义dp[i][j]=true代表前i个数,进行任意组合能得到余数j。那么有
if(dp[j][k]) dp[i][(k+num[j+1][i])%m] = true;{j<=i-1}
其实m为要模的数,num[j+1][i]代表数串中第j+1到第i个形成的数字对m求余的值。这个要首先通过预处理求得,否则会超时。总的复杂度为O(n^3)。
J:Number Reversing Game
搜索题。双向广搜+hash。
K:Special max_heap
组合数学

posted on 2010-01-18 20:39 飞翔天使 阅读(400) 评论(0)  编辑 收藏 引用 所属分类: ACM

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理