Codeforces div2 940 [A-D]
Problem - A - Codeforces
您得到了长度为 $a_1, a_2, \ldots, a_n$ 的 $n$ 棒。找出可以同时构造的正则(等边)多边形的最大数目,例如:
多边形的每一边都是由一根棍子组成的。
- 不在多于 $1$ 的多边形中使用棒。
注意: 棍子不能折断。
think
我们可以贪心的折成三角形
code
Submission #257585982 - Codeforces
// Codeforces - Codeforces Round 940 (Div. 2) and CodeCraft-23 A. Stickogon
// https://codeforces.com/contest/1957/problem/A 2024-04-21 22:37:40
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
void solve() {
cin >> n;
vector<int> a(n);
for (auto &i : a) cin >> i;
map<int, int> mp;
for (auto i : a) mp[i]++;
int ans = 0;
for (auto [x, y] : mp) ans += y / 3;
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}
Problem - B - Codeforces
给定整数 $n$ 和 $k$ ,构造一个由 $n$ 非负整数(即 $\geq 0$ ) $a _1, a _2, \ldots, a _n$ 组成的序列,使得
- $\sum\limits _{i = 1}^n a _i = k$
- 在 $a _1 | a _2 | \ldots | a _n$ 的二进制表示中, $1$ 的个数被最大化,其中 $|$ 表示位或操作。
think
我们可以让第一个数取到1最多的数
后面的数是多少都无所谓,第二个填剩下的k,其余可以全填0
如果只有一个数直接输出就行
code
Submission #257585581 - Codeforces
// Codeforces - Codeforces Round 940 (Div. 2) and CodeCraft-23 B. A BIT of a
// Construction https://codeforces.com/contest/1957/problem/B 2024-04-21
// 22:40:37
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, k;
void solve() {
cin >> n >> k;
vector<int> a(n);
if (n == 1)
cout << k << "\n";
else {
for (int i = 31; i >= 0; i--) {
if (k >= ((1LL << i) - 1LL)) {
a[0] = ((1LL << i) - 1LL);
k -= ((1LL << i) - 1LL);
break;
}
}
a[1] = k;
for (auto it : a) cout << it << " ";
cout << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}
Problem - C - Codeforces
你被给予一个 $n \times n$ 棋盘,在那里你和计算机轮流把白车和黑车分别放置在棋盘上。在放置车子时,你必须确保没有两只车子互相攻击。如果两个 Rooks 共享同一行或同一列,则不论颜色如何,它们都会相互攻击。
一个有效的移动是把一个车放在一个位置( $r$ , $c$ ) ,使它不攻击任何其他车。
你首先开始,当你做了一个有效的移动,放置一个白色车的位置( $r$ , $c$ ) ,计算机将镜像你和放置一个黑色车的位置( $c$ , $r$ )。如果 $r = c$ ,则计算机无法镜像您的移动,并跳过它的回合。
您已经使用计算机进行了 $k$ 步骤(计算机也反映了这些步骤) ,您必须继续进行游戏,直到没有有效的步骤剩余。当你在 $k$ 移动之后继续游戏时,有多少种不同的最终配置是可能的?保证 $k$ 移动是有效的。由于答案可能很大,请将其打印为模数 $10^9+7$ 。
think
我们先想一下给出的k
操作有什么用
给定了一对坐标,那么该横纵坐标可以直接从棋盘中抹去
然后就从n
棋盘变成了n-2
棋盘
我们先处理 所有的操作, 然后将其还原成一个未操作的 x
棋盘
对于 p
棋盘 我们可以通过在右下角添加一个√
转换到 p+1
棋盘(右下角不空方案数)
我们也可以通过 p-1
棋盘 枚举哪一个对角线上的方格和 右下角的方格的行列 配对 从而转移到p+1
棋盘(右下角空方案数)
这样 我们可以统计出 右下角 为 空 或者 不空的 所有方案数
于是便可以求出答案
code
Submission #257624584 - Codeforces
// Codeforces - Codeforces Round 940 (Div. 2) and CodeCraft-23 C. How Does the
// Rook Move? https://codeforces.com/contest/1957/problem/C 2024-04-21 22:47:58
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
constexpr int N = 8E5 + 10;
constexpr int mod = 1E9 + 7;
using i64 = long long;
template <class T>
constexpr T power(T a, i64 b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template <i64 P>
struct MLong {
i64 x;
constexpr MLong() : x{} {}
constexpr MLong(i64 x) : x{norm(x % getMod())} {}
static i64 Mod;
constexpr static i64 getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(i64 Mod_) { Mod = Mod_; }
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr i64 val() const { return x; }
explicit constexpr operator i64() const { return x; }
constexpr MLong operator-() const {
MLong res;
res.x = norm(getMod() - x);
return res;
}
constexpr MLong inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MLong &operator*=(MLong rhs) & {
x = mul(x, rhs.x, getMod());
return *this;
}
constexpr MLong &operator+=(MLong rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MLong &operator-=(MLong rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MLong &operator/=(MLong rhs) & { return *this *= rhs.inv(); }
friend constexpr MLong operator*(MLong lhs, MLong rhs) {
MLong res = lhs;
res *= rhs;
return res;
}
friend constexpr MLong operator+(MLong lhs, MLong rhs) {
MLong res = lhs;
res += rhs;
return res;
}
friend constexpr MLong operator-(MLong lhs, MLong rhs) {
MLong res = lhs;
res -= rhs;
return res;
}
friend constexpr MLong operator/(MLong lhs, MLong rhs) {
MLong res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
i64 v;
is >> v;
a = MLong(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
return os << a.val();
}
friend constexpr bool operator==(MLong lhs, MLong rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MLong lhs, MLong rhs) {
return lhs.val() != rhs.val();
}
};
template <>
i64 MLong<0LL>::Mod = mod;
using mint = MLong<0LL>;
mint dp[N];
int k;
void solve() {
cin >> n >> k;
set<int> S;
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
S.insert(x);
S.insert(y);
}
if (S.size() == n)
cout << "1\n";
else {
n -= S.size();
cout << dp[n] << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
dp[1] = 1;
dp[2] = 3;
int val = 5E5;
for (int i = 3; i <= val + 5; i++) {
dp[i] = dp[i - 1] + ((i - 1LL) * dp[i - 2] * 2LL);
}
int __;
cin >> __;
while (__--) solve();
return 0;
}
Problem - D - Codeforces
给定一个数组 $a_1, a_2, \ldots, a_n$ 。查找元组的数目( $x, y, z$ ) ,以便:
- $1 \leq x \leq y \leq z \leq n$ ,和
- $f(x, y) \oplus f(y, z)>f(x, z)$ .
我们定义 $f(l, r) = a_l \oplus a_{l + 1} \oplus \ldots \oplus a_{r}$ ,其中 $\oplus$ 表示按位异或操作。
第一行包含单个整数 $t$ ( $1 \leq t \leq 10^4$ )ー测试用例的数量。
每个测试用例的第一行包含一个整数 $n$ ( $1 \leq n \leq 10^5$ )。
每个测试用例的第二行包含 $n$ 整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ )。
保证所有测试用例中 $n$ 的总和不超过 $10^5$ 。
think
我们设 $S_i$ 代表的是$a_1 \oplus \dots \oplus a_i$
那么$f(x,y)=S_y\oplus S_{x-1}$
$$
\begin{align}
f(x, y) \oplus f(y, z)&>f(x, z)\\
S_y\oplus S_{x-1} \oplus S_z\oplus S_{y-1}&>S_z\oplus S_{x-1}\\
a_y\oplus S_z\oplus S_{x-1}&>S_z\oplus S_{x-1}
\end {align}
$$
我们枚举每一个$a_y$
欲使$a_y\oplus S_z\oplus S_{x-1}>S_z\oplus S_{x-1}$
只需找到 $a_y$ 的最高位
使得 $S_z\oplus S_{x-1}$ 的这一位是0
这一步又有两种情况
一种 是 都是 1
一种 是 都是 0
那么我们就可以用拆位前缀和来统计
总的时间复杂度是$O(32n)$
可以通过本题
code
Submission #257640485 - Codeforces
// Codeforces - Codeforces Round 940 (Div. 2) and CodeCraft-23 D. A BIT of an
// Inequality https://codeforces.com/contest/1957/problem/D 2024-04-21 23:47:53
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
constexpr int N = 2E5 + 10;
int dig(int x) {
int res = 31;
while (res >= 0 and (x & (1LL << res)) == 0) res--;
return res + 1;
}
int a[N];
int S[N];
int Lcol[N][32];
int Rcol[N][32];
void solve() {
cin >> n;
for (int i = 0; i <= n + 1; i++) {
a[i] = S[i] = 0;
for (int j = 0; j < 32; j++) {
Lcol[i][j] = Rcol[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
S[i] = S[i - 1] ^ a[i];
}
// for (int i = 0; i <= n; i++) cout << S[i] << " \n"[i == n];
Lcol[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 31; j++) {
Lcol[i][j] = Lcol[i - 1][j];
}
for (int j = 0; j < 30; j++) {
if ((S[i] >> j) & 1) {
Lcol[i][j + 1]++;
}
}
}
Rcol[n + 1][0] = 1;
for (int i = n; i >= 1; i--) {
for (int j = 0; j < 31; j++) {
Rcol[i][j] = Rcol[i + 1][j];
}
for (int j = 0; j < 30; j++) {
if ((S[i] >> j) & 1) {
// cout << S[i] << " " << (S[i] >> j) << "\n";
// cout << "ij " << i << " " << j + 1 << "\n";
Rcol[i][j + 1]++;
}
}
}
int ans = 0;
// 左边选一个异或前缀和
// 右边选一个异或前缀和
// 要求当前数异或上边两个以后比他俩原来大
// 找当前数字二进制的1 要求左边的数和右边的数这一位一样
for (int i = 1; i <= n; i++) {
int dg = dig(a[i]);
ans += (Lcol[i - 1][dg]) * (Rcol[i][dg]); // 都有
ans += (i - Lcol[i - 1][dg]) * (n - i + 1 - Rcol[i][dg]); // 都没有
//
// cout << (Lcol[i - 1][dg]) * (Rcol[i][dg]) << " "
// << (i - Lcol[i - 1][dg]) * (n - i + 1 - Rcol[i][dg]) << "\n";
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}