Codeforces Round 937 (Div. 4)[A-G]
进算竞小群加我
A. Stair, Peak, or Neither?
您将获得三位数字 $a$ 、 $b$ 和 $c$ 。确定它们是否形成楼梯、山峰或两者都不形成。
- 楼梯满足条件 $a<b<c$ 。
- 峰值满足条件 $a<b>c$ 。
code
int n, m;
void solve() {
int a, b, c;
cin >> a >> b >> c;
if (a < b and b < c)
cout << "STAIR\n";
else if (a < b and b > c)
cout << "PEAK\n";
else
cout << "NONE\n";
}
B. Upscaling
给你一个整数 $n$ 。输出一个由 $2 \times 2$ 个方格组成的 $2n \times 2n$ 棋盘,交替出现” $\#$ “和” $\texttt{.}$ “,左上角的方格为” $\#$ “。
上图是 $n=1,2,3,4$ 的答案。
THINK
我们将四个小方块看成一个方块
那么我们可以发现
奇数行开头的方块都是#
偶数行开头的方块都是·
那么我们判断一下行数的奇偶,然后行内遍历的时候判断一下列的奇偶取反就好
code
constexpr int N = 50;
char a[N][N];
void solve() {
cin >> n;
int f = 1;
for (int i = 1, f = 0; i <= n + n; i += 2, f ^= 1) {
for (int j = 1, w = f; j <= n + n; j += 2, w ^= 1) {
if (w & 1) {
a[i][j] = a[i + 1][j] = a[i][j + 1] = a[i + 1][j + 1] = '.';
} else {
a[i][j] = a[i + 1][j] = a[i][j + 1] = a[i + 1][j + 1] = '#';
}
}
}
for (int i = 1; i <= n + n; i++) {
for (int j = 1; j <= n + n; j++) {
cout << a[i][j];
}
cout << "\n";
}
}
C. Clock Conversion
给出 24 小时制的时间,输出 12 小时制的相应时间。
- 24 小时格式 将一天分为 24 小时,从 $00$ 到 $23$ ,每个小时有 60 分钟,从 $00$ 到 $59$ 。
- 12 小时格式 将一天分为两半:上半部分为 $\mathrm{AM}$ ,下半部分为 $\mathrm{PM}$ 。在每一半中,小时按 $12, 01, 02, 03, \dots, 11$ 的顺序编号。每个小时有 60 分钟,从 $00$ 到 $59$ 。
think
语法题不作细解
code
int n, m;
string to_strinsg(int x) {
string s;
while (x) {
s += char('0' + x % 10);
x /= 10;
}
reverse(all(s));
return s;
}
void solve() {
char ch;
string s;
cin >> n >> ch >> m;
if (n >= 12)
s = "PM";
else
s = "AM";
if (n >= 13)
n -= 12;
else if (n == 0)
n += 12;
string _n = to_strinsg(n);
string _m = to_strinsg(m);
if (_n.size() == 1)
_n = "0" + _n;
else if (_n.size() == 0)
_n = "00";
if (_m.size() == 1)
_m = "0" + _m;
else if (_m.size() == 0)
_m = "00";
cout << _n << ch << _m << " " << s << "\n";
}
D. Product of Binary Decimals
如果一个数是正整数,且其十进制符号中的所有数字都是 $0$ 或 $1$ ,我们就称它为二进制十进制数。例如, $1010111$ 是二进制十进制,而 $10201$ 和 $787788$ 不是。
给定一个数 $n$ ,问你是否可以将 $n$ 表示为一些(不一定不同的)二进制小数的乘积。
第一行包含一个整数 $t$ ( $1 \leq t \leq 5 \cdot 10^4$ ) - 测试用例数。
每个测试用例的唯一一行包含一个整数 $n$ ( $1 \leq n \leq 10^5$ )。
THINK
我们看一下$n$ 是很小的
对于一个数 $x$ 暴力判断是不是 二进制十进制数的时间是 $O(log_{10}(x))$的
对此我们可以预处理出$[1,10^5]$以内的所有二进制十进制数
运用二进制状态压缩和快速幂可以在$2^6\times log_2(x)$的时间内预处理完毕
我们注意到一个数是不可以除以0
的 除以1
数字不会发生变化
所以在下面我们忽略这两个数
然后我们就可以暴力拆$n$ 我们观察到最小的二进制十进制可能的因子是10
,也就是最坏情况下拆一个 $n$ 的时间复杂度是$O(2^6log_{10}(n))$的
判断的时间复杂度是$O(log_{10}(x))$
所以总的时间复杂度是$O(2^6log^2_{10}(n))$
可以通过本题
code
// Codeforces - Codeforces Round 937 (Div. 4) D. Product of Binary Decimals
// https://codeforces.com/contest/1950/problem/D 2024-03-29 13:55:18
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
vector<int> nums;
bool is(int x) {
while (x) {
if (x % 10 != 0 and x % 10 != 1)
return false;
else
x /= 10;
}
return true;
}
int dfs(int x) {
if (is(x))
return true;
else {
bool falg = false;
for (auto it : nums) {
if (x >= it) {
if (x % it == 0 and dfs(x / it)) falg |= true;
} else
break;
}
return falg;
}
}
// 快速幂
int qmi(int a, int b, int p = 1E18) {
int res = 1 % p;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
void solve() {
cin >> n;
if (dfs(n))
cout << "YES\n";
else
cout << "NO\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
for (int i = 2; i < (1LL << 6); i++) {
int res = 0;
for (int j = 0; j < 6; j++)
if ((i >> j) & 1) res += qmi(10, j);
nums.emplace_back(res);
}
int __;
cin >> __;
while (__--) solve();
return 0;
}
E. Nearly Shortest Repeating Substring
给你一个长度为 $n$ 的字符串 $s$ ,它由小写拉丁字符组成。求最短字符串 $k$ 的长度,使得多个(可能是一个) $k$ 可以连接在一起,形成一个长度与 $s$ 相同的字符串,且最多只有一个不同的字符。
更正式地说,求最短字符串 $k$ 的长度,使得 $c = \underbrace{k + \cdots + k}_ {x\rm\\ \text{times}}$ 为某个正整数 $x$ ,字符串 $s$ 和 $c$ 长度相同,且 $c_ i \neq s _ i$ 最多有一个 $i$ (即存在 $0$ 或 $1$ 这样的位置)。
think
这个题并不存在单调性,如果套二分的话会WA3
这个题暴力判断每一个答案
是一个调和级数的复杂度
形如n+n/2+n/3+n/4+……
可以转换为调和级数
$$
\begin{align}
1+\frac 1 2+\frac 1 3+\frac 1 4+\dots&=ln(n)+γ\\
于是\\
n+\frac n 2+\frac n 3+\frac n 4+\dots&=n(1+\frac 1 2+\frac 1 3+\frac 1 4+\dots)\\
&=nln(n)
\end{align}
$$
所以直接暴力的时间复杂度是$O(nln(n))$的
然后就可以通过本题
code
// Codeforces - Codeforces Round 937 (Div. 4) E. Nearly Shortest Repeating
// Substring https://codeforces.com/contest/1950/problem/E 2024-03-28 23:00:28
#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;
string s;
cin >> s;
int ans = -1;
auto check = [&](int x) -> bool {
int res = 0;
for (int i = 0, cnt = 0; i < x; i++, cnt = 0) {
map<char, int> mp;
for (int j = i; j < n; j += x, cnt++) {
mp[s[j]]++;
}
if (mp.size() == 1)
continue;
else {
vector<int> tmp;
for (auto [v, w] : mp) {
tmp.emplace_back(w);
}
sort(all(tmp));
res += cnt - tmp.back();
}
}
return res <= 1;
};
vector<int> test;
for (int i = 1; i <= n; i++)
if (n % i == 0) test.emplace_back(i);
for (int i = 0; i < test.size(); i++)
if (check(test[i])) {
cout << test[i] << "\n";
return;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}
F. 0, 1, 2, Tree!
求满足以下条件的具有 $a+b+c$ 顶点的有根树 $^{\dagger}$ 的最小高度:
- $a$ 顶点恰好有 $2$ 个子节点,
- $b$ 顶点恰好有 $1$ 子节点,并且
- $c$ 顶点恰好有 $0$ 子节点。
如果不存在这样的树,您应该报告它。
上面的树以顶部顶点为根,每个顶点都标有其子节点的数量。这里是 $a=2$ 、 $b=1$ 、 $c=3$ ,高度是 $2$ 。
$^{\dagger}$ 有根树是没有循环的连通图,具有称为根的特殊顶点。在有根树中,由边连接的任意两个顶点中,一个顶点是父顶点(距离根较近的顶点),另一个顶点是子顶点。
树中两个顶点之间的距离是它们之间的最短路径中的边数。有根树的高度是从顶点到根的最大距离。
think
F题难得就是想起来用queue模拟高度
想到以后就没有难度了
可以归结到trick
中
code
// Codeforces - Codeforces Round 937 (Div. 4) F. 0, 1, 2, Tree!
// https://codeforces.com/contest/1950/problem/F 2024-03-28 23:17:34
#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
void solve() {
int a, b, c;
cin >> a >> b >> c;
if (a + 1 != c)
cout << "-1\n";
else {
queue<int> q;
q.emplace(0);
int ans = 0;
while (q.size()) {
auto it = q.front();
ans = it;
q.pop();
if (a) {
q.emplace(it + 1);
q.emplace(it + 1);
a--;
} else if (b) {
q.emplace(it + 1);
b--;
}
}
cout << ans << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}
G. Shuffling Songs
Vladislav 的播放列表包含 $n$ 首歌曲,编号从 $1$ 到 $n$ 。歌曲 $i$ 具有流派 $g_i$ 和作者 $w_i$ 。他希望制作一个播放列表,使得每对相邻的歌曲要么具有相同的作者,要么来自相同的流派(或两者)。他称这样的播放列表令人兴奋。 $g_i$ 和 $w_i$ 都是长度不超过 $10^4$ 的字符串。
使用所有歌曲制作一个令人兴奋的播放列表可能并不总是可能的,因此随机播放过程分两步进行。首先,删除一定数量(可能为零)的歌曲,然后重新排列播放列表中的剩余歌曲以使其令人兴奋。
由于 Vladislav 不喜欢歌曲从他的播放列表中删除,因此他希望制作播放列表执行尽可能少的删除操作。帮助他找到需要执行的最少删除次数,以便能够重新排列其余歌曲,使播放列表变得令人兴奋。
THINK
这个题我们观察一下数据范围
$n\le 16$
那么就是一个很明显的状压的数据范围
然后我们就用状压DP跑最大联通数
code
// Codeforces - Codeforces Round 937 (Div. 4) G. Shuffling Songs
// https://codeforces.com/contest/1950/problem/G 2024-03-29 14:07:55
#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> e(n);
vector<string> g(n), w(n);
for (int i = 0; i < n; i++) cin >> g[i] >> w[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i] == g[j] or w[i] == w[j]) {
e[i] |= (1LL << j);
}
}
}
vector<int> dp(1LL << n);
for (int i = 0; i < n; i++) {
dp[1LL << i] |= 1LL << i;
}
int ans = 0;
for (int i = 1; i < (1LL << n); i++) {
if (dp[i]) ans = max(ans, (int)__builtin_popcount(i));
for (int j = 0; j < n; j++) {
if ((((~i) >> j) bitand 1) and (dp[i] bitand e[j])) {
dp[i | 1LL << j] |= 1LL << j;
}
}
}
cout << n - ans << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int __;
cin >> __;
while (__--) solve();
return 0;
}