郑州公司建站模板,wordpress开发者手册,wordpress ,搜索引擎优化是什么无穷的数列 找规律 【问题描述】 有一个无穷序列如下#xff1a; 110100100010000100000… 请你找出这个无穷序列中指定位置上的数字。 【输入】 第一行一个正整数 N#xff0c;表示询问次数#xff1b;接下来的 N 行每行一个正整数 Ai#xff0c;Ai 表示在序列中的位置。 …无穷的数列 找规律 【问题描述】 有一个无穷序列如下 110100100010000100000… 请你找出这个无穷序列中指定位置上的数字。 【输入】 第一行一个正整数 N表示询问次数接下来的 N 行每行一个正整数 AiAi 表示在序列中的位置。 【解题过程】 找规律就好了。对于一个给定的位置 P可以发现如果 P 上的数字是 1那么必然满足 P-1 x*(x1)/2那么判断这个方程是否有整数解即可开平方取整再乘。 1 次 AC。 方程 动态规划 【问题描述】 【输入】 第一行是 n 和 c。 第二行是 n 个数分别表示 a1, a2, ..., an。 【输出】 输出解的组数结果对 999983 取模。 【解题过程】 一开始真的没思路啊刚好数学在上排列组合有个神奇的「隔板法」差点误入歧途。 然后想到了一个很奇葩的方法用 f[i] 表示用这个式子组成 i 这个值有几组解则 f[i] sum{ f[i-a[j]], 1jn } 看上去有点道理然后其实是错的。这种状态转移的方式无法判断重复的情况比如 b1 取 1b2 取 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]], 1jn 然后如果用上滚动数组的话最后表现出来的代码与上面那种错误方法几乎完全一样只是外循环和内循环调换了一下。 然后听到 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≤10000所有数≤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 最近的那个匹配所在的位置则可以进行递推 若 aibj则 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 分。转载于:https://www.cnblogs.com/lsdsjy/p/3982489.html
