要求(A/B)%9973，但由于A很大，我們只給出n(n=A%9973)(我們給定的A必能被B整除笑跛，且gcd(B,9973) = 1)熬甚。
Input
數(shù)據(jù)的第一行是一個T逢渔，表示有T組數(shù)據(jù)。
每組數(shù)據(jù)有兩個數(shù)n(0 <= n < 9973)和B(1 <= B <= 10^9)乡括。
Output
對應(yīng)每組數(shù)據(jù)輸出(A/B)%9973肃廓。
Sample Input
2
1000 53
87 123456789
Sample Output
7922
6060

百度到的模運算的性質(zhì):

                   (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葵第。
到這里我們能夠發(fā)現(xià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;
}

定義一個二維數(shù)組：

image.png

它表示一個迷宮缀台，其中的1表示墻壁，0表示可以走的路哮奇，只能橫著走或豎著走膛腐，不能斜著走，要求編程序找出從左上角到右下角的最短路線鼎俘。
Input
一個5 × 5的二維數(shù)組哲身，表示一個迷宮。數(shù)據(jù)保證有唯一解贸伐。
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的二維數(shù)組，用BFS误辑。從左上角（0, 0）位置開始沧踏，上下左右進行搜索，可以定義一個方向數(shù)組巾钉，代表上下左右四個方向翘狱，使用方向數(shù)組，可以使一個點上下左右移動砰苍。用來表示從左上角到右下角的最短路徑中每個元素的前一個元素的下標潦匈，即保存路徑，方便后面的輸出赚导。
通過廣度搜索借助隊列進行操作茬缩，我們可以把已走過的路標記為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.

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
輸入島嶼的數(shù)量坐標還有雷達的探測范圍圈暗，求至少需要多少個雷達掂为。
如果覆蓋不到，就輸出-1.用貪心算法求最優(yōu)解员串。
將島嶼的坐標存儲在結(jié)構(gòu)體中勇哗，將島嶼按距離順序排列，一個一個取出寸齐，是否能同時存在一個圓中欲诺，如果不能則需要一個新的雷達......

#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只有一個出發(fā)點。
用兩遍BFS海铆，一次記錄每個時間的火勢迹恐，一次搜索Joe的可行路線挣惰。還沒完全弄懂卧斟，跟不上大佬們的操作。

#include <iostream>
#include <queue>
#include <memory.h>
#include <stdio.h>
#define MAX 1100
using namespace std;
struct P//用來存儲路徑的節(jié)點
{
    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數(shù)組
int times[MAX][MAX];//記錄每個地方被燒到所需的時間
int r, c;//行憎茂，列
int Step;//記錄最終逃脫所需的步數(shù)或時間
P J;
queue<P> q;

void clear_q()//清除隊列中的數(shù)據(jù)
{
    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;
}