刚学OI,萌新全WA，求大佬查错

yuio @ 2019-07-11 10:31:55

#include<bits/stdc++.h>
using namespace std;
#define F(x,a,b) for(int x=a;x<=b;x++)
const int mx=40005;
int cnt[mx][205],n,m,t,c[mx],tot[mx],Mn[mx],out[mx];
struct node{
int id,num;
}col[mx];
bool cmp(node a,node b){return a.num<b.num;}
int main(){
scanf("%d%d",&n,&m);
F(i,1,n){scanf("%d",&col[i].num);col[i].id=i;}
sort(col+1,col+1+n,cmp);
F(i,1,n){
    c[col[i].id]=col[i].num!=col[i-1].num?++t:t;
    out[t]=col[i].num;
}
int len=pow(n,1.0/3),g=0;
F(i,1,n){
    tot[c[i]]++;
    if(!(i%len)||i==n){
        int M=0;g++;
        F(j,1,t){
            cnt[g][j]=tot[j];
            int ti=cnt[g][j]-cnt[g-1][j];
            if(ti>M){M=ti;Mn[g]=j;}
        }
    }
}
F(i,1,m){
    int l,r;
    scanf("%d%d",&l,&r);
    int q[mx]={0},ll,rr,lg=(l-1)/len+1,rg=r/len;
    if(lg==rg){ll=rr=l;}
    else{ll=lg*len;rr=rg*len;}
    F(j,l,ll)q[c[j]]++;
    F(j,rr+1,r)q[c[j]]++;
    int M=0,ans;lg=min(lg,rg);
    F(j,1,t)if(q[j]){
        q[j]+=cnt[rg][j]-cnt[lg][j];
        if(q[j]>M){M=q[j];ans=j;}
    }
    F(j,lg+1,rg){
        int mn=Mn[j],ti=cnt[rg][mn]-cnt[lg][mn];
        if(M<ti||(M==ti&&mn<ans)){M=ti;ans=mn;}
    }
    printf("%d\n",out[ans]);
}
return 0;
}

by TEoS @ 2019-07-11 10:45:33

萌新都问黑题吗qwq 卑微

by yuio @ 2019-07-11 10:57:15

我是练习时间长达两年半的OIer。。？

by Clintikas97 @ 2019-07-11 16:47:00

https://www.luogu.org/problemnew/show/P1468

by Smile_Cindy @ 2019-07-11 19:20:01

#include<bits/stdc++.h>
using namespace std;
#define F(x,a,b) for(int x=a;x<=b;x++)
const int mx=40005;
int cnt[mx][205],n,m,t,c[mx],tot[mx],Mn[mx],out[mx];
struct node{
int id,num;
}col[mx];
bool cmp(node a,node b){return a.num<b.num;}
int main(){
scanf("%d%d",&n,&m);
F(i,1,n){scanf("%d",&col[i].num);col[i].id=i;}
sort(col+1,col+1+n,cmp);
F(i,1,n){
    c[col[i].id]=col[i].num!=col[i-1].num?++t:t;
    out[t]=col[i].num;
}
int len=pow(n,1.0/3),g=0;
F(i,1,n){
    tot[c[i]]++;
    if(!(i%len)||i==n){
        int M=0;g++;
        F(j,1,t){
            cnt[g][j]=tot[j];
            int ti=cnt[g][j]-cnt[g-1][j];
            if(ti>M){M=ti;Mn[g]=j;}
        }
    }
}
F(i,1,m){
    int l,r;
    scanf("%d%d",&l,&r);
    int q[mx]={0},ll,rr,lg=(l-1)/len+1,rg=r/len;
    if(lg==rg){ll=rr=l;}
    else{ll=lg*len;rr=rg*len;}
    F(j,l,ll)q[c[j]]++;
    F(j,rr+1,r)q[c[j]]++;
    int M=0,ans;lg=min(lg,rg);
    F(j,1,t)if(q[j]){
        q[j]+=cnt[rg][j]-cnt[lg][j];
        if(q[j]>M){M=q[j];ans=j;}
    }
    F(j,lg+1,rg){
        int mn=Mn[j],ti=cnt[rg][mn]-cnt[lg][mn];
        if(M<ti||(M==ti&&mn<ans)){M=ti;ans=mn;}
    }
    printf("%d\n",out[ans]);
}
return 0;
}

by yuio @ 2019-07-11 20:17:47

突然发现我题目看错了。。。然而改完之后依然全WA

using namespace std;
#define F(x,a,b) for(int x=a;x<=b;x++)
const int mx=40005;
int cnt[mx][205],n,m,t,l,r,ans;
int c[mx],tot[mx],Mn[mx],out[mx];
struct node{int id,num;}col[mx];
bool cmp(node a,node b){return a.num<b.num;}
int to(int x){return (x+ans-1)%n+1;}
int main(){
    scanf("%d%d",&n,&m);
    F(i,1,n){scanf("%d",&col[i].num);col[i].id=i;}
    sort(col+1,col+1+n,cmp);
    F(i,1,n){
        c[col[i].id]=col[i].num!=col[i-1].num?++t:t;
        out[t]=col[i].num;
    }
    int len=pow(n,1.0/3),g=0;
    F(i,1,n){
        tot[c[i]]++;
        if(!(i%len)||i==n){
            int M=0;g++;
            F(j,1,t){
                cnt[g][j]=tot[j];
                int ti=cnt[g][j]-cnt[g-1][j];
                if(ti>M){M=ti;Mn[g]=j;}
            }
        }
    }
    F(i,1,m){
        scanf("%d%d",&l,&r);
        l=to(l);r=to(r);if(l>r)swap(l,r);
        if(l>n){ans=0;cout<<0<<endl;continue;}
        r=min(r,n);
        int q[mx]={0},ll,rr,lg=(l-1)/len+1,rg=r/len;
        if(lg==rg){ll=rr=l;}
        else{ll=lg*len;rr=rg*len;}
        F(j,l,ll)q[c[j]]++;
        F(j,rr+1,r)q[c[j]]++;
        int M=0;lg=min(lg,rg);
        F(j,1,t)if(q[j]){
            q[j]+=cnt[rg][j]-cnt[lg][j];
            if(q[j]>M){M=q[j];ans=j;}
        }
        F(j,lg+1,rg){
            int mn=Mn[j],ti=cnt[rg][mn]-cnt[lg][mn];
            if(M<ti||(M==ti&&mn<ans)){M=ti;ans=mn;}
        }
        ans=out[ans];
        printf("%d\n",ans);
    }
    return 0;
}

by xcyy @ 2019-08-09 19:04:14

@yuio 萌新专做紫题？？？