Atcoder ABC413游记

atcoder尼干嘛哈哈哎呦

Atcoder ABC414游记(A~E)

A.Streamer Takahashi

题目描述

流媒体播放器 Takahashi 决定从 $L$ 点钟到 $R$ 点钟（使用 $24$ 小时钟）进行流媒体播放。

他有 $N$ 个听众，其中 $i$ 个听众可以收听 $X_i$ 点到 $Y_i$ 点的流媒体节目。

有多少听众可以从头到尾收听高桥的节目？

思路

高桥就是个流媒体播放器（（（怒怒怒

没错这个题面翻译来自deepl不代表本博客立场

水

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, l, r;
    cin >> n >> l >> r;
    int ans = 0;
    while (n--) {
        int x, y;
        cin >> x >> y;
        ans += (x <= l && y >= r);
    }
    cout << ans;
    return 0;
}

B.String Too Long

题目描述

给你 $N$ 对字符和 $(c_1,l_1),(c_2,l_2),\ldots,(c_N,l_N)$ 个整数。

假设 $S$ 是由 $l_1$ 个字符 $c_1$ 、 $l_2$ 个字符 $c_2$ 、 $\ldots$ 和 $l_N$ 个字符 $c_N$ 依次连接而成的字符串。

输出 $S$ 。但是，如果 $S$ 的长度超过 $100$ ，则输出 “Too Long”。

思路

水（忽略我这个小馋猫吃的那几发

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n;
    cin >> n;
    string ans;
    ans.clear();
    int cnt = 0;
    while (n--) {
        char s;
        int x;
        cin >> s >> x;
        if (cnt + x > 100) {
            cout << "Too Long";
            return 0;
        }
        cnt += x;
        while (x--) {
            ans = ans + s;
        }
    }
    cout << ans;
    return 0;
}

C. 死亡毒瘤Palindromic

题目描述

流媒体播放器给你一个正整数$A$和一个又大又恶心的正整数$N$。

你需要把不超过$N$的在$10$进制下和在$A$进制下的所有回文数加和并输出（（（

思路

Takahashi你个流媒体播放器（（（ 这题本来写的是正解一百多行代码调了我半个多小时 还没完我cph按照两秒的时限判发现过不了 想优化想了半个小时 想跳D了然后才发现时间限制是3秒（

然后你oj上给我跑出来才0.7s（（（

首先不难想到，我们可以先根据$N$计算这个回文串的最大长度，然后BF字符串的前半段，我们立马就可以确定后半段

然后得到全部的字符串后直接stoi（赛时忘记了这个STL啊啊啊啊）然后判断在$A$进制下是不是回文就可以了

但是还涉及一堆细节 比如前导零这种的 这些看代码 这就是这题难点（（（

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a, n;
int ans = 0;
bool check(int x)
{
    string tp;
    tp.clear();
    while (x) {
        tp += ((x % a) + '0');
        x /= a;
    }
    string ttp = tp;
    reverse(tp.begin(), tp.end());
    return ttp == tp;
}
int to10(string x)
{
    int res = 0;
    for (int i = 0; i < x.length(); i++) {
        res = (res * 10) + (x[i] - '0');
    }
    return res;
}
void dfs(string s, int x)
{
    if (x == -1) { 
        return;
    }
    string tp = s;
    reverse(tp.begin(), tp.end());
    string ttp = s + tp;
    int a = to10(ttp);
    if (a <= n && check(a)) {
        ans += a;
    }
    tp.erase(0, 1);
    ttp = s + tp;
    a = to10(ttp);
    if (a <= n && check(a)) {
        ans += a;
    }


    if (s.empty()) {
        for (char i = '1'; i <= '9'; i++) {
            dfs(s + i, x - 1);
        }
    } else {
        for (char i = '0'; i <= '9'; i++) {
            dfs(s + i, x - 1);
        }
    }
}
void solve(int x)
{
    string tp;
    tp.clear();
    dfs(tp, x);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> n;
    int tp = n, cnt = 0;
    while (tp) {
        cnt++;
        tp /= 10;
    }
    solve((cnt + 1) / 2);
    cout << ans;
    return 0;
}

D. Transmission Mission

题目描述

在一条数线上有 $N$ 座房子，编号从 $1$ 到 $N$ 。房子 $i$ 位于坐标 $X_i$ 。同一坐标上可能有多个房屋。

在数线上的任意实数坐标上放置 $M$ 基站。然后，为每个基站设置一个非负整数信号强度。

当基站的信号强度设置为 $x$ 时，当且仅当基站与房屋之间的距离最多为 $\displaystyle\frac{x}{2}$ 时，该基站的信号才能到达房屋。特别是当 $x=0$ 时，信号只能到达与基站位于同一坐标上的房屋。

求当基站的位置和信号强度设置为至少有一个基站的信号能到达每栋房屋时，可能的最小信号强度总和。

可以证明，对于任何满足约束条件的输入，答案都是整数。

思路

硬吃下一大坨恶心人的C题了 一看还剩40分钟 求心理阴影面积（（（

看到题的第一眼：二分答案啊 然后二分最大值写了半天发现$\text check$函数写不出来 然后发现只剩25分钟了

然后发现可以贪（（ 看相邻房子位置差即可

啊啊我为什么不会了 有二分答案的大佬做出来吗（（（直接登录github在下面喷我即可

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if (m == n) {
        cout << 0 << '\n';
        return 0;
    }
    sort(a.begin(), a.end());
    vector<int> b;
    for (int i = 1; i < n; i++) {
        b.push_back(a[i] - a[i - 1]);
    }
    sort(b.rbegin(), b.rend());
    int cnt1 = a.back() - a.front();
    int cnt2 = 0;
    for (int i = 0; i < m - 1; i++) {
        cnt2 += b[i];
    }
    cout << cnt1 - cnt2 << '\n';
    return 0;
}

E. Count A%B=C

题目描述

求满足以下条件的整数元组 $(a, b, c)$ 的个数，模数 $998244353$ 。

• $1 \leq a,b,c \leq N$
• $a,b,c$ 成对地不同。
• $a$ 除以 $b$ 的余数等于 $c$ 。

思路

很好 做完D已经还剩10分钟了 于是我直接暴力把前面的答案输出出来开始瞪眼 结果瞪不出来 想用OEIS又怕被喷（（（

于是还剩1分钟的时候我决定开始推式子 反正这场比赛注定掉分了

OEIS链接 用OEIS的都给我出来！！！！！

那我们来推式子把 我这种没怎么学数学的人没点手法都推不出来QAQ

首先根据题目说的，三个数不能相等，我们就能知道$A \not= B$，但是如果$A < B$那就会$A = C$，所以我们可以得到$A > B > C > 0$！！！

然后一瞪眼发现你直接算并不容易，我们可以考虑用所有的情况减去$a \mid b$的情况就可以了吧

然后我们可以枚举$b$来确定$a$吧

那我们就要求：

$\displaystyle \sum_{B=1}^{N}(N-B+1) -$ $\displaystyle \sum_{B=1}^{N} \left\lfloor \frac{N}{b} \right\rfloor$

这里这俩$(N-B+1)$和$\displaystyle \left\lfloor \frac{N}{B} \right\rfloor$原本是一个式子的，我把它们提出来了

那前面的这个式子不就是小学二年级都学过的等差数列求和，就是$\displaystyle \frac{N*(N+1)}{2}$，那后面的那个不就是可爱的数论分段吗！！！

那$\text O(\sqrt{N})$不就瞬秒了！！！

（真的是瞬秒，这里我推式子就只用20min，交那么晚是因为被烦人的cloudflare耽误了！！！不怪我！！！你们数学大佬和AIer们肯定更快）

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n;
int fastpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
signed main()
{
    cin >> n;
    int cnt = 0;
    for (int l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        int q = n / l;
        if (q <= n / q) {
            cnt = (cnt + ((r - l + 1) % mod) * (q % mod)) % mod;
        } else {
            for (int i = l; i <= r; ++i) {
                cnt = (cnt + (n / i) % mod) % mod;
            }
        }
    }

    int ans = 0;
    ans = (ans + (((n % mod) * ((n + 1) % mod)) % mod * fastpow(2, mod - 2)) % mod) % mod;
    ans = (ans - cnt) % mod;
    if (ans < 0) {
        ans += mod;
    }
    cout << ans;
    return 0;
}