【6319 HDU】Problem A. Ascending Rating（单调队列）

亦凉 2022-05-17 08:12 111阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6319][http_acm.hdu.edu.cn_showproblem.php_pid_6319]

题意：输入T组测试样例，每组测试样例包含7个整数n，m，k，p，q，r，mod，接下来一行输入前k个数，后n-k个数用公式a\[ i \] =(p×a\[ i−1 \]+q×i+r) mod MOD，输出A和B，其中![A=\\sum\_\{i-1\}^\{n-m+1\}(max\_\{i\}\\oplus i)][A_sum_i-1_n-m_1_max_i_oplus i]，![B=\\sum\_\{i-1\}^\{n-m+1\}(count\_\{i\}\\oplus i)][B_sum_i-1_n-m_1_count_i_oplus i]，max初始值是-1，count初始值是0，当在任意的连续的m长子区间内遇到比max大的值时，就更新max的值，并且count+1；则，max里面存的是任意连续的m长子区间内的最大值，count是指最大值变化的次数。

思路：这道题用到了单调队列的知识点，单调队列是专业用来求数组中任意子区间内的最大值或最小值。然后这道题唯一的区别是单调队列是从后往前遍历的，如果你从前往后遍历的话，可能你在入队的时候把后一个区间里面的比较重要的数删了，所以为了避免这种情况，就从后往前遍历。

单调队列知识点参考博客：[https://blog.csdn.net/qq\_41181772/article/details/81364243][https_blog.csdn.net_qq_41181772_article_details_81364243]

My DaiMa：

#include<bits/stdc++.h>
    using namespace std;
    const int Max = 10000003;
    typedef long long ll;
    ll a[Max],v[Max];
    int main()
    {
        int t;
        ll n,m,k,p,q,r,mod;
        scanf("%d",&t);
        while( t-- )
        {
            scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&m,&k,&p,&q,&r,&mod);
            for( ll i = 1; i<= k; i++)
                scanf("%lld",&a[i]);//输入前k个数
            for(ll i = k+1; i <= n; i++)
                a[i] = (p*a[i-1]+q*i+r)%mod;//根据公式计算后n-k个数
            ll ans = 0,cunt = 0;
            ll head = 1,tail = 0;//队列的头和尾，维护队列的队首作为答案
            for( ll i = n; i >= 1; i--)//要求最大值，因此此单调队列是单调递减队列
            {
                while(head <= tail && a[v[tail]] <= a[i]) tail--;//当要入队的那个数比队尾要大时，为了维护这个递减队列，就要把队尾去掉，直到找到比要入队的数小的数时跳出循环，此时就保证了这个队列还是递减队列
                v[++tail] = i;//将这个数入队，放在第一个比他小的数的后面
                if(i+m-1 <= n)
                {
                    while(v[head] > i+m-1) head++;//如果队首所代表的下标不在此区间内，就需要让队首+1
                    ans += i^a[v[head]];//最大值就是队首
                    cunt += i^(tail-head+1);//最大值改变的次数就是队列的个数
                }
            }
            printf("%lld %lld\n",ans,cunt);
        }
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_6319]: http://acm.hdu.edu.cn/showproblem.php?pid=6319
[A_sum_i-1_n-m_1_max_i_oplus i]: https://private.codecogs.com/gif.latex?A%3D%5Csum_%7Bi-1%7D%5E%7Bn-m&plus;1%7D%28max_%7Bi%7D%5Coplus%20i%29
[B_sum_i-1_n-m_1_count_i_oplus i]: https://private.codecogs.com/gif.latex?B%3D%5Csum_%7Bi-1%7D%5E%7Bn-m&plus;1%7D%28count_%7Bi%7D%5Coplus%20i%29
[https_blog.csdn.net_qq_41181772_article_details_81364243]: https://blog.csdn.net/qq_41181772/article/details/81364243