负担集训-Test4

------------------------------------------------
啊,我好惨啊...
为什么ACM会有卡EPS的计算几何题啊...
话说最近好像得了一场比赛至少有两道题调不出来的病...
这破游戏好难玩啊...
------------------------------------------------

 
概述
------------------------------------------------
赛中通过5题,赛后通过3题,共通过8题
------------------------------------------------
 
比赛记录
------------------------------------------------
一开始我从几道easy里面随便选了一道H,想了一想,好像有点难,又过了一会儿想出来一个哈希的算法,于是我就开始写,结果交上去wa到死,调不出来,于是我就先去做其他题了。
我看了一下通过人数最多的D题,好像挺简单的,就A了,然后又跑去看E,过了一会儿也A了,然后把K也A了,这样一来easy就只剩H了,我暂时不想调H,就跑去看G,想了一会儿,好像会做了,写写写,又是wa到死,顿时我感觉药丸了。
这个时候我使用了上厕所大法,去厕所里晃了一圈,顿时神清气爽,思维变得异常清晰,回来之后一眼找出了H的错误,于是就A掉了,然后我跑去调G,又一眼找出了G的错误,于是又把GA掉了(上厕所大法的效果奇好啊...)
然后我又跑去看I,好像挺简单的,写一写,wa了,调了一会儿,不知道错误在哪里,于是我又跑去看C,卧槽高精度,有点慌,瞎写了一下,果然T了
然而考试一结束我立刻就知道G怎么做了...
------------------------------------------------
 
比赛题解
------------------------------------------------
A:(赛后通过)
就是说n个点,m个要求,每个要求是某两个点中必须恰好有0个/1个/2个染黑,求最少要把几个点染黑才能满足要求,或者输出不可能满足
n,m<=200000
 
首先把0个和2个的要求满足了,然后dfs染色就好了
------------------------------------------------
C:(赛后通过)
就是给定n<=5001,求C(2n,n)/(n+1)的值
 
这是一道高精度题
做法是把所有要乘、要除的数质因数分解,然后求出哪些质数是要乘的,然后把他们撑起来就好
这样就只需要一个高精*单精的乘法
------------------------------------------------
D:(赛中通过)
两个人玩色子,每个人有两个色子,每个色子有不超过100个面,上面的数字不超过100,每个人的分数是他的色子上的点数之和,求谁的获胜概率更大
 
暴力即可
------------------------------------------------
E:(赛中通过)
有n个大楼,要把他们全部夷为平地,有两种操作,一种是把所有大楼削低一层,一种是直接把一个大楼夷为平地,问至少多少次操作把所有大楼夷为平地。
n<=100000,大楼的高度<=1000000
 
枚举一下第一种操作执行多少次,再加上比操作次数高的大楼数就是总次数,更新一下答案即可。
------------------------------------------------
G:(赛中通过)
有n个老年人要上车,车上一共只有m个位置,第i个老年人上车的条件是第a[i]个老年人也上车(如果一个老年人没有要求,那么就有a[i]=i),问最多让多少个老年人上车。n,m<=2000
 
首先把(i,a[i])这个关系当成边,建一个有向图出来。
我们把有边相连(不论方向)的点叫做一个块。
因为每个点只有一个出边,因此一个块肯定是这样的:中心是一个环,然后环外面有很多小尾巴,这些小尾巴都是没有环的。
我们假设一个块的中心的环大小是s[i],外面的小尾巴个数是p[i]
那么这个块可以去的老人数量就是[s[i],s[i] + p[i]]中的任意整数,或者0(因为这个块中如果有人去的话,中间那个环肯定必须全部去,然后每次可以加一个小尾巴)
因为每一个人只属于一个块,且对他这个块的区间长度的贡献不超过1,因此所有区间长度加起来是O(n)的
因此我们可以这样DP:f[i][j]表示考虑了前i个块,一空去了j个人,可不可行,每次转移只需要枚举已经要去的人数,再枚举这一个块去的人数,转移一下就就好了。
最后答案就是满足f[n][r] = true的最大的r
------------------------------------------------
H:(赛中通过)
给你两个圆,两个圆上分别有一些半径被描黑了,问这两个图案能否通过旋转变得相同。
半径数量<=200000
 
我们把所有半径的角度排个序,如果这两个序列旋转(就是不断把第一个元素放到最后去)一定次数之后他们的差分相等的话,那么答案就是可行,否则就是不可行。
可以考虑哈希,一个序列直接差分,把哈希值求出来,另一个不断地旋转,每次更新一下他差分之后的哈希值,然后不断比较两个值就可以了
------------------------------------------------
I:(赛后通过)
给你平面上的n条直线,问有多少个正方形,n<=2000
 
首先求出每个直线的角度
然后暴力求一个f数组出来,f[i][j]表示夹角均为i,距离为j的直线对数
然后再枚举一下每对平行直线,假设和他们垂直的角度为h[i],距离为d[i],那么答案就加上f[h[i]][j[i]]
发现这样的话,实际上每个正方形被求了两次,因此最后答案除以2即可
------------------------------------------------
K:(赛中通过)
说是有一个火车,容量为c,按顺序经过了n个车站,每个车站给出了3个数据:上车人数,下车人数,还在继续等的人数,请你判断这些数据是否是假的
1.火车上的人数随时不能超过c,不能低于0
2.终点站不能有人上车,终点站之后车上的人数必须为0
3.没有人会车上明明还有空位却偏不上车
如果以上有不满足的,就是假数据,否则是真数据
 
暴力模拟即可
------------------------------------------------
 
比赛总结
------------------------------------------------
现在我感觉调代码是一个很大的问题
不知道是不是我一年没怎么练习的原因,还是不习惯ACM的原因,我这几天基本上每次考场上A的题都比我会做的题少2道左右,很多题就是因为一些SB错误一直卡住。
这一次考试也是这种情况,G、H、I耽搁了太多时间,而且I题还没A掉(而且还是因为EPS的问题,把EPS从1e-9改成1e-5就过了,ACM上出这种题真的不会被骂吗?...),又导致C题没什么时间做
这种死活调不出来题的情况,以前搞OI的时候一周也难得遇到一次,现在每天都有那么几道题是这样的..
果然还是需要提升代码能力啊...
------------------------------------------------