2024ICPC武汉邀请赛个人题解

题目排序由个人认为难度排序。

怠惰的弈方

2259人浏览 · 2024-05-06 04:09:22

怠惰的弈方 · 2024-05-06 04:09:22 发布

2024ICPC武汉邀请赛个人题解

题目排序由个人认为难度排序

题解火车头

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <bitset>
#include <cmath>
#include <numeric>

#define endl '\n'

#define ft first
#define sd second

#define yes cout << "yes\n"
#define no cout << "no\n"

#define Yes cout << "Yes\n"
#define No cout << "No\n"

#define YES cout << "YES\n"
#define NO cout << "NO\n"

#define pb push_back
#define eb emplace_back

#define all(x) x.begin(), x.end()
#define unq_all(x) x.erase(unique(all(x)), x.end())
#define sort_all(x) sort(all(x))
#define reverse_all(x) reverse(all(x))

#define INF 0x7fffffff
#define INFLL 0x7fffffffffffffffLL

#define RED cout << "\033[91m"
#define GREEN cout << "\033[92m"
#define YELLOW cout << "\033[93m"
#define BLUE cout << "\033[94m"
#define MAGENTA cout << "\033[95m"
#define CYAN cout << "\033[96m"
#define RESET cout << "\033[0m"

// 红色
#define DEBUG1(x)                     \
    RED;                              \
    cout << #x << " : " << x << endl; \
    RESET;

// 绿色
#define DEBUG2(x)                     \
    GREEN;                            \
    cout << #x << " : " << x << endl; \
    RESET;

// 蓝色
#define DEBUG3(x)                     \
    BLUE;                             \
    cout << #x << " : " << x << endl; \
    RESET;

// 品红
#define DEBUG4(x)                     \
    MAGENTA;                          \
    cout << #x << " : " << x << endl; \
    RESET;

// 青色
#define DEBUG5(x)                     \
    CYAN;                             \
    cout << #x << " : " << x << endl; \
    RESET;

// 黄色
#define DEBUG6(x)                     \
    YELLOW;                           \
    cout << #x << " : " << x << endl; \
    RESET;

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<string, ll> psl;

typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pss> vpss;

typedef vector<vi> vvi;
typedef vector<vl> vvl;

typedef queue<int> qi;
typedef queue<ll> ql;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef queue<psi> qpsi;
typedef queue<psl> qpsl;

typedef priority_queue<int> pqi;
typedef priority_queue<ll> pql;
typedef priority_queue<string> pqs;
typedef priority_queue<pii> pqpii;
typedef priority_queue<psi> pqpsi;
typedef priority_queue<pll> pqpl;
typedef priority_queue<psi> pqpsl;

typedef map<int, int> mii;
typedef map<int, bool> mib;
typedef map<ll, ll> mll;
typedef map<ll, bool> mlb;
typedef map<char, int> mci;
typedef map<char, ll> mcl;
typedef map<char, bool> mcb;
typedef map<string, int> msi;
typedef map<string, ll> msl;
typedef map<int, bool> mib;

typedef unordered_map<int, int> umii;
typedef unordered_map<ll, ll> uml;
typedef unordered_map<char, int> umci;
typedef unordered_map<char, ll> umcl;
typedef unordered_map<string, int> umsi;
typedef unordered_map<string, ll> umsl;

template <typename T>
inline void read(T &x)
{
    T f = 1;
    x = 0;
    char ch = getchar();
    while (0 == isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (0 != isdigit(ch))
        x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
    x *= f;
}

template <typename T>
inline void write(T x)
{
    if (x < 0)
    {
        x = ~(x - 1);
        putchar('-');
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

I. Cyclic Apple Strings

题目大意

给你一个由 $0, 1$ 组成的字符串，可以任选一个任意长度的子段，将其向左旋转任意长度，例如 $110$ 向左旋转一次就是 $101$ 。问最少需要多少次操作使得字符串单调递增。

解题思路

对于任意一个连续的 $1$ 和连续的 $0$ 组成子串，我们都可以在一次操作内将所有 $0$ 旋转到 $1$ 的前面。所以，只需要统计在 $1$ 后面的连续 $0$ 段数量即可。即只需要找出有多少个 $10$ 就行。

题解

/*#####################################BEGIN#####################################*/

void solve()
{
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 1; i < s.size(); i++)
    {
        if (s[i] == '0' && s[i - 1] == '1')
            ans++;
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    // std::cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}

/*######################################END######################################*/

K. Party Games

题目大意

给你 $n$ 个整数 $1,2,3,\dots,n$ ，每次可以从最左端或者最右端拿走一个数字，如果当前所剩的数异或和为 $0$ 或被拿完则输了。问谁会赢。

解题思路

由异或和的性质可以得知，当二进制位上的 $1$ 的数量都为偶数时，异或和为 $0$ 。所以从 $0\sim n$ 连续进行异或和，每隔 $4$ 个数就会出现一次异或和为 $0$ 。

$0, 1, 2, 3$ 的二进制形式为 $0000_2,0001_2,0010_2,0011_2$ 。

$4, 5, 6, 7$ 的二进制形式为 $0100_2,0101_2,0110_2,0111_2$ 。

每隔四位都会使得所有位上的 $1$ 的数量为偶数。

所以对于整个序列来说，我们只需要考虑对前 $3$ 个和最多后 $4$ 个数字博弈。

可以写成 $0001_2,0010_2,0011_2,xx00_2,xx01_2,xx10_2,xx11_2$ 。

先从简单向复杂推导。

$f (0)$ ，当 $n\mod 4=0$ 时，当前的序列为 $0001_2,0010_2,0011_2,xx00_2$ 。先手只要拿掉 $xx00_2$ 就必胜。

$f (1)$ ，当 $n\mod 4=1$ 时，当前的序列为 $0001_2,0010_2,0011_2,xx00_2,xx01_2$ 。先手只要拿掉 $0001_2$ 就必胜。

$f (2)$ ，当 $n\mod 4=2$ 时，当前的序列为 $0001_2,0010_2,0011_2,xx00_2,xx01_2,xx10_2$ 。先手不可能拿掉 $xx10_2$ ，这样就会使得 $f(2)\rightarrow f(1)$ ，导致后手必胜，所以只能拿 $0001_2$ ，后手这时只需要拿走 $0010_2$ ，就会使得异或和为 $0$ ，所以无论如何后手必胜。

$f (3)$ ，当 $n\mod 4=3$ 时，当前的序列为 $0001_2,0010_2,0011_2,xx00_2,xx01_2,xx10_2，xx11_2$ 。异或和已经为 $0$ ，先手不能拿掉任何数，后手必胜。

题解

/*#####################################BEGIN#####################################*/

const string t1 = "Fluttershy";
const string t2 = "Pinkie Pie";

void solve()
{
    int n;
    cin >> n;
    cout << (n % 4 < 2 ? t1 : t2) << endl;
}

int main()
{
    ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    std::cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}

/*######################################END######################################*/

B. Countless Me

题目大意

给你 $n$ 个数字组成的数组 $a$ ，你可以对任意两个数字 $a_i,a_j$ 进行一次操作，使得 $a_i+x,a_j-x$ 。最多进行 $n$ 次操作。确保每次运算后所有 $a_i,a_j$ 都保持非负整数。我们的目标是最小化 $ans=a_1|a_2|a_2\dots|a_n$ 的值。

解题思路

很容易可以证明，我们可以在这 $n$ 次操作内把数组内所有元素变成不超过 $s=\sum ^{n}_{i=1}a_i$ 的任意数。

所以我们需要考虑的是，如和将 $s$ 分配到 $n$ 个位置上，使得 $an s$ 最小。

贪心的考虑，我们肯定是要让手里待分配的数字变小，使情况简化，所以从高位开始分配。

从最高位开始贪心，如果不分配当前位数 $i$ 的二进制值，转到 $i - 1$ 位可以把 $s$ 分配完的话，就不进行分配（），否则就从 $s$ 中分配出 $x=min(n,\lfloor \frac{s}{2^i} \rfloor)$ 个 $2^i$ ，只有 $n$ 个位置，所以最多只能分配 $n$ 个。

题解

/*#####################################BEGIN#####################################*/

void solve()
{
    ll n;
    cin >> n;
    ll a;
    ll s = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        s += a;
    }
    ll ans = 0;
    for (int i = 30; i >= 0; i--)
    {
        if (s > n * ((1 << i) - 1))
        {
            ans |= 1 << i;
            ll x = min(n, s >> i);
            s -= x * (1 << i);
        }
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    // std::cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}

/*######################################END######################################*/

有一个由正整数 $a_{i,j}(1\le a_{i,j}\le n\times n)$ 组成的 $n\times n$ 大小的矩阵，对于矩阵中的任意一个元素都有 $a_{i,j}\ge a_{i-1,j}(i\gt1),a_{i,j}\ge a_{i,j-1}(j\gt1)$ 。你不知道这个矩阵里面每个位置的具体值，但你每次可以进行一次查询，查询矩阵中给定位置 $a_{i,j}$ 是否小于等于指定整数 $x$ ，如果小于等于会返回 $1$ ，否则返回 $0$ 。

通过不超过 $50000$ 次，寻找 $k$ 值。 $k$ 值被定义为对 $n \times n$ 个元素进行降序排序时，第 $k$ 个元素的值。

解题思路

二分+暴力检查。

考虑到是否有 $k$ 个元素大于当前选择的值是具有单调性性的，我们可以直接二分寻找最终答案。每次暴力查询矩阵中是否有 $k$ 个元素大于它。

题解

/*#####################################BEGIN#####################################*/

int n, k;

bool query(int i, int j, int x)
{
    cout << "? " << i << " " << j << " " << x << endl;
    int res;
    cin >> res;
    return res;
}

bool check(int x)
{
    int cnt = 0;
    for (int i = 1, j = n; i <= n; i++)
    {
        while (j >= 1 && !query(i, j, x))
            j--;
        cnt += n - j;
    }
    return cnt >= k;
}

void solve()
{
    cin >> n >> k;
    int l = 1, r = n * n;
    int ans = 0;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            l = mid + 1;
        else
        {
            r = mid - 1;
            ans = mid;
        }
    }
    cout << "! " << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    // std::cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}

/*######################################END######################################*/

D. ICPC

题目大意

在一张长桌上， $n$ 个座位排成一排，从左到右的第 $i_{th}$ 个座位上摆放着 $a_i$ 份量的菜肴。由由子从 $s_{th}$ 座位开始，每秒结束时，她可以移动到与当前座位相邻的任何座位(她也可以选择留在当前座位)。她所到达的座位上的任何菜肴都会被她吃掉。

由由子想知道她能吃的菜肴的最大总份量。对于满足 $1 \leq s \leq n, 1 \leq t \leq 2 n$ 的所有正整数 $s, t$ ，你需要计算如果由由子从 $s_{th}$ 座位开始，移动 $t$ 秒，她可以吃掉的菜肴的最大总份量。

让 $F_{s,t}$ 表示由由子从座位 $s$ 开始，在 $t$ 秒内可以吃掉的菜肴的最大总份量。为了验证你已经计算出 $1 \leq s \leq n, 1 \leq t \leq 2 n$ 的所有 $F_{s,t}$ 的值，请输出整数 $_{s=1}^{n}(s+⨁_{t=1}^{2n}t⋅F_{s,t})$ 。

解题思路

很简单的二维 $d p$ 。对于所有移动，要么一直走到头不折返，要么只折返一次然后走到头。

设 $g_{s,t}$ 为在位置 $s$ 移动不超过 $t$ 次且不折返的吃掉菜肴的最大值，先利用前缀和可以简单算出 $g_{s,t}$ 。

对于折返一次的走法，设在走 $i$ 步后折返，则最大值为 $g_{s+i,t-i}$ 。

综上，可以推出状态转移方程 $F_{s,t}=max(g_{s+i,t-|i|}),1\le s+i\le n,t-|i|\ge 1$ 。

由于 $n\le 5000$ ，所以 $d p$ 的时间复杂度不能超过 $n^2$ ，只能进行两层循环，所以需要压缩一下。

题解

/*#####################################BEGIN#####################################*/

const int N = 5e3 + 5;
int a[N];
ll F[N][2 * N];
ll g[N][2 * N];
ll sum[N];
int n;

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for (int s = 1; s <= n; s++)
    {
        for (int t = 1; t <= 2 * n; t++)
        {
            int l = max(1, s - t);
            int r = min(n, s + t);
            g[s][t] = max(sum[s] - sum[l - 1], sum[r] - sum[s - 1]);
        }
    }
    // 向左移动然后折返
    for (int s = 1; s <= n; s++)
    {
        for (int t = 1; t <= 2 * n; t++)
        {
            F[s][t] = max(F[s - 1][t - 1], g[s][t]);
        }
    }
    // 向右移动然后折返
    for (int s = n; s >= 1; s--)
    {
        for (int t = 1; t <= 2 * n; t++)
        {
            g[s][t] = max(g[s][t], g[s + 1][t - 1]);
            F[s][t] = max(F[s][t], g[s][t]);
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ll temp = 0;
        for (int j = 1; j <= 2 * n; j++)
        {
            temp ^= j * F[i][j];
        }
        ans ^= (i + temp);
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    int _ = 1;
    // std::cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}

/*######################################END######################################*/