UESTC 1256 昊昊喜欢运动 n^2的预处理 or 前缀和

#include 
#include 
#include 
#define LOCAL
using namespace std;
int n[2008],cot[108];
int main()
{
    #ifdef LOCAL
    freopen("a.txt","r",stdin);
    #endif // LOCAL
    int N,M,Q,x,y,cott;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++){
        scanf("%d",&n[i]);
    }

    scanf("%d",&Q);
    while(Q--){
        cott=0;
        memset(cot,0,sizeof(cot));
        scanf("%d%d",&x,&y);
        for(int i=x;i<=y;i++)
            if(cot[n[i]]==0) {cott++;cot[n[i]]++;}
        //for(int j=0;j<=M;j++)
        //    if(cot[j]!=0) ;
        printf("%d",cott);
        if(Q) printf("n");

    }
    return 0;
}

#include 
#include 
//#define LOCAL
using namespace std;
const int maxn=2000+2;
int n[maxn],cot[108],ans[maxn][maxn];
int main()
{
    #ifdef LOCAL
    freopen("a.txt","r",stdin);
    #endif // LOCAL
    int N,M,Q,x,y,cott;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++){
        scanf("%d",&n[i]);
    }
    //ans[maxn][maxn]就不用memset了，由于这里没有必要，而且数组比较大，memset起来还是要耗点时间的
    //n^2的预处理
    for(int i=1;i<=N;i++){
        memset(cot,0,sizeof(cot));cott=0;
        for(int j=i;j<=N;j++){
            if(cot[n[j]]==0) {cott++;cot[n[j]]++;}
            ans[i][j]=cott;//由于这里指的是[x,y]，且1<=x,所以上面要用 int i=1;i<=N;i++,下面j也是
        }   //数组和所需要对应好
    }
    //询问
    scanf("%d",&Q);
    while(Q--){
        scanf("%d%d",&x,&y);
        printf("%d",ans[x][y]);
        if(Q) printf("n");
    }
    return 0;
}

3、前缀和思想

#include 
#include 
#define LOCAL
using namespace std;
int ans[2002][108];
int main()
{
    #ifdef LOCAL
    freopen("a.txt","r",stdin);
    #endif // LOCAL
    int N,M,Q,x,y,cott,n;
    scanf("%d%d",&N,&M);
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=N;i++){
        scanf("%d",&n);                                //原来的n[maxn]也可以省掉了
        ans[i][n]++;
        for(int j=1;j<=M;j++) ans[i][j]+=ans[i-1][j];  //边输入边维护 前面的所有信息都要维护过来1-M的出现次数
        //前面用了j<i，i可能很大，不越界才怪,改的时候，不要漏地方没改
    }

    scanf("%d",&Q);
    while(Q--){
        cott=0;
        scanf("%d%d",&x,&y);
        for(int i=1;i<=M;i++){ if((ans[y][i]-ans[x-1][i])>0) cott++;    //注意索引
        }
        printf("%d",cott);
        if(Q) printf("n");
    }
    return 0;
}

前面数组越界了，返回了一个RF，在不知道是越界引起的时候，我加了个#include 以后返回了WA，嘿嘿挺好玩的。

非特殊说明，本站所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx