AtCoder Beginner Contest 中的小思维题

PHarr / 2024-08-24 / 原文

078D

https://atcoder.jp/contests/abc078/tasks/arc085_b

问题陈述

我们有一副由 $N$ 张牌组成的扑克牌。每张牌上都写着一个整数。从最上面开始的第 $i$ 张牌上的整数是 $a _ i$ 。

两个人 X 和 Y 将用这副扑克牌玩一个游戏。最初，X 手中有一张写有 $Z$ 的牌，Y 手中有一张写有 $W$ 的牌。然后，从 X 开始，他们将交替进行以下操作：

从牌顶抽若干张牌。然后，丢弃手中的牌，保留最后抽出的牌。这里至少要抽出一张牌。

当牌组中没有牌时，游戏结束。游戏的得分是两位玩家手中牌上所写整数的绝对差值。

X 玩游戏的目的是使得分最大，而 Y 玩游戏的目的是使得分最小。游戏的得分是多少？

思路

其实可以想到就是，X 能拿到的只有倒数第二个或者倒数第一个，因为如果 X 选择了中间的任何一个，Y 的都可以剩下一些更差迫使 X 丢弃当前选择的。所以考虑一下选择哪一个更有就好了。要特判一下就是如果 $n=1$ 则只能选择倒数一个。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

using vi = vector<int>;

i32 main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int n, z, w;
	cin >> n >> z >> w;
	vi a(n + 1);
	for(int i = 1; i <= n; i ++) cin >> a[i];
	if(n == 1){
		cout << abs(a[n] - w);
	}else {
		cout << max(abs(a[n] - a[n-1]), abs(a[n] - w)); 
	}
	return 0; 
}

091C

贪心

把红色点从小到大排序，蓝色点从大到小排序，然后对于每个红色点，找到所有满足的蓝色点中 $y$ 最小的。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pii> a(n), b(n);
    for (auto &[x, y]: a) cin >> x >> y;
    for (auto &[x, y]: b) cin >> x >> y;
    sort(a.begin(), a.end(), greater<>());
    sort(b.begin(), b.end());
    vi vis(n);
    for (auto &[ax, ay]: a) {
        int p = -1;
        for (int j = 0; j < n; j++) {
            if (vis[j]) continue;
            if (b[j].first <= ax or b[j].second <= ay) continue;
            if (p == -1) p = j;
            else if (p != -1 and b[j].second < b[p].second) p = j;
        }
        if (p != -1) vis[p] = 1;
    }
    cout << accumulate(vis.begin(), vis.end(), 0ll);
    return 0;
}

二分图最大匹配

直接上匈牙利算法

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9;

vector<vi> e;
vector<bool> vis;
vi p;
int n;

bool match(int x) {
    for (auto y: e[x]) {
        if (vis[y]) continue;
        vis[y] = 1;
        if (p[y] == 0 or match(p[y])) {
            p[y] = x;
            return true;
        }
    }
    return false;
}

int Hungarian() {
    int cnt = 0;
    p.resize(n + n + 1);
    for (int i = 1; i <= n; i++) {
        vis = vector<bool>(n + n + 1);
        if (match(i)) cnt++;
    }
    return cnt;
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n;
    vector<pii> a(n + n + 1);
    for (int i = 1; i <= n + n; i++) cin >> a[i].first >> a[i].second;
    e.resize(n + n + 1);
    for (int i = 1; i <= n; i++)
        for (int j = n + 1; j <= n + n; j++)
            if (a[i].first < a[j].first and a[i].second < a[j].second)
                e[i].push_back(j), e[j].push_back(i);

    cout << Hungarian() << "\n";
    return 0;
}

067D

两个人的最优策略都是优先占领 1 到 n 路径上的点，因为被占领的点，其子树也不能被占领。最后统计一下每个人最多可以占领多少个，比较一下即可。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;
using pii = pair<int, int>;

const int inf = 1e9;


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vi> e(n + 1);
    for (int i = 1, x, y; i < n; i++)
        cin >> x >> y, e[x].push_back(y), e[y].push_back(x);

    vi dis1(n + 1, inf);
    dis1[1] = 0;
    queue<int> q;
    q.push(1);
    while (not q.empty()) {
        int x = q.front();
        q.pop();
        for (auto y: e[x]) {
            if (dis1[y] < dis1[x] + 1) continue;
            dis1[y] = dis1[x] + 1, q.push(y);
        }
    }

    vi dis2(n + 1, inf);
    dis2[n] = 0;
    q.push(n);
    while (not q.empty()) {
        int x = q.front();
        q.pop();
        for (auto y: e[x]) {
            if (dis2[y] < dis2[x] + 1) continue;
            dis2[y] = dis2[x] + 1, q.push(y);
        }
    }

    vi color(n + 1);
    queue<int> q1, q2;
    for (int i = 1; i <= n; i++) {
        if (dis1[i] + dis2[i] != dis1[n]) continue;
        if (dis1[i] <= dis2[i]) q1.push(i);
        else q2.push(i), color[i] = 2;
    }
    while (not q1.empty()) {
        int x = q1.front();
        q1.pop();
        for (auto y: e[x]) {
            if (color[y]) continue;
            color[y] = 1, q1.push(y);
        }
    }
    while (not q2.empty()) {
        int x = q2.front();
        q2.pop();
        for (auto y: e[x]) {
            if (color[y]) continue;
            color[y] = 2, q2.push(y);
        }
    }
    vi cnt(3);
    for (int i = 1; i <= n; i++)
        cnt[color[i]]++;
    if (cnt[1] > cnt[2]) cout << "Fennec";
    else cout << "Snuke";
    return 0;
}

123D

虽然枚举的种类是 $10^9$ 但是注意到 $k$ 最大是 $3000$，因此可以暴力枚举 $A,B$ 然后取前 $K$ 个，然后再暴力枚举即可。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;

const int inf = 1e9;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int x, y, z, k;
    cin >> x >> y >> z>> k;
    vi a(x), b(y), c(z);
    for (auto &i: a) cin >> i;
    for (auto &i: b) cin >> i;
    for (auto &i: c) cin >> i;
    vi ab;
    for (const auto &ai: a)
        for (const auto &bi: b)
            ab.push_back(ai + bi);
    sort(ab.begin(), ab.end() , greater<>());
    ab.resize(min((int) ab.size(), k));
    vi abc;
    for (const auto &abi: ab)
        for (const auto &ci: c)
            abc.push_back(abi + ci);
    sort(abc.begin(), abc.end(), greater<>());
    abc.resize(min((int) abc.size(), k));
    for(const auto abci : abc) cout << abci << "\n";
    return 0;
}

046D

可以想到的是能出布就出布，因为出布不会减分，但是出石头可能会减分。所以出的顺序应该是 gpgpgp

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

using vi = vector<int>;

i32 main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	string s;
	cin >> s;
	int res = 0;
	for(int i = 1; i < s.size(); i += 2)
		res += (s[i] == 'g');
	for(int i = 0; i < s.size(); i += 2)
		res -= (s[i] == 'p');
	cout << res;
	return 0; 
}

096D

考虑只选择个位为 $1$ 的质数，这样的话五个数的和一定为 $5$ 的倍数。

#include <bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;
using i128 = __int128;

#define int i64

using vi = vector<int>;

bool isPrime(int x){
	if(x < 2) return false;
	for(int i = 2; i * i <= x; i ++)
		if(x % i == 0) return false;
	return true;
}

i32 main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int n;
	cin >> n;
	for(int i = 1; n > 0; i += 10)
		if(isPrime(i)) cout << i << " ", n --;
	return 0; 
}

占位

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d

204D

https://atcoder.jp/contests/abc204/tasks/abc204_d

令 $m = \sum T_i$

设 dp 的状态转移方程为 $f[i][j]$ 表示前 $i$ 个菜肴，占用第一个烤箱时长为 $j$ 的方案是否存在。

这样的话直接 $O(nm)$ 的枚举转移就好了

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> T(N);
  for (int i = 0; i < N; i++){
    cin >> T[i];
  }
  int S = 0;
  for (int i = 0; i < N; i++){
    S += T[i];
  }
  vector<vector<bool>> dp(N + 1, vector<bool>(S + 1, false));
  dp[0][0] = true;
  for (int i = 0; i < N; i++){
    for (int j = 0; j <= S; j++){
      if (dp[i][j]){
        dp[i + 1][j] = true;
        dp[i + 1][j + T[i]] = true;
      }
    }
  }
  int ans = S;
  for (int i = 0; i <= S; i++){
    if (dp[N][i]){
      ans = min(ans, max(i, S - i));
    }
  }
  cout << ans << endl;
}

但是我们注意到对于任意一个 $j$ 满足 $f[i][j]$ 成立，则一定会有 $f[i+1][j + T_{i+1}]$ 成立。如果吧 $f[i]$ 看成一个二进制数，则相当于左移 $T_{i+1}$ 位，这样的话，我们可以是用 bitset 快速求解。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;

const int M = 1e5;
bitset<M + 1> f;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m = 0;
    cin >> n;
    f[0] = true;

    for (int i = 1, t; i <= n; i++) {
        cin >> t;
        m += t;
        f |= (f << t);
    }

    int res = INT_MAX;
    for (int i = 0; i <= m; i++)
        if (f[i]) res = min(res, max(i, m - i));
    cout << res;

    return 0;
}

207E

https://atcoder.jp/contests/abc207/tasks/abc207_e

令 $f[i][j]$ 表示分成 $i$ 段的情况下前 $j$ 个元素的方案数。可以得到一个 $O(n^3)$ 的转移如下

\[f[i][j] = \sum_{k = 0}^{j-1}f[i-1][k] \times ( sum(k + 1 , j) \equiv 0 \mod{i}) \]

然后 $sum(k + 1 , j) \equiv 0 \mod{i}$ 等价与 $\sum(1,j) \equiv \sum(1,k) \mod i$

因此我们其实可以用 $i$ 个前缀和计算出转移

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;

#define int i64

using vi = vector<int>;

const int mod = 1e9 + 7;

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;

    vi a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i], a[i] += a[i - 1];

    vector f(n + 1, vi(n + 1));
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        vector<int> cnt(i);
        cnt[0] = f[i - 1][0];
        for (int j = 1; j <= n; j++)
            f[i][j] = cnt[a[j] % i], (cnt[a[j] % i] += f[i - 1][j]) %= mod;
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
        res = (res + f[i][n]) % mod;
    cout << res;

    return 0;
}

074C

https://atcoder.jp/contests/abc074/tasks/arc083_a

一个满有意思的枚举题。看似是 dp 但实际上估计范围后，发现枚举复杂度是正确的。

#include<bits/stdc++.h>

using namespace std;


using i32 = int32_t;
using i64 = long long;

#define int i64

const int inf = INT_MAX / 2;

i32 main() {
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;
    A *= 100, B *= 100;

    int x = 1, y = 0;
    for (int i = 0; A * i <= F; i++)
        for (int j = 0; A * i + B * j <= F; j++) {
            int p = A * i + B * j, q = 0;
            if (p == 0) continue;
            int T = min(F - p, p * E / 100);
            for (int k = 0, l; k * C <= T; k++) {
                l = (T - k * C) / D;
                q = max(q, k * C + l * D);
            }
            if (x + y != 0 and q * x > y * (p + q)) x = p + q, y = q;
        }
    if (y == 0) cout << A << " 0";
    else cout << x << " " << y;

    return 0;
}