发表文章

[最新] 2018 Multi-University Training Contest 3 - Problem A. Ascending Rating (单调队列)

mrtreeeee 15天前 27

http://acm.hdu.edu.cn/showproblem.php?pid=6319

 

题意:

太长了。

POINT:

倒着用单调队列求窗口最大值,并且这样队列里的元素个数就是count值。

o(n)扫一遍就可以了。

 

比赛中也差不多,但是我是顺着扫的,所以用了单调栈o(n)处理了每个元素到最后的最长上升子序列。但是单调队列的窗口长度写成了k,wa到了最后。sad,犯了很弱智的错误

 

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
#define LL long long
using namespace std;
const LL maxn=2e7+7;
LL a[maxn];
LL cnt[maxn];
LL Max[maxn];
LL Min[maxn];

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}


struct node
{
    LL x,y;
}v[maxn];

LL n,m,k,p,q,r,mod;

void getmax()
{
    LL head=1,end=0;
    for(LL i=n;i>n-m+1;i--)
    {
        while(head<=end&&v[end].x<=a[i]) end--;
        v[++end].x=a[i],v[end].y=i;
    }
    for(LL i=n-m+1;i>=1;i--)
    {
        while(head<=end&&v[end].x<=a[i]) end--;
        v[++end].x=a[i],v[end].y=i;
        while(v[head].y-i>=m) head++;
        Max[i]=v[head].x;
        Min[i]=end-head+1;
    }

}

int main()
{
    LL T;
    scanf("%lld",&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++){
            scan_d(a[i]);
        }
        for(LL i=k+1;i<=n;i++){
            a[i]=(p*a[i-1]+q*i+r)%mod;
        }
        getmax();
        LL ansa=0,ansb=0;
        for(LL i=1;i<=n-m+1;i++){
            ansa+=Max[i]^i;
            ansb+=Min[i]^i;
        }
        printf("%lld %lld\n",ansa,ansb);
    }

    return 0;
}

 

 

 

 

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
#define LL long long
using namespace std;
const LL maxn=2e7+7;
LL a[maxn];
LL cnt[maxn];
LL Max[maxn];
LL stc[maxn];
LL Min[maxn];

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}


struct node
{
    LL x,y,cnt;
}v[maxn];

LL n,m,k,p,q,r,mod;

void getmax()
{
    LL x=0;
    LL head=1,end=0;
    for(LL i=1;i<m;i++)
    {
        while(head<=end&&v[end].x<=a[i]) end--;
        v[++end].x=a[i],v[end].y=i;
        v[end].cnt=cnt[i];
    }
    for(LL i=m;i<=n;i++)
    {
        while(head<=end&&v[end].x<=a[i]) end--;
        v[++end].x=a[i],v[end].y=i;
        v[end].cnt=cnt[i];
        while(i-v[head].y>=m) head++;
        Max[++x]=v[head].x;
        Min[x]=v[head].cnt;
    }
}

int main()
{
    LL T;
    scanf("%lld",&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++){
            scan_d(a[i]);
        }
        for(LL i=k+1;i<=n;i++){
            a[i]=(p*a[i-1]+q*i+r)%mod;
        }
        LL top=0;
        stc[++top]=a[n];
        cnt[n]=top;
        for(LL i=n-1;i>=1;i--){
            while(top!=0&&stc[top]<=a[i]){
                top--;
            }
            stc[++top]=a[i];
            cnt[i]=top;
        }
        getmax();
        LL ansa=0,ansb=0;
        for(LL i=1;i<=n-m+1;i++){
            ansa+=(Max[i]^i);
            if(a[i]==0)
                ansb+=(cnt[i]-Min[i])^i;
            else{
                 ansb+=(cnt[i]-Min[i]+1)^i;
            }
        }
        printf("%lld %lld\n",ansa,ansb);
    }

    return 0;
}

 

相关推荐
最新评论 (0)
返回
发表文章
mrtreeeee
文章数
471
评论数
0
注册排名
699000