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)写过去。

发表评论

电子邮件地址不会被公开。