1001 内蒙创业

内蒙创业
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 52 Accepted Submission(s) : 23
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
莱特与瑞秋毕业了，他们决定在内蒙创业成立一家畜牧业公司，创业第一步：他们希望给公司里的每一只羊一个编号。
编号的命名规则如下：
1.长度为10位；
2.前两位必须为”LQ”；
3.后八位必须为数字；
现在有若干个字符串，希望你写一个程序判断它是不是一个合法编号。
Input
第一行一个T(1≤T≤20)代表数据组数。
每组测试数据有一个字符串s(1≤|s|≤20)，s只包含数字和大写英文字母，代表等待判断的字符串。
Output
如果编号合法输出”YES”，否则输出”NO”。
Sample Input
3
LQ12345678
LQ123
QL12345678
Sample Output
YES
NO
NO

#include<bits/stdc++.h>
using namespace std;
int main(){
    
	int T;  cin>>T;
	while(T--){
    
		string s;  cin>>s;
		if(s.size()==10 &&s.substr(0,2)=="LQ"){
    
			int ok = 1;
			for(int i = 2; i < s.size(); i++)
				if(!isdigit(s[i]))ok = 0;
			if(ok==1)cout<<"YES\n";
			else cout<<"NO\n";
		}else {
    
			cout<<"NO\n";
		}
	}
	return 0;
}

1002 挑战棋王丁爸

挑战棋王丁爸
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 24 Accepted Submission(s) : 13
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
一丁三年级的时候学会了跳棋，但一直到现在都没能赢过丁爸（毕竟是棋王~）。

刚好，一丁最近学会了bfs，就打算写一个小程序帮助自己打破零胜的记录。

在一个n*m的矩形棋盘上，一丁想要走动的棋子的坐标是x1,y1,想要棋子到达的坐标是x2,y2。棋子只能往上下左右四个方向走，如果棋子某一方向上相邻的位置没有别的棋子，那就可以直接走一步到达相邻位置，并且走的次数加一，如果走的方向上相邻位置有别的棋子，那也可以直接跳过去，但是只能跳过一个棋子，也就是相当于往一个方向走了两步，并且走的次数还是加一，不过这种情况必须要保证棋子跳到的位置没有别的棋子。

在已知棋盘信息和想要移动的棋子的起点坐标和终点坐标后，一丁希望输出最少走的次数，如果不能走到终点，则输出-1。
Input
题目有多组输入。

每组数据第一行是两个整数n（1<=n<=10）和m(1<=m<=10)，分别表示矩形棋盘的行数和列数。

接下来一共有n行，每行m个字符。只包含‘.’和‘’两种字符。其中，‘.’表示这个位置没有棋子，‘’表示这个位置有棋子。

最后还有一行包含四个正整数x1,y1,x2,y2,分别表示棋子起点的行列坐标和棋子最后想要到达的行列坐标。

题目保证1<=x1,x2<=n, 1<=y1,y2<=m，并且（x1，y1）位置上肯定是‘*’，（x2,y2）上肯定是‘.’。
Output
输出棋子从（x1,y1）到（x2,y2）的最小步数，如果不能到达则输出-1。
Sample Input
3 3
…
..
…
1 1 3 3

3 3
.
…*
**.
1 1 3 3
Sample Output
3
-1

#include<bits/stdc++.h>
using namespace std;
char a[20][20];
int d[20][20];
int dx[4] = {
    1,-1,0,0};
int dy[4] = {
    0,0,-1,1};
int main(){
    
	int n, m; 
	while(cin>>n>>m &&n&&m){
    
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				cin>>a[i][j];
		int sx, sy, ex, ey;
		cin>>sx>>sy>>ex>>ey;
		
		memset(d,-1,sizeof(d));;
		d[sx][sy] = 0;
		queue<pair<int,int> >q;
		q.push(make_pair(sx,sy));
		while(q.size()){
    
			int x = q.front().first, y = q.front().second;
			q.pop();
			for(int i = 0; i < 4; i++){
    
				int nx = x+dx[i], ny = y+dy[i];
				if(nx>=1&&nx<=n && ny>=1&&ny<=m &&a[nx][ny]=='.' && d[nx][ny]==-1){
    
					d[nx][ny] = d[x][y]+1;
					q.push(make_pair(nx,ny));
				}else if(nx>=1&&nx<=n && ny>=1&&ny<=m &&a[nx][ny]=='*' && d[nx][ny]==-1){
    
					nx = nx+dx[i]; ny = ny+dy[i];
					if(nx>=1&&nx<=n && ny>=1&&ny<=m &&a[nx][ny]=='.' && d[nx][ny]==-1){
    
						d[nx][ny] = d[x][y]+1;
						q.push(make_pair(nx,ny));
					}
				}
			}
		}
		cout<<d[ex][ey]<<"\n";
	}
	return 0;
}

1003 条条大路通罗马

条条大路通罗马
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 46 Accepted Submission(s) : 11
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
给定一张通往罗马的地图，地图由0，1组成，1代表罗马的盟国，可走，0代表敌国，不可走（会被当成奸细抓起来）。小明现在被随机传送到了一个国家（x1,y1），他想到罗马(x2,y2)，要求每次只能向右或向下到一个国家，求问从起点到罗马有多少种不同的方案。（数据保证x1<=x2,y1<=y2）
Input
有多组测试数据
每组测试数据第一行两个整数n,m代表地图边界
接下来n行，每行m个数字
接下来一行四个整数代表x1,y1,x2,y2
(1<=n,m<=10,1<=x1,x2<=n,1<=y1,y2<=m)
Output
每组数据一行，代表有多少种不同的方案
Sample Input
4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 2 2
Sample Output
2
Author
shenjx
Source
dbfs

#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[20][20], vis[20][20];
int sx, sy, ex, ey;

int ans;
int dx[2] = {
    1,0};
int dy[2] = {
    0,1};
void dfs(int x, int y){
    
	if(x==ex&&y==ey){
    ans++; return ;}
	if(x<1||x>n || y<1||y>m || a[x][y]==0)return ;
	for(int i = 0; i < 2; i++){
    
		int nx=x+dx[i], ny=y+dy[i];
		if(!vis[nx][ny]){
    
			vis[nx][ny] = 1;
			dfs(nx,ny);
			vis[nx][ny] = 0;
		}
	}
}

int main(){
    
	while(cin>>n>>m &&n&&m){
    
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++)
				cin>>a[i][j];
		cin>>sx>>sy>>ex>>ey;
		
		ans = 0;
		memset(vis,0,sizeof(vis));;
		dfs(sx,sy);
		cout<<ans<<"\n";
	}
	return 0;
}

1004 争当图书管理员

争当图书管理员
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 33 Accepted Submission(s) : 11
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个正整数。
每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。
小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他需要的书，请输出-1。
Input
输入包含多组测试用例。
每组数据的第一行，包含两个正整数 n 和 q，以一个空格分开，分别代表图书馆里书的数量和读者的数量。
接下来的 n 行，每行包含一个正整数，代表图书馆里某本书的图书编码。
接下来的 q 行，每行包含两个正整数，以一个空格分开，第一个正整数代表图书馆里读者的需求码的长度，第二个正整数代表读者的需求码。

1 ≤ n ≤ 1,000，1 ≤ q ≤ 1,000，所有的图书编码和需求码均不超过 10,000,000。
Output
每组数据输出 q 行，每行包含一个整数，如果存在第 i 个读者所需要的书，则在第 i 行输出第 i 个读者所需要的书中图书编码最小的那本书的图书编码，否则输出-1。
Sample Input
5 5
2123
1123
23
24
24
2 23
3 123
3 124
2 12
2 12
Sample Output
23
1123
-1
-1
-1
Hint
第一位读者需要的书有 2123、1123、23，其中 23 是最小的图书编码。第二位读者需要的书有 2123、1123，其中 1123 是最小的图书编码。对于第三位，第四位和第五位读者，没有书的图书编码以他们的需求码结尾，即没有他们需要的书，输出-1。
Source
ACM程序设计竞赛实训（甲）- 期末测试

//nq<1e7, 可以暴力
#include<bits/stdc++.h>
using namespace std;
int a[1010];
int main(){
    
	ios::sync_with_stdio(false);
	int n, q;
	while(cin>>n>>q &&n&&q){
    
		for(int i = 1; i <= n; i++)
			cin>>a[i];
		sort(a+1,a+n+1);
		while(q--){
    
			int len, b;  cin>>len>>b;
			int t = pow(10,len), ok = 0;
			for(int i = 1; i <= n; i++){
    
				if((a[i]-b)%t==0){
    //匹配后缀
					ok = 1;
					cout<<a[i]<<"\n";
					break;
				}
			}
			if(ok==0)cout<<"-1\n";
		}
	}
	return 0;
}