首页 > 代码库 > 04day1

04day1

无穷的数列

找规律

【问题描述】

有一个无穷序列如下:

110100100010000100000…

请你找出这个无穷序列中指定位置上的数字。

【输入】

第一行一个正整数 N,表示询问次数;接下来的 N 行每行一个正整数 Ai,Ai 表示在序列中的位置。

【解题过程】

找规律就好了。对于一个给定的位置 P,可以发现如果 P 上的数字是 1,那么必然满足 P-1 = x*(x+1)/2,那么判断这个方程是否有整数解即可(开平方取整再乘)。

1 次 AC。

?

方程

动态规划

【问题描述】

【输入】

第一行是 n 和 c。

第二行是 n 个数,分别表示 a1, a2, ..., an。

【输出】

输出解的组数(结果对 999983 取模)。

【解题过程】

一开始真的没思路啊,刚好数学在上排列组合,有个神奇的「隔板法」,差点误入歧途。

然后想到了一个很奇葩的方法,用 f[i] 表示用这个式子组成 i 这个值有几组解,则

f[i] = sum{ f[i-a[j]], 1<=j<=n }

看上去有点道理,然后其实是错的。这种状态转移的方式无法判断重复的情况,比如 b1 取 1,b2 取 1 是可以由两种情况(1, 0 和 0, 1)推过来的,加的时候也就多加了。

然后居然想了将近一个小时才想到正解,我也是醉了。

用 f[i][j] 表示用 a1, a2, ..., ai 来组成 j 有多少组解,则

f[i][j] = f[i-1][j] + f[i-1][j-a[i]], 1<=j<=n

然后如果用上滚动数组的话,最后表现出来的代码与上面那种错误方法几乎完全一样,只是外循环和内循环调换了一下。

然后听到 lzw 大神说无限背包。然后就没有然后了。

1 次 AC。

?

交错匹配

动态规划

【问题描述】

有两排非负整数 A[1..N],B[1..M],如果 A[i]=B[j]=k,那么可以在 A[i]和 B[j]之间连一条线,称为一条 k 匹配,每个数至多连一条线。另外,每个 k 匹配都必须恰好跟一个 r 匹配相交,且 k≠r。现在要求一个最大的匹配数。

例如:以下两行数的最大匹配数为 8.一个数最多只能和一个数连线。

【输入】

输入文件第一行包含两个正整数 n 和 m。

第二行 n 个自然数,表示 a[i]。

第三行 m 个自然数,表示 b[i]。

【数据规模】

30%的数据满足 n,m≤30。

60%的数据满足 n,m≤200。

100%的数据满足 n,m≤1000,0<所有数≤32767。

【解题过程】

看到什么最大匹配的还以为是二分图,吓了一小跳。

然后从数据范围来看几乎可以肯定是 O(mn) 的动态规划。

借鉴 LCS 的状态表示,用 f(i, j) 表示 a1, ..., ai 与 b1, ..., bj 之间的最大匹配数,那么我们只要考虑 ai 与 bj 是否需要进行匹配。如果要进行匹配,那么只要在 bj 的左边找与 ai 匹配的数、在 ai 的左边找与 bj 匹配的数就能保证两个匹配相交。很明显,对于 ai 找 bj 左边距离 bj 最近的那个匹配才可能是最优解,对于 bj 也应该找 ai 左边最近的匹配。这个找匹配的过程我们可以事先进行预处理。用 p(i, j) 表示 ai 在 b1, b2, ..., bj 中离 bj 最近的那个匹配所在的位置,则可以进行递推:

若 ai=bj,则 p(i, j) = j

否则,p(i, j) = p(i, j-1)

然后可以用 q(j, i) 表示 bj 在 a1, a2, ..., ai 中离 ai 最近的那个匹配的位置,递推过程类似。

然后就可以写出状态转移方程了,

f(i, j) = max{ f(q(j, i-1)-1, p(i, j-1)-1), f(i-1, j), f(i, j-1), f(i-1, j-1) }

初始得分 90 分。原因是把递推的嵌套循环范围写错了(这样也能拿 90 分?)。

04day1