CCCC L3习题集

L3-001 凑零钱

题意：n 个硬币，要付 m 元，输出硬币面值$v_1\le v_2\le\cdots\le v_k$，输出满足条件$v_1+v_2+\cdots+v_k=m$的最小序列。

法一：dfs。法二：0-1 背包。

法一

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e4 + 5;

int n, m, sum, cnt, flag;
int a[N], ans[N];

void dfs(int pos, int sum) {
    if (sum > m) return;
    if (sum == m) {
        flag = 1;
        printf("%d", ans[1]);
        for (int i = 2; i <= cnt; ++i)
            printf(" %d", ans[i]);
        puts("");
        return;
    }
    for (int i = pos; i <= n; ++i) {
        ans[++cnt] = a[i];
        dfs(i + 1, sum + a[i]);
        if (flag) break;
        cnt--;
    }
}

int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    if (sum < m) puts("No Solution");
    else {
        sort(a + 1, a + n + 1);
        dfs(1, 0);
        if (!flag) puts("No Solution");
    }
    return 0;
}

法二

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e4 + 5;

int n, m;
int w[N], dp[N];
int vis[N][N];

bool cmp(int a, int b) { return a > b; }

int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &w[i]);
    }
    sort(w + 1, w + n + 1, cmp);
    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= w[i]; --j) {
            if (dp[j] <= dp[j-w[i]] + w[i]) {
                vis[i][j] = 1;
                dp[j] = dp[j-w[i]] + w[i];
            }
        }
    }
    if (dp[m] != m) puts("No Solution");
    else {
        vector<int> v;
        int t = m, id = n;
        while (t) {
            if (vis[id][t]) {
                v.push_back(w[id]);
                t -= w[id];
            }
            id--;
        }
        printf("%d", v[0]);
        for (int i = 1; i < (int)v.size(); ++i)
            printf(" %d", v[i]);
        puts("");
    }
    return 0;
}

L3-002 特殊堆栈

题目链接

题意：在实现栈的基础操作上，实现取中值操作。

法一：树状数组+二分求第 $\lceil\frac{n}{2}\rceil$ 小。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;

int m;
int c[N];
stack<int> s;

int lowbit(int x) { return x & -x; }

void add(int x, int val) {
    for (; x < N; x += lowbit(x))
        c[x] += val;
}

int sum(int x) {
    int res = 0;
    for (; x; x -= lowbit(x))
        res += c[x];
    return res;
}

void PeekMedian() {
    int l = 1, r = N, k = (s.size() + 1) / 2;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (sum(mid) >= k) {
            r = mid;
        }
        else l = mid + 1;
    }
    printf("%d\n", l);
}

int main() 
{
    scanf("%d", &m);
    char str[15];
    int x;
    while (m--) {
        scanf("%s", str);
        if (str[1] == 'u') {
            scanf("%d", &x);
            s.push(x);
            add(x, 1);
        }
        else if (str[1] == 'o') {
            if (!s.empty()) {
                add(s.top(), -1);
                printf("%d\n", s.top());
                s.pop();
            }
            else puts("Invalid");
        }
        else if (str[1] == 'e') {
            if (!s.empty()) {
                PeekMedian();
            }
            else puts("Invalid");
        }
    }
    return 0;
}

法二：c++ with stl。

 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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;

int m, top;
int sta[N];
vector<int> ord;

int main() 
{
    scanf("%d", &m);
    char str[15];
    while (m--) {
        scanf("%s", str);
        if (str[1] == 'u') {
            scanf("%d", &sta[++top]);
            ord.insert(lower_bound(ord.begin(), ord.end(), sta[top]), sta[top]);
        }
        else if (str[1] == 'o' && top) {
            ord.erase(lower_bound(ord.begin(), ord.end(), sta[top]));
            printf("%d\n", sta[top--]);
        }
        else if (str[1] == 'e' && top) {
            printf("%d\n", ord[(top - 1) / 2]);
        }
        else puts("Invalid");
    }
    return 0;
}

L3-003 社交集群

题目链接

题意：第 $i$ 个人有 $k_i$ 个兴趣爱好，拥有相同兴趣爱好的人在一个社交集群，求有多少个社交集群和每个集群的人数。

很水的并查集。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1005;

int n, k;
int p[N], a[N], fa[N];

int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

void unite(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) return;
    fa[fx] = fy;
}

int main() 
{
    scanf("%d", &n);
    int x;
    for (int i = 1; i <= 1001; ++i) fa[i] = i;
    for (int i = 1; i <= n; ++i) {
        scanf("%d: %d", &k, &x);
        p[i] = x;
        for (int j = 1; j < k; ++j) {
            scanf("%d", &x);
            unite(x, p[i]);
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        int hobby = find(p[i]);
        if (!a[hobby]) cnt++;
        a[hobby]++;
    }
    sort(a + 1, a + 1001, greater<int>());
    printf("%d\n%d", cnt, a[1]);
    for (int i = 2; i <= cnt; ++i) printf(" %d", a[i]);
    puts("");
    return 0;
}

L3-004 肿瘤诊断

题目链接

题意：求所有体积不小于 t 的连通块总体积。

三维 bfs 即可。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, M = 1300, N = 130, L = 65;

struct node {
    int x, y, z;
    node (int x, int y, int z) : x(x), y(y), z(z) {}
};

int m, n, l, t;
int a[M][N][L], vis[M][N][L];
int dx[] = {1, 0, -1, 0, 0, 0};
int dy[] = {0, 1, 0, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};

int bfs(int x, int y, int z) {
    queue<node> q;
    int cnt = 0;
    q.push(node(x, y, z));
    vis[x][y][z] = 1;
    while (!q.empty()) {
        node u = q.front();
        q.pop();
        cnt++;
        for (int i = 0; i < 6; ++i) {
            int tx = u.x + dx[i];
            int ty = u.y + dy[i];
            int tz = u.z + dz[i];
            if (tx >= 1 && tx <= m && ty >= 1 && ty <= n && tz >= 1 && tz <= l && a[tx][ty][tz] && !vis[tx][ty][tz]) {
                vis[tx][ty][tz] = 1;
                q.push(node(tx, ty, tz));
            }
        }
    }
    if (cnt >= t) return cnt;
    else return 0;
}

int main() 
{
    scanf("%d%d%d%d", &m, &n, &l, &t);
    for (int i = 1; i <= l; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int k = 1; k <= n; ++k) {
                scanf("%d", &a[j][k][i]);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= l; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int k = 1; k <= n; ++k) {
                if (a[j][k][i] && !vis[j][k][i]) {
                    ans += bfs(j, k, i);
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

L3-005 垃圾箱分布

题目链接

题意：$n(\le10^3)$ 个居民点，$m(\le10)$ 个垃圾箱侯选地，$k(\le10^4)$ 条道路，$maxd$ 表示居民点与垃圾箱之间不能超过的最大距离，居民点从 $1$ 到 $n$ 编号，垃圾箱侯选地从 $G1$ 到 $Gm$ 编号，求最佳垃圾箱候选地，使得该位置到所有居民点最短距离最大，并且每个居民点距离不超过 $maxd$。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。

对每个候选地 dijkstra，第一个样例貌似错了。

 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
76
77
78
79
80
81
82
83
84
85
86
87


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<double, int> P;
const int INF = 0x3f3f3f3f, N = 1e3 + 15, M = 2e4 + 5;

int n, m, k, maxd, tot;
int v[N];
double d[N];
int ver[M], nxt[M], head[N];
double edge[M];

void add(int x, int y, double z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > q;
    q.push(P(0, s));
    for (int i = 1; i <= n + m; ++i) d[i] = INF;
    memset(v, 0, sizeof(v));
    d[s] = 0;
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (d[y] > d[x] + edge[i]) {
                d[y] = d[x] + edge[i];
                q.push(P(d[y], y));
            }
        }
    }
}

int main() 
{
    scanf("%d%d%d%d", &n, &m, &k, &maxd);
    string a, b;
    int x, y;
    double z;
    while (k--) {
        cin >> a >> b >> z;
        if (a[0] == 'G') x = stoi(a.substr(1)) + n;
        else x = stoi(a);
        if (b[0] == 'G') y = stoi(b.substr(1)) + n;
        else y = stoi(b);
        add(x, y, z);
        add(y, x, z);
    }
    int id = 0;
    double ans = 0, ansavg = INF;
    for (int i = 1; i <= m; ++i) {
        dijkstra(n + i);
        double avg = 0, mind = d[1];
        int flag = 0;
        for (int j = 1; j <= n; ++j) {
            avg += 1.0 * d[j];
            if (d[j] > maxd) { flag = 1; break; }
            mind = min(mind, d[j]);
        }
        if (flag) continue;
        avg /= n;
        if (mind > ans) {
            id = i;
            ans = mind;
            ansavg = avg;
        }
        else if (mind == ans && avg < ansavg) {
            id = i;
            ansavg = avg;
        }
    }
    if (id) printf("G%d\n%.1lf %.1lf\n", id, ans, ansavg);
    else puts("No Solution");
    return 0;
}

L3-007 天梯地图

题目链接

题意：$n(2\le n\le500)$ 个点，$m$ 条道路，每条道路长度，和通过该道路所需时间，如果最快到达路线不唯一，则输出几条最快路线中最短的那条。而如果最短距离的路线不唯一，则输出途径节点数最少的那条。

裸模板题，两次 dijkstra 分别求最短路径和最快路径。

  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
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f, N = 505, M = 3e5 + 5;

int n, m, tot, st, ed;
int ver[M], edge[M], tim[M], nxt[M], head[N];
int d[N], t[N], cost[N], pre[N];
vector<int> path1, path2;

void add(int x, int y, int d, int t) {
    ver[++tot] = y, edge[tot] = d, tim[tot] = t, nxt[tot] = head[x], head[x] = tot;
}

void dijkstra1() {
    priority_queue<P, vector<P>, greater<P> > q;
    memset(d, 0x3f, sizeof(d));
    q.push(P(0, st));
    d[st] = 0;
    pre[st] = -1;
    cost[st] = 0;
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (d[y] > d[x] + edge[i]) {
                d[y] = d[x] + edge[i];
                q.push(P(d[y], y));
                pre[y] = x;
                cost[y] = cost[x] + 1;
            }
            else if (d[y] == d[x] + edge[i]) {
                if (cost[y] > cost[x] + 1) {
                    q.push(P(d[y], y));
                    pre[y] = x;
                    cost[y] = cost[x] + 1;
                }
            }
        }
    }
    path1.push_back(ed);
    for (int i = ed; ~pre[i]; i = pre[i])
        path1.push_back(pre[i]);
}

void dijkstra2() {
    priority_queue<P, vector<P>, greater<P> > q;
    memset(t, 0x3f, sizeof(t));
    q.push(P(0, st));
    t[st] = 0;
    pre[st] = -1;
    cost[st] = 0;
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i];
            if (t[y] > t[x] + tim[i]) {
                t[y] = t[x] + tim[i];
                q.push(P(t[y], y));
                pre[y] = x;
                cost[y] = cost[x] + edge[i];
            }
            else if (t[y] == t[x] + tim[i]) {
                if (cost[y] > cost[x] + edge[i]) {
                    q.push(P(t[y], y));
                    pre[y] = x;
                    cost[y] = cost[x] + edge[i];
                }
            }
        }
    }
    path2.push_back(ed);
    for (int i = ed; ~pre[i]; i = pre[i])
        path2.push_back(pre[i]);
}

bool equal() {
    if (path1.size() != path2.size()) return false;
    for (int i = 0; i < (int)path1.size(); ++i)
        if (path1[i] != path2[i]) return false;
    return true;
}

int main() 
{
    scanf("%d%d", &n, &m);
    int x, y, op, len, tim;
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d%d%d", &x, &y, &op, &len, &tim);
        add(x, y, len, tim);
        if (!op) add(y, x, len, tim);
    }
    scanf("%d%d", &st, &ed);
    dijkstra1();
    dijkstra2();
    if (equal()) {
        printf("Time = %d; Distance = %d: ", t[ed], d[ed]);
        for (int i = (int)path1.size() - 1; i >= 1; --i) {
            printf("%d => ", path1[i]);
        }
        printf("%d\n", path1[0]);
    }
    else {
        printf("Time = %d: ", t[ed]);
        for (int i = (int)path2.size() - 1; i >= 1; --i) {
            printf("%d => ", path2[i]);
        }
        printf("%d\n", path2[0]);
        printf("Distance = %d: ", d[ed]);
        for (int i = (int)path1.size() - 1; i >= 1; --i) {
            printf("%d => ", path1[i]);
        }
        printf("%d\n", path1[0]);
    }
    return 0;
}

L3-008 喊山

题目链接

题意：给出 n 个点，m 个连接关系，k 个询问点求距该点最远的点。

以询问的点为根层序遍历。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e4 + 5;

int n, m, k;
int vis[N], d[N];
vector<int> v[N];

int main() 
{
    scanf("%d%d%d", &n, &m, &k);
    int x, y;
    while (m--) {
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for (int i = 1; i <= k; ++i) {
        scanf("%d", &x);
        int ans = INF, maxn = 0;
        memset(vis, 0, sizeof(vis));
        queue<int> q;
        q.push(x);
        d[x] = 1; vis[x] = 1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (d[u] > maxn) {
                maxn = d[u];
                ans = INF;
            }
            if (u != x) ans = min(ans, u);
            for (int j = 0; j < (int)v[u].size(); ++j) {
                if (!vis[v[u][j]]) {
                    q.push(v[u][j]);
                    vis[v[u][j]] = 1;
                    d[v[u][j]] = d[u] + 1;
                }
            }
        }
        if (ans != INF) printf("%d\n", ans);
        else puts("0");
    }
    return 0;
}

L3-010 是否完全二叉搜索树

题目链接

题意：将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

按性质建树，左右子树分别为 rt<<1 和 rt<<1|1，最后按顺序遍历输出并判断是否完全二叉树。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;

int n;
int tree[1<<20];

void build(int rt, int val) {
    if (!tree[rt]) tree[rt] = val;
    else if (tree[rt] < val) build(rt<<1, val);
    else build(rt<<1|1, val);
}

int main() 
{
    scanf("%d", &n);
    int x;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &x);
        build(1, x);
    }
    int flag = 1, cnt = 1;
    for (int i = 1; cnt <= n; ++i) {
        if (!tree[i]) flag = 0;
        else {
            printf("%d", tree[i]);
            if (cnt++ != n) putchar(' ');
        }
    }
    if (flag) printf("\nYES\n");
    else printf("\nNO\n");
    return 0;
}

L3-013 非常弹的球

题目链接

题意：小球以一定动能斜抛出，求停止时最远距离。

$\angle{ans}=45\degree$ 时，$s_{max}=\frac{2E}{mg}$。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;

double g = 9.8, E = 1000, w, p, ans, s = 1;

int main() 
{
    scanf("%lf%lf", &w, &p);
    w /= 100;
    while (s > eps) {
        ans += (s = 2 * E/ (w * g));
        E *= (1 - p / 100);
    }
    printf("%.3lf\n", ans);
    return 0;
}

L3-015 球队“食物链”

题目链接

题意：给出 $n$ 个球队，$n\times n$ 场联赛结果表，其中第 $i$ 行第 $j$ 列的字符为球队 $i$ 在主场对阵球队 $j$ 的比赛结果：$W$ 表示球队 $i$ 战胜球队 $j$，$L$ 表示球队 $i$ 负于球队 $j$，$D$ 表示两队打平，$-$表示无效（当 $i=j$ 时），找出食物链，存在多条找出字典序最小的。“食物链”为一个 $1$ 至 $n$ 的排列 $\{T_1 T_2 ⋯ T_N\}$，满足：球队 $T_1$ 战胜过球队 $T_2$，球队 $T_2$ 战胜过球队 $T_3$，⋯，球队 $T_{n−1}$ 战胜过球队 $T_n$，球队 $T_n$ 战胜过球队 $T_1$。

只需要记录胜利的情况即可，dfs 中需要进行剪枝。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 25;

int n, flag;
int win[N][N], vis[N], ans[N];

void dfs(int id, int num) {
    if (flag) return;
    ans[id] = num;
    if (id == n) {
        if (win[num][1]) flag = 1;
        return;
    }
    bool f = 0; // 剪枝判断
    for (int i = 1; i <= n; ++i)
        if (!vis[i] && win[i][1]) f = 1;
    if (!f) return;
    vis[num] = 1;
    for (int i = 1; i <= n; ++i)
        if (!vis[i] && win[num][i])
            dfs(id + 1, i);
    vis[num] = 0;
}

int main() 
{
    scanf("%d", &n);
    char str[25];
    for (int i = 1; i <= n; ++i) {
        scanf("%s", str + 1);
        for (int j = 1; j <= n; ++j) {
            if (str[j] == 'W') win[i][j] = 1;
            else if (str[j] == 'L') win[j][i] = 1;
        }
    }
    dfs(1, 1);
    if (flag) {
        printf("%d", ans[1]);
        for (int i = 2; i <= n; ++i)
            printf(" %d", ans[i]);
        puts("");
    }
    else puts("No Solution");
    return 0;
}

L3-016 二叉搜索树的结构

题目链接

题意：根据给出的序列建立二叉搜索树，并给出一些询问，判断是否正确。

数组建树，模拟即可。

 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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 105;

struct BST {
    int l, r, fa;
    int val, h;
}a[N];

int n, m, tot;
map<int, int> mp;

int New(int val) {
    a[++tot].val = val;
    a[tot].h = 1;
    a[tot].fa = -1;
    return tot;
}

void insert(int &p, int val, int height, int fa) {
    if (!p) {
        a[++tot].val = val;
        a[tot].h = height + 1;
        a[tot].fa = fa;
        p = tot;
        return;
    }
    if (val == a[p].val) return;
    if (val < a[p].val) insert(a[p].l, val, height + 1, p);
    else insert(a[p].r, val, height + 1, p);
}

int main() 
{
    int x, y;
    scanf("%d%d", &n, &x);
    int rt = New(x);
    mp[x] = rt;
    for (int i = 2; i <= n; ++i) {
        scanf("%d", &x);
        insert(rt, x, 0, rt);
        mp[x] = tot;
    }
    scanf("%d", &m);
    string str;
    while (m--) {
        cin >> x >> str;
        int flag = 0;
        if (str == "is") {
            cin >> str >> str;
            if (str == "root") {
                if (mp[x] == rt) flag = 1;
            }
            else if (str == "parent") {
                cin >> str >> y;
                if (a[mp[y]].fa == mp[x] && mp[x]) flag = 1; 
            }
            else if (str == "left") {
                cin >> str >> str >> y;
                if (a[mp[y]].l == mp[x] && mp[x]) flag = 1;
            }
            else if (str == "right") {
                cin >> str >> str >> y;
                if (a[mp[y]].r == mp[x] && mp[x]) flag = 1;
            }
        }
        else if (str == "and") {
            cin >> y >> str >> str;
            if (!mp[x] || !mp[y]) flag = 0;
            else if (str == "siblings") {
                if (a[mp[x]].fa == a[mp[y]].fa) flag = 1;
            }
            else if (str == "on") {
                cin >> str >> str >> str;
                if (a[mp[x]].h == a[mp[y]].h) flag = 1;
            }
        }
        if (flag) puts("Yes");
        else puts("No");
    }
    return 0;
}

L3-018 森森美图

题目链接

题意：计算出了一个图像中所有像素点与周围点的相似程度的分数，分数越低表示某个像素点越“像”一个轮廓边缘上的点。给出起点 A 和终点 B，连接这两个点的直线就将图像分为两部分，然后在这两部分中分别寻找一条从 A 到 B 且与轮廓重合程度最高的曲线。

忽略正好位于连接A和B的直线（注意不是线段）上的像素点，即不认为这部分像素点在任何一个划分部分上，因此曲线也不能经过这部分像素点。曲线是八连通的，但为了计算准确，某像素连接对角相邻的斜向像素时，得分额外增加两个像素分数和的$\sqrt{2}$倍减一。

利用叉积判断与直线的关系，bfs 2 次找两部分最小值。

 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
76
77
78
79
80
81
82
83
84
85


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const double INF = 0x3f3f3f3f;
const int N = 105;

int n, m, sx, sy, ex, ey;
int vis[N][N];
double g[N][N], d[N][N];
int dx[8] = { 1, -1, 0, 0, 1, 1, -1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, 1, -1 };

struct node {
    int x, y;
    node(int x, int y) : x(x), y(y) {}
};

int cross(node a, node b, node c) {
    return ((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b. y- a.y));
}

bool check(int flag, int x, int y) {
    if (x == ex && y == ey) return 1;
    if (x < 0 || x >= n || y < 0 || y >= m) return 0;
    int res = cross(node(sx, sy), node(ex, ey), node(x, y));
    if ((res > 0 && flag) || (res < 0 && !flag)) return 1;
    return 0;
}

void bfs(int flag) {
    queue<node> q;
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            d[i][j] = INF;
        }
    }
    q.push(node(sx, sy));
    d[sx][sy] = g[sx][sy];
    vis[sx][sy] = 1;
    while (!q.empty()) {
        node u = q.front();
        vis[u.x][u.y] = 0;
        q.pop();
        for (int i = 0; i < 8; ++i) {
            int tx = u.x + dx[i];
            int ty = u.y + dy[i];
            if (!check(flag, tx, ty)) continue;
            double res = d[u.x][u.y] + g[tx][ty];
            if (i > 3) res += (g[tx][ty] + g[u.x][u.y]) * (sqrt(2) - 1);
            if (d[tx][ty] > res) {
                d[tx][ty] = res;
                if (!vis[tx][ty]) {
                    vis[tx][ty] = 1;
                    q.push(node(tx, ty));
                }
            }
        }
    }
}

int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%lf", &g[i][j]);
        }
    }
    scanf("%d%d%d%d", &sy, &sx, &ey, &ex);
    bfs(1);
    double ans = d[ex][ey];
    bfs(0);
    ans += d[ex][ey];
    printf("%.2lf\n", ans - g[sx][sy] - g[ex][ey]);
    return 0;
}

L3-020 至多删三个字符

题目链接

题意：给定一个全小写英文字母字符串(长度在 $[4,10^6]$)，允许最多删掉 3 个字符，可以得到多少种不同字符串。

用 $dp[i][j]$ 表示前 $i$ 个字符删去 $j$ 个得到不同字符串的数量。则

删去第 $i$ 个字符，$dp[i][j+1]+=dp[i-1][j]$。
不删第 $i$ 个字符，$dp[i][j]+=dp[i-1][j]$。

这样会计算进很多重复方案，比如 $i$ 前的一个位置 $k$ 满足 $str[i]==str[k]$，并且两个位置距离小于删去的字符数，删掉第 $k$ 个和删掉第 $i$ 个得到字符串相同，需要去掉这种情况，即 $dp[i][j]-=dp[k-1][j-(i-k)]$。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e6 + 5;

char str[N];
ll dp[N][4];

int main() 
{
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= 3; ++j) {
            if (j < 3) dp[i][j+1] += dp[i-1][j];
            dp[i][j] += dp[i-1][j];
            for (int k = i - 1; k >= 1 && k >= i - j; --k) {
                if (str[k] == str[i]) {
                    dp[i][j] -= dp[k-1][j-(i-k)];
                    break;
                }
            }
        }
    }
    printf("%lld\n", dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3]);
    return 0;
}

L3-021 神坛

题目链接

题意：给出 $n(3\le n\le5000)$ 个点，选择 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
39
40
41


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int N = 5005;
const ll INF = 4e18;

struct point {
    ll x, y;
    bool operator < (const point &rhs) const {
        return x * rhs.y > y * rhs.x;
    }
}p[N], vec[N];

int n;

int main() 
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld%lld", &p[i].x, &p[i].y);
    ll ans = INF;
    for (int i = 1; i <= n; ++i) {
        int tot = 0;
        for (int j = 1; j <= n; ++j) {
            if (i == j) continue;
            vec[++tot] = { p[j].x - p[i].x, p[j].y - p[i].y };
        }
        sort(vec + 1, vec + tot + 1);
        for (int j = 1; j < tot; ++j) {
            ans = min(ans, abs(vec[j].x * vec[j+1].y - vec[j+1].x * vec[j].y));
        }
    }
    printf("%.3lf\n", 1.0 * ans / 2);
    return 0;
}

L3-022 地铁一日游

题目链接

题意：森森决定用以下的方式坐地铁：在某一站上车（不妨设为地铁站 A），则对于所有车费相同的到达站，森森只会在计费距离最远的站或线路末端站点出站，然后用森森美图 App 在站点外拍一张认证照，再按同样的方式前往下一个站点。在给定出发站的情况下（在出发时森森也会拍一张照），他的整个旅程中能够留下哪些站点的认证照？

留下认证的站点：线路起点终点以及出站点为某个车费中最远的站点。

 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
76
77
78
79
80
81


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 205;

int n, m, k, q;
int isend[N], vis[N];
int a[N][N];
vector<int> g[N];

void floyd() {
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}

void dfs(int x) {
    vis[x] = 1;
    for (auto i : g[x])
        if (!vis[i])
            dfs(i);
}

int main() 
{
    scanf("%d%d%d", &n, &m, &k);
    memset(a, 0x3f, sizeof(a));
    for (int i = 1; i <= n; ++i) a[i][i] = 0;
    int x, y, dis;
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &x);
        isend[x] = 1;
        while (getchar() != '\n') {
            scanf("%d%d", &dis, &y);
            if (a[x][y] > dis) {
                a[x][y] = a[y][x] = dis;
            }
            x = y;
        }
        isend[x] = 1;
    }
    floyd();
    for (int i = 1; i <= n; ++i) {
        map<int, int> mp;
        for (int j = 1; j <= n; ++j) {
            if (a[i][j] != INF && a[i][j] > mp[2+a[i][j]/k])
                mp[2+a[i][j]/k] = a[i][j];
        }
        for (int j = 1; j <= n; ++j) {
            if (a[i][j] == mp[2+a[i][j]/k] || (i != j && isend[j] && a[i][j] != INF))
                g[i].push_back(j);
        }
    }
    scanf("%d", &q);
    int st;
    while (q--) {
        scanf("%d", &st);
        memset(vis, 0, sizeof(vis));
        dfs(st);
        int flag = 0;
        for (int i = 1; i <= n; ++i) {
            if (vis[i]) {
                if (flag) putchar(' ');
                printf("%d", i);
                flag = 1;
            }
        }
        puts("");
    }
    return 0;
}

L3-025 那就别担心了

题目链接

题意：n 个点和 m 条有向边，给出起点终点 A B，求 A 到 B 的路径条数，判断从 A 出发是否只会到 B。

建图删掉除多余的点，从 A 拓扑到 B。

 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


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 505;

int n, m;
vector<int> edge[N];
int ind[N], cnt[N];

int main() 
{
	scanf("%d%d", &n, &m);
    int x, y, st, ed;
    while (m--) {
    	scanf("%d%d", &x, &y);
    	edge[x].push_back(y);
    	ind[y]++;
    }
    scanf("%d%d", &st, &ed);
    queue<int> q1;
    for (int i = 1; i <= n; ++i) {
    	if (!ind[i] && i != st) q1.push(i);
    }
    while (!q1.empty()) {
    	int cur = q1.front();
    	q1.pop();
    	for (auto i : edge[cur]) {
    		ind[i]--;
    		if (!ind[i] && i != st) q1.push(i);
    	}
    }
    queue<int> q2;
    q2.push(st);
    cnt[st] = 1;
    int flag = 1;
    while (!q2.empty()) {
    	int cur = q2.front();
    	q2.pop();
    	if (cur == ed) continue;
    	if (edge[cur].empty()) flag = 0;
    	for (auto i : edge[cur]) {
    		cnt[i] += cnt[cur];
    		ind[i]--;
    		if (!ind[i]) q2.push(i);
    	}
    }
    printf("%d ", cnt[ed]);
    if (flag) puts("Yes");
    else puts("No");
    return 0;
}

Contents

L3-001 凑零钱

L3-002 特殊堆栈

L3-003 社交集群

L3-004 肿瘤诊断

L3-005 垃圾箱分布

L3-007 天梯地图

L3-008 喊山

L3-010 是否完全二叉搜索树

L3-013 非常弹的球

L3-015 球队“食物链”

L3-016 二叉搜索树的结构

L3-018 森森美图

L3-020 至多删三个字符

L3-021 神坛

L3-022 地铁一日游

L3-025 那就别担心了