二模 (10) day2

第一题:

题目大意:求出区间 [L,R]里约数最多的数。   L,R<=10^9

解题过程:

1.一开始我就往恶心的数据去想了,比如 L=R=一个超级大的质数。。 那么 用搜索质因子的方法  是不可能搜到它的,于是就放弃了搜索质因子的方法,用了个类筛法。直接暴力求出100w以内所有数的约数,骗到了30分。

2.AC算法:还是枚举质因子,枚举65536以内的所有质数,然后加很多乱七八糟的剪枝,还在研究中。。。待AC。


第二题:

题目大意:给出一个长度为N的整数数列,要求改变一些数字,使该数列递增。。  (N<=100000)

解题过程:

1.因为要递增,自然就想到了LIS,求一个LIS,那么答案就是 N-LIS的长度。。 但是题目的意思是 不能把一个数变成小数。。也就是 2 3 4 3 5 这样的数据,不能把第2个3改成4.5来使得数列递增。。  不过直接写个LIS可以拿到80分,可惜二分写错了。。结果爆0.

2.AC算法:要求一个特殊的LIS,这里的LIS必须满足相邻两个数的差必须大于等于它们的位置差。 也就是说 Aj 要 连在 Ai 后面的条件 是 :

j-i<=Aj-Ai      -->      Ai-i<=Aj-j

所以只要把所以Ai减去它的位置i,然后求最长非降子序列即可。

本来以为二分绝对不会写错的,还是不够小心。。


第三题:

题目大意:求出从矩阵左上角(1,1) 到 右下角 (n,m) 的一条路径,使得路径上所有正数和除以负数和的绝对值最小 , 求这个最小值。

解题过程:

这题是真心好题。学到了二分的新用法。。  首先假设 答案 是 ans,路径上正数和为x,负数和的绝对值为y, 那么 满足 :

ans>=x/y     -->   ans*y-x>=0

那么二分ans,设为t, 答案就是 满足 t*y-x >=0 的 最小的 t 。

要使不等式恒成立,必须左边的最小值大于等于0,所以用经典的过河卒的dp方法求出这个最小值即可。

上一篇:Delphi Application.MessageBox详解


下一篇:biztalk中使用WCF-SQL接受传送数据【转】