hdu 4379 The More The Better ( 2012 Multi-University Training Contest 8)

http://acm.hdu.edu.cn/showproblem.php?pid=4379
The More The Better
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 800    Accepted Submission(s): 208
Problem Description
Given an sequence of numbers {X
1, X
2, ... , X
n}, where X
k = (A * k + B) % mod. Your task is to find the maximum sub sequence {Y
1, Y
2, ... , Y
m} where every pair of (Y
i, Y
j) satisfies Y
i + Y
j <= L (1 ≤ i < j ≤ m),
and every Yi <= L (1 ≤ i ≤ m ).
Now given n, L, A, B and mod, your task is to figure out the maximum m described above.
 
Input
Multiple test cases, process to the end of input. Every test case has a single line. A line of 5 integers: n, L, A, B and mod. (1 ≤ n ≤ 2*10
7, 1 ≤ L ≤ 2*10
9, 1 ≤ A, B, mod ≤ 10
9)
 
Output
For each case, output m in one line.
 
Sample Input

   
     

      
    1 8 2 3 6 
   
     
5 8 2 3 6

 
Sample Output

   
     

      
    1 4
   
     

 
Source
2012 Multi-University Training Contest 8
 
 
 
簡単な問題は、まずL/2未満のものをすべて入れることができることを考えて、最後に、問題の意味によって、L/2より大きい数を入れることができて、L/2より小さい数の中の最大値にこのL/2より大きい数とLより小さい数を加えると、答えは1つプラスします.最後に、すべての数がL/2未満の処理に注意してください.O(n)アルゴリズムはこの問題を通過することができる.
 
好蛋疼的题目是好蛋疼痛的题目,好蛋疼痛的题目是好蛋疼痛的题目,好蛋疼痛的题目是好蛋疼痛的题目,好蛋疼痛的题目是好蛋疼痛的题目,好蛋疼痛的题目是好蛋疼痛的题目.
 


View Code
 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #include<
set>
 8 #include