首页 > 代码库 > 二模 (4) day1

二模 (4) day1

第一题:

题目描述:

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

 

解题过程:

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

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

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

初始得分100;

 


 

第二题:

题目大意:求方程 a1x1 + b2x2 + b3x3 + ....  bnxn 的正整数解。 

 

解题过程:

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;

二模 (4) day1