Codeforces Round 992 (Div. 2) 解题陈述
竞赛地址: https://codeforces.com/contest/2040
A. Game of Division
标题
https://codeforces.com/contest/2040/problem/A
题意
给你一个长度为 \(n\) 的整数数组 \(a_1, a_2, \ldots, a_n\) 和一个整数数组 \(k\) 。
两个玩家正在玩一个游戏。第一个玩家挑选一个索引 \(1 \le i \le n\) 。然后第二个玩家挑选不同的索引 \(1 \le j \le n, i \neq j\) 。假如 \(|a_i - a_j|\) 不能被 \(k\) 整除，则第一个玩家取胜。不然，第二位棋手取胜。
咱们扮演第一个玩家。确认是否或许取胜，假如或许，应该挑选哪个索引 \(i\) 。
数字 \(x\) 的绝对值用 \(|x|\) 表明，假如是 \(x \ge 0\) ，则等于 \(x\) ，不然等于 \(-x\) 。
思路
模仿
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
题意
您有一个长度为 \(n\) 的零数组 \(a_1, a_2, \ldots, a_n\) 。
你可以对它进行两种操作：
- 在 \(1 \le i \le n\) 和 \(a_i = 0\) 之间挑选一个索引 \(i\) ，并将 \(1\) 赋值给 \(a_i\) ；
- 挑选一对索引 \(l\) 和 \(r\) ，使得 \(1 \le l \le r \le n\) ， \(a_l = 1\) ， \(a_r = 1\) ， \(a_l + \ldots + a_r \ge \lceil\frac{r - l + 1}{2}\rceil\) ，并将一切 \(l \le i \le r\) 的 \(1\) 赋值给 \(a_i\) 。
要使数组中的一切元素都等于 1，至少需求进行多少次序一种类型的运算？
思路
第 \(i\) 次序一种类型的运算，可掩盖的最大规模为第 \(i - 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\(^{\text{∗}}\) \(p_1, p_2, \ldots, p_n\) of integers from \(1\) to \(n\). We can introduce the following sum for it\(^{\text{†}}\):
