比赛地址: https://codeforces.com/contest/2040
A. Game of Division 题目 https://codeforces.com/contest/2040/problem/A
题意 给你一个长度为
两个玩家正在玩一个游戏。第一个玩家选择一个索引
我们扮演第一个玩家。确定是否可能获胜，如果可能，应该选择哪个索引
数字
思路 模拟
AC代码
点击查看代码
```cpp
#define _USE_MATH_DEFINES // To use the definition of cmath
#include
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
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，至少需要进行多少次第一种类型的运算？
思路 第
先初始化每一个i的范围，再二分查找。
AC代码
点击查看代码
```cpp
#define _USE_MATH_DEFINES // To use the definition of cmath
#include
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
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
Let us consider all permutations of length
For the permutation
For the permutation
in the first position where
Input
Each test contains multiple test cases. The first line contains the number of test cases
The only line of each test case contains two integers
It is guaranteed that the sum of
Output
For each test case, if there are less than
Otherwise, print the
Example
点击查看测试样例
**Input**
```
6
3 2
3 3
4 11
4 6
6 39
7 34
```
**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
In the first test case, you have to print the second suitable permutation of length
In the second test case, you have to print the third suitable permutation of length
题意 考虑从
让我们考虑所有长度为
对于
对于排列
在
输入
每个测试包含多个测试用例。第一行包含测试用例的数量
每个测试用例的唯一一行包含两个整数
保证所有测试用例中
输出
对于每个测试用例，如果合适的排列组合少于
否则，打印
备注
让我们计算所有长度为
在第一个测试用例中，您必须打印长度为
在第二个测试用例中，您必须打印长度为
思路 通过打表，可以观察到。值为最大的 为
所以只要值为最大的 不超过
这里给出
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 是从 3：0b0011 的后 3 位，往前挪动 1 位形成的。
而 3 是从 1：0b0001 的后两位，往前挪动 1 位形成的。
同样的 4：0b0100 是以同样的方式从 2:0b0010 转移过来的。
得出结论：第
AC代码
点击查看代码
```cpp
#define _USE_MATH_DEFINES // To use the definition of cmath
#include
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
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& 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 v(n);
iota(v.rbegin(), v.rend(), 1LL);
dfs(k, v);
ranges::reverse(v);
ranges::copy(v, ostream_iterator(cout, " "));
cout << '\n';
}
int main() {
int T;
for (cin >> T; T > 0; --T) {
solve();
}
return 0;
}
```
