本文主要是介绍福州大学第十二届程序设计竞赛 解题报告,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
由于这个OJ比较蛋疼,比赛时提交的代码看不到,所以就不附代码了,只说思路。
A 非提的救赎
待补。
B 完美的数字
求一个区间内,所有数的“完美度”的和,完美度定义为数i能分解为多少组i=A*A*B(A<=B)。区间范围达到了10^15。举个例子,什么样的数可以分解为A=4呢,前几个是64 80 96,因为A<=B。所以这个数至少是A的立方,而且这个数减去A的立方以后,能被A的平方整除。
预处理算出每个数的平方、立方。写一个函数fun(x)计算区间1~x的结果,题目的答案就是fun(b)-fun(a-1)。在函数fun(x)中,枚举每个A,计算A^3~x这个区间内,有多少个数能被A^2整除,累加起来。
C 位置信息挖掘
给一些用户,商品,城市间的信息,有一部分缺失,要求根据已知尽可能补全。
并查集。商品编号1~N,用户编号N+1~N+M,城市编号N+M+1~N+M+N+M。利用给的信息,进行合并(缺失的就不用合并了)。注意如果城市参加了合并,一定是将其他内容向城市合并。最后根据所属集合输出。
D So Hard
小数化为最简分数。
So坑。最水的一题我交9发才过。说两种可行办法。一是浮点数读入。直接乘上1000000000作为分子,1000000000则作为分母。分子分母求gcd约分。二是字符串读入,处理出整数部分和小数部分,然后换算成一个分数去约分。
E 星系碰撞
平面上有许多点,两个集合,如果两个点距离不大于5,它们一定属于不同的集合。给所有点坐标,问一个集合中最多能有多少元素。
时限30s的神题。。然而我竟然TLE了好几次。这题求的是二分图最大独立集。我一开始还想不明白怎么把它们分为2个集合,后来学弟说了一个方法,类似于染色,如果某个点染哪种颜色都可以,就随意给它一种颜色。也就是距离不大于5的点之间建边,跑最大匹配,根据最大独立集=点数-最大匹配得出结果。但是要注意,如果暴力计算每两个点之间距离会超时。优化方法是先按x坐标排序,然后计算每两个点之间距离,当两个点x坐标大于5以后,直接忽略后面的点。
其实这种方法还是有点问题的。如果所有点的x坐标都在0~5范围内,y坐标分布得比较广,应该还是会跪的。所以我觉得应该随机抽一些点出来,考察他们在哪个方向上分布得比较散,就按它排序。
F 检查站点
一座山,上面各个地点是树型结构,你在山顶(树根),需要访问每个节点一次,每条边向上走有一定的代价,向下走没有,问访问所有节点的最小代价。
树型DP。显然最后一次访问到叶子以后,就不用回去了,省下来的代价就是一条根到叶子的路径。DP求费用最大路径即可。
G Escape
迷宫,入口走到出口,墙不能走,有岩浆,每秒向四个方向蔓延。有岩浆不能走。问是否能走出迷宫。
BFS,先BFS预处理所有地点被岩浆蔓延到的时间(不能一个一个点处理,需要一次性把所有岩浆点加到队列里一次性BFS完成,否则TLE)。然后BFS搜一下是否有路就好了。注意如果先到终点岩浆才蔓过来是可以的。
H 最小花费
一个01串,如果交换相邻的01代价是x,交换不相邻的代价是y。需要把所有1换到前面,问最小代价。
其实每次只有两种决策,要么花费y把最右边的“1”换到最左边的“0”,要么把最左边需要移动的“1”,连续换到最左边的“0”(连续花费若干个x)。想到这一点还是不好做,然后我们可以发现,其实把最右边的“1”通过相邻交换到最左边的“0”的花费,是x乘以他们的距离。即设当前最右边的“1”在pos1,最左边的“0”在pos0,如果pos0<pos1,移动它的代价就是min(y,x*(pos1-pos0))。
这篇关于福州大学第十二届程序设计竞赛 解题报告的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!