AC

恩...刚结束的宁波赛区比赛...
话说比赛结束时就感到我们要悲剧了...
不过还好结果没有坏到预期的地步...

首先不得不说的是...纪念品...杯具等...
还有自助晚宴真是豪华啊...各种肉和水产品...每样拿一个都够撑死我了...
当然还有点心,汤,水果,饮料,还有米饭...

看着别人拿了一堆...真佩服他们的胃...
我拿的东西还没超出盘子凹陷的部分...就吃饱了...胃口真小...

比赛结果...悲剧的是我们队只做出4题...并且后2小时貌似没有出题...而且还不是没有思路...有1~2题应该能出的...
不算太坏的是...ICPC排名踩在银牌尾巴上...并且是唯一4题拿银的...
这次比赛深刻的感受到...水题做太多了...不过话说我最近也没怎么做题...
如果把做水题的时间去做别的题的话...可是读了题发现自己会做...就会不甘心放在那里...而是花上几分钟或十几分钟去A掉...这种冲动...

闭些房子里还用着原始的马桶，属于简易的痰盂，我经过的时候常看见老人将秽物倒进河水，还在河边冲洗，用刷子擦，坚硬的幕的时候裁判简单说了下各道题的类型...
下面是详细内容

一共10题...
第一名出了8题,10题都有队伍过
A是潜水艇吃金币,横向速度始终是1,纵向速度在所在格子里的装置会进行调整,自己可以在一些格子上设置装置,不过自己设置的装置只能+1或者-1...
然后一段时间要上来换气?...最后问最多能拿到多少金币...
题目不是我读的...但是感觉像是dp...但是那输入格式让人有点烦躁...于是没去深入...
[这是一道中等难度的动态规划]

B是僵尸大战植物,5*5的格子里有植物,你扮演僵尸,有4种僵尸,攻击力各不相同,价格也不相同,还有蜘蛛及其价格
一行上僵尸总攻击力超过植物总防御力的话,一行植物被消灭
蜘蛛可以消灭一个格子上的植物
有四种植物,一种是消灭了有奖金的,一种是有防御力的,一种是使得自己和上下两行的僵尸中,football player的攻击力变低,一种是自身和周围8格不受蜘蛛影响
僵尸和蜘蛛都是一次性的,下一次进攻需要另外买...
消灭一行有奖金,一开始手中有一些钱,问能否消灭植物,能的话消灭完毕后剩余金钱最多是多少
当时没有仔细想...因为还有别的看起来更容易的题目等着做...
[这是一道有点复杂的搜索题]

C是占座,规模很小的模拟,没什么可说的
[这是一道简单的模拟]

D是凹多边形硬币放入凹多边形槽里,硬币是竖着放的
实际就是硬币旋转到某个角度时宽度最小s1,以及槽的多边形内最长的不穿越边界的线段长度s2,如果s1<=s2,就是可行的,否则不可行 我的思路是硬币做凸包,然后计算每条边和不相邻的顶点距离最大值的最小值,而槽是枚举任意两顶点,找到他们连线在多边形内的线段长度... 不过非常莫名其妙的TLE了...复杂度应该是O(n^3),而且n才20... [这是一道有难度的计算几何题]

E是撑伞,给定许多不相交的圆,要构造一个大圆,使得大圆圆心在某个小圆的圆心,并且对于每个小圆,它和大圆相交部分面积要不小于自身面积的一半
圆相交模板上,然后二分,直接过...
[这是一道简单的计算几何题]

F是贴海报,给定许多矩形的坐标,每个矩形都被挖掉一个矩形,问所有这种形状的并的面积...数据规模50000
用线段树去做的扫描线法矩形并的面积...也许是模板太烂了...结果TLE了...
敲了两份模板,都TLE...期间还有奇怪的WA...别说把最初的TLE的代码多交几次就过了...不可能吧...
总之可以说这次比赛主要栽在这题上了...这题可是有大把大把的人过了的啊...
在最后点评的时候说了时限...我震惊了...这题居然才1s的时限...真...不知别人怎么做的...
[这是一道中等的数据结构题]

GH不详,似乎是难题...题目也没看...其中一题是推公式的,还有一题是很复杂的东西...

I是买东西,每种货物都有个价格ki,有四种方法入手该货物
一是用价值为ki的金币去交换
二是用价值为ki-1的金币加上一个珠子去交换
三是用价格为ki的物品去交换
四是用某些更便宜的物品加上一定量的金币去交换
关于第四条,如果便宜的物品价格kj,金币价值pj,那么换取得到的物品价格ki>kj+pj
利用上述四条规则,可以尽可能少的金子去换取货物,每个货物能用最少的金子gi来得到,称之为该货物的价值,显然有gi

J是p2p下载,模拟一段时间的p2p下载,只有一个文件,一开始一些机器有该文件,称之为server,没有下载完成的机器称为client
每两台机器间有传输速度,client从每个server处下载,当某个client下载完该文件后,在下一秒自动成为server
给定每台机器的开机时间(开机才能下载),以及client开始下载的时间,问经过T秒后,每台机器的下载进度
规模很小,直接一秒秒模拟就行了...为了方便起见(?)我是一段段时间来模拟的...
[这是一道中等的模拟题]

以上...

标签：contest, regional