526互联

AtCoder Begining Contest 297 VP报告

发布时间 2023-04-12 00:41:35作者: 叁纔

AtCoder Begining Contest 297 VP报告

写在前面：

前面靠手速抢了点分，B卡了一小会，然后E想的时间比较长，其他的题目基本上出的还算平均，感觉D题的思路很巧妙，因为最近一直在学数学有关的，出的还算快，感觉还不错吧，毕竟代码都不长不会写的很急。

A - Double Click

题干

高橋君は、時刻 \(0\) にパソコンの電源をつけ、それからマウスを \(N\) 回クリックしました。\(i(1≤i≤N)\) 回目のクリックは時刻 \(T_i\)に行われました。

高橋君が時刻 \(x_1\) と時刻 \(x_2\) (ただし\(x_1<x_2\))にマウスを連続してクリックしたとき、\(x_2−x_1≤D\) であれば時刻 \(x_2\) にダブルクリックが成立したと言います。

高橋君が最初にダブルクリックを成立させた時刻を求めてください。ただし、高橋君が \(1\) 回もダブルクリックを成立させていないならば -1 を出力してください。

解题思路

很明显作为一道abc的签到题，本题的玩法十分明显，求高橋君第一次双击成功的时刻。

所以只需要读入后依次判断差分与\(D\)的大小关系即可。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 110;

int a[N];

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i < n; ++i) {
        if (a[i] - a[i - 1] <= m) {
            cout << a[i];
            return;
        }
    }
    cout << -1;
}

int main() {
    ios;
    solve();
}

B - chess960

题干

長さ \(8\) の文字列 \(S\) が与えられます。\(S\) には K, Q がちょうど \(1\) 文字ずつ、R, B, N がちょうど \(2\) 文字ずつ含まれます。 \(S\) が以下の条件を全て満たしているか判定してください。

  • \(S\) において左から \(x,y (x<y)\) 文字目が B であるとする。このとき \(x\) と \(y\) の偶奇が異なる。
  • K は \(2\) つの R の間にある。より形式的には、\(S\) において左から\(x,y (x<y)\) 文字目が R であり、 \(z\) 文字目が K であるとする。このとき、 \(x<z<y\) が成り立つ。

解题思路

一开始看岔了，没注意到这里面每个字母给的都很齐全，限制也都足，制約中说了ちょうど１/２文字（恰好1/2个），卡了一小会，好在看样例发现了。主体操作实际上就是模拟题述的过程，由于长度限制为8，所以怎么玩都不会TLE，轻松水过。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 110;

int a[N];

void solve() {
    string s;
    cin >> s;
    int cnt = 0;
    bool flag = false;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == 'B') {
            a[cnt++] = i + 1;
        } else if (s[i] == 'K' && !flag) {
            cout << "No" << endl;
            return;
        } else if (s[i] == 'R') {
            flag = !flag;
        }
    }
    cout << ((a[0] & 1) ^ (a[1] & 1) ? "Yes" : "No") << endl;
}

int main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

C - PC on the Table

题干

\(H\) 個の長さ \(W\) の ., T からなる文字列 \(1,2,…,S_1,S_2,…,S_H\) が与えられます。

高橋君は以下の操作を 00 回以上何回でも行うことができます。

  • \(1≤i≤H,1≤j≤W−1\) を満たす整数であって、\(S_i\) の \(j\) 番目の文字も \(j+1\) 番目の文字も T であるようなものを選ぶ。 \(S_i\) の \(j\) 番目の文字を P で置き換え、\(S_i\) の \(j+1\) 番目の文字を C で置き換える。

高橋君が操作回数の最大化を目指すとき、操作終了後の \(S_1,S_2,…,S_H\) としてあり得るものの一例を出力してください。

解题思路

啥都说好了不就是模拟贪心了嘛，题目说了任何一个都行，而且每次操作都只会改变当前行，那么我们就可以按照唯一确定的方式去处理，也就是贪心处理每一行扫到的TT，按照题意转换即可。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 110;

char g[N][N];

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> g[i];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m - 1; ++j) {
            if (g[i][j] == 'T' && g[i][j + 1] == 'T') {
                g[i][j] = 'P';
                g[i][j + 1] = 'C';
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << g[i] << endl;
    }
}

int main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

D - Count Subtractions

题干

正整数 \(A,B\) が与えられます。

あなたは \(A=B\) になるまで以下の操作を繰り返します。

  • \(A,B\) の大小関係に応じて、次の \(2\) 個のうちどちらかの処理を行う。
    • \(A>B\) ならば、\(A\) を \(A−B\) で置き換える。
    • \(A<B\) ならば、\(B\) を \(B−A\) で置き換える。

\(A=B\) になるまで、操作を何回行うか求めてください。ただし、有限回の操作で \(A=B\) になることが保証されます。

解题思路

看起来很像模拟题？不妨再仔细看看，发现这个操作好眼熟啊。如果\(A\)比\(B\)大就把\(A\)变成\(A-B\)，否则把\(B\)变成\(B-A\)。仔细想想，这不就是更相减损术嘛，如果模拟这个过程，那么复杂度可能不允许我们通过所有样例。所以我们可以用欧几里得算法，也就是辗转相除法来替换题述的过程，这样相当于加法变成了乘法，可以大量降低复杂度。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 110;

void solve() {
    LL a, b;
    cin >> a >> b;
    if (a < b) swap(a, b);
    LL res = 0;
    while (true) {
        if (a == b) {
            cout << res << endl;
            return;
        } else if (!(a % b)) {
            res += a / b - 1;
            cout << res << endl;
            return;
        }
        res += a / b;
        a = a % b;
        if (a < b) swap(a, b);
    }
}

int main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

E - Kth Takoyaki Set

题干

AtCoder 王国では、\(N\) 種類のたこ焼きが売られています。\(i\) 種類目のたこ焼きの値段は \(A_i\) 円です。

高橋君は、合計で \(1\) 個以上のたこ焼きを買います。このとき、同じたこ焼きを複数個買うことも許されます。

高橋君が支払う金額としてあり得るもののうち、安い方から \(K\) 番目の金額を求めてください。ただし、同じ金額を支払う方法が複数存在する場合は \(1\) 回だけ数えます。

解题思路

今天才跟桑佬去吃了章鱼小丸子就遇到了这个题目，たこ焼き就是章鱼烧。虽然题目说的花里胡哨，但是内核其实很简单，就是说给了一堆数，确立一个集合，包含这几个数，以及他们其中任意项之和的闭集，由于这个集合对加法封闭，所以是一个无限集。我们既然不能完全确定集合，就需要在建立集合的时候完成输出工作并return，说到集合并且还要按照由小到大输出，那么很明显，set该上场了。接下来就是如何处理我们的set。有和有set，如果要取第\(k\)小，那么不妨把最小的弹出\(k\)次，这样最小的就是原来第\(k\)小的了。不过还有一个问题，我们该怎么保证弹出的最小值在之后的运算中依然是最小值呢。这其实很简单，因为是和闭集，我们只需要在创建的时候不断填入只会增大的部分即可。比如代码中使用了插入最小值和原数组每个值的和的方式，这样可以使得我们插入的元素尽可能小，不会出现erase的时候出现跳跃的情况。使用这个方法就可以在极短的代码中完成这一题啦。

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <set>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 110;

int cnt;
int a[N];
set<LL> st;

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    st.insert(0);
    while (cnt++ < k) {
        for (int i = 0; i < n; ++i) {
            st.insert(*st.begin() + a[i]);
        }
        st.erase(st.begin());
    }
    cout << *st.begin() << endl;
}

int main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}