历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

Codeforces Global Round 22 A~D

作者：

Goku74 , 2022-10-02 15:41:14 , 所有人可见 , 阅读 338

3

1

Codeforces Global Round 22

A.Glory Addicts

题目大意

一个英雄打怪兽，他有 $n$ 个技能，每个技能要么是火焰系要么是霜冻系，第 $i$ 个技能的伤害值是 $b_i$ 。每个技能只能使用一次，但英雄可以用任意顺序释放这些技能。此外，英雄还有一个被动技能，如果当前使用的技能和上一个使用的技能类型不同，当前技能将造成双倍伤害。问英雄最多能造成多少伤害。

解题思路

怎么上来就这么大码量啊喂，懵逼了好几分钟(
思维上没有什么难度，就是贪心，分情况讨论
$1.$ 技能类型单一，没有办法交错，那么答案就是所有伤害加起来
否则肯定是是把伤害高的交错用，对应下面两种情况
$2.$ 两类技能的数量相同，那么就挑出最小的伤害第一个用，后面全部交错造成双倍
$3.$ 两类技能的数量不同，那么就优先把两类技能中伤害比较高的优先交错，再加上多出来的那个类型的伤害

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q;
LL a[N], b[N];
bool cmp(LL a, LL b)
{
    return a > b;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
    {
        std::vector<LL> fire;
        std::vector<LL> frost;
        std::cin >> n;
        for (int i = 1; i <= n; ++i)
            std::cin >> a[i];
        for (int i = 1; i <= n; ++i)
            std::cin >> b[i];
        for (int i = 1; i <= n; ++i)
        {
            if (a[i])
                fire.push_back(b[i]);
            else
                frost.push_back(b[i]);
        }
        LL ans = 0;
        if (fire.empty() || frost.empty()) //没有办法交错用
        {
            if (!fire.empty())
                for (int i = 0; i < fire.size(); ++i)
                    ans += fire[i];
            if (!frost.empty())
                for (int i = 0; i < frost.size(); ++i)
                    ans += frost[i];
            std::cout << ans << '\n';
            continue;
        }
        std::sort(fire.begin(), fire.end(), cmp);
        std::sort(frost.begin(), frost.end(), cmp);
        if (fire.size() != frost.size())
        {
            m = std::min(fire.size(), frost.size());
            for (int i = 0; i < m; ++i) //少的那个类型全部两倍
                ans += fire[i] * 2 + frost[i] * 2;
            // 加上剩下的那个类型
            if (fire.size() == m)
            {
                for (int i = m; i < frost.size(); ++i)
                    ans += frost[i];
            }
            else
            {
                for (int i = m; i < fire.size(); ++i)
                    ans += fire[i];
            }
        }
        else //最小伤害的那个技能第一个用，其他全部能两倍
        {
            for (int i = 0; i < fire.size(); ++i)
                ans += fire[i] * 2 + frost[i] * 2;
            ans -= std::min(fire[fire.size() - 1], frost[frost.size() - 1]);
        }
        std::cout << ans << '\n';
    }
    return 0;
}

B.Prefix Sum Addicts

题目大意

假设 $a_1,a_2,\cdots ,a_n$ 是长度为 $n$ 的有序不减序列 $(a_1\leq a_2\leq \cdots \leq a_n)$
定义前缀和 $s_i=\sum_{j=1}^{i}{a_j}$
现在告诉你最后 $k$ 个前缀和，即 $s_{n-k+1},\cdots,s_{n-1},s_n$
问是否可能存在对应的 $a$ 数组

解题思路

就是说这才像前面两题嘛(
首先 $k$ 等于 $1$ 时肯定 $YES$
否则，要检查两种情况
因为可以从 $s_{n-k+1},\cdots,s_{n-1},s_n$ 得到 $a_{n-k+2},\cdots ,a_{n-1},a_n$ 的信息
所以要确保 $a_{n-k+2},\cdots ,a_{n-1},a_n$ 是有序不减的
其次，因为 $a_1,a_2,\cdots ,a_{n-k+1}$ 这 $n-k+1$ 个数都 $\leq a_{n-k+2}$
所以要检查 $s_{n-k+1}$ 是否 $\leq (n-k+1)\times a_{n-k+2}$

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 2e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q, k;
LL s[N], a[N];
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
    {
        std::cin >> n >> k;
        for (int i = n - k + 1; i <= n; ++i)
            std::cin >> s[i];
        if (k == 1)
        {
            std::cout << "YES" << '\n';
            continue;
        }
        for (int i = n; i >= n - k + 2; --i)
            a[i] = s[i] - s[i - 1];

        bool impossible = false;
        // 要检查的第一种情况
        if ((n - k + 1) * a[n - k + 2] < s[n - k + 1])
            impossible = true;
        // 要检查的第二种情况
        for (int i = n - k + 2; i <= n - 1; ++i)
            if (a[i] > a[i + 1])
                impossible = true;

        if (impossible)
            std::cout << "NO" << '\n';
        else
            std::cout << "YES" << '\n';
    }
    return 0;
}

C.Even Number Addicts

题目大意

$Alice$ 和 $Bob$ 在玩一个游戏。这个游戏初始有一个长度为 $n$ 的序列 $a$ 。他们轮流行动， $Alice$ 先手。轮到行动的那个人，需要从序列里取走一个数，当序列里没有数时，游戏结束。游戏结束时，如果 $Alice$ 取走的数的和是偶数，那么 $Alice$ 获胜，否则 $Bob$ 获胜。给定游戏开始时的序列，假设两人都以最优策略玩，问谁会赢。

解题思路

$n$ 的数据范围只给到了 $100$ ，给不太会推结论的人放了条生路(
说明只要记忆化搜索即可，注释写得很清楚了
记忆化搜索真的对解决小数据的博弈论很有帮助，不熟悉的话建议掌握
官方题解有只根据奇数偶数个数就能知道谁获胜的结论，有兴趣可以去看看

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 110;
const LL M = 2;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
LL n, m, q;
LL a[N];
int dp[N][N][M][M];    // 剩余偶数个数,剩余奇数个数,当前轮到了谁,Alice当前数的奇偶
bool dfs(int even, int odd, int a, int b) // 返回1代表Alice赢，返回0代表Bob赢
{
    if (dp[even][odd][a][b] != -1) //记忆化
        return dp[even][odd][a][b];
    if (!odd && !even)   //游戏结束
        return dp[even][odd][a][b] = 1 - b; // Alice手里是偶数就返回1，否则返回0
    if (a == 1)  //当前轮到Bob
    {
        if (even > 0 && (dfs(even - 1, odd, 1 - a, b) == 0) || odd > 0 && (dfs(even, odd - 1, 1 - a, b) == 0))
        // Bob拿偶数并且这种局面是Bob赢                       或 Bob拿奇数并且这种局面是Bob赢
            return dp[even][odd][a][b] = 0;
        else
            return dp[even][odd][a][b] = 1;
    }
    else //当前轮到Alice
    {
        if ((even > 0 && dfs(even - 1, odd, 1 - a, b) == 1) || odd > 0 && (dfs(even, odd - 1, 1 - a, 1 - b) == 1))
        // Alice拿偶数并且这种局面是Alice赢                   或 Alice拿奇数并且这种局面是Alice赢
            return dp[even][odd][a][b] = 1;
        else
            return dp[even][odd][a][b] = 0;
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
    {
        memset(dp, -1, sizeof dp);
        std::cin >> n;
        LL odd = 0, even = 0;
        for (int i = 1; i <= n; ++i)
        {
            std::cin >> a[i];
            if (a[i] & 1)
                ++odd;
            else
                ++even;
        }
        if (dfs(even, odd, 0, 0) == 1)
            std::cout << "Alice" << '\n';
        else
            std::cout << "Bob" << '\n';
    }
    return 0;
}

D.Permutation Addicts

题目大意

给定一个 $n$ 排列 $a$ 和一个门槛 $k$ ，可构造 $b$ 数组：
构造规则如下(真的好难流畅地用中文表述)：

现在只有 $b$ 数组，让你还原出一种可能的 $a$ 和 $k$

解题思路

先看怎么求 $k$ ：
根据题意有 $a_i\leq k\Longleftrightarrow b_{a_i}\gt k$
因为 $a$ 是排列，所以正好有 $k$ 个 $a_i$ 满足 $a_i\leq k$
意味着正好有 $k$ 个 $b_i$ 满足 $b_i\gt i$
就是说只要统计 $b_i\gt i$ 的数量，就是 $k$ 的大小
再看怎么求 $a$ ：
$a_i\leq k\Longleftrightarrow b_{a_i}\gt k$
$a_i\gt k\Longleftrightarrow b_{a_i}\leq k$
可以发现 $a_i$ 与 $b_{a_i}$ 在关于 $k$ 的关系这件事上是相反的
抛去 $a$ 数组看 $b$ 数组
就是说 $b_i$ 与 $i$ 在关于 $k$ 的关系上是相反的
那么就可以转换为图上的问题
在 $b_i$ 与 $i$ 间连边，这样最后的图是一颗树(可以试着画几个样例)
优先遍历没有儿子的节点(意味着不是题目里的 $last$ )，放进 $a$ 里

具体代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
typedef long long LL;
typedef std::pair<int, int> PII;
const LL N = 1e5 + 10;
const LL M = 50;
const LL INF = 0x7f7f7f7f7f7f7f7f;
const LL MOD = 1e9 + 7;
int n, m, q, k;
int b[N];
std::vector<int> G[N];
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
    {
        std::cin >> n;
        k = 0;
        for (int i = 0; i <= n + 1; ++i)
            G[i].clear();
        for (int i = 1; i <= n; ++i)
        {
            std::cin >> b[i];
            if (b[i] > i)
                ++k;
            G[b[i]].push_back(i);
        }
        for (int i = 0; i <= n + 1; ++i)
            std::sort(G[i].begin(), G[i].end(), [](int a, int b)
                      { return G[a].size() < G[b].size(); });
        std::vector<int> a;
        if (G[0].size())
            a.push_back(0);
        else
            a.push_back(n + 1);
        while (a.size() < n + 1)
        {
            int u = a.back();
            for (int v : G[u])
                a.push_back(v);
        }
        std::cout << k << '\n';
        for (int i = 1; i < a.size(); ++i)
            std::cout << a[i] << ' ';
        std::cout << '\n';
    }
    return 0;
}

0 评论

App 内打开