• Codeforces Round #834 (Div. 3) A-G


    比赛链接

    A

    题目

    知识点:模拟。

    确定开头字母,然后循环比较即可。

    时间复杂度 \(O(n)\)

    空间复杂度 \(O(n)\)

    题解

    #include
    #define ll long long
    using namespace std;
    bool solve() {
    string s;
    cin >> s;
    string t = "Yes";
    int pos = -1;
    if (s[0] == t[0]) pos = 0;
    else if (s[0] == t[1]) pos = 1;
    else if (s[0] == t[2]) pos = 2;
    else return false;
    for (auto ch : s) {
    if (ch != t[pos]) return false;
    pos = (pos + 1) % 3;
    }
    cout << "YES" << '\n';
    return true;
    }
    int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
    if (!solve()) cout << "NO" << '\n';
    }
    return 0;
    }

    B

    题目

    知识点:枚举。

    找到总和等于 \(sum + s\) 的排列,其中 \(sum\) 是原来序列的和。这个排列的最大数字不能小于原来序列里的最大数字,否则不合法。

    时间复杂度 \(O(n)\)

    空间复杂度 \(O(1)\)

    题解

    #include
    #define ll long long
    using namespace std;
    bool solve() {
    int m, s;
    cin >> m >> s;
    int mx = 0, sum = 0;
    for (int i = 1;i <= m;i++) {
    int x;
    cin >> x;
    sum += x;
    mx = max(x, mx);
    }
    int ans = -1;
    for (int i = 1;i <= 70;i++) {
    if (i * (i + 1) / 2 == sum + s) {
    ans = i;
    break;
    }
    }
    if (ans >= mx) cout << "YES" << '\n';
    else cout << "NO" << '\n';
    return true;
    }
    int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
    if (!solve()) cout << -1 << '\n';
    }
    return 0;
    }

    C

    题目

    知识点:贪心。

    分类讨论:

    1. \(a=b\) ,不用操作。
    2. \(|a-b|\geq x\) ,一次操作。
    3. 先将 \(a\)\(l\) (或 \(r\) ),再将 \(l\) (或 \(r\) )变成 \(x\) ,两次操作(如果可以的话)。
    4. 先将 \(a\)\(l\) (或 \(r\) ),再将 \(l\) (或 \(r\) )变成 \(r\) (或 \(l\) ),再将 \(r\) (或 \(l\) )变成 \(x\) ,三次操作(如果可以的话)。
    5. 无解,因为 \(a\) 变换到 \(l\)\(r\) 将会拥有与 \(b\) 的最大距离,再不行就无解。

    时间复杂度 \(O(1)\)

    空间复杂度 \(O(1)\)

    题解

    #include
    #define ll long long
    using namespace std;
    bool solve() {
    int l, r, x;
    int a, b;
    cin >> l >> r >> x;
    cin >> a >> b;
    if (a == b) cout << 0 << '\n';
    else if (abs(a - b) >= x) cout << 1 << '\n';
    else if (a - l >= x && b - l >= x || r - a >= x && r - b >= x) cout << 2 << '\n';
    else if (a - l >= x && r - l >= x && r - b >= x || r - a >= x && r - l >= x && b - l >= x) cout << 3 << '\n';
    else cout << -1 << '\n';
    return true;
    }
    int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
    if (!solve()) cout << -1 << '\n';
    }
    return 0;
    }

    D

    题目

    知识点:数论,贪心。

    显然尽可能配对 \(2\)\(5\) 因子,随后尽可能乘 \(10\)

    先找到 \(n\) 中已有的 \(2\)\(5\)因子数量,然后先用 \(mul\) 配平因子数(这样操作的得到的 \(mul\) 最小)。

    之后,给 \(mul\)\(10\) 直到再次操作会超过 \(m\)

    最后把 \(mul\) 加倍到最大值 \(m\) 内最大值。

    时间复杂度 \(O(\log n + \log m)\)

    空间复杂度 \(O(1)\)

    题解

    #include
    #define ll long long
    using namespace std;
    bool solve() {
    int n, m;
    cin >> n >> m;
    int t = n;
    int c2 = 0, c5 = 0;
    while (t % 2 == 0) t /= 2, c2++;
    while (t % 5 == 0) t /= 5, c5++;
    int mul = 1;
    while (c2 < c5 && mul * 2LL <= m) mul *= 2, c2++;
    while (c2 > c5 && mul * 5LL <= m) mul *= 5, c5++;
    while (mul * 10LL <= m) mul *= 10;
    cout << 1LL * n * (m / mul) * mul << '\n';
    return true;
    }
    int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
    if (!solve()) cout << -1 << '\n';
    }
    return 0;
    }

    E

    题目

    显然贪心策略是从小到大吸收,考虑道具使用顺序。

    方法一

    知识点:枚举,dfs。

    只有三个道具,直接搜索所有使用顺序即可,每次先把能吸收的吸收了。

    时间复杂度 \(O(n)\)

    空间复杂度 \(O(n)\)

    方法二

    知识点:线性dp。

    \(dp[i][j][k]\) 表示吸收了前 \(i\) 个人, \(2\) 倍道具剩 \(j\) 个, \(3\) 倍道具剩 \(k\) 个的最大能量。

    转移时,先从吸收了 \(i-1\) 个人的状态转移到吸收了 \(i\) 个人的状态,再考虑吸收了 \(i\) 个人的状态后使用道具的情况。

    使用道具时的转移不需要考虑转移顺序。某个状态被其他的状态更新后,再使用道具的状态一定会被更新他的状态包括,因此不需要考虑更新顺序。

    时间复杂度 \(O(n)\)

    空间复杂度 \(O(n)\)

    题解

    方法一

    #include
    #define ll long long
    using namespace std;
    int n;
    int a[200007];
    int dfs(int pos, int cntg, int cntb, ll h) {
    while (pos <= n && h > a[pos]) h += a[pos++] / 2;
    int mx = pos - 1;
    if (cntg >= 1) mx = max(mx, dfs(pos, cntg - 1, cntb, h * 2));
    if (cntb >= 1) mx = max(mx, dfs(pos, cntg, cntb - 1, h * 3));
    return mx;
    }
    bool solve() {
    int h;
    cin >> n >> h;
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    cout << dfs(1, 2, 1, h) << '\n';
    return true;
    }
    int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
    if (!solve()) cout << -1 << '\n';
    }
    return 0;
    }

    方法二

    #include
    #define ll long long
    using namespace std;
    int a[200007];
    ll f[200007][3][2];
    bool solve() {
    int n, h;
    cin >> n >> h;
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1;i <= n;i++)
    for (int j = 0;j <= 2;j++)
    for (int k = 0;k <= 1;k++)
    f[i][j][k] = 0;
    f[0][2][1] = h;
    f[0][1][1] = h * 2;
    f[0][2][0] = h * 3;
    f[0][0][1] = h * 4;
    f[0][1][0] = h * 6;
    f[0][0][0] = h * 12;
    for (int i = 1;i <= n;i++) {
    for (int j = 0;j <= 2;j++)
    for (int k = 0;k <= 1;k++)
    if (f[i - 1][j][k] > a[i]) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k] + a[i] / 2);
    for (int j = 0;j <= 2;j++) {
    for (int k = 0;k <= 1;k++) {
    if (j >= 1) f[i][j - 1][k] = max(f[i][j - 1][k], f[i][j][k] * 2);
    if (k >= 1) f[i][j][k - 1] = max(f[i][j][k - 1], f[i][j][k] * 3);
    if (j >= 2) f[i][j - 2][k] = max(f[i][j - 2][k], f[i][j][k] * 4);
    if (j >= 1 && k >= 1) f[i][j - 1][k - 1] = max(f[i][j - 1][k - 1], f[i][j][k] * 6);
    if (j >= 2 && k >= 1) f[i][j - 2][k - 1] = max(f[i][j - 2][k - 1], f[i][j][k] * 12);
    }
    }
    }
    for (int i = n;i >= 0;i--)
    for (int j = 0;j <= 2;j++)
    for (int k = 0;k <= 1;k++)
    if (f[i][j][k]) {
    cout << i << '\n';
    return true;
    }
    return true;
    }
    int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
    if (!solve()) cout << -1 << '\n';
    }
    return 0;
    }

    F

    题目

    知识点:贪心,枚举。

    显然答案不会大于等于 \(p\) ,即只需要考虑 \(a_n\) 关于缺失数字的大小即可,用 set 存出现过的数。

    如果没有小于 \(a_n\) 的缺失数字,就不需要进位,设最大的缺失数字为 \(mx\) (不存在则设为 \(a_n\) ),答案为 \(mx - a_n\)

    如果有小于 \(a_n\) 的缺失数字,则必须进位。进位后,一定会出现 \(0\) 以及模拟进位后变化的最高位的数字,需要纳入 set 。随后找到小于 \(a_n\) 的最大缺失数字 \(mx\) (不存在则设为 \(0\) ),答案为 \(mx + p-a_n\)

    因为给出的数字最多只有 \(100\) 个,所以每次找数字的次数不会超过 \(100\) 次。

    时间复杂度 \(O(n \log n)\)

    空间复杂度 \(O(n)\)

    题解

    #include
    #define ll long long
    using namespace std;
    int a[107];
    bool solve() {
    int n, p;
    cin >> n >> p;
    for (int i = 1;i <= n;i++) cin >> a[i];
    set<int> st;
    for (int i = 1;i <= n;i++) st.insert(a[i]);
    bool cf = 0;
    for (int i = a[n];i >= 0 && !cf;i--) cf |= !st.count(i);
    if (cf) {
    st.insert(0);
    for (int i = n - 1;i >= 0;i--) {
    if (a[i] + 1 < p) {
    st.insert(a[i] + 1);
    break;
    }
    }
    int mx = a[n] - 1;
    while (mx > 0 && st.count(mx)) mx--;
    cout << mx + p - a[n] << '\n';
    }
    else {
    int mx = p - 1;
    while (mx > a[n] && st.count(mx)) mx--;
    cout << mx - a[n] << '\n';
    }
    return true;
    }
    int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
    if (!solve()) cout << -1 << '\n';
    }
    return 0;
    }

    G

    题目

    知识点:构造,二分,贪心。

    显然,\(a_{2i} = b_i\) 最优,接下来考虑 \(a_{2i-1}\)

    首先,我们希望出现在前面的数字尽可能小,但因为留下的数字是较大的,不一定能让后面数字有解。于是,若要确定这个数字,那么就必须每次都需要检查一遍后面的数字是否还有解,这样很难以较小复杂度实现。

    但是,我们知道出现在后面的数字要尽可能大,我们可以从后往前确定数字,这样就尽可能保留了小的数字,使得前面的数有解。并且,保留的数字不会比这种方案更小,因此如果前面的数字还是无解,那就真的无解。

    因此,我们先把 \(1\)\(n\) 存在 set 中,把出现过的数字删除。如果删除的数字已经删过,那么不可能是个排列,所以无解。然后,从后往前,确定未出现的数中小于 \(b_i\) 的最大数当作 \(a_{2i-1}\) ,如果没有则无解。

    时间复杂度 \(O(n \log n)\)

    空间复杂度 \(O(n)\)

    #include
    #define ll long long
    using namespace std;
    int a[200007], b[100007];
    bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n / 2;i++) cin >> b[i], a[i * 2] = b[i];
    set<int> st;
    for (int i = 1;i <= n;i++) st.insert(i);
    for (int i = 1;i <= n / 2;i++) {
    if (!st.count(b[i])) return false;
    st.erase(b[i]);
    }
    for (int i = n / 2;i >= 1;i--) {
    auto pos = st.lower_bound(b[i]);
    if (pos == st.begin()) return false;
    a[i * 2 - 1] = *prev(pos);
    st.erase(prev(pos));
    }
    for (int i = 1;i <= n;i++) cout << a[i] << ' ';
    cout << '\n';
    return true;
    }
    int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
    if (!solve()) cout << -1 << '\n';
    }
    return 0;
    }
  • 相关阅读:
    细说Linux的图形界面系统XServer与VNC及其它
    python 另一种将内容写入记事本的方式
    python+java+vue校园办公室报修管理系统#计算机毕业设计
    介绍一款开源、高性价比的在线教育建站系统
    C++调用OpenCV实现图像平滑处理
    C++ //练习 9.19 重写上题的程序,用list替代deque。列出程序要做出哪些改变。
    彻底搞懂MySQL主从复制工作原理:2个日志 | 3种存储格式 |3个线程|4种工作模式
    Java System.gc()具有什么功能呢?
    Taurus.MVC-Java 版本打包上传到Maven中央仓库(详细过程):2、PGP下载安装与密钥生成发布
    如何解决 IntelliJ IDEA 2024 启动总闪退问题?一站式解决方案!
  • 原文地址:https://www.cnblogs.com/BlankYang/p/16906184.html