本文由zhc撰写
小测8 - 最短路径 实时评测
问题描述：
唐僧被妖怪关在迷宫中。孙悟空好不容易找到一张迷宫地图，并通过一个魔法门来到来到迷宫某个位置。假设迷宫是一个n * m的矩阵，它有两种地形，0表示平地，1表示沼泽，孙悟空只能停留在平地上。
孙悟空目前的位置在坐标(sx,sy)处，他可以向上下左右四个方向移动。
请你帮助孙悟空计算一下，迷宫中是否存在一条路从他所在位置(sx,sy)到达唐僧所在位置(tx,ty)，如果有，请计算出最短的一条路径。
输入描述：
每个测试样例的第1行是2个正整数n (1≤n≤100)，m (1≤m≤100)，表示迷宫是n * m的矩阵。接下来的n行输入迷宫，每行有m个数字（0或者1），数字之间用一个空格间隔。
接下来的1行是4个整数sx,sy,tx,ty，1≤sx,tx≤n，1≤sy,ty≤m，表示孙悟空所在位置为第sx行第sy列，唐僧所在位置为第tx行第tx列。迷宫左上角编号是(1,1)，右下角编号是(n, m)。
数据保证(sx,sy)格和(tx,ty)必定为平地，且孙悟空的初始位置(sx, sy)并不在唐僧所在格(tx, ty)。
输出描述：
输出孙悟空到达唐僧处所需经过的最短路径，如果不能到达，请输出“No”
输入样例1：
2 2
0 1
1 0
1 1 2 2
输出样例1：
No
输入样例2：
4 4
0 0 0 1
0 1 0 0
0 1 0 0
0 0 0 1
1 1 3 4
输出样例2：
5
#include <iostream>
#include<vector>
#include<cstring>
using namespace std;
int n,m;
int near[4][2]={0,1,0,-1,1,0,-1,0};
int d[101][101];
int best[101][101];
int vis[101][101];
void refresh(int x,int y){
for(int i=0;i<4;++i){
int x0=x+near[i][0];
int y0=y+near[i][1];
if(x0<1||x0>n||y0<1||y0>m) continue;
if(d[x0][y0]==1&&best[x0][y0]>(best[x][y]+d[x0][y0])){
best[x0][y0]=best[x][y]+d[x0][y0];
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
int t;
cin>>t;
d[i][j]=1-t;
best[i][j]=9999;
vis[i][j]=0;
}
}
int sx,sy,tx,ty;
cin>>sx>>sy>>tx>>ty;
if(sx==tx&&sy==ty){
cout<<0;
return 0;
}
best[sx][sy]=0;
vis[sx][sy]=1;
refresh(sx,sy);
while(true){
int min=9999;
int x,y;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(d[i][j]==1&&vis[i][j]==0&&min>best[i][j]){
min=best[i][j];
x=i;
y=j;
}
}
}
if(min==9999) break;
if(x==tx&&y==ty) break;
vis[x][y]=1;
refresh(x,y);
}
if(best[tx][ty]==9999) cout<<"No";
else cout<<best[tx][ty];
return 0;
}
小测9 - 简单哈希 实时评测
题目描述
使用线性探测法(Linear Probing)可以解决哈希中的冲突问题，其基本思想是：设哈希函数为h(key) = d, 并且假定哈希的存储结构是循环数组, 则当冲突发生时, 继续探测d+1, d+2…, 直到冲突得到解决.
例如, 现有关键码集为 {47，7，29，11，16，92，22，8，3}，设：哈希表表长为m=11；哈希函数为Hash(key)=key mod 11；采用线性探测法处理冲突。建哈希表如下：
现在给定哈希函数为Hash(key)= key mod m，要求按照上述规则, 使用线性探测法处理冲突.要求建立起相应哈希表，并按要求打印。
输入描述
仅有一个测试用例, 第1行为整数n与m（1 <= n, m <= 10000）， n代表key的总数, m代表哈希表的长度, 并且令哈希函数为: Hash(key) = key mod m.
接下来n行，每行一个整数，代表一个key。Key与key两两不相同 ( 0 <= key <= 10, 000)。
输出描述
输出建立好的hash表，比如下表
应输出
0#11
1#22
2#NULL
3#47
4#92
5#16
6#3
7#7
8#29
9#8
10#NULL
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int data[m];
for(int i=0;i<m;++i) data[i]=-1;
for(int i=0;i<n;++i){
int num;
cin>>num;
int key=num%m;
int k=0;
while(data[(key+k)%m] !=-1) ++k;
data[(key+k)%m]=num;
}
for(int i=0;i<m;++i){
cout<<i<<"#";
if(data[i]==-1) cout<<"NULL"<<endl;
else cout<<data[i]<<endl;
}
}小测10 - 简单字符串匹配
题目描述
给定两个字符串s1和s2，要求判定s2是否能够被s1做循环移位（rotate）得到的字符串包含。说明：字符串s1和s2中不包含空格，每个字符串至少包含一个字符。
例如：给定S1= AABCD，S2=CDAA，则返回True；给定s1=ABCD，S2=ACBD，则返回False
输入描述
第一行为整数n（n<2,000,0），第2到n+1行为n个输入数据，每行包括两个字符串，字符串s1和字符串s2。字符串的长度不超过100。
输出描述
针对每个例子，如果s2能够被s1做循环移位得到的字符串包含，输出True，否则输出False；每个输出结果为独立的一行。
输入样例
2
AABCD CDAA
ABCD ACBD
输出样例
True
False
#include<iostream>
using namespace std;
int main(){
int times;
cin>>times;
while(times-->0){
string s1,s2;
cin>>s1>>s2;
bool ok=false;
for(int i=0;i<s1.size();++i){
if(s1[i]==s2[0]){
ok=true;
int k1=i;
int k2=0;
while(k2<s2.size()){
if(s1[k1]!=s2[k2]){
ok=false;
break;
}
k1++;
k1=k1%(s1.size());
k2++;
}
if(ok) break;
}
}
if(ok) cout<<"True"<<endl;
else cout<<"False"<<endl;
}
return 0;
}小测11 - 畅通工程 实时评测
2022-01-19 18:08
1000 ms
32 MB
李正鸿 (lizhh98@mail2.sysu.edu.cn)
题目描述
某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
输入描述
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
输出描述
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
输入样例
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
输出描述
2
-1
#include<iostream>
#include<cstring>
using namespace std;
#define int_max 2000000//int_max
int N;
int best[200];
int vist[200];
int d[200][200];
void refresh(int x){
for(int i=0;i<N;++i){
if(d[x][i]!=-1&&best[i]>(best[x]+d[x][i]))
best[i]=best[x]+d[x][i];
}
}
int main(){
while(cin>>N){
int M;
cin>>M;
//memset(vist,0,sizeof(vist));
//memset(best,int_max,sizeof(best));
memset(d,-1,sizeof(d));
for(int i=0;i<N;++i){
d[i][i]=0;
vist[i]=0;
best[i]=int_max;
}
for(int i = 0; i <M ; ++i){
int x,y,t;
cin>>x>>y>>t;
if(x!=y&&(d[x][y]==-1||t<d[x][y])){
d[x][y]=t;
d[y][x]=t;
}
}
int start,end;
cin>>start>>end;
if(start==end){
cout<<0<<endl;
continue;
}
best[start]=0;
vist[start]=1;
refresh(start);
while(true){
int min=int_max;
int closest;
for(int i=0;i<N;++i){
if(vist[i]==0&&min>best[i]){
min=best[i];
closest=i;
}
}
if(min==int_max) break;
if(closest==end) break;
vist[closest]=1;
refresh(closest);
}
if(best[end]==int_max) cout<<-1<<endl;
else cout<<best[end]<<endl;
}
return 0;
}小测12 - 飞盘高手
题目描述
杰克是美国某小镇有名的飞盘高手。他掷飞盘的时候有一个习惯，在一叠飞盘中，从第一个飞盘（即位于顶端的飞盘）开始，从上往下依次编号为1～N。当至少还有两个飞盘的时候，杰克通常会掷出一个飞盘，然后把新的第一个飞盘放到所有飞盘的最后。输入N，输出每次扔掉的飞盘，以及最后剩下的飞盘。
输入描述
第一行为一个整数t（0<t<20），表示测试用例个数。以下t行每行包含一个整数n（0<n<40）,为一个测试用例的飞碟数。
输出描述
为每个测试用例单独输出一行，该行中依次输出每次掷出的飞盘编号以及最后剩下飞盘，每个飞盘后跟着一个空格。
输入样例
2
7
4
输出样例
1 3 5 7 4 2 6
1 3 2 4
#include<iostream>
#include<queue>
using namespace std;
int main(){
int t;
cin>>t;
while(t-->0){
int n;
cin>>n;
queue<int> Q;
for(int i = 1; i<=n;++i) Q.push(i);
for(int k=0;k<n;++k){
cout<<Q.front()<<" ";
Q.pop();
Q.push(Q.front());
Q.pop();
}
cout<<endl;
}
}