[洛谷0925]NOIP模拟赛 个人公开赛 OI

时间：2021-11-10 03:31:08

 P3395 路障

题目背景

此题约为NOIP提高组Day1T1难度。

题目描述

B君站在一个n*n的棋盘上。最开始，B君站在(1,1)这个点，他要走到(n,n)这个点。

B君每秒可以向上下左右的某个方向移动一格，但是很不妙，C君打算阻止B君的计划。

每秒结束的时刻，C君会在(x,y)上摆一个路障。B君不能走在路障上。

B君拿到了C君准备在哪些点放置路障。所以现在你需要判断，B君能否成功走到(n,n)。

保证不会走到某处，然后被一个路障砸死。

输入输出格式

输入格式：

首先是一个正整数T，表示数据组数。

对于每一组数据：

第一行，一个正整数n。

接下来2n-2行，每行两个正整数x和y，意义是在那一秒结束后，(x,y)将被摆上路障。


输出格式：

对于每一组数据，输出Yes或No，回答B君能否走到(n,n)。

输入输出样例


输入样例#1：
　 
2

2

1 1

2 2

5

3 3

3 2

3 1

1 2

1 3

1 4

1 5

2 2
输出样例#1：
　 
Yes

Yes

说明

样例解释：

以下0表示能走，x表示不能走，B表示B君现在的位置。从左往右表示时间。

Case 1:

0 0    0 0    0 B  (已经走到了)

B 0    x B    x 0 
Case 2:

0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0

0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0

0 0 0 0 0    0 0 x 0 0    0 0 x 0 0    0 0 x 0 0

0 0 0 0 0    0 0 0 0 0    0 0 x 0 0    0 0 x 0 0

B 0 0 0 0    0 B 0 0 0    0 0 B 0 0    0 0 x B 0 ......(B君可以走到终点)

数据规模：

防止骗分，数据保证全部手造。

对于20%的数据，有n<=3。

对于60%的数据，有n<=500。

对于100%的数据，有n<=1000。

对于100%的数据，有T<=10。

100分代码：

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int dx[]={,,,-};

const int dy[]={,-,,};

const int N=1e3+;

int n,m,T,dis[N][N];

bool vis[N][N];

struct node{

    int x,y,lim;

};

bool bfs(int sx,int sy){

    queue<node>q;

    q.push((node){sx,sy,});

    if(sx==n&&sy==n) return ;

    memset(vis,,sizeof vis);

    vis[sx][sy]=;

    while(!q.empty()){

        node h=q.front();q.pop();

        for(int i=;i<;i++){

            int nx=h.x+dx[i];

            int ny=h.y+dy[i];

            if(!vis[nx][ny]&&nx>&&nx<=n&&ny>&&ny<=n&&(!dis[nx][ny]||h.lim<dis[nx][ny])){

                vis[nx][ny]=;

                q.push((node){nx,ny,h.lim+});

                if(nx==n&&ny==n) return ;

            }

        }

    }

    return ;

}

int main(){

    scanf("%d",&T);

    while(T--){

        memset(dis,,sizeof dis);

        scanf("%d",&n);

        for(int i=,x,y;i<=*n-;i++) scanf("%d%d",&x,&y),dis[x][y]=i;

        puts(bfs(,)?"Yes":"No");

    }

    return ;

}

P3396 哈希冲突

　

题目背景

此题约为NOIP提高组Day2T2难度。

题目描述

众所周知，模数的hash会产生冲突。例如，如果模的数p=7，那么4和11便冲突了。

B君对hash冲突很感兴趣。他会给出一个正整数序列value[]。

自然，B君会把这些数据存进hash池。第value[k]会被存进(k%p)这个池。这样就能造成很多冲突。

B君会给定许多个p和x，询问在模p时，x这个池内数的总和。

另外，B君会随时更改value[k]。每次更改立即生效。

保证[洛谷0925]NOIP模拟赛 个人公开赛 OI.

输入输出格式

输入格式：
　

　

第一行，两个正整数n,m，其中n代表序列长度，m代表B君的操作次数。

第一行，n个正整数，代表初始序列。

接下来m行，首先是一个字符cmd，然后是两个整数x,y。

  • 若cmd='A'，则询问在模x时，y池内数的总和。

  • 若cmd='C'，则将value[x]修改为y。

　


输出格式：

对于每个询问输出一个正整数，进行回答。

输入输出样例


输入样例#1：
　 
10 5

1 2 3 4 5 6 7 8 9 10

A 2 1

C 1 20

A 3 1

C 5 1

A 5 0
输出样例#1：
　 
25

41

11

说明

样例解释

A 2 1的答案是1+3+5+7+9=25.

A 3 1的答案是20+4+7+10=41.

A 5 0的答案是1+10=11.

数据规模

对于10%的数据，有n<=1000,m<=1000.

对于60%的数据，有n<=100000.m<=100000.

对于100%的数据，有n<=150000,m<=150000.

保证所有数据合法，且1<=value[i]<=1000.

100分代码：

#include<cstdio>

#include<iostream>

using namespace std;

const int N=1.5e5+;

int a[N];

inline const int read(){

    register int x=,f=;

    register char ch=getchar();

    while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline const char in(){

    for(register char ch=getchar();;ch=getchar()) if(ch>='A'&&ch<='Z') return ch;

}

int main(){

    int n=read(),m=read();char ch;

    for(int i=;i<=n;i++) a[i]=read();

    for(int i=;i<=m;i++){

        if((ch=in())=='A'){

            int x=read(),y=read();

            int s=;

            for(int i=y;i<=n;i+=x) s+=a[i];

            printf("%d\n",s);

        }

        else{

            int x=read(),y=read();

            a[x]=y;

        }

    }

    return ;

}

P3397 地毯

　

题目背景

此题约为NOIP提高组Day2T1难度。

题目描述

在n*n的格子上有m个地毯。

给出这些地毯的信息，问每个点被多少个地毯覆盖。

输入输出格式

输入格式：

第一行，两个正整数n、m。意义如题所述。

接下来m行，每行两个坐标(x1,y1)和(x2,y2)，代表一块地毯，左上角是(x1,y1)，右下角是(x2,y2)。


输出格式：

输出n行，每行n个正整数。

第i行第j列的正整数表示(i,j)这个格子被多少个地毯覆盖。

输入输出样例


输入样例#1：
　 
5 3

2 2 3 3

3 3 5 5

1 2 1 4
输出样例#1：
　 
0 1 1 1 0

0 1 1 0 0

0 1 2 1 1

0 0 1 1 1

0 0 1 1 1

说明

样例解释

0 0 0 0 0         0 0 0 0 0        0 1 1 1 0

0 1 1 0 0         0 1 1 0 0        0 1 1 0 0

0 1 1 0 0    ->   0 1 2 1 1   ->   0 1 2 1 1

0 0 0 0 0         0 0 1 1 1        0 0 1 1 1

0 0 0 0 0         0 0 1 1 1        0 0 1 1 1

数据范围

对于20%的数据，有n<=50，m<=100。

对于100%的数据，有n<=1000，m<=1000。

100分代码：

#include<cstdio>

using namespace std;

const int N=1e3+;

int n,m,a[N][N];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++){

        int x1,x2,y1,y2;

        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

        for(int j=x1;j<=x2;j++){

            for(int k=y1;k<=y2;k++){

                a[j][k]++;

            }

        }

    }

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++){

            printf("%d ",a[i][j]);

        }

        printf("\n");

    }

    return ;

}

相关文章