首页 > 代码库 > 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