国家企业信用信息查询系统官网/seo主要做什么工作
P1135 奇怪的电梯
奇怪的电梯
题目描述
呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 iii 层楼(1≤i≤N1 \le i \le N1≤i≤N)上有一个数字 KiK_iKi(0≤Ki≤N0 \le K_i \le N0≤Ki≤N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如: 3,3,1,2,53, 3, 1, 2, 53,3,1,2,5 代表了 KiK_iKi(K1=3K_1=3K1=3,K2=3K_2=3K2=3,……),从 111 楼开始。在 111 楼,按“上”可以到 444 楼,按“下”是不起作用的,因为没有 −2-2−2 楼。那么,从 AAA 楼到 BBB 楼至少要按几次按钮呢?
输入格式
共二行。
第一行为三个用空格隔开的正整数,表示 N,A,BN, A, BN,A,B(1≤N≤2001 \le N \le 2001≤N≤200,1≤A,B≤N1 \le A, B \le N1≤A,B≤N)。
第二行为 NNN 个用空格隔开的非负整数,表示 KiK_iKi。
输出格式
一行,即最少按键次数,若无法到达,则输出 -1
。
样例 #1
样例输入 #1
5 1 5
3 3 1 2 5
样例输出 #1
3
提示
对于 100%100 \%100% 的数据,1≤N≤2001 \le N \le 2001≤N≤200,1≤A,B≤N1 \le A, B \le N1≤A,B≤N,0≤Ki≤N0 \le K_i \le N0≤Ki≤N。
// https://www.luogu.com.cn/problem/P1135
#include<bits/stdc++.h>
using namespace std;const int INF=0x3f3f3f3f;
const int N=222;
int in[N];
int anscnt[N];struct A{ int now,cnt; };
int n,a,b;void bfs()
{queue<A> q;q.push( (A){ a,0 } );anscnt[a]=0; // initwhile( !q.empty() ){int now=q.front().now;int cnt=q.front().cnt;q.pop();if( now==b ) return ;int tnow1=now-in[now];if( tnow1>=1 && cnt+1<anscnt[tnow1] ){anscnt[tnow1]=cnt+1;q.push( (A){ tnow1,cnt+1 } );} int tnow2=now+in[now];if( tnow2<=n && cnt+1<anscnt[tnow2] ){anscnt[tnow2]=cnt+1;q.push( (A){ tnow2,cnt+1 } );}}
}int main()
{int i;scanf("%d%d%d",&n,&a,&b );for( i=1;i<=n;i++ )scanf("%d",&in[i] );memset( anscnt,0x3f,sizeof( anscnt ) );bfs();// int != cosnt int -> 不能用三目运算符if( anscnt[b]==INF ) printf("-1\n");else printf("%d\n",anscnt[b] ); return 0;
}
// 一行,即最少按键次数,若无法到达,则输出 -1。
P1141 01迷宫
01迷宫
题目描述
有一个仅由数字 000 与 111 组成的 n×nn \times nn×n 格迷宫。若你位于一格 000 上,那么你可以移动到相邻 444 格中的某一格 111 上,同样若你位于一格 111 上,那么你可以移动到相邻 444 格中的某一格 000 上。
你的任务是:对于给定的迷宫,询问从某一格开始能移动到多少个格子(包含自身)。
输入格式
有一个仅由数字 000 与 111 组成的 n×nn \times nn×n 格迷宫。若你位于一格 000 上,那么你可以移动到相邻 444 格中的某一格 111 上,同样若你位于一格 111 上,那么你可以移动到相邻 444 格中的某一格 000 上。
你的任务是:对于给定的迷宫,询问从某一格开始能移动到多少个格子(包含自身)。
输出格式
mmm 行,对于每个询问输出相应答案。
样例 #1
样例输入 #1
2 2
01
10
1 1
2 2
样例输出 #1
4
4
提示
所有格子互相可达。
对于 20%20\%20% 的数据,n≤10n \leq 10n≤10;
对于 40%40\%40% 的数据,n≤50n \leq 50n≤50;
对于 50%50\%50% 的数据,m≤5m \leq 5m≤5;
对于 60%60\%60% 的数据,n,m≤100n,m \leq 100n,m≤100;
对于 100%100\%100% 的数据,n≤1000,m≤100000n \leq 1000,m \leq 100000n≤1000,m≤100000。
// https://www.luogu.com.cn/problem/P1141
#include<bits/stdc++.h>
using namespace std;const int dx[]={ 0,0,0,1,-1 };
const int dy[]={ 0,1,-1,0,0 };
const int N=1111;
char g[N][N];
bool used[N][N];
int a[N][N];
int b[N*N]; // 连通块极限值: 任意两点之间都是单独成块
int cnt;
int n,m;struct A{ int x,y; };inline bool f( int x,int y )
{return x>=1 && x<=n && y>=1 && y<=n ;
}void bfs( int stx,int sty )
{queue<A> q;q.push( (A){ stx,sty } );used[stx][sty]=1;while( !q.empty() ){int x=q.front().x;int y=q.front().y;q.pop();a[x][y]=cnt;b[cnt]++; // 利用映射关系 记录连通块大小for( int i=1;i<=4;i++ ){int tx=x+dx[i];int ty=y+dy[i];if( f( tx,ty ) && used[tx][ty]==0 && g[x][y]+g[tx][ty]=='0'+'1' ){used[tx][ty]=1; // 先打上标记 避免同一个点多次进入队列q.push( (A){ tx,ty } );}}}
}int main()
{int i,j;scanf("%d%d",&n,&m );for( i=1;i<=n;i++ )for( j=1;j<=n;j++ )cin>>g[i][j];for( i=1;i<=n;i++ )for( j=1;j<=n;j++ ){if( used[i][j]==0 ){++cnt;bfs( i,j );}}while( m-- ){scanf("%d%d",&i,&j );printf("%d\n",b[a[i][j]] );}return 0;
}
P1746 离开中山路
离开中山路
题目背景
《爱与愁的故事第三弹·shopping》最终章。
题目描述
爱与愁大神买完东西后,打算坐车离开中山路。现在爱与愁大神在 x1,y1x_1,y_1x1,y1 处,车站在 x2,y2x_2,y_2x2,y2 处。现在给出一个 n×n(n≤1000)n \times n(n \le 1000)n×n(n≤1000) 的地图,000 表示马路,111 表示店铺(不能从店铺穿过),爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间,他要求最短到达目的地距离(每两个相邻坐标间距离为 111)。你能帮他解决吗?
输入格式
第 111 行包含一个数 nnn。
第 222 行到第 n+1n+1n+1 行:整个地图描述(000 表示马路,111 表示店铺,注意两个数之间没有空格)。
第 n+2n+2n+2 行:四个数 x1,y1,x2,y2x_1,y_1,x_2,y_2x1,y1,x2,y2。
输出格式
只有 111 行,即最短到达目的地距离。
样例 #1
样例输入 #1
3
001
101
100
1 1 3 3
样例输出 #1
4
提示
对于 20%20\%20% 数据,满足 1≤n≤1001\leq n \le 1001≤n≤100。
对于 100%100\%100% 数据,满足 1≤n≤10001\leq n \le 10001≤n≤1000。
// https://www.luogu.com.cn/problem/P1746
#include<bits/stdc++.h>
using namespace std;const int dx[]={ 0,1,-1,0,0 };
const int dy[]={ 0,0,0,1,-1 };
const int INF=0x3f3f3f3f;
const int N=1111;
char g[N][N];
int anscnt[N][N];
struct A{ int x,y,cnt; };
int n,stx,sty,edx,edy;bool f( int x,int y ) // 1 表示店铺(不能从店铺穿过)
{return x>=1 && x<=n && y>=1 && y<=n && g[x][y]=='0' ;
}void bfs()
{queue<A> q;q.push( (A){ stx,sty } );anscnt[stx][sty]=0;while( !q.empty() ){int x=q.front().x;int y=q.front().y;int cnt=q.front().cnt;q.pop();for( int i=1;i<=4;i++ ){int tx=x+dx[i];int ty=y+dy[i];if( f( tx,ty ) && cnt+1<anscnt[tx][ty] ){anscnt[tx][ty]=cnt+1;q.push( (A){ tx,ty,cnt+1 } );}}}
}int main()
{int i,j;scanf("%d",&n );for( i=1;i<=n;i++ )for( j=1;j<=n;j++ )cin>>g[i][j];scanf("%d%d%d%d",&stx,&sty,&edx,&edy );memset( anscnt,0x3f,sizeof( anscnt ) );bfs();printf("%d\n",anscnt[edx][edy] );return 0;
}
P1747 好奇怪的游戏
好奇怪的游戏
题目背景
《爱与愁的故事第三弹·shopping》娱乐章。
调调口味来道水题。
题目描述
爱与愁大神坐在公交车上无聊,于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘:***(游戏名被打上了马赛克)。这个游戏类似象棋,但是只有黑白马各一匹,在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是:马可以走“日”,也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数,你能帮他解决这个问题么?
输入格式
第1行:两个整数x1,y1
第2行:两个整数x2,y2
输出格式
第1行:黑马到1,1的步数
第2行:白马到1,1的步数
样例 #1
样例输入 #1
12 16
18 10
样例输出 #1
8
9
提示
100%数据:x1,y1,x2,y2<=20
// https://www.luogu.com.cn/problem/P1747
#include<bits/stdc++.h>
using namespace std;const int dx[]={ 0,2,-2,2,-2, 1,-1,1,-1,2,-2,2,-2 };
const int dy[]={ 0,2,2,-2,-2, 2,-2,-2,2,1,-1,-1,1 };
const int INF=0x3f3f3f3f;
const int N=25;
int anscnt[N][N];
struct A{ int x,y,cnt; };bool f( int x,int y ) // 不好规定范围 但可以证明下述范围一定存在最优解
{return x>=1 && x<=22 && y>=1 && y<=22 ;
}void bfs( int stx,int sty )
{queue<A> q;q.push( (A){ stx,sty,0 } );anscnt[stx][sty]=0;while( !q.empty() ){int x=q.front().x;int y=q.front().y;int cnt=q.front().cnt;q.pop();for( int i=1;i<=12;i++ ){int tx=x+dx[i];int ty=y+dy[i];if( f( tx,ty ) && cnt+1<anscnt[tx][ty] ){anscnt[tx][ty]=cnt+1;q.push( (A){ tx,ty,cnt+1 } );}}}
}int main()
{int x,y;memset( anscnt,0x3f,sizeof( anscnt ) ); scanf("%d%d",&x,&y ); bfs( x,y ); printf("%d\n",anscnt[1][1] );memset( anscnt,0x3f,sizeof( anscnt ) ); scanf("%d%d",&x,&y ); bfs( x,y ); printf("%d\n",anscnt[1][1] );return 0;
}
P1902 刺杀大使
刺杀大使
题目描述
某组织正在策划一起对某大使的刺杀行动。他们来到了使馆,准备完成此次刺杀,要进入使馆首先必须通过使馆前的防御迷阵。
迷阵由 n×mn\times mn×m 个相同的小房间组成,每个房间与相邻四个房间之间有门可通行。在第 nnn 行的 mmm 个房间里有 mmm 个机关,这些机关必须全部打开才可以进入大使馆。而第 111 行的 mmm 个房间有 mmm 扇向外打开的门,是迷阵的入口。除了第 111 行和第 nnn 行的房间外,每个房间都被使馆的安保人员安装了激光杀伤装置,将会对进入房间的人造成一定的伤害。第 iii 行第 jjj 列 造成的伤害值为 pi,jp_{i,j}pi,j(第 111 行和第 nnn 行的 ppp 值全部为 000)。
现在某组织打算以最小伤害代价进入迷阵,打开全部机关,显然,他们可以选 择任意多的人从任意的门进入,但必须到达第 nnn 行的每个房间。一个士兵受到的伤害值为他到达某个机关的路径上所有房间的伤害值中的最大值,整个部队受到的伤害值为所有士兵的伤害值中的最大值。现在,这个恐怖组织掌握了迷阵的情况,他们需要提前知道怎么安排士兵的行进路线可以使得整个部队的伤害值最小。
输入格式
第一行有两个整数 n,mn,mn,m,表示迷阵的大小。
接下来 nnn 行,每行 mmm 个数,第 iii 行第 jjj 列的数表示 pi,jp_{i,j}pi,j。
输出格式
输出一个数,表示最小伤害代价。
样例 #1
样例输入 #1
4 2
0 0
3 5
2 4
0 0
样例输出 #1
3
提示
- 50%50\%50% 的数据,n,m≤100n,m \leq 100n,m≤100;
- 100%100\%100% 的数据,n,m≤1000n,m \leq 1000n,m≤1000,pi,j≤1000p_{i,j} \leq 1000pi,j≤1000。
// https://www.luogu.com.cn/problem/P1902
#include<bits/stdc++.h>
using namespace std;const int dx[]={ 0,1,-1,0,0 };
const int dy[]={ 0,0,0,1,-1 };
const int N=1111;
int g[N][N];
bool used[N][N];
int n,m;
struct A{ int x,y; };bool f( int x,int y )
{return x>=1 && x<=n && y>=1 && y<=m && used[x][y]==0 ;
}bool bfs( int maxx )
{queue<A> q;for( int i=1;i<=m;i++ ){q.push( (A){ 1,i } );used[1][i]=1;}while( !q.empty() ){int x=q.front().x;int y=q.front().y;q.pop();if( x==n ) return 1;for( int i=1;i<=4;i++ ){int tx=x+dx[i];int ty=y+dy[i];if( f( tx,ty ) && g[tx][ty]<=maxx ){used[tx][ty]=1;q.push( (A){ tx,ty } );}}}return 0;
}int main()
{int i,j,x,y,mid;scanf("%d%d",&n,&m );for( i=1;i<=n;i++ )for( j=1;j<=m;j++ )scanf("%d",&g[i][j] );x=0,y=1000;while( x<y ){memset( used,0,sizeof( used ) );mid=( x+y )>>1; // 最小化模板 if( bfs(mid) ) y=mid; // 求最大值else x=mid+1;}printf("%d\n",x );return 0;
}
// 越大越满足要求 -> 求最大值 -> 最小化模板