2024牛客寒假算法基础集训营2

A Tokitsukaze and Bracelet

签到

void solve() {
	k = 0;
	int a, b, c;
	cin >> a >> b >> c;
	if (a >= 150)k++;
	if (a >= 200)k++;
	if (b >= 34)k++;
	if (b >= 45)k++;
	if (c >= 34)k++;
	if (c >= 45)k++;
	cout << k << '\n';
}

B Tokitsukaze and Cats

TomiokapEace 想知道至少需要购买多少片防猫网才能使所有猫无法移动。

四周黑色边框即为防猫网。

将 $x, y$ 分别排序，如果 $x (y)$ 相等且另外一个坐标相差不超过 1 则可以省下一个网。

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> a(k), b(k);

    for (int i = 0; i < k; i++) {
        cin >> a[i].first >> a[i].second;
        b[i].first = a[i].second, b[i].second = a[i].first;
    }
    int count = k * 4;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i = 1; i < k; i++) {
        if (a[i].first == a[i - 1].first && a[i].second - a[i - 1].second == 1)count--;
        if (b[i].first == b[i - 1].first && b[i].second - b[i - 1].second == 1)count--;
    }

    cout << count << '\n';
}

E/F Tokitsukaze and Eliminate (easy)(hard)

初始有 $n$ 个宝石从左到右排成一排，第 $i$ 个宝石的颜色为 $c o l_{i}$ 。Tokitsukaze 可以进行若干次以下操作：

任选一种颜色 $x$ ，将颜色为 $x$ 的最右边那颗宝石、以及该宝石右边的所有宝石全部消除。

Tokitsukaze 想知道至少需要几次操作才能把 $n$ 个宝石全部消除。

easy: $1 \leq c o l_{i} \leq m i n (n, 2)$
hard: $1 \leq c o l_{i} \leq n$

GPT 使用了 multiset 可以使得删除操作可以在 $l o g n$ 复杂度，肯定不是正解 $\dots$

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    multiset<int> a1, a2;
    for (int i = 0;i < n;i++) {
        cin >> a[i];
        if (a[i] == 1)
            a1.insert(i);
        else if (a[i] == 2) a2.insert(i);
    }
    int ans = 0, dei = n;
    while (!a1.empty() && !a2.empty()) {
        dei = min(*a1.rbegin(), *a2.rbegin());
        auto it = a1.lower_bound(dei);
        while (it != a1.end()) {
            a1.erase(it++);
        }
        it = a2.lower_bound(dei);
        while (it != a2.end()) {
            a2.erase(it++);
        }
        ans++;
    }
    ans += (a1.size() > 0 ? a1.size() : a2.size());
    cout << ans << '\n';
}

(没看懂 $\dots$ )

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> is, c;

    for (int i = 0;i < n;i++) {
        cin >> a[i];
        is[a[i]]++;
    }
    int ans = 0;
    for (int i = n - 1;i >= 0;i--) {
        is[a[i]]--;
        c[a[i]]++;
        if (!is[a[i]]) {
            is.erase(a[i]);c.erase(a[i]);
        }
        if (is.size() == c.size()) {
            ans++;c.clear();
        }
    }
    cout << ans << '\n';
}

等题解..

I/J Tokitsukaze and Short Path (plus)(minus)

加和减的唯一区别是边权的计算方式。

Tokitsukaze 有一个 n 个顶点的完全图 G，顶点编号是 1 到 n，编号为 i 的顶点的值是 $a_{i}$ 。

完全图指的是每对顶点之间都恰好有一条无向边的图。对于顶点 u 和顶点 v 之间的无向边，边权计算方式如下：

$i f (u = v) w_{u, v} = 0, o t h e r w i s e, w_{u, v} =∣ a_{u} + a_{v} ∣ \pm ∣ a_{u} - a_{v} ∣$

定义 $d i s t (i, j$ )表示顶点 $i$ 为起点，顶点 $j$ 为终点的最短路。求 $\sum_{i = 1}^{n} \sum_{j = 1}^{n} d i s t (i, j)$

关于最短路的定义：

定义一条从 s 到 t 的路径为若干条首尾相接的边形成的序列且该序列的第一条边的起点为 s，最后一条边的终点为 t，特别的，当 s=t 时该序列可以为空。

定义一条从 s 到 t 的路径长度为该路径中边权的总和。

定义 s 到 t 的最短路为 s 到 t 所有路径长度中的最小值。

这题乍一看是图论，但是肯定不是用图论的方法做。

Solution

I (plus)

按照题意：

最短路径一定是与之相连的节点，若不是结果一定会变大
如果 a[u]>a[v} 则 $w_{i, j} + = 2 \times a [u]$ ,反之则 $w_{i, j} + = 2 \times a [v]$

若将数组排序后则 a[i]<=a[j] 恒成立，之后只需要加 2*a[j] 即可。

则答案形式：

for i (0, n - 1)
	for j (i + 1,n - 1)
		ans += 2 * a[j]
ans *= 2

$1, 2, 3, 4, \dots, n - 1 \to p r e [n - 1] - p r e [0]$
$2, 3, 4, \dots, n - 1 \to p r e [n - 1] - p r e [1]$
$3, 4, \dots, n - 1 \to p r e [n - 1] - p r e [2]$
$n - 1 \to p r e [n - 1] - p r e [n - 2]$

cnt = pre[n - 1]
for i (0, n - 2)
	ans += cnt - pre[i]

for(int i = 2, j = 1; i <= n; i ++, j ++)
	ans += w[i] * 2 * j;

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n), pre(n);
    ll r1 = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        r1 += a[i];
    }
    sort(a.begin(), a.end());
    pre[0] = a[0];
    for (int i = 1;i < n;i++) {
        pre[i] = pre[i - 1] + a[i];
    }

    ll ans = 0;
    for (int i = 1;i < n;i++) {
        ans += r1 - pre[i - 1];
    }
    cout << ans * 4 << '\n';
}

J (minus)

主要问题是找到最短路，只有两种可能：a[i-1] * 2 || 4 * a[0]

暴力做法：

ll ans = 2 * a[0] * (n - 1);

for (int i = 1;i < n;i++) {
	for (int j = i + 1;j < n;j++) {
		ans += min(2 * a[i], 4 * a[0]);
	}
}
cout << ans * 2 << '\n';

正解：

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

    sort(a.begin(), a.end());

    ll ans = 2 * a[0] * (n - 1);

    for (int i = 1;i < n;i++) {
        ans += min(2 * a[i], 4 * a[0]) * (n - i - 1);
    }
    cout << ans * 2 << '\n';
}

D Tokitsukaze and Slash Draw

Tokitsukaze 的卡组有 $n (1 \leq n \leq 5000)$ 张卡片，她已经知道「一击必杀！居合抽卡」这张卡片是在卡组中从最下面往上数的第 $k$ 张卡片。她挑选了 $m (1 \leq m \leq 1000)$ 种能够调整卡组中卡片顺序的卡片，第 $i$ 种类型的卡片效果是：把卡组最上方的 $a_{i}$ 张卡片拿出来按顺序放到卡组最下方。这个效果你可以理解为：首先将一张卡片拿出来，然后把这张卡片放到卡组最下方，这个动作重复做 $a_{i}$ 次。而发动第 $i$ 种类型的卡片效果，需要支付 $b_{i}$ 的 $cost$ 。

Tokitsukaze 可以通过一些操作使每种类型的卡片可以发动无限次，她是否能够让「一击必杀！居合抽卡」这张卡片出现在卡组的最上方？如果能，请输出最少需要支付的 $cost$ ，如果不能，请输出 -1。

Solution

DP | dijkstra (同余最短路模型)

$d p [x] = min (d p [x], d p [(x + a_{i}) % n] + b_{i})$

D_哔哩哔哩_bilibili

$m n_{i}$ 表示在 mod n 条件下目标卡片向上移动 $i$ 步的最小 $cost$

(没看懂 $\dots$ )

const int maxn = 3e5 + 10;
int a[maxn], b[maxn];
ll mn[maxn], dp[5010][5010];
void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++) {
        mn[i] = 1e18;
    }

    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        for (int j = 1; j <= n; j++) {
            int nxt = j * a[i] % n;//表示a[i]的倍数都可以翻
            if (!nxt) nxt = n; //可以注释掉？
            mn[nxt] = min(mn[nxt], 1ll * j * b[i]);//表示a[i]的倍数时的cost
        }
    }

    for (int i = 1; i <= n; i++) {
        if (i == k) {
            dp[0][i] = 0;
        } else {
            dp[0][i] = 1e18;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];
        }

        for (int j = 1; j <= n; j++) {
            int nxt = (j + i) % n;
            if (!nxt) nxt = n;
            dp[i][nxt] = min(dp[i][nxt], dp[i - 1][j] + mn[i]);
        }
    }

    if (dp[n][n] == 1e18) {
        cout << -1 << '\n';
    } else {
        cout << dp[n][n] << '\n';
    }
}

【持续更新】2024牛客寒假算法基础集训营2 题解 | JorbanS - 知乎

 int n, m, k, a[N], b[N];
 ll f[N];
 
 ll solve() {
     cin >> n >> m >> k;
     for (int i = 0; i < m; i ++) cin >> a[i] >> b[i];
     memset(f, -1, sizeof f);
     f[k - 1] = 0;
     queue<int> q;
     q.push(k - 1);
     while (!q.empty()) {
         auto u = q.front();
         q.pop();
         for (int i = 0; i < m; i ++) {
             int v = (u + a[i]) % n;
             if (f[v] != -1 && f[v] <= f[u] + b[i]) continue;
             f[v] = f[u] + b[i];
             q.push(v);
         }
     }
     return f[n - 1];
 }

D_哔哩哔哩_bilibili

$d p [x] = min (d p [x], d p [(x + a_{i}) % n] + b_{i})$

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(m+1), b(m+1), d(n+1, INTMAX_MAX);
    vector<bool> vis(n+1, 0);
    for (int i = 1;i <= m;i++)cin >> a[i] >> b[i];
    priority_queue<pair<ll, ll>> q;
    q.push({ 0,0 });
    d[0] = 0;
    while (q.size()) {
        ll u = q.top().second; q.pop();
        if (vis[u])continue;
        vis[u] = true;
        for (int i = 1;i <= m;i++) {
            ll v = (u + a[i]) % n;
            if (d[v] > d[u] + b[i]) {
                d[v] = d[u] + b[i];
                if (!vis[v])q.push({ -d[v], v });
            }
        }
    }
    if (d[n - k] == INTMAX_MAX)d[n - k] = -1;
    cout << d[n - k] << '\n';
}

K/L/M Tokitsukaze and Password (easy)

Tokitsukaze 在古老的遗迹中找到一张破旧的卷轴，上面写着的一串长度为 n 的数字正是打开遗迹深处宝箱的密码。虽然卷轴上的一些数字已经模糊不清，但 Tokitsukaze 可以根据从世界各地打听到关于密码的情报来还原出真正的密码。令密码为整数 x，情报如下：

情报 1. $x$ 没有前导 $0$ 。
情报 2. $x$ 是 $8$ 的倍数。
情报 3. 密码 x 满足 $x \leq y$ 。
情报 4. 对于相同的字母，密码不能是不同的字母，反之，不同的字母不能是相同的密码(对于 _ 无限制)。

现在 Tokitsukaze 想要根据已有情报暴力破解密码，她想尝试所有可能的密码。她告诉你标记后的字符串 s，以及整数 y，请你告诉她有多少种不同的密码 $(\mod 10^{9} + 7)$ 。

easy: $1 \leq T \leq 100, 1 \leq n \leq 9$
hard: $1 \leq T \leq 10000, 1 \leq n \leq 2 \times 10^{5}$
(题目有变) EX: $1 \leq T \leq 10000, 1 \leq k \leq 2 \times 10^{5}, 1 \leq q \leq 10^{4}$

Solution

这题的数据范围很小，肯定就是暴力，关键是暴力如何写 $\dots$

bfs(很麻烦) 或者 6 层循环暴力

我连暴力都不会

void solve() {
    int n;
    string s;
    ll y;
    cin >> n >> s >> y;
    set<ll> ans;
    for (int a = 0; a <= 9; a++)
        for (int b = 0; b <= 9; b++)
            for (int c = 0; c <= 9; c++)
                for (int d = 0; d <= 9; d++)
                    for (int _ = 0; _ <= 9; _++) {
                        if (a == b || a == c || a == d || b == c || b == d || c == d)continue;//a,b,c,d不相同
                        int x = 0;
                        for (auto i : s) {
                            if (i == 'a') x = x * 10 + a;
                            if (i == 'b') x = x * 10 + b;
                            if (i == 'c') x = x * 10 + c;
                            if (i == 'd') x = x * 10 + d;
                            if (i == '_') x = x * 10 + _;
                            if (isdigit(i))
                                x = x * 10 + i - '0';
                        }
                        if (to_string(x).size() == n && x <= y && x % 8 == 0)ans.insert(x);
                    }
    cout << ans.size() % mod << '\n';
}

C Tokitsukaze and Min-Max XOR

Tokitsukaze 有一个长度为 $n$ 的序列 $a$ 和一个 $k$ $(0 \leq a_{i}, k \leq 10^{9}, 1 \leq n \leq 2 \times 10^{5})$

有多少种递增( $b_{i - 1} < b_{i}$ )序列 $b$ 满足：

$1 \leq b_{i} \leq n$
$min (a_{b_{1}}, a_{b_{2}}, \dots, a_{b_{m}}) \oplus max (a_{b_{1}}, a_{b_{2}}, \dots, a_{b_{m}}) \leq k$

输出答案 $\mod 10^{9} + 7$

Solution

01 trie (01字典树)+逆元 (待更 $\dots$ )

(PS: $\oplus$ 记得加括号，不然容易出错)

选定一个 a[i] | a[j] 作为最小值与最大值，则在 [i,j] 之间的数字可以任意选择，即： $2^{j - i - 1}$

当 i==j 时，这时最大值和最小值为同一个数，也算是一种选择。

sort(a)
for i(0, n - 1)
	for j(i + 1, n - 1)
		if (a[i] ^ a[j]) <= k
			ans += 2 ^ (j - i - 1)
ans += n # i==j: ans++

这样做肯定是过不了的，需要在小于 $O (n^{2})$ 的情况下快速枚举 a[i],a[j]

【题目讲解】2024牛客寒假算法基础集训营2 讲题上半场_哔哩哔哩_bilibili

G/H Tokitsukaze and Power Battle (easy)(hard)

easy | hard 区别是 $a_{i}$ 和 $y$ 的范围。
easy: $0 \leq a_{i}, y \leq 10^{9}$
hard: $- 10^{9} \leq a_{i}, y \leq 10^{9}$

数组的 $n$ 个整数为 $a_{1}, a_{2}, \dots, a_{n}$ 。

q 次操作分别为：

1 x y 将第 $x$ 个数字 $a_{x}$ 修改为 $y$ 。
2 l r 在 $[l, r]$ 中选择一段 $[i, j]$ ，然后选择一个切断点 $x$ 将铁分成 $[i, x]$ 和 $[x + 1, j]$ 两段。

Tokitsukaze 获得第一段，对手获得第二段。之后他们把获得的铁锻造成剑，剑的力量为区间上的数字之和。Tokitsukaze 想知道她锻造出的剑与对手的剑的力量的差值最大是多少。注意：Tokitsukaze 与对手必须一人一段，不能全拿也不能全给对手。

对于每个操作 2，输出一个整数，表示 Tokitsukaze 锻造出的剑与对手的剑最大力量差值。

线段树 (待更 $\dots$ )