Codeforces Round 941 Div.2

2024-05-01

ICPC-CCPC

字数统计: 1.2k | 阅读时长≈ 4 分钟

构造场。

CF1966D.Missing Subsequence Sum

题目信息

Problem - D - Codeforces

给你两个整数和。求一个大小最多为的非负整数序列，使得下列条件成立。

没有和为的的子序列。
对于所在的所有，存在一个和为的的子序列。

如果可以从中删除几个（可能是零个或全部）元素，而不改变其余元素的顺序，那么序列就是的子序列。例如，是的子序列。

可以证明，在给定的约束条件下，解总是存在的。

输入

输入的第一行包含一个整数 ( )--测试用例的数量。测试用例说明如下。

每个测试用例由一行组成，包含两个整数和 ( , )--上述参数。

保证所有测试用例中的总和不超过。

题目解析

首先数据范围 $左右$ 基本是把二进制构造怼到了脸上。

首先想到本题最终和没有关系，我的目标就是构造长度为的数组。

如果没有的限制，我的构造顺序就完全可以如下：很好，现在的问题是要求序列不存在和为的子序列。

那么首先第一点，这一项要被掉。此处

这一项掉以后，比小的项最多构造到，不会超过.

此时，序列会空余出区间无法构造.

区间补充和,即可填充

接下来是重点。

问题解决了么？

还没有。

对于目标数，我们采取凑取。

对于采用二进制表示，依旧可能使用到，更进一步的，使用到.

如何填补被挖去的，只需将置换成即可保证。

所以还需要补充.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);
void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a;
    int log = __lg(k);
    int sum = 0;
    for (int i = 0; i < log; i++)
    {
        a.push_back(1LL << i);
        sum += 1LL << i;
    }
    if (k - 1 - sum)
        a.push_back(k - 1 - sum);
    sum = k - 1;
    a.push_back(k + 1);
    a.push_back(k + 1 + (1LL << log));
    while (a.size() < 25)
    {
        log++;
        a.push_back((1LL << log));
    }
    cout << 25 << endl;
    for (auto p : a)
    {
        cout << p << " ";
    }
    cout << endl;
}
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

CF1966C.Everything Nim

题目信息

Problem - C - Codeforces

爱丽丝和鲍勃正在玩一个关于堆石头的游戏。轮到每个玩家时，他们都会选择一个正整数，这个正整数最多等于最小的非空堆的大小，然后从每个非空堆中一次性取出个石子。第一个无法下棋的棋手（因为所有棋子都是空的）就算输。

既然爱丽丝先下，如果双方都以最佳方式下棋，谁会赢得比赛？

题目解析

如果只有一堆石子，那么必然获胜。

进一步的说，如果能够控制最后一对石子是自己先手，那么可以做到这一点的人必胜。

同理，可以简单推理出相同个数的石子堆不具有影响答案的能力，可以视作堆石子个数各不相同的石子堆。

考虑先手必胜，如果有堆各不相同的石子，那么先手想控制最后一堆的先手权，只需要每次迫使后手拿走自己拿的那一堆的所有石子，因为后手想赢不会主动这么做。

所以对于最少有个石子的石子堆，先手要拿个，迫使后手只能拿一个，经过一个回合消除一堆石子。

问题在于如果先手操作过程中导致了自己下一次拿只能拿一个丢了先手权如何处理。

设当前最少得石子堆为，第二少的为。

如果先手拿，那么后手拿，先手下一次只能拿，先手权被迫让出。

那么此时先手可以直接拿走，迫使后手得到的先手权再转移回自己手中。

也就是说，率先面对当前操作的石子堆石子个数时的人，有必胜决定方案，无论后续先手权的转移次数如何，当前人的一定可以将最后一堆的先手权握到自己手里。

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    cin >> n;
    set<int> s;
    for (int i = 1; i <= n; i++)
    {
        int u;
        cin >> u;
        s.insert(u);
    }
    int size = s.size();
    if (size == 1)
    {
        cout << "Alice" << endl;
        return;
    }
    bool flag = 0;
    int cnt = 0;
    while (!s.empty())
    {
        int top = *s.begin();
        if (top == cnt + 1)
        {
            flag ^= 1;
            cnt = top;
            s.erase(top);
        }
        else
            break;
    }
    if (s.empty())
    {
        if (flag)
            cout << "Alice" << endl;
        else
            cout << "Bob" << endl;
    }
    else
    {
        if (flag)
            cout << "Bob" << endl;
        else
            cout << "Alice" << endl;
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！