首页 > 其他分享 >AtCoder Beginner Contest 中的小思维题

AtCoder Beginner Contest 中的小思维题

时间：2024-08-23 12:36:51浏览次数：8  
标签：AtCoder Beginner Contest int vi cin i64 i32 using

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;
}

标签：AtCoder,Beginner,Contest,int,vi,cin,i64,i32,using
From： https://www.cnblogs.com/PHarr/p/18375766

相关文章

  • AtCoder Beginner Contest 048
    A-AtCoder***Contest先输出首字母，然后遍历字符串，遇到空格就输出后面的第一个字符。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); strings; getline(cin,s); cout<<s[0];......
  • Atcoder Beginner Contest 365
    AtcoderBeginnerContest365A题意输入年份，输出该年份天数。思路略B题意输入一个序列，输出该序列次大值的位置。思路略C题意给定\(N\)，序列\(A\)和\(M\)。求满足下条件的\(x\)最大值。\[\sum_{i=1}^{n}\min(x,A_i)\leM\]思路式子左边有单调性，二分\(x\)......
  • AtCoder Beginner Contest 047
    A-FightingoverCandies简单排序。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); vector<int>a(3); cin>>a[0]>>a[1]>>a[2]; sort(a.begi......
  • AtCoder Beginner Contest 367
    A-ShoutEveryday思路：水题一道，模拟即可。B-Cut.0思路：直接cin和cout即可，c++输入输出性质。C-EnumerateSequences思路：注意到数据范围很小，因此考虑到搜素所有的序列，然后判断是否合法。D-Pedometer思路：观察到是环上问题，先断环为链，观察题目，可以发现，对于s,它的终......
  • AtCoder Beginner Contest 046
    A-AtCoDeerandPaintCans#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios::sync_with_stdio(false),cin.tie(nullptr); set<int>s; for(inti=0;i<3;i++){ intx; cin>>x; s.inser......
  • [AtCoder - tdpc_game] ：ゲーム 题解
    [AtCoder-tdpc_game]：ゲーム题解一道小清新\(dp\)题。定义\(dp_{i,j}\)为第一堆山还有\(i\)个物品，第二堆山还有\(j\)个物品，すぬけ君能取得物品的最大价值。由于只能取两座山最上面的物品，假设当前两座山分别有\({x,y}\)个物品，すぬけ君选后只能有两种情况，分别为\(d......
  • AtCoder ABC 367
    前言本题解部分思路来自于网络，仅供参考。A-ShoutEveryday题目大意给定Takahashi每天的睡觉时间和起床时间，求Takahashi在$A$时是睡着的还是清醒的。解题思路根据题意模拟即可。code#include<bits/stdc++.h>usingnamespacestd;intmain(){inta,b,c;......
  • AtCoder Beginner Contest 367
    题目链接：AtCoderBeginnerContest367总结：发挥很一般，A一直wa。开场有点事，导致D也没debug出来。A.ShoutEverydaytag：模拟Solution：注意\(B>C\)与\(B<C\)的不同情况即可。voidsolve(){  inta,b,c;  cin>>a>>b>>c;  if(c>b){    if(......
  • Atcoder [ABC367F] Rearrange Query 题解
    简要题意给定两个长度为\(N\)的序列\(A\)和\(B\)。有\(Q\)个查询，每个查询给定\(l,r,L,R\)，其中\(l\leqr,L\leqR\)，要求判断\(A\)的第\(l\)项到第\(r\)项构成的集合与\(B\)的第\(L\)项到第\(R\)项构成的集合是否相等。题解显然两个相等的集合所有元素......
  • Atcoder [ABC367C] Enumerate Sequences 题解
    简要题意给定\(n,k\)和\(R_i\)，你需要输出所有满足下列条件的整数序列：长度为\(n\)。第\(i\)个元素的范围为\([1,R_i]\)。一个序列的所有元素的总和为\(k\)的倍数。输出请按照按照从左至右按位从小到大的顺序输出。题解注意到数据范围很小，我们可以直接爆搜，这里用......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99