Atcoder ABC397游记

Atcoder ABC397游记（A~D）

A.Thermometer

题目描述

诗音测量到她的体温是$X$摄氏度。

体温由以下几条规则进行分类：

• 高于$38.0$摄氏度：高烧

• 高于或等于$37.5$摄氏度，并且低于$38.0$摄氏度：低烧

• 低于$37.5$摄氏度：健康

所以诗音的体温应该是哪个等级？

思路

水

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    double n;
    cin >> n;
    if (n >= 38) {
        cout << 1;
    } else if (n >= 37.5) {
        cout << 2;
    } else {
        cout << 3;
    }
    return 0;
}

B.Ticket Gate Log

题目描述

给你一个字符串$S$，包含字符i和o。诗音想要往字符串里加入尽可能少的字符，让字符串满足下面的条件：

• 字符串的长度为$N$为偶数，并且对于所有$1 \leq i \leq \frac{N}{2}$满足$S_i=$i且$S_{i+1}=$o。

思路

水

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int cnt = 0;
    char q = 'i';
    int ans = 0;
    int n = s.length();
    while (cnt < n) {
        if (s[cnt] == q) {
            cnt++;
            q = (q == 'i') ? 'o' : 'i';
        } else {
            ans++;
            q = (q == 'i') ? 'o' : 'i';
        }
    }
    int tot = n + ans;
    if (tot % 2 != 0) {
        ans++;
    }
    cout << ans;
    return 0;
}

C.Variety Split Easy

题目描述

给你个长度为$N$的整数数组$A=(A_1,A_2, \dots , A_N)$。

你需要把$A$划分成两个非空部分，而且应该连续，并且要使这两个部分不同的数的数量和最大。

输出这个最大值。

思路

你看这个数据范围，如果直接BF肯定挂掉。

那我们就得动动脑子了，我们可以维护两个数组，分别对应了前后缀在当前下标的不同元素数量。

我们对于前后缀处理的时候可以分别维护一个unordered_map来记录元素是否出现，如果出现了就是前一个元素$+1$。

那最后我们枚举分割点取最大值，当前分割点$i$的答案就是前缀数组的第$i$个元素$+$后缀数组的第$i+1$个元素了。

说了这么半天好像也不难啊

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    vector<int> pre(n + 1, 0);
    unordered_map<int, int> cntp;
    for (int i = 1; i <= n; ++i) {
        if (cntp.find(a[i]) == cntp.end()) {
            cntp[a[i]] = 1;
            pre[i] = pre[i - 1] + 1;
        } else {
            pre[i] = pre[i - 1];
        }
    }
    vector<int> s(n + 2, 0);
    unordered_map<int, int> cnts;
    for (int i = n; i >= 1; --i) {
        if (cnts.find(a[i]) == cnts.end()) {
            cnts[a[i]] = 1;
            s[i] = s[i + 1] + 1;
        } else {
            s[i] = s[i + 1];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n - 1; ++i) {
        int now = pre[i] + s[i + 1];
        if (now > ans) {
            ans = now;
        }
    }
    cout << ans;
    return 0;
}

D.Cubes

题目描述

给你一个正整数$N$，给出关于$x$和$y$的不定方程$x^3-y^3=N$的正整数解，如果无解就输出-1。

思路

啊哈，数学不好的oier要吃亏了

这怎么分析呢，只能玩一下这个式子了。

为了防止乐子抬杠，我会用稍微严格一点的证法。

首先根据题目的条件我们可以得到$x^3=N+y^3$，因为这三坨东西都是正整数，所以可以得到$x>y$。

$\because N \in \mathbb{N}$

$\therefore N \leq 1$

$ \Rightarrow x$至少比$y$大$1$。

$\therefore x^3 - y^3 > (y+1)^3 - y^3 = 3y² + 3y + 1$

假设存在解 $(x,y)$，则：

$y^3 < x^3 = y^3 + N$
$ \quad \Rightarrow \quad y^3 < N + y^3$

当 $y$ 超过 $\sqrt[3]{N}$ 时，$y^3$ 本身已经远大于 $N$，此时不等式的条件不可能满足。因此，$y$ 的上界必然 $\leq \sqrt[3]{N} $。

说了这么多又大又臭的式子，就是为了减小我们的枚举范围，上面得出的结论就是让我们把$y$的枚举范围缩小到了1e6，因为$N$最大到1e18。那这道题不就简单了！！！

这里放的是赛时代码，我以为开ll就够了，没想到还会WA，于是脑袋一热开了int128，别喷我QAQ

代码

#include<bits/stdc++.h>
using namespace std;
#define int __int128
signed main()
{
    long long _n;
    cin >> _n;
    int n = _n;
    int mx = 0;
    int l = 1, r = 2e7;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (mid * mid * mid <= 4 * n) {
            mx = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    bool flag = false;
    int x, y;
    for (int a = 1; a <= mx; a++) {
        if (n % a != 0) {
            continue;
        }
        int b = n / a;
        int d = -3 * a * a + 12 * b;
        if (d < 0) {
            continue;
        }
        int sqrtd = sqrt((unsigned long long)d);
        if (sqrtd * sqrtd != d) {
            continue;
        }
        int num = -3 * a + sqrtd;
        if (num <= 0 || num % 6 != 0) {
            continue;
        }
        y = num / 6;
        if (y <= 0) {
            continue;
        }
        x = a + y;
        if (x * x * x - y * y * y == n) {
            flag = true;
            break;
        }
    }
    if (flag) {
        unsigned long long _x = x, _y = y;
        cout << _x << ' ' << _y;
    } else {
        cout << -1;
    }
    return 0;
}

总结

嘿嘿嘿哈