二模（4） day1

第一题：

题目描述：

有一个无穷序列如下：110100100010000100000…请你找出这个无穷序列中指定位置上的数字

解题过程：

1.考虑到1的数目比0少的多，就从1的位置的规律开始分析。前几项1的位置是 1,2,4,7,11,16. 可以发现 A_n=A_n-1 + n-1 . 用点数列的知识可以求出通项公式。

An=n*(n-1)/2 + 1 。

如果位置k是1，那么有 k=x*（x-1）/2 +1 。就变成一个解方程的题，只要判断根是不是正整数就好。

初始得分100；

第二题：

题目大意：求方程 a₁x₁ + b₂x₂ + b₃x₃ + .... b_nx_n 的正整数解。

解题过程：

1.其实就是一个无限背包问题。

初始得分100；

第三题：

题目大意：出个2行数，N个在上，M个在下，然后上下两行相同的数可以连线，每一条连线都必须和另外一条连线相交（也只能和一条），且两条线的相连的4个数不能全相同。

求最多的连线数。

解题过程：

1.两条线的dp，无非是用F[i][j]来表示状态。先预处理出每个数能和那些数连线。F[i][j]表示A序列前i个，B序列前j个数且A[i],B[j]都有人连线的最优解。

显然如果A[i]能和多个数相连，那么肯定会去和B中最位置靠近j且小于j的B[k]相连，B[j]也是同理。设A[i]和B[q]，B[j]和A[p]相连，那么找p，q可以用二分查找。

那么可以得到状态转移方程：F[i][j]=max(F[r][s]+2),r<p && s<q。 max(F[r][s])可以在计算F[i][j]的时候更新得到，用一个g[][]保存。

那么方程就变成F[i][j]=F[p-1][q-1]+2;

2.另外来自YYL的方法：对于每一个i，j，可以预处理出相应的p，q。设F[i][j]对于的p为H1[i-1][j],q为H2[i][j-1]，可以用递推处理出所有的H1，H2.

举个例子：如果A[i]!=B[j],那么H2[i][j]=H2[i][j-1]。如果A[i]==B[j]，那么H2[i][j]=j;

初始得分100；

巴特西