Andrew Stankevich Contest #32 Problem C 二维平面反演, 动态凸包

地址

给定n(1 ≤ n ≤ 105)个点,一个点(x, y)是好的,当且仅当以(0, 0) – (x, y)为直径的圆内不包含其它好的点。(x, y)皆是原点外的整点。0 ≤ |x|, |y| ≤ 30000。输出所有好的点。

因为题目的这个递归定义,显然应该按(x, y)到原点的距离从小到大排序,然后每次插入点之前检测一下,如果圆内没有点就插入,否则就拒绝。

这题因为给的都是整点,范围又小,构造不出大数据,直接用这个方法是能过的- -b……但是显然这不是一个令人满意的做法。

因为所有的圆都过原点,很容易想到对整个平面进行反演

这样圆都会变成一条直线,而“在圆内”反演后就会变成“在这个直线的一侧”(与原点相反的一侧)。

于是反演过后变成这样一个问题:每次给一条直线,问是否之前插入的点都在这个直线的某一侧。如果是,把这个点插入点集。

那么如何快速判断一个点集是否全都在一条直线的某一侧?

不妨把直线看成一个向量,容易想到如果对这些点集求出一个凸包,那么凸包上向量的极角是单调的,在上面找到出与当前直线对应向量最相近的两条边,中间的那个顶点就是在该直线法向量方向看最远的点。于是只要判断这个点是否符合条件就可以了。

剩下的问题就是给定一个凸包,每次有插入操作,怎么快速动态地维护这个凸包?

对于这个单调的东西,手写一个平衡树维护凸包顶点肯定是能做的,但是也可以偷懒利用STL的set。但是这里有个问题,到底是维护set < Line > set < Point >?对于判断是否在直线一端的部分,只有存Line能做,对于后面凸包的动态插入,只有Point能做……于是只能两个都维护了,在插入凸包的时候两个一起操作。

这里还有一个小技巧,因为叉乘只能判左还是右,超过180°的很容易写出奇怪的情况,于是动态凸包我是通过上凸壳和下凸壳来维护的。但是这样就要写两种情况,一个好的方法是对于下凸壳,直接左右翻转,上下翻转(也就是所有点的坐标都取负),这样就变成同样维护上凸壳了。

时间复杂度:O(n lg n)
空间复杂度:O(n)

PS.反演精度比较坑爹,建议使用相对误差进行几何上的判定。

代码

Codeforces #239

A

把直角的那个顶点放在原点,枚举其中一条边的横坐标,然后勾股定理得到纵坐标。旋转90度得到另外一个直角边的方向向量,伸缩到对应长度,看看是否整点。唯一的trick是除了直角边的那条边平行与坐标轴要注意。

B

令f[i][j]表示现在才在i上,i上的次数是奇数,其它位置都是偶数的情况下,从i走到j所需要的步数。
f[i][j] = f[i][j-1] + f[a[j-1]][j-1] + 2
记忆化递归求解f[0][n]即可。

C

先考虑单次操作的情况,f[i][0] = C[k + i – L][k] = 要求的答案。
对这个f[i][0]做一次差分,那么f[i][1] = f[i + 1][0] – f[i][0],可以看做这是i处的导数。
然后f[i][2]视为对f[i][1]这个数列作差分,一直往上。
然后由于C[m][n] = C[m – 1][n] + C[m – 1][n – 1],所以你会发现f[i][j] = C[k + i – L][k – j]。
那么现在变换一下f的递推关系得到f[i + 1][j] = f[i][j] + f[i][j + 1]。
也就是说,如果我知道到第i个数字的各阶导数,那么我可以一个一个数字往后推,得到其它数字以及他们的各阶导数。
又因为f[i][j] = C[k + i – L][k – j],k不超过100,所以j只要算到100阶就行了,再高后面的都是0。
由于这个递推式里面是加法,和答案里的求和相吻合,所有可以把各个询问叠在一起往后加着算。

于是得到这么一个算法,对于每个询问,求出他在l处的各阶导数,放进f[l][0..k]里面,在r出也求出各阶导数,放到f[r][0..k]里面(这里是为了抵消,用减法放进去)。
最后,大家一起从前往后推就好了。

D

令f[i][j][k]表示第i行到第j行这个子矩阵里,左边界选择第k列,右边界最远能到第几列。
首先f[i][j][k] ≤ min(f[i][j – 1][k], f[i + 1][j][k], f[i][j][k + 1])
除了这几个限制外,可能产生新冲突的就只可能是”第i行k列和第j行k列上的元素”与”第i行后面的元素和第j列后面的元素”。
那么按j – i的大小枚举i, j,再倒着枚举k,就可以用一个桶记录每个元素在第i行以及第j行最前出现的列是多少。
这样就可以处理掉这两个元素产生的冲突。
桶的清空稍微用一些编码技巧,就能O(n^3)写过去。

SRM 614

250

三次方枚举卡住左方,下方,以及右方/上方,再一个for计算矩形内的点,n^4暴力。

其实枚举前两个之后,每个点要求的len是固定的,按这个sort能达到n^3 lg n的复杂度。

525

这题比赛的时候没有过是很不应该的……就是一个很典型的dp。回忆一下这场SRM的过程,总结了一下为什么写这种计数自己经常会写但写得很慢。得出以下几点:

  1. 我想的过程中,经常会陷入局部情况或者说特例的求解,这样弄得最后整个代码就非常混乱,往往写出很多种情况,而这会极大的降低编码的效率。
  2. 组合计数问题,对独立的步骤进行划分是尤为重要的。而不同情况下每个步骤的操作都是类似的。把类似的过程统一处理往往能得到事半功倍的效果。
  3. 总得来看,其实这是architecture上的失败和大局观上的失败。

既然意识到了这个问题,那就在以后练习/比赛的时候注意提高吧。

算法大致是分小环和大环dp。

小环通过一个函数统一处理:count(int x, int y, int n, bool o)。这个函数返回的是,在小环上,一个接口在x号点,另一个接口在y号点,整个环的人数是n,x接口和y接口的颜色是否相等时的方案数。这个conut可以通过递推进行预处理(只和两条独立的链有关)。

然后在大环上,用g[i][j]表示处理完前i个小环,给下面的接口的颜色和“第0个环给第n-1个环的颜色”是否相等。再次递推。

最后输出g[n-1][0]即可。

1000

这题就是给定N, M, goalX, goalY求下面这个函数……

  1. 当i = goalX, j = goalY, f(i, j) = 0
  2. 其他情况 f(i, j) = (f((i + 1) % N, j) + f(i, (j + 1) % M)) / 2 + 1

输出f(0, 0)即可。

规模有100,迭代是可行的一个做法。

但是这样的迭代是过不了的……

        clr(f, 0);
        rep (it, 10000) {
            rep (i, N) rep (j, M) {
                if (i != goalX || j != goalY) {
                    int ni = (i + 1) % N, nj = (j + 1) % M;
                    f[i][j] = 1 + (f[ni][j] + f[i][nj]) / 2;
                }
            }
        }

这是因为顺序不科学导致的……因为(goalX, goalY)才是不动点,这样盲目地走看上去就很悲剧。
假设现在我在goalX, goalY,那么我影响到的路线应当是沿着-1方向过来的。
所以改成下面这样迭代顺序就过了。

        clr(f, 0);
        rep (it, 10000) {
            rep (_i, N) rep (_j, M) {
                int i = goalX - _i, j = goalY - _j;
                if (i < 0) i += N;
                if (j < 0) j += M;
                if (i != goalX || j != goalY) {
                    int ni = (i + 1) % N, nj = (j + 1) % M;
                    f[i][j] = 1 + (f[ni][j] + f[i][nj]) / 2;
                }
            }
        }

除了迭代以外,对于这种互相依赖的关系,迭代矩阵的又是满秩的,高斯消元解方程也是一个选择。那么假设M+N-1个未知量,其中M个在同一行,N个在同一列(为了方便,最好把不动点放在交错的位置)。这样其它的所有函数值都可以表示为这N+M-1个未知量的线性组合。绕了一圈一个,就可以得到M+N级别个方程,而M+N只有200,高斯消元是没有压力的。

但是zYc大师说好像有问题,等下写个代码看看能不能过。

更新
这个高斯消元算法是可以AC的。
代码在此

SRM 613

250

枚举分隔的位置,左边的一起向左,右边的一起向右。统计答案即可。

500

看了WJMZBMR的代码才明白过来T_T,容斥太弱了。算出区间内每个数包含的素因子。然后因为要gcd变为1,所以可以看成不能包含素因子Pi这若干个条件的与。接着就可以用容斥原理了。

900

看了芒果的代码才明白过来。首先是不能一行一行来填,这样dp的状态太难表示。

然后考虑一列一列来填。

  1. 假如只有left的话,就可以f[i][j]来表示填好前i列,其中有j列还没分配的时候的方案数。然后这个j其实蕴含了前面有j列是要填东西的,但是还没决定填在哪些行这么个意思。然后遇到left的结束端点,就可以拿这些数目去分配。大致就是乘个A几几的组合数。
  2. 现在如果有right的话,可以按left反过来那样处理,但是现在要统一起来,只能考虑从左往右填。由于一个行进入可填范围就不会变没了,所以f[i][j]表示填好前i列,还有j行没搞定。于是每次可以选择(或者不选)一个行,用当前列来填上。
  3. 最后把前两种dp合起来,f[i][j][k]转移一下就好了。

2014年的春游

本来今天打算做opencup的,结果早上一起来发现猛犸半夜发了条消息说今天出题。于是屁颠屁颠地跑去参加东莞帮的春游了。

首先是订的餐厅正门在装修,绕了几百米才进到去。我只能说十分感动……然后饭桌上miffy说要玩我是间谍。我表示从来没玩过,但是还是作为大菜鸟加入了这个游戏。但是我没有想到我的信誉就在这个游戏中破产了……

首先是大家抽到“女人”,学妹抽到“小三”。我第一个说,直接就说了麦当劳N年前的广告词“我就喜欢”。结果第一轮就被投死了(这是说明小伙伴都认为我是gay吗 )……然后后来学妹说“男人都挺喜欢的”,我当时就十分感动,终于有学妹同意我的观点了。结果最后发现学妹一直以为我说的是我喜欢小三。我立马感觉膝盖中了一枪……

后来有一次我抽到“爱做”,大家抽到“做*爱”。然后大家都说这词太坑爹不玩,我还不知道自己是卧底,大声说这回我可以说我就喜欢了吧!然后发现大家眼神不对劲……

后来跟着大队去逛西湖和太子湾。我说这是我第一次去太子湾,然后被学妹鄙视成马。

逛完以后发现坐公交回不来了,步行了很长一段时间以后遇到一个车10块一个人载到黄龙。大家都犹豫上不上……由于我记得那段路长得简直坑爹,于是直接就说了不管你们上不上,反正我是要上了。于是大家也一起上了,然后顺利回到玉泉正门。回来以后我跟阿龟老莫介绍了正门的波霸奶茶,于是一起去喝了一杯,我们都表示大颗的珍珠十分给力,下次还来……