Martian148's blog
martian148
2024-11-14
目录

CCPC2023 秦皇岛站 题解

# CCPC2023 秦皇岛站 题解

The 2nd Universal Cup. Stage 9: Qinhuangdao (opens new window)

# A - Make SYSU Great Again I

# Solution

难得构造题签到，蛇形走位就好了

# Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5e4 + 5;
ll n, k;
ll dx[2] = {0, 1};
ll dy[2] = {1, 0};
int main(){
    ios::sync_with_stdio(false);
    map<pair<int, int>, int> mp;
    cin >> n >> k;
    ll x = 1, y = 1, cnt = 0;
    for(int i = 1; i <= 2 * n - 1; i ++){
        mp[{x, y}] = 1;
        cnt ++;
        cout << x << " " << y << '\n';
        x += dx[cnt & 1];
        y += dy[cnt & 1];
    }
    mp[{1, n}] = 1;
    cout << 1 << " " << n << "\n";
    cnt ++;
    if(cnt == k) return 0;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            if(!mp[{i, j}]) cout << i << " " << j << "\n", cnt ++;
            mp[{i, j}] = 1;
            if(cnt == k) return 0;
        }
    }
    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

# D - Yet Another Coffee

# Question

nn 个物品，mm 个优惠券，第 ii 个物品的价格为 aia_i，每个优惠券只能在 [1,ri][1,r_i] 整个区间内使用一次，每次减少 wiw_i 的价格，价格可以被减成负数，对每个 k=1∼nk=1\sim n 求恰好买 kk 个物品的最小花费

# Solution

我用了一种和std不太一样的做法

可以通过归纳 + 反证得出对于 k+1k+1 个购买的物品，实际上就是在 kk 个购买物品的基础上再购买一个，如果我们购买 kk 个物品的集合为 {S}\{S\} 可以维护 SS 中最靠前的物品 jj，那么接下来选择的一个物品要么就是在 1∼j−11\sim j-1，要么就是在 j+1∼nj+1\sim n

贪心可以得出，我们可以在 jj 处使用完所有优惠券，我们先预处理出买第 ii 个物品时，把能用的优惠券全用完的优惠价格 g[i]g[i]

  • 如果考虑接下来一个选择 1∼j−11\sim j-1，那么我们只需要找 a[i]−g[i]a[i]-g[i] 最小值，作为新的 jj，产生的代价为 a[i]−g[i]+g[j]a[i]-g[i]+g[j]，这可以用一个预处理来维护
  • 如果考虑 j+1∼nj+1\sim n，那么只需要找到 j+1∼nj+1\sim n 最小的 a[i]a[i] 且 ii 不在 SS 中，这可以用一个堆来维护

总时间复杂度为 O(n+klog⁡n)O(n+k\log n)

# Code

#include <bits/stdc++.h>

using ll = long long;
const ll INF = 1e17;

void solve() {
    int n, m; std::cin >> n >> m;
    std::vector<ll> a(n + 1), g(n + 1, 0);
    std::vector<std::pair<int, ll>> p(m + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    for (int i = 1; i <= m; i++) std::cin >> p[i].first >> p[i].second;

    sort(p.begin() + 1, p.end());

    ll sum = 0;
    for (int i = n, j = m; i ; i--) {
        while (j > 0 && p[j].first >= i) sum += p[j--].second;
        g[i] = sum;
    }
    

    std::vector<int> pre(n + 1, 0);
    pre[1] = 1;
    for (int i = 2; i <= n; i ++) {
        if (a[i] - g[i] < a[pre[i - 1]] - g[pre[i - 1]])
            pre[i] = i;
        else 
            pre[i] = pre[i - 1];
    }

    int pos = 0;
    for (int i = 1; i <= n; i++) {
        if (pos == 0 || a[i] - g[i] < a[pos] - g[pos])
            pos = i;
    }
    
    typedef std::pair<ll, int> pli;
    std::priority_queue<pli, std::vector<pli>, std::greater<pli>> pq;

    for (int i = pos + 1; i <= n; i++)
        pq.push({a[i], i});

    // std::cout << pos << ": ";
    ll ans = a[pos] - g[pos];
    std::cout << ans << " ";
    for (int k = 2; k <= n; k++) {
        ll now1 = INF, now2 = INF;
        if (!pq.empty()) {
            now1 = pq.top().first;
        }
        if (pos != 1) {
            int pos_ = pre[pos - 1];
            now2 = g[pos] + a[pos_] - g[pos_];
        }

        if (now1 < now2) {
            // std::cout << pq.top().second << ": ";
            pq.pop();
            ans += now1;
        }
        else {
            int pos_ = pre[pos - 1];
            ans += now2;
            for (int j = pos_ + 1; j < pos; j++)
                pq.push({a[j], j});
            pos = pos_;
            // std::cout << pos << ": ";
        }

    
        std::cout << ans << " ";
    }
    std::cout << "\n";
}

int main() {
    freopen ("D.in", "r", stdin);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int T; std::cin >> T;
    while (T--) solve();
    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
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

# F - ministry of prime

# Question

给定一个长度为 nn 的数组 aa，修改最少的数字，使得相邻两个元素的和是质数

# Solution

考虑到偶数除了 22 以外都不是质数

由此猜想，对于一个三元组 (x,y,z)(x,y,z) 如果 x,yx,y 奇偶性相同，则可以找到一个奇偶性和 x,yx,y 不同的 zz，使得 x+z,y+zx+z,y+z 是奇数，用程序验证后发现可行

于是可以定义 dp[i][0/1/2/3]dp[i][0/1/2/3] 表示前 ii 个数

  • 00：没有修改当前数字
  • 11：把当前数字修改成一个不为 11 的奇数
  • 22：把当前数字修改成偶数
  • 33：把当前数字修改成 11

定义出来了，转移方程很容易也写出来了

# Code

#include <bits/stdc++.h>

constexpr int N = 1e5 + 5, V = 3e5 + 5;
constexpr int INF = 0x3f3f3f3f;

bool vis[V];

void init() {
    vis[1] = 1;
    for (int i = 2; i < V; i++) {
        for (int j = 2; i * j < V; j++)
            vis[i * j] = 1;
    }
}

bool is_prime(int x) {
    return !vis[x];
}

int dp[N][4];

int main() {
    freopen ("F.in", "r", stdin);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);
    init();

    int n; std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0; dp[1][1] = 1; dp[1][2] = 1; dp[1][3] = 1;
    for (int i = 2; i <= n; i++) {
        
        int tmp = INF;
        if (is_prime(a[i] + a[i - 1])) tmp = std::min(tmp, dp[i - 1][0]);
        if (a[i] % 2 == 1) tmp = std::min(tmp, dp[i - 1][2]);
        if (a[i] % 2 == 0) tmp = std::min(tmp, dp[i - 1][1]);
        if (is_prime(a[i] + 1)) tmp = std::min(tmp, dp[i - 1][3]);
        dp[i][0] = tmp;

        tmp = INF;
        if (a[i - 1] % 2 == 0) tmp = std::min(tmp, dp[i - 1][0] + 1);
        tmp = std::min(tmp, dp[i - 1][2] + 1);
        dp[i][1] = tmp;

        tmp = INF;
        if (a[i - 1] % 2 == 1) tmp = std::min(tmp, dp[i - 1][0] + 1);
        tmp = std::min(tmp, dp[i - 1][1] + 1);
        tmp = std::min(tmp, dp[i - 1][3] + 1);
        dp[i][2] = tmp;

        tmp = INF;
        if (is_prime(a[i - 1] + 1)) tmp = std::min(tmp, dp[i - 1][0] + 1);
        tmp = std::min(tmp, dp[i - 1][2] + 1);
        tmp = std::min(tmp, dp[i - 1][3] + 1);
        dp[i][3] = tmp;
    }
    int ans = std::min({dp[n][0], dp[n][1], dp[n][2], dp[n][3]});
    std::cout << ans << '\n';
    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
53
54
55
56
57
58
59
60
61
62
63

# G - Path

# Solution

签到题

# Code

#include <bits/stdc++.h>
#define int long long

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int ans = 0;
    int n, m; std::cin >> n >> m;
    std::vector<int> a(n), b(m);
    for (auto &x : a) std::cin >> x;
    for (auto &x : b) std::cin >> x;
    for (int i = 1; i < n; i++)
        ans += abs(a[i] - a[i - 1]);
    for (int i = 1; i < m; i++)
        ans += abs(b[i] - b[i - 1]);
    
    std::cout << ans << '\n';
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# J - Keyi LIkes Reading

# Solution

签到题

# Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5e4 + 5;
ll n, W, a[MAXN], c[15], f[9000], s[9000];
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> W;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        c[a[i] - 1] ++;
    }
    for(int S = 0; S < (1 << 13); S ++){
        for(int i = 0; i < 13; i ++){
            if((S >> i) & 1){
                s[S] += c[i];
            }
        }
    }
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for(int S = 0; S < (1 << 13); S ++){
        for(int S_ = 0; S_ < (1 << 13); S_ ++){
            if(((S_ | S) == S) && s[S_] <= W){
                f[S] = min(f[S], f[S - S_] + 1);
            }
        }
    }
    cout << f[(1 << 13) - 1] << "\n";
    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
上次更新: 2024/11/04, 07:55:26
CCPC2023 桂林站
CCPC2024 哈尔滨站 题解

← CCPC2024 哈尔滨站 题解→

最近更新
01
逻辑学
12-13
02
中华传统文化
12-12
03
欧拉回路
11-14
更多文章>
Theme by Vdoing | Copyright © 2024-2024 Martian148 | MIT License