Codeforces Round 992 (Div. 2) 解题报告

比赛地址: https://codeforces.com/contest/2040

A. Game of Division

题目

https://codeforces.com/contest/2040/problem/A

题意

给你一个长度为的整数数组和一个整数数组。

两个玩家正在玩一个游戏。第一个玩家选择一个索引。然后第二个玩家选择不同的索引。如果不能被整除，则第一个玩家获胜。否则，第二位棋手获胜。

我们扮演第一个玩家。确定是否可能获胜，如果可能，应该选择哪个索引。

数字的绝对值用表示，如果是，则等于，否则等于。

思路

模拟

AC代码

点击查看代码

#define _USE_MATH_DEFINES // To use the definition of cmath

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

// mp.reserve(1024), mp.max_load_factor(0.75);
// Used only for basic types, pair and tuple.
template<typename T>
struct custom_hash_base {
    size_t operator()(const T& x) const {
        static const size_t seed = chrono::steady_clock::now().time_since_epoch().count();
        return _Hash_bytes(&x, sizeof(x), seed);
    }
};

static const auto _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("../in.txt", "r", stdin);
#endif
    return nullptr;
}();

int nums[101], k;
int n;
int st[101];

inline void solve() {
    cin >> n >> k;
    memset(st, 0, sizeof(int) * (k + 1));
    for (int i = 1; i <= n; ++i) {
        cin >> nums[i];
    }
    for (int i = 1; i <= n; ++i) {
        bool flag = true;
        for (int j = 1; j <= n && flag; ++j) {
            if (i == j) continue;
            if (abs(nums[i] - nums[j]) % k == 0) flag = false;
        }
        if (flag) {
            cout << "YES\n" << i << "\n";
            return;
        }
    }
    cout << "NO\n";
}

int main() {
    int T;
    for (cin >> T; T > 0; --T) {
        solve();
    }
    return 0;
}

B. Paint a Strip

题目

https://codeforces.com/contest/2040/problem/B

题意

您有一个长度为的零数组。

你可以对它进行两种操作：

在和之间选择一个索引，并将赋值给；
选择一对索引和，使得，，，，并将所有的赋值给。

要使数组中的所有元素都等于 1，至少需要进行多少次第一种类型的运算？

思路

第次第一种类型的运算，可覆盖的最大范围为第次的范围加1，再乘2。

先初始化每一个i的范围，再二分查找。

AC代码

点击查看代码

#define _USE_MATH_DEFINES // To use the definition of cmath

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

// mp.reserve(1024), mp.max_load_factor(0.75);
// Used only for basic types, pair and tuple.
template<typename T>
struct custom_hash_base {
    size_t operator()(const T& x) const {
        static const size_t seed = chrono::steady_clock::now().time_since_epoch().count();
        return _Hash_bytes(&x, sizeof(x), seed);
    }
};

static const auto _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("../in.txt", "r", stdin);
#endif
    return nullptr;
}();

int n;
constexpr int N = 20;
ll st[N];

static const auto init= []() {
    st[1] = 1;
    for (int i = 2; i < N; ++i) {
        st[i] = (st[i - 1] + 1) << 1;
    }
    return 0;
}();

inline void solve() {
    cin >> n;
    int p = lower_bound(st + 1, st + N, n) - st - 1;
    while (st[p] < n) ++p;
    cout << p << '\n';
}

int main() {
    int T;
    for (cin >> T; T > 0; --T) {
        solve();
    }
    return 0;
}

C. Ordered Permutations

题目

https://codeforces.com/contest/2040/problem/C

time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Consider a permutation of integers from to . We can introduce the following sum for it:

Let us consider all permutations of length with the maximum possible value of . Output the -th of them in lexicographicalorder, or report that there are less than of them.

A permutation of length is an array consisting of distinct integers from to in arbitrary order. For example, is a permutation, but is not a permutation ( appears twice in the array), and is also not a permutation ( but there is in the array).

For example:

For the permutation the value of is equal to
For the permutation the value of is equal to .

An array is lexicographically smaller than an array if and only if one of the following holds:

is a prefix of , but ; or
in the first position where and differ, the array has a smaller element than the corresponding element in .

Input

Each test contains multiple test cases. The first line contains the number of test cases (). The description of the test cases follows.

The only line of each test case contains two integers and (; ) — the length of the permutation and the index number of the desired permutation.

It is guaranteed that the sum of over all test cases does not exceed .

Output

For each test case, if there are less than suitable permutations, print .

Otherwise, print the -th suitable permutation.

Example

点击查看测试样例

Input

Output

1 3 2
2 3 1
-1
2 4 3 1
-1
2 3 4 5 7 6 1

Note

Let us calculate the required sum for all permutations of length (ordered lexicographically):

Permutation	Value of

In the first test case, you have to print the second suitable permutation of length . Looking at the table, we see that it is the permutation .

In the second test case, you have to print the third suitable permutation of length . Looking at the table, we see that it is the permutation .

题意

考虑从到的整数的排列。从到的整数的排列组合。我们可以为它引入下面的和：

让我们考虑所有长度为的排列，其最大可能值为。按词典顺序输出其中的第个，或者报告它们的数量少于。

长度为的排列是由个不同的整数组成的数组，这些整数从到按任意顺序排列。例如，是一个排列，但不是一个排列（在数组中出现了两次），也不是一个排列（，但数组中有）。

例如

对于这个排列，的值等于。
对于排列来说，的值等于。 .

当且仅当以下条件之一成立时，数组的lexicographically小于数组：

是的前缀，但是；或者
在和不同的第一个位置，数组中的元素小于中的相应元素。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 ( )。测试用例说明如下。

每个测试用例的唯一一行包含两个整数和（；{47522742}）。( ; ) - 排列的长度和所需排列的索引号。

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

输出

对于每个测试用例，如果合适的排列组合少于，则打印。

否则，打印个合适的排列。

备注

让我们计算所有长度为（按词典顺序排列）的排列所需的和：

Permutation	的值

在第一个测试用例中，您必须打印长度为的第二个合适的排列。观察表格，我们会发现是长度为的排列。

在第二个测试用例中，您必须打印长度为的第三个合适的排列。观察表格，我们会发现是长度为的排列。

思路

通过打表，可以观察到。值为最大的排列的数量为。

所以只要值为最大的排列的数量不超过则有解，否则输出 -1

这里给出为 5 的情况：

 1: 1 2 3 4 5 = 35

 2: 1 2 3 5 4 = 35

 3: 1 2 4 5 3 = 35
 4: 1 2 5 4 3 = 35

 5: 1 3 4 5 2 = 35
 6: 1 3 5 4 2 = 35
 7: 1 4 5 3 2 = 35
 8: 1 5 4 3 2 = 35

 9: 2 3 4 5 1 = 35
10: 2 3 5 4 1 = 35
11: 2 4 5 3 1 = 35
12: 2 5 4 3 1 = 35
13: 3 4 5 2 1 = 35
14: 3 5 4 2 1 = 35
15: 4 5 3 2 1 = 35
16: 5 4 3 2 1 = 35

假设取 7：0b0111

会发现 7 是从 3：0b0011 的后 3 位，往前挪动 1 位形成的。

而 3 是从 1：0b0001 的后两位，往前挪动 1 位形成的。

同样的 4：0b0100 是以同样的方式从 2:0b0010 转移过来的。

得出结论：第个排列是第 prev_k（把移除二进制的最高位，如果二进制bit 1的个数为1则左移1位）个排列的后 m（k 二进制的最左边1的位置）位往前挪动1位形成的。

AC代码

点击查看代码

#define _USE_MATH_DEFINES // To use the definition of cmath

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

// mp.reserve(1024), mp.max_load_factor(0.75);
// Used only for basic types, pair and tuple.
template<typename T>
struct custom_hash_base {
    size_t operator()(const T& x) const {
        static const size_t seed = chrono::steady_clock::now().time_since_epoch().count();
        return _Hash_bytes(&x, sizeof(x), seed);
    }
};

static const auto _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("../in.txt", "r", stdin);
#endif
    return nullptr;
}();

ll n, k;

inline ll get_next(ll x) {
    --x;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    ++x;
    return x;
}

inline void dfs(ll ck, vector<ll>& v) {
    if (ck <= 1)
        return;
    if (__builtin_popcountll(ck) == 1)
        dfs(ck >> 1, v);
    else
        dfs(ck - (get_next(ck) >> 1), v);
    ck = get_next(ck);
    int i = 64 - __builtin_clzll(ck) - 1;
    ll x = v[i];
    v.erase(v.begin() + i);
    v.insert(v.begin(), x);
}

inline void solve() {
    cin >> n >> k;
    const int ci = 64 - __builtin_clzll(get_next(k));
    if (n < ci) {
        cout << -1 << '\n';
        return;
    }
    vector<ll> v(n);
    iota(v.rbegin(), v.rend(), 1LL);
    dfs(k, v);
    ranges::reverse(v);
    ranges::copy(v, ostream_iterator<ll>(cout, " "));
    cout << '\n';
}

int main() {
    int T;
    for (cin >> T; T > 0; --T) {
        solve();
    }
    return 0;
}

A. Game of Division

题目

题意

思路

AC代码

B. Paint a Strip

题目

题意

思路

AC代码

C. Ordered Permutations

题目

题意

思路

AC代码

那些算法在哪里？

JDK 18 及以上使用标准输出流中文输出乱码问题

stazxr