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)
。
输入输出样例
221 12 253 33 23 11 21 31 41 52 2
YesYes
说明
样例解释:
以下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 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 x 0 0 0 0 x 0 0 0 0 x 0 00 0 0 0 0 0 0 0 0 0 0 0 x 0 0 0 0 x 0 0B 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#include #include using namespace std;const int dx[]={ 0,0,1,-1};const int dy[]={ 1,-1,0,0};const int N=1e3+10;int n,m,T,dis[N][N];bool vis[N][N];struct node{ int x,y,lim;};bool bfs(int sx,int sy){ queue q; q.push((node){sx,sy,0}); if(sx==n&&sy==n) return 1; memset(vis,0,sizeof vis); vis[sx][sy]=1; while(!q.empty()){ node h=q.front();q.pop(); for(int i=0;i<4;i++){ int nx=h.x+dx[i]; int ny=h.y+dy[i]; if(!vis[nx][ny]&&nx>0&&nx<=n&&ny>0&&ny<=n&&(!dis[nx][ny]||h.lim
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]
。每次更改立即生效。
保证.
输入输出格式
输入格式:
第一行,两个正整数n,m
,其中n
代表序列长度,m
代表B君的操作次数。
第一行,n
个正整数,代表初始序列。
接下来m
行,首先是一个字符cmd
,然后是两个整数x,y
。
-
若
cmd='A'
,则询问在模x
时,y
池内数的总和。 - 若
cmd='C'
,则将value[x]
修改为y
。
输出格式:
对于每个询问输出一个正整数,进行回答。
输入输出样例
10 51 2 3 4 5 6 7 8 9 10A 2 1C 1 20A 3 1C 5 1A 5 0
254111
说明
样例解释
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#include using namespace std;const int N=1.5e5+10;int a[N];inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';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=1;i<=n;i++) a[i]=read(); for(int i=1;i<=m;i++){ if((ch=in())=='A'){ int x=read(),y=read(); int s=0; 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 0;}
P3397 地毯
题目背景
此题约为NOIP提高组Day2T1难度。
题目描述
在n*n
的格子上有m
个地毯。
给出这些地毯的信息,问每个点被多少个地毯覆盖。
输入输出格式
输入格式:
第一行,两个正整数n、m
。意义如题所述。
接下来m
行,每行两个坐标(x1,y1)
和(x2,y2)
,代表一块地毯,左上角是(x1,y1)
,右下角是(x2,y2)
。
输出格式:
输出n
行,每行n
个正整数。
第i
行第j
列的正整数表示(i,j)
这个格子被多少个地毯覆盖。
输入输出样例
5 32 2 3 33 3 5 51 2 1 4
0 1 1 1 00 1 1 0 00 1 2 1 10 0 1 1 10 0 1 1 1
说明
样例解释
0 0 0 0 0 0 0 0 0 0 0 1 1 1 00 1 1 0 0 0 1 1 0 0 0 1 1 0 00 1 1 0 0 -> 0 1 2 1 1 -> 0 1 2 1 10 0 0 0 0 0 0 1 1 1 0 0 1 1 10 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分代码:
#includeusing namespace std;const int N=1e3+10;int n,m,a[N][N];int main(){ scanf("%d%d",&n,&m); for(int i=1;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=1;i<=n;i++){ for(int j=1;j<=n;j++){ printf("%d ",a[i][j]); } printf("\n"); } return 0;}