SZTU_ACM2024寒期集训训练赛-基础组第二场

A - Not Shading CodeForces - 1627A

思路

分类讨论

  • 如果目标格已经是黑色，直接输出 \(0\)
  • 如果目标格的同行或者同列是黑色，输出 \(1\)
  • 如果存在黑色格子，输出 \(2\)
  • 其他则为 \(-1\)

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char mp[111][111];

void solve()
{
    int n, m, x, y;
    cin >> n >> m >> x >> y;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];

    if (mp[x][y] == 'B')
    {
        cout << 0 << '\n';
        return;
    }
    for (int k = 1; k <= n; k++)
    {
        if (mp[k][y] == 'B')
        {
            cout << 1 << '\n';
            return;
        }
    }
    for (int k = 1; k <= m; k++)
    {
        if (mp[x][k] == 'B')
        {
            cout << 1 << '\n';
            return;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (mp[i][j] == 'B')
            {
                cout << 2 << '\n';
                return;
            }
        }
    }
    cout << -1 << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

B - 转圈游戏 洛谷 - P1965

思路

快速幂，如果求移动了多少位后对 \(n\) 取模，即求 \((x+m*10^k)\%n\)

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int qpow(int a, int b, int mod)
{
    int res = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
            res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
    }
    return res;
}

void solve()
{
    int n, m, k, x;
    cin >> n >> m >> k >> x;
    cout << (x + 1LL * m * (qpow(10, k, n) % n) % n) % n << endl;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

C - Broken Rounding AtCoder - abc273_b

思路

从个位开始，向高位四舍五入直到第 \(k\) 位

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    ll x;
    int k;
    cin >> x >> k;

    ll t = 1;
    for (int i = 1; i <= k; i++)
    {
        t *= 10;
        if (x % t / (t / 10) >= 5)
            x = x - x % t + t;
        else
            x = x - x % t;
    }
    cout << x;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

D - 营救 洛谷 - P1396

思路

最小生成树，当 \(s\) 和 \(t\) 联通时即为答案

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Edge
{
    int u, v, w;
    bool operator<(const Edge &e) const
    {
        return w > e.w;
    }
};

vector<int> fa;

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

void solve()
{
    int n, m, s, t;
    cin >> n >> m >> s >> t;

    fa.resize(n + 1);
    iota(fa.begin(), fa.end(), 0);

    priority_queue<Edge> pq;
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        pq.push({u, v, w});
    }

    while (!pq.empty())
    {
        Edge e = pq.top();
        pq.pop();

        int fu = find(e.u), fv = find(e.v);
        if (fu != fv)
        {
            fa[fu] = fv;
            if (find(s) == find(t))
            {
                cout << e.w << '\n';
                return;
            }
        }
    }
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

E - Welcome to AtCoder AtCoder - abc151_c

思路

记录题目有没有 \(AC\) 过，如果没 \(AC\) 过就累加 \(WA\) 的次数，最后遍历所有的题目，累加结果即可

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n, m;
    cin >> n >> m;

    vector<int> ac(n + 1), wa(n + 1);
    while (m--)
    {
        int p;
        string s;
        cin >> p >> s;

        if (s == "AC")
            ac[p] = 1;
        else if (!ac[p])
            wa[p]++;
    }

    int ac_cnt = 0, wa_cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (ac[i])
        {
            ac_cnt++;
            wa_cnt += wa[i];
        }
    }

    cout << ac_cnt << ' ' << wa_cnt << '\n';
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

F - 摄像头 洛谷 - P2712

思路

拓扑排序，记录这个摄像头有没有出现过，监视着哪些摄像头和被多少摄像头监视。

然后拓扑排序，入度为零且出现过的摄像头进队。

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int n;
    cin >> n;

    vector<int> in(555), out(555);
    vector<vector<int>> g(555);

    for (int i = 0; i < n; i++)
    {
        int u, k;
        cin >> u >> k;
        out[u] = 1;
        while (k--)
        {
            int v;
            cin >> v;
            in[v]++;
            g[u].push_back(v);
        }
    }

    queue<int> q;
    for (int i = 0; i <= 500; i++)
        if (!in[i] && out[i])
            q.push(i);

    int cnt = n;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        cnt--;

        for (int v : g[u])
        {
            in[v]--;
            if (!in[v] && out[v])
                q.push(v);
        }
    }

    if (cnt == 0)
        cout << "YES";
    else
        cout << cnt;
}

int main()
{
    cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}
ACM > 题解 > SZTU_ACM
#算法 #SZTU_ACM
SZTU_ACM2024寒期集训训练赛-基础组第二场
http://xiaowhang.github.io/archives/2254342841/
作者
Xiaowhang
发布于
2024年1月24日
许可协议