A.Vanishing Pitch—签到

题意：有一个棒球在 [t,s] 时间内是隐身的，飞行速度为 v，一个人在距离发球点为 d 的距离准备接球，问这个人能否在接到棒球（即球可以被看到）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int v, t, s, d;
    while (cin >> v >> t >> s >> d) {
        if (v * t <= d && s * v >= d)
            cout << "No" << endl;
        else
            cout << "Yes" << endl;
    }
    // system("pause");
    return 0;
}

B.Remove It—签到

题意：将给出的长度为 n 的数列中等于 x 的数不输出，其余的数输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, x;
    while (cin >> n >> x) {
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            int num;
            cin >> num;
            if (num != x) ans.push_back(num);
        }
        for (auto e : ans)
            cout << e << ' ';
        cout << endl;
    }
    // system("pause");
    return 0;
}

C.Digital Graffiti—DFS

题意：在 n*m 的棋白块盘中有唯一一个由多个黑块形成的实心黑色多边形且保证这个多边形不碰棋盘的边缘部分，请判断这个多边形的边数

思路：易知 n 边形存在 n 个角，所以搜索棋盘中有多少个角即可。方法是判断一个田字形的四个方块是否含有 1 个或者 3 个黑块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 15;

string mz[maxn];
int dir[][2] = {{0, 0}, {1, 0}, {0, 1}, {1, 1}};

bool check(int x, int y) {
    int temp = 0;
    for (int i = 0; i < 4; ++i) {
        int xx = x + dir[i][0], yy = y + dir[i][1];
        if (mz[xx][yy] == '.') ++temp;
    }
    if (temp == 1 || temp == 3) return true;
    return false;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int h, w;
    while (cin >> h >> w) {
        for (int i = 1; i <= h; ++i) {
            for (int j = 1; j <= w; ++j)
                cin >> mz[i][j];
        }
        int cnt = 0;
        for (int i = 1; i < h; ++i) {
            for (int j = 1; j < w; ++j) {
                if (check(i, j))
                    ++cnt;
            }
        }
        cout << cnt << endl;
    }
    // system("pause");
    return 0;
}

D.Circle Lattice Points—模拟+高精度

题意：给定一个圆心和半径，判断圆内以及圆上存在多少个整数

思路：枚举一维 y 然后根据毕达哥拉斯定理找到与圆两个交点 x 的左边坐标，已知同一垂直方向上两个交点的横坐标了就可以计算出中间的整数点个数了。这题坑点在于浮点的错误，因为题目给定的范围是 1e5 并且是浮点数就可能出现圆心为 (-0.0001,0)，半径为 1e5 的圆，此时计算涉及 (1e5)2 - (10-4)2 超过了 long double 的范围。解决的简单方法就是将给出的半径扩大一下加个 1e-14 这样就保证了圆上的点即使出现浮点误差也可以被包含在圆内了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
    long double x, y, r;
    while (cin >> x >> y >> r) {
        ll ans = 0;
        r += 1e-14;
        for (ll i = ceil(y - r); i <= floor(y + r); ++i) {
            long double dx = sqrt(r * r - (y - i) * (y - i));
            long double left = x - dx, right = x + dx;
            ans += floor(right) - ceil(left) + 1;
        }
        cout << ans << endl;
    }
    // system("pause");
    return 0;
}

E.Come Back Quickly—最小正权环路问题

题意：题目给出一个由 n 个点 m 条有向边组成的图，请计算每个点所在的最小正权环路

思路：方法就是将起点不放入队列，并将其相邻的点加入队列并更新长度为边长。然后在跑最短路就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> P;  //用 P代替 pair<int,int>
const int V = 2005;
const int E = 2005;

int dis[V], head[V];
bool vis[V];
struct node {
    int nex, to, w;
} edge[E];

int cnt;  //寄存指针

void init() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}

inline void add(int u, int v, int w) {  //内联函数加快速度
    cnt++;
    edge[cnt].nex = head[u];
    head[u] = cnt;
    edge[cnt].to = v;
    edge[cnt].w = w;
}

void dij(int start) {
    //初始化放在init()里也可以
    memset(vis, 0, sizeof(vis));
    memset(dis, inf, sizeof(dis));

    //定义优先队列存 pair，小顶堆，注意最后两个尖括号间必须有空格。
    priority_queue<P, vector<P>, greater<P> > que;
    //pair第一个元素存的是dis[i]，第二个元素存的是i，也就是可达的节点;
    //pair比较大小是先比较first，也就是比较dis，符合dij算法要求。
    for (int i = head[start]; i != -1; i = edge[i].nex)
        dis[edge[i].to] = min(dis[edge[i].to], edge[i].w), que.push(P(edge[i].w, edge[i].to));
    while (!que.empty()) {
        //取出堆顶元素
        P p = que.top();  //拿出队首元素
        que.pop();
        int v = p.second;
        if (dis[v] < p.first) continue;
        //遍历v能到的所有点
        for (int i = head[v]; i != -1; i = edge[i].nex) {
            node e = edge[i];

            //如果可以松弛，直接更新。
            if (e.w + dis[v] < dis[e.to]) {
                dis[e.to] = e.w + dis[v];
                que.push(P(dis[e.to], e.to));
            }
        }
    }
}

signed main() {
    int n, m;
    cin >> n >> m;
    init();
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
    }
    for (int i = 1; i <= n; ++i) {
        dij(i);
        cout << (dis[i] == inf ? -1 : dis[i]) << endl;
    }
    // system("pause");
    return 0;
}