hdu3706基础的单调队列

hdu3706基础的单调队列

题意： 解释题意不如直接把这个题粘贴过来，因为题目很短题意很容易懂。 Give you three integers n, A and B.  Then we define Si = Ai mod B and Ti = Min{ Sk | i-A <= k <= i, k >= 1} Your task is to calculate the product of Ti (1 <= i <= n) mod B.   Input Each line will contain three integers n(1 <= n <= 107),A and B(1 <= A, B <= 231-1).  Process to end of file.   Output For each case, output the answer in a single line.

Sample Input

1 2 3 2 3 4 3 4 5 4 5 6 5 6 7   Sample Output 2 3 4 5 6 思路：       比较简单的一个单调队列题目，我们可以建立一个单调递增的单调队列，开一个1000W的数组，不用怕报内存，内存够，然后我们每次都把一个新值进队列，然后把队尾比这个值大于等于的出队，对头把下标之差大于A的出队就行了，每次都是把一个新的值放进队列，然后在对头拿一个最小的来作为当前的T,然后一边更新，一边拿，一边记录答案就行了，O(n)的时间复杂度，1000W的，可以过（不过感觉还是有点险，但这个题目都O(n)了在过不了，那估计就设计到转换什么的了，那我就做不了了，嘿嘿）。

#include#include#define N 10000005typedef struct{ int id; __int64 num;}NODE;NODE Q[N];int tou ,wei;__int64 A ,B ,n;void insert(int id ,__int64 num){ for(int i = wei ;i > tou ;i --) { if(Q[wei].num >= num) wei --; else break; } Q[++wei].num = num; Q[wei].id = id; for(int i = tou + 1 ;i <= wei ;i ++) if(id - Q[i].id > A) tou ++; else break;}int main (){ while(~scanf("%d %I64d %I64d" ,&n ,&A ,&B)) { __int64 now = A % B; __int64 Ans = 1; tou = wei = 0; for(int i = 1 ;i <= n ;i ++) { insert(i ,now); Ans = (Ans * Q[tou+1].num) % B; now = now * A % B; } printf("%I64d\n" ,Ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。