Astria's Blog

主题

codeforces-round-805-div-3ac ​

A. Round Down the Price ​

题目大意 ​

Original Link

  • 对于一个数\(N\)，求其最接近且不大于该数的\(10^m\)
    • 输出\(N-10^m\)

思想 ​

  • 初始化p = 1e11，循环枚举p = p / 10直到p < n

代码 ​

cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

void solve() {
    LL n;
    cin >> n;

    LL p = 1e11;
    while (p > n) {
        p /= 10;
    }
    cout << n - p << endl;
}

int main() {
    int _;
    cin >> _;

    while (_--) {
        solve();
    }
    return 0;
}

B. Polycarp Writes a String from Memory ​

题目大意 ​

Original Link

  • 对于字符串\(S\)，每天只能遍历三个不同字母
    • 几天可以遍历完\(S\)

思想 ​

  • 模拟
    • vis[s[i]]记录s[i]是否为新字母，cnt记录当天的新字母的个数
    • 当cnt == 4说明要开始新的一天，并清空记忆

代码 ​

cpp
#include <bits/stdc++.h>
using namespace std;

void solve() {
    string s;
    cin >> s;

    int flag = 0;
    bool vis[300];
    memset(vis, 0, sizeof vis);

    int cnt = 0;
    for (int i = 0; i < s.size(); i++) {
        if (!vis[s[i]]) {
            cnt++;
            if (cnt == 4) {
                cnt = 1;
                flag++;
                memset(vis, 0, sizeof vis);
            }
            vis[s[i]] = 1;
        }
    }
    if (cnt) flag++;

    cout << flag << endl;
}

int main() {
    int _;
    cin >> _;

    while (_--) {
        solve();
    }
    return 0;
}

C. Train and Queries ​

题目大意 ​

Original Link

  • 顺次给定\(n\)个车站，先经过的车站可以走到后面的车站
    • 编号可能重复出现，即可能重复经过一个车站
    • 对于\(k\)次询问，给出起点和终点车站编号，求是否可以从起始站到终点站

思想 ​

  • map&lt;int,int&gt; l, r分别存储某一编号的站点最左边的下标和最右边的下标
    • 对于每次询问，若起始站的最左边的下标小于终点站的最右边的下标，则可行

代码 ​

cpp
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;

    map<int, int> l, r;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (l[x] == 0) {
            l[x] = r[x] = i;
        } else {
            l[x] = min(l[x], i);
            r[x] = max(r[x], i);
        }
    }

    while (m--) {
        int x, y;
        cin >> x >> y;
        if (l[x] != 0 && l[y] != 0) {
            if (l[x] < r[y])
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

int main() {
    int _;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}