Codeforces Round #658 (Div. 2)【ABC2】
2024-09-07 02:47:17
做完前四题还有一个半小时...
比赛链接:https://codeforces.com/contest/1382
A. Common Subsequence
题意
给出两个数组,找出二者最短的公共子序列。
题解
最短即长为一。
代码
#include <bits/stdc++.h>
using namespace std; void solve() {
int n, m; cin >> n >> m;
set<int> a, b;
for (int i = 0; i < n; ++i) {
int x; cin >> x;
a.insert(x);
}
for (int i = 0; i < m; ++i) {
int x; cin >> x;
b.insert(x);
}
for (auto i : a) {
if (b.count(i)) {
cout << "YES" << "\n";
cout << 1 << ' ' << i << "\n";
return;
}
}
cout << "NO" << "\n";
} int main() {
int t; cin >> t;
while (t--) solve();
}
B. Sequential Nim
题意
给出 $n$ 堆石子的数量,两人轮流从最左端的非空堆中取任意数量的石子,无法再取者判负,判断游戏的胜者。
题解
第一次取到数量大于 $1$ 的石子堆的人获胜。
证明
将石子堆分为两类:连续的数量 $>1$ 的和单独的数量 $=1$ 的,第一次取到数量大于 $1$ 的石子堆的人可以通过取得剩一个或全部取完来迫使对方进入自己的节奏。
代码
#include <bits/stdc++.h>
using namespace std; void solve() {
int n; cin >> n;
int get_non_one = -1;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
if (x > 1 and get_non_one == -1) get_non_one = i;
}
if (get_non_one == -1) {
cout << (n & 1 ? "First" : "Second") << "\n";
} else {
cout << (get_non_one & 1 ? "First" : "Second") << "\n";
}
} int main() {
int t; cin >> t;
while (t--) solve();
}
C2. Prefix Flip (Hard Version)
题意
每次可以选取二进制串的前 $p$ 位全部取反然后反转,输出将二进制串 $a$ 变为 $b$ 的任一方案。
题解
先从前向后将 $a$ 的前缀合并为单一字符,然后从后向前操作与 $b$ 的不同位。
代码
#include <bits/stdc++.h>
using namespace std; void solve() {
int n; cin >> n;
string a, b; cin >> a >> b;
vector<int> p;
for (int i = 1; i < n; ++i) {
if (a[i] != a[i - 1]) {
p.push_back(i);
}
}
char now = a.back();
for (int i = n - 1; i >= 0; --i) {
if (now != b[i]) {
p.push_back(i + 1);
now = (now == '0' ? '1' : '0');
}
}
cout << p.size() << ' ';
for (int i : p) cout << i << ' ';
cout << '\n';
} int main() {
int t; cin >> t;
while (t--) solve();
}
最新文章
- 【SDOI2009】HH的项链
- Material Design使用记录
- Grafana 安装
- [转]Java中继承、多态、重载和重写介绍
- 安装小企鹅fcitx输入法
- android service总结
- How to choose between zombie.js and PhantomJS for automated web testing? [closed]
- 【RAC】RAC相关基础知识
- 高性能消息队列 CKafka 核心原理介绍(上)
- JAVASE高级2
- SSM-SpringMVC-33:SpringMVC中拦截器Interceptor讲解
- Spring Boot使用Maven打包替换资源文件占位符
- Django2 Django MTV模板
- JVM--01
- SPFA找最大比例环
- Java 8 中常用的函数式接口
- React子组件怎么改变父组件的state
- tp框架中的一些疑点知识-3
- 使用formData上传文件,ajax上传
- how to use kvo with swift (怎样在swift中使用kvo)