要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。
Input
数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。
Sample Input
2
1000 53
87 123456789
Sample Output
7922
6060
百度到的模运算的性质:
(a+b) % c==(a % c + b % c) %c ,
(a-b) % c==(a % c - b % c) % c,
(a*b) % c==(a % c * b % c) % c。
分析：
能够运用欧几里德算法解出gcd(a,b)=ax1+by1中的x1、y1的值
n=A%9973，则n=A-A/99739973。
又A/B=x。则A=Bx。
所以Bx-A/99739973=n。即Bx-9973y=n。
到这里我们能够发现：仅仅要求出x的值，就可以算出x%9973。也就是(A/B)%9973了。
#include<iostream>
using namespace std;
int main()
{
int i, b, n, t;
cin>>t;
while (t--)
{
cin>> n>> b;
for (i = 0;i < 9973;i++)
if ((((b % 9973)*i) % 9973 - n) % 9973 == 0)
{
break;
}
cout<<i;
}
return 0;
}
定义一个二维数组：
image.png
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
一个5 × 5的二维数组，用BFS。从左上角（0, 0）位置开始，上下左右进行搜索，可以定义一个方向数组，代表上下左右四个方向，使用方向数组，可以使一个点上下左右移动。用来表示从左上角到右下角的最短路径中每个元素的前一个元素的下标，即保存路径，方便后面的输出。
通过广度搜索借助队列进行操作，我们可以把已走过的路标记为1，这样能保证路径最短，直到搜索到右下角（4, 4），输出路径即可。
#include <queue>
#include <iostream>
using namespace std;
int maze[7][7], pre[30], vis[30];
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
bool isLeagal(int r, int c)
{
if (r < 0 || c < 0 || r > 4 || c > 4)
return false;
if (maze[r][c] == 1)
return false;
return true;
}
void print(int des)
{
if (pre[des] != -1)
print(pre[des]);
cout << '(' << des / 5 << ", " << des % 5 << ')' << endl;
}
void bfs()
{
queue<int> que;
memset(vis, 0, sizeof(vis));
pre[0] = -1;
vis[0] = true;
que.push(0);
int now, next;
int r, c, tr, tc;
while (!que.empty())
{
now = que.front();
que.pop();
r = now / 5;
c = now % 5;
for (int i = 0; i < 4; i++)
{
tr = r + dir[i][0];
tc = c + dir[i][1];
next = tr * 5 + tc;
if (isLeagal(tr, tc) && !vis[next])
{
pre[next] = now;
if (next == 24) return;
vis[next] = true;
que.push(next);
}
}
}
}
int main()
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
cin >> maze[i][j];
bfs();
print(24);
return 0;
}
Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.
We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.
image.png
Input
The input consists of several test cases. The first line of each case contains two integers n (1 ≤ n ≤ 1000)
and d, where n is the number of islands in the sea and d is the distance of coverage of the radar
installation. This is followed by n lines each containing two integers representing the coordinate of the
position of each island. Then a blank line follows to separate the cases.
The input is terminated by a line containing pair of zeros.
Output
For each test case output one line consisting of the test case number followed by the minimal number
of radar installations needed. ‘-1’ installation means no solution for that case.
Sample Input
3 2
1 2
-3 1
2 1
1 2
0 2
0 0
Sample Output
Case 1: 2
Case 2: 1
输入岛屿的数量坐标还有雷达的探测范围，求至少需要多少个雷达。
如果覆盖不到，就输出-1.用贪心算法求最优解。
将岛屿的坐标存储在结构体中，将岛屿按距离顺序排列，一个一个取出，是否能同时存在一个圆中，如果不能则需要一个新的雷达......
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{
int x;
int y;
}land[1001];
bool cmp(node a, node b)
{
if (a.x != b.x)
return a.x < b.x;
return a.y > b.y;
}
int main()
{
ios::sync_with_stdio(false);
int n;
int maxy;
long long d;
int cas = 1;
while (cin >> n >> d)
{
maxy = 0;
if (n == 0 && d == 0)
break;
bool suc = true;
for (int i = 0;i < n;i++)
{
cin >> land[i].x >> land[i].y;
maxy = max(maxy, land[i].y);
}
sort(land, land + n, cmp);
int cnt = 1;
int i = 1;
if (maxy > d)
{
cout << "Case " << cas++ << ": " << -1 << endl;
continue;
}
double r = land[0].x + sqrt(d*d - land[0].y*land[0].y);
while (i < n)
{
double rr = land[i].x + sqrt(d*d - land[i].y*land[i].y);
if (rr < r)
{
r = rr;
i++;
continue;
}
if (sqrt((land[i].x - r)*(land[i].x - r) + land[i].y*land[i].y) > d)
{
cnt++;
r = rr;
}
i++;
}
cout << "Case " << cas++ << ": " << cnt << endl;
}
return 0;
}
Joe works in a maze. Unfortunately, portions of the maze have
caught on fire, and the owner of the maze neglected to create a fire
escape plan. Help Joe escape the maze.
Given Joe’s location in the maze and which squares of the maze
are on fire, you must determine whether Joe can exit the maze before
the fire reaches him, and how fast he can do it.
Joe and the fire each move one square per minute, vertically or
horizontally (not diagonally). The fire spreads all four directions
from each square that is on fire. Joe may exit the maze from any
square that borders the edge of the maze. Neither Joe nor the fire
may enter a square that is occupied by a wall.
Input
The first line of input contains a single integer, the number of test
cases to follow. The first line of each test case contains the two
integers R and C, separated by spaces, with 1 ≤ R, C ≤ 1000. The
following R lines of the test case each contain one row of the maze. Each of these lines contains exactly
C characters, and each of these characters is one of:
• #, a wall
• ., a passable square
• J, Joe’s initial position in the maze, which is a passable square
• F, a square that is on fire
There will be exactly one J in each test case.
Output
For each test case, output a single line containing ‘IMPOSSIBLE’ if Joe cannot exit the maze before the
fire reaches him, or an integer giving the earliest time Joe can safely exit the maze, in minutes.
image.png
Joe被困在着火的迷宫里，火势随着时间蔓延，问Joe是否能够安全到达迷宫边界
坑点：可以有多个起火点，Joe只有一个出发点。
用两遍BFS，一次记录每个时间的火势，一次搜索Joe的可行路线。还没完全弄懂，跟不上大佬们的操作。
#include <iostream>
#include <queue>
#include <memory.h>
#include <stdio.h>
#define MAX 1100
using namespace std;
struct P//用来存储路径的节点
{
int r, c;
int step;
P(int _r, int _c, int _s)
{
r = _r, c = _c, step = _s;
}
P() {}
};
const int dr[] = { 0,0,1,-1 };
const int dc[] = { 1,-1,0,0 };
char Map[MAX][MAX];//存储地图
int visit[MAX][MAX];//BFS中的visit数组
int times[MAX][MAX];//记录每个地方被烧到所需的时间
int r, c;//行，列
int Step;//记录最终逃脱所需的步数或时间
P J;
queue<P> q;
void clear_q()//清除队列中的数据
{
while (!q.empty())
q.pop();
}
void show_time()
{
for (int i = 0;i < r;i++)
{
for (int j = 0;j < c;j++)
{
cout << times[i][j] << ' ';
}
cout << endl;
}
}
void bfs_fire()
{
int i;
int R, C, Time;
while (!q.empty())
{
P temp = q.front();
q.pop();
for (i = 0;i < 4;i++)
{
R = temp.r + dr[i];
C = temp.c + dc[i];
Time = temp.step + 1;
if (R >= 0 && R < r&&C >= 0 && C < c && (Map[R][C] == '.' || Map[R][C] == 'J') && visit[R][C] == 0)
{
visit[R][C] = 1;
q.push(P(R, C, Time));
times[R][C] = Time;
}
}
}
}
int bfs_joe()
{
int i;
int R, C, Time;
clear_q();
q.push(J);
visit[J.r][J.c] = 1;
while (!q.empty())
{
P temp = q.front();
q.pop();
if (temp.r == 0 || temp.r == (r - 1) || temp.c == 0 || temp.c == (c - 1))
{
Step = temp.step + 1;
return 1;
}
for (i = 0;i < 4;i++)
{
R = temp.r + dr[i];
C = temp.c + dc[i];
Time = temp.step + 1;
if (R >= 0 && R < r&&C >= 0 && C < c&&Map[R][C] == '.'&&visit[R][C] == 0 && Time < times[R][C])
{
visit[R][C] = 1;
q.push(P(R, C, Time));
}
}
}
return 0;
}
int main()
{
int i, j;
int t;
cin >> t;
while (t--)
{
clear_q();
cin >> r >> c;
for (i = 0;i < r;i++)
{
cin >> Map[i];
for (j = 0;j < c;j++)
{
if (Map[i][j] == 'F')
{
q.push(P(i, j, 0));
times[i][j] = 0;
visit[i][j] = 1;
}
if (Map[i][j] == 'J')
{
J.r = i;
J.c = j;
J.step = 0;
}
}
}
for (i = 0;i < r;i++)
{
for (j = 0;j < c;j++)
{
times[i][j] = 1000000007;
}
}
memset(visit, 0, sizeof(visit));
bfs_fire();
memset(visit, 0, sizeof(visit));
if (bfs_joe())
cout << Step << endl;
else
cout << "IMPOSSIBLE" << endl;
}
return 0;
}
网友评论