请所有集训队员务必准时参加,欢迎所有爱好者参加。地点:7404

2009**学院ACM省赛单人选拔赛(2)


参加竞赛人数
 21
解答题目人数
 21
创建者
开始时间
2009-03-21 11:30:00.0
结束时间
2009-03-21 16:30:00.0
当前时间
2025-12-18 13:42:14
状态
已结束

题库:

题目号
标题
正确率(正确/总提交)
正确解答人数
提交人数
最佳解决(者)
A
64%( 18/ 27)
18
18
0MS/hqj
B
17%( 3/ 17)
3
5
15MS/crq
C
0%( 0/ 9)
0
2
 
D
56%( 18/ 31)
17
17
E
71%( 19/ 25)
19
19
0MS/sw
F
57%( 5/ 8)
5
5
G
42%( 3/ 7)
3
4
H
0%( 0/ 2)
0
1
 
I
80%( 14/ 17)
14
14
31MS/tzxyc
J
18%( 2/ 11)
2
4
922MS/nbjwl

解题报告:

A 简单题
     因为p的范围很小才99 所以从700-799就可以满足全部要求了。可以打表出来,找出每个连续的一段满足要求的数,保存起来(并且要求新存的段长度比原先的要长),打出一张表,对每个要求的数,2分答案。(把1-99的结果都保存好,直接输出)。反正“转折点”很少,怎么搞都可以。
B 简单题
     直接bfs无向图mst。
C 中等偏难。
       给定直线,对每条直线,传说解不等式组可以过,直接看是否存在一个点在直线之上。(左端点取max,右端点取min,如果左>=右,直接break掉)。有点ft...O(n^2) n=5000 rp好的可以过....
   我用的方法类似于凸包,先把所有直线按照斜率a由小到大排序,斜率相同取b较大的,扔掉b小的。于是所有直线斜率不同。准备一个栈,栈里面存放上一次能看到的“最上面”的直线以及这条直线能看到的范围x(x值右边的部分可以被看到)。初始时,把斜率最小的直线入栈,并记录x值为-inf。然后对第i条直线,所做的是用第i条直线和栈顶直线求交点x,如果这个x值不大于栈顶的x值,则把栈顶元素弹出,继续求交,否则退出。这种判断操作直到栈为空,或者当前栈顶的x值大于栈顶的x值。然后把第i条直线入栈,继续,看后面的直线。最后栈中的直线数就是能看到的。这种做法类似于凸包的方法,除去排序外,每条直线至多出入栈一次,复杂度O(n)。总复杂度是O(nlogn)。
D 简单题。
     没有太多好说的,直接硬搞就行。原题的输出要求比这个麻烦得多,是要输出(f(x))'=g(x)的,这就有对系数为1和0的输出处理,以及指数为0和1的处理。题目简化了,没什么注意的地方了。
E 简单题
     找最大最小值,没什么好说的。
F 可以认为是简单模拟。
     直接打表10^9是显然不可行的。其实我认为最简单的做法,是预map所有不超过1000的数的读法和阿拉伯数,这样读数可以分3节处理。注意一下and,zero等就好了。输出直接输出数字没有逗号。-.-
G 简单dp。
     背包....注意体力可以为0,满了不能再超。
H 中等题
     比较显然的矩阵乘方。用O(nlogn)的求幂方法即可。有一点注意题目中的K=0时(没有从该容器倒水的规则),并不是把其中的水都到出去,而是它其中的水始终保持不变。(若第p个容器K=0,则与输入的是1,下一行是p,等价)
I 中等题
     O(n^3)的dp。枚举两行i,j再枚举一列k。起初,用一个ans=0表示结果,设a[c]表示设定i,j后截止到当前列,i,j行的位置都是第c种福娃的列数。(c=0,1,2,3,4)。每当循环k前,先把a数组都清0。mat为输入矩阵,然后循环k,如果mat[k]==mat[j] [k],设mat[k]为第c种福娃,则总数ans显然应该加上a[c](前面那些列都可以和当前列构成满足要求的矩阵的),并且a[c]数加1。最后ans为所求。
J 简单题
     可能图看不大清楚。其实点光源到(x,y,z)到它在z=0平面的投影点的光强度最强,然后随着它在z=0平面投影点为圆心的同心圆由里到外强度逐渐减弱,点光源(x,y,z)到(x0,y0,z0)光强度的计算,(I/R^2)*cosi 而cosi=z/R   R=distance((x,y,z),(x0,y0,z0))。题目所求的是整点的最强的光强,由上述分析,可知,最强的点不可能“太靠外”,于是枚举 z=0平面的点即可。根据坐标范围,我只简单枚举了-100到+100的x与y。复杂度100*100*n,差不多有100w。

|返回 |   | 转到页头|
Copyright © 2008-2025 (浙ICP备2022001332号), TZOJ. All Rights Reserved.
2017-2025 台州市非普软件技术有限公司,浙江省台州市君悦大厦B幢1603室