醉心代码无法自拔

程序员的自我修养(?)

0%

齐鲁工业大学ACM队内排位赛 2024秋季第一场 部分题解

发表于 更新于 分类于
本文字数： 3.5k 阅读时长 ≈ 6 分钟

点我补题

竞赛结果：Solved ADGH。

A.01

思路

如果 $0$ 或者 $1$ 有一个是偶数个，则一定可以通过操作将它们全部反转成另一个数字。所以只需要判断两个数字是否都是奇数个即可。

代码

1
2
3
4
5
6
void solve()
{
    string str;
    cin >> str;
    cout << (count(all(str), '0') & 1 && count(all(str), '1') & 1 ? "NO" : "YES") << endl;
}

B.肥胖基因

思路

这不就是一个模拟查找。不知道为什么赛时写锅了只有80分。可恶。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve()
{
    int n, m, ans1 = 0, ans2 = 0;
    string s1, s2;
    cin >> n >> m >> s1 >> s2;
    vector<int> a(s1.size() + 1);
    int temp = 0;
    for (int i = 0; i < n - m + 1; i++)
    {
        if (s1.substr(i, m) == s2)
        {
            for (int j = i; j < i + m; j++)
                a[j]++;
            if ((temp != 0 && i > temp) || temp == 0)
                ans2++, temp = i + m - 1;
        }
    }
    for (int i = 0; i < n; i++)
        if (a[i] != 0)
            ans1++;
    cout << ans1 << " " << ans2 << endl;
}

D.春游

思路

暴力就能过。推数学公式还容易推出毛病来。注意 int范围不够。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using i64 = long long;
void solve()
{
    int n;
    cin >> n;
    i64 ans = LLONG_MAX;
    for (int big = 0;; big++)
    {
        int rmd = max(0ll, n - big * 49);
        int small = (rmd / 33) + (rmd % 33 ? 1 : 0);
        int money = big * 3300 + small * 1900;
        ans = min(ans, money);
        if (49 * big > n)
            break;
    }
    cout << ans << endl;
}

G.找7

思路

说起来你可能不信贫僧是用DFS过的。实际上 $k$ 的范围完全可以缩小到7，因为最坏的结果就是 1+1+1+1+1+1+1。所以再往上的 $k$ 都是吓唬人玩的。将所有数用 map 预处理一遍 mod 7 的结果就好了。

代码

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
int ans = INT_MAX;
vector<int> d(10);
map<int, vector<int>> mp;
void dfs(int end, int curpos, int curval)
{
    if (curpos == end)
    {
        int curSum = 0;
        if (curval % 7 == 0)
        {
            map<int, int> idx;
            for (int i = 0; i < end; i++)
            {
                idx[d[i]]++;
                if (idx[d[i]] > mp[d[i]].size())
                    return;
                curSum += mp[d[i]][idx[d[i]] - 1];
            }
            ans = min(ans, curSum);
        }
        return;
    }
    for (int i = 1; i < 7; i++)
    {
        d[curpos] = i;
        dfs(end, curpos + 1, curval + i);
        d[curpos] = 0;
    }
}
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> vec(n);
    for (int i = 0; i < n; i++)
    {
        cin >> vec[i];
        if (vec[i] != 0)
            mp[vec[i] % 7].push_back(vec[i]);
    }
    for (auto &[k, v] : mp)
        sort(all(v));
    if (mp[0].size())
        ans = mp[0][0];
    for (int i = 1; i <= min(k, 7); i++)
    {
        dfs(i, 0, 0);
    }
    cout << (ans == INT_MAX ? -1 : ans) << endl;
}

H.路径

思路

搜索入门题。是个签到。迷宫类题目真的是搜索必会了，判边界之类的。

然后我个人习惯用 pair<int,int>充当 Point，非常爽。可以用 priority_queue。

代码

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
using Point = pair<int, int>;
#define x first
#define y second

vector<Point> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void solve()
{
    int n, m;
    cin >> n >> m;
    Point start, end;
    vector<vector<char>> vec(n, vector<char>(m));
    vector<vector<bool>> vis(n, vector<bool>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> vec[i][j];
            if (vec[i][j] == 'S')
                start = {i, j};
            if (vec[i][j] == 'E')
                end = {i, j};
        }
    }
    priority_queue<pair<int, Point>, vector<pair<int, Point>>, greater<>> que;
    int ans = INT_MAX;
    que.push({0, start});
    vis[start.x][start.y] = true;
    while (!que.empty())
    {
        auto [step, cur] = que.top();
        que.pop();
        if (cur == end)
        {
            ans = min(ans, step);
            continue;
        }
        for (auto dir : directions)
        {
            Point nxt = {dir.x + cur.x, dir.y + cur.y};
            if (nxt.x >= 0 && nxt.x < n && nxt.y >= 0 && nxt.y < m && !vis[nxt.x][nxt.y] && vec[nxt.x][nxt.y] != '#')
                que.push({vec[nxt.x][nxt.y] == '@' ? step + 3 : step + 1, nxt}), vis[nxt.x][nxt.y] = true;
        }
    }
    if (ans == INT_MAX)
    {
        cout << "The End!!!" << endl;
        return;
    }
    cout << ans << endl;
}

待补：C，F，I