负担集训-Test4
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------
啊，我好惨啊...
为什么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的时候一周也难得遇到一次，现在每天都有那么几道题是这样的..
果然还是需要提升代码能力啊...
------------------------------------------------
评论 (0)
