醉心代码无法自拔

程序员的自我修养(?)

0%

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

发表于
本文字数： 5.8k 阅读时长 ≈ 10 分钟

点我补题

竞赛结果：Solved ABCEFG。

A.好朋友

思路

从 $x$ 处出发，分别向左右两侧找最近的房子并且计算距离即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve()
{
    int n, x, m;
    cin >> n >> x >> m;
    x--;
    vector<int> vec(n);
    for (int i = 0; i < n; i++)
        cin >> vec[i];
    int lft = INT_MAX, rt = INT_MAX;
    for (int i = x - 1; i >= 0 && lft == INT_MAX; i--)
        if (vec[i] != 0 && vec[i] <= m)
            lft = i;
    for (int i = x + 1; i < n && rt == INT_MAX; i++) 
        if (vec[i] != 0 && vec[i] <= m)
            rt = i;
    int ans = min(abs(lft - x), abs(rt - x)) * 10;
    cout << ans << endl;
}

B.三元组

思路

记录每个数字出现的下标，然后对于数组中每一个数字 $a[i]$ ，二分查找其左侧的 $a[i]+1$ 和右侧的 $a[i]+1$。并且用 distance STL 来计算还存在几个下标符合要求，相乘即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve()
{
    int n;
    cin >> n;
    vector<int> vec(n + 1);
    map<int, vector<int>> pos;
    for (int i = 1; i <= n; i++)
        cin >> vec[i], pos[vec[i]].push_back(i);
    int ans = 0;
    for (int i = 2; i < n; i++)
    {
        auto search = pos[vec[i] + 1];
        auto lft = lower_bound(all(search), i);
        if (lft != search.end())
            ans += distance(search.begin(), lft) * distance(lft, search.end());
    }
    cout << ans << endl;
}

C.平分苹果

思路

赛时写了个特别难绷的模拟。

赛后队友点了一下发现，不进位的二进制加法 == 异或。

于是就成水题了。

只要异或起来不等于0，无解。否则和减去最小值即可。

代码

1
2
3
4
5
6
7
8
9
10
void solve()
{
    int n;
    cin >> n;
    vector<int> vec(n);
    int x = 0, sum = 0, mn = INT_MAX;
    for (i64 i = 0; i < n; i++)
        cin >> vec[i], sum += vec[i], mn = min(mn, vec[i]), x ^= vec[i];
    cout << (x ? -1 : sum - mn) << endl;
}

D.套餐

思路

背包 dp，还是个二维的。

I don't know how to write dp I am dp 低手。

（大雾）

对于第 $a[i]$ 个食物组， 有 $dp[j][k] = min(dp[j][k], dp[max(0, j - a[i].first)][max(0, k - a[i].second)] + 1)$，跑一遍取从 $dp[x][y]$ 到 $dp[N][N]$ 的最小值就行了。

二维背包要跑三次 $for$ ，记好了。

代码

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
void solve()
{
    int n, ft, sd, sum1, sum2;
    pair<int, int> a[305];
    vector<vector<int>> dp(305, vector<int>(305, INT_MAX - 1e4));
    cin >> n >> ft >> sd;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].first >> a[i].second;
        sum1 += a[i].first, sum2 += a[i].second;
    }
    if (sum1 < ft || sum2 < sd)
        cout << "-1\n";
    else
    {
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 300; j >= 0; j--)
                for (int k = 300; k >= 0; k--)
                    dp[j][k] = min(dp[j][k], dp[max(0, j - a[i].first)][max(0, k - a[i].second)] + 1);
        int ans = INT_MAX - 1e4;
        for (int i = ft; i <= 300; i++)
            for (int j = sd; j <= 300; j++)
                ans = min(ans, dp[i][j]);
        cout << ans;
    }
}

E.取球

思路

用队列模拟并且每次在出队一对球以后将新队首再次记录即可，麻烦一点的小模拟。

代码

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
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<queue<int>> bar(m);
    for (int i = 0; i < m; i++)
    {
        int k;
        cin >> k;
        int ball;
        while (k--)
            cin >> ball, bar[i].push(ball);
    }
    map<int, vector<int>> ontop_idx;
    queue<int> both;
    for (int i = 0; i < m; i++)
    {
        int ball = bar[i].front();
        ontop_idx[ball].push_back(i);
        if (ontop_idx[ball].size() == 2)
            both.push(ball);
    }
    while (!both.empty())
    {
        int ball = both.front();
        both.pop();
        for (int i = 0; i < 2; i++)
        {
            int idx = ontop_idx[ball][i];
            bar[idx].pop();
            if (!bar[idx].empty())
            {
                int cur_top = bar[idx].front();
                ontop_idx[cur_top].push_back(idx);
                if (ontop_idx[cur_top].size() == 2)
                    both.push(cur_top);
            }
        }
    }
    for (auto it : bar)
    {
        if (!it.empty())
        {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

F.航班

思路

带点权的 dijkstra。可以在板子里找到对应的模板。注意 $N$ 的大小。

哦本题需要缓存一下结果防止爆TLE。没有其他问题了。

代码

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
const int MAXN = 310;
struct Edge
{
    int to, weight;
};
struct Node
{
    int dis, from;
    bool operator>(const Node &a) const { return dis > a.dis; }
};
vector<Edge> edges[MAXN];
vector<int> dis(MAXN), vis(MAXN);
vector<int> value(MAXN);
vector<int> vec(MAXN);
priority_queue<Node, vector<Node>, greater<Node>> que;
void dijkstra(int n, int s)
{
    dis = vector<int>(MAXN, INT_MAX);
    vis = vector<int>(MAXN, 0);
    dis[s] = 0;
    value[s] = vec[s];
    que.push({0, s});
    while (!que.empty())
    {
        int from = que.top().from;
        que.pop();
        if (vis[from])
            continue;
        vis[from] = 1;
        for (auto edge : edges[from])
        {
            int to = edge.to, weight = edge.weight;
            if (dis[to] > dis[from] + weight)
            {
                dis[to] = dis[from] + weight;
                value[to] = value[from] + vec[to];
                que.push({dis[to], to});
            }
            else if (dis[to] == dis[from] + weight && value[to] < value[from] + vec[to])
            {
                value[to] = value[from] + vec[to];
                que.push({dis[to], to});
            }
        }
    }
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> vec[i];
    vector<string> grid(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> grid[i];
        grid[i] = '#' + grid[i];
        for (int j = 1; j <= n; j++)
        {
            if (grid[i][j] == 'Y')
                edges[i].push_back({j, 1});
        }
    }
    int q;
    cin >> q;
    vector<vector<int>> res_dis(n + 1);
    vector<vector<int>> res_val(n + 1);
    for (int i = 1; i <= n; i++)
    {
        dijkstra(n, i);
        res_dis[i] = dis;
        res_val[i] = value;
    }
    while (q--)
    {
        int from, to;
        cin >> from >> to;
        if (res_dis[from][to] == INT_MAX)
        {
            cout << "Impossible" << endl;
            continue;
        }
        else
            cout << res_dis[from][to] << " " << res_val[from][to] << endl;
    }
}

G.商品

思路

可以 dp ，但是有没有不 dp 也能过的思路。

有的，优先队列处理一下就行了。

记录每个物品的保质期，按照保质期倒序排序，在第 $day[i+1]$ 到 $day[i]$ 天的时间段内只有保质期到 $day[i+1]$ 的商品可供售卖，将他们扔到一个池子里按照价值排序即可。排序这块用 priority_queue 就完全OK。

本题输入逻辑比较逆天，所以 $n$ 放在了主函数而非 solve 里。注意一下。

代码

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
void solve(int n)
{
    map<int, vector<int>, greater<>> mp;
    vector<int> days;
    for (int i = 0; i < n; i++)
    {
        int p, d;
        cin >> p >> d;
        mp[d].push_back(p);
    }
    for (auto &[k, v] : mp)
        days.push_back(k);
    days.push_back(0);
    int ans = 0;
    priority_queue<int> pool;
    for (int i = 1; i < days.size(); i++)
    {
        int cnt = days[i - 1] - days[i];
        for (auto v : mp[days[i - 1]])
            pool.push(v);
        while (cnt-- && !pool.empty())
            ans += pool.top(), pool.pop();
    }
    cout << ans << "\n";
}