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

A - AtCoder Cards AtCoder - abc301_c

思路

记录两个字符串每个字符出现的次数。如果非 \(@,\ a,\ t,\ c,\ o,\ d,\ e,\ r\) 字符出现次数不同直接为不可以。

对比 \(a,\ t,\ c,\ o,\ d,\ e,\ r\) 字符的出现差多少个，如果比 \(@\) 多则不可以，反之则可以。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    string s, t;
    cin >> s >> t;
    vector<int> a(200), b(200);
    for (auto &i : s)
        a[i]++;
    for (auto &i : t)
        b[i]++;

    int num = a['@'] + b['@'];

    for (int i = 0; i < 200; i++)
    {
        if (i == '@')
            continue;

        if (a[i] != b[i])
        {
            string tmp = "atcoder";
            if (tmp.find(i) == string::npos)
            {
                cout << "No";
                return;
            }
            else
            {
                num -= abs(a[i] - b[i]);
            }
        }
    }

    if (num >= 0)
        cout << "Yes";
    else
        cout << "No";
}

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

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

    return 0;
}

B - PERKET 洛谷 - P2036

思路一

深度优先搜索，判断所有的选择情况。每次有选和不选两种操作，分别搜索下去。当深度为 \(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
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

vector<int> acid, bitter;
vector<bool> st;
int n, ans = 0x3f3f3f3f;
bool flag = false;

void dfs(int x)
{
    if (x > n)
    {
        int sum1 = 1, sum2 = 0;
        for (int i = 1; i <= n; i++)
        {
            if (st[i])
            {
                flag = true;
                sum1 *= acid[i];
                sum2 += bitter[i];
            }
        }
        if (flag)
            ans = min(ans, abs(sum1 - sum2));

        return;
    }

    dfs(x + 1);

    st[x] = 1;
    dfs(x + 1);
    st[x] = 0;
}

void solve()
{
    cin >> n;
    acid.resize(n + 1);
    bitter.resize(n + 1);
    st.resize(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> acid[i] >> bitter[i];

    dfs(1);

    cout << ans;
}

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

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

    return 0;
}

思路二

因为只有选和不选两种情况，且 \(n \le 10\) 那么可以用二进制数表示。 \(1\) 为选了， \(0\) 为没选

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

int n, ans = 0x3f3f3f3f;

void solve()
{
    cin >> n;
    vector<int> acid(n + 1), bitter(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> acid[i] >> bitter[i];

    for (ll i = 1; i < (1 << n); i++)
    {
        ll t = i;
        int a = 1, b = 0, p = 1;
        while (t)
        {
            if (t & 1)
            {
                a *= acid[p];
                b += bitter[p];
            }
            t >>= 1;
            p++;
        }
        ans = min(ans, abs(a - b));
    }

    cout << ans;
}

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

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

    return 0;
}

C - Merge Sequences AtCoder - abc294_c

思路

将两个序列合并后排序，然后二分查找下标即可

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int j = 0; j < m; j++)
        cin >> b[j];

    vector<int> t = a;
    t.insert(t.end(), b.begin(), b.end());
    sort(t.begin(), t.end());

    for (int i = 0; i < n; i++)
        cout << lower_bound(t.begin(), t.end(), a[i]) - t.begin() + 1 << ' ';
    cout << endl;
    for (int i = 0; i < m; i++)
        cout << lower_bound(t.begin(), t.end(), b[i]) - t.begin() + 1 << ' ';
    cout << endl;
}

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

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

    return 0;
}

D - Call the ID Number AtCoder - abc293_b

思路

模拟过程，记录谁没被叫过即可。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<bool> vis(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (!vis[i])
            vis[a[i]] = 1;
    }

    vector<int> ans;
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
            ans.push_back(i);
    }

    cout << ans.size() << '\n';
    for (auto i : ans)
        cout << i << ' ';
}

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

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

    return 0;
}

E - K Swap AtCoder - abc254_c

思路

模拟过程，将每组排完序放回序列，判断最终序列是否满足严格升序

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= k; i++)
    {
        vector<int> tmp;
        for (int j = i; j <= n; j += k)
            tmp.push_back(a[j]);

        sort(tmp.begin(), tmp.end(), greater<int>());

        for (int j = i; j <= n; j += k)
        {
            a[j] = tmp.back();
            tmp.pop_back();
        }
    }

    for (int i = 1; i < n; i++)
    {
        if (a[i] > a[i + 1])
        {
            cout << "No";
            return;
        }
    }
    cout << "Yes";
}

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

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

    return 0;
}

F - 01迷宫 洛谷 - P1141

思路

\(BFS\) 判断一个格子可以去到哪些格子，给这些点一个相同的编号，然后再从另一个没有编号的格子开始搜索，直到所有的格子都有编号，记录每个编号多少个格子。

最后通过查询编号对应的格子数即可得到结果

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
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
const int N = 1e5 + 10;
const int M = 1e5 + 10;

char mp[1111][1111];
int vis[1111][1111];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int n, m;

int bfs(int x, int y, int id)
{
    queue<pair<int, int>> q;
    q.push({x, y});
    vis[x][y] = id;
    int cnt = 0;
    while (!q.empty())
    {
        int x = q.front().first, y = q.front().second;
        q.pop();
        cnt++;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || ny < 1 || nx > n || ny > n || vis[nx][ny] || mp[nx][ny] == mp[x][y])
                continue;
            vis[nx][ny] = id;
            q.push({nx, ny});
        }
    }

    return cnt;
}

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

    vector<int> ans(1);
    int id = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (!vis[i][j])
                ans.push_back(bfs(i, j, id++));
        }
    }

    while (m--)
    {
        int x, y;
        cin >> x >> y;
        cout << ans[vis[x][y]] << '\n';
    }
}

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/1127881834/
作者
Xiaowhang
发布于
2024年1月22日
许可协议