1991(div1+div2)
A. Maximize the Last Element
给你一个由
在一次操作中,你将从数组
重复执行这个操作直到
求
易得:只有奇数位置的元素可以留下
void solve() {
int n;cin >> n;
vector<int> a(n + 1);
for (int i = 1;i <= n;i++)cin >> a[i];
int mx = 0;
for (int i = 1;i <= n;i += 2) {
mx = max(mx, a[i]);
}
cout << mx << '\n';
}
}
B. AND Reconstruction
给你一个由
构造 -1
如何将条件化简?
有条件:
void solve() {
int n;cin >> n;
vector<int> b(n), a(n);
for (int i = 1;i < n;i++)cin >> b[i];
for (int i = 1;i < n;i++) {
for (int j = __lg(b[i]);j >= 0;j--) {
if ((b[i] >> j) & 1) {
a[i - 1] |= (1 << j);a[i] |= (1 << j);
}
}
}
for (int i = 1;i < n;i++) {
if ((a[i - 1] & a[i]) != b[i]) {
cout << "-1\n";return;
}
}
for (auto x : a)cout << x << ' ';
cout << '\n';
}
jiangly:
void solve() {
int n;
std::cin >> n;
std::vector<int> b(n - 1);
for (int i = 0; i < n - 1; i++) {
std::cin >> b[i];
}
std::vector<int> a(n);
for (int i = 0; i < n - 1; i++) {
a[i] |= b[i];
a[i + 1] |= b[i];
}
for (int i = 0; i < n - 1; i++) {
if ((a[i] & a[i + 1]) != b[i]) {
std::cout << -1 << "\n";
return;
}
}
for (int i = 0; i < n; i++) {
std::cout << a[i] << " \n"[i == n - 1];
}
}
C. Absolute Zero
给你一个由
在一次操作中,您将执行以下两步移动:
- 选择一个整数
( )。 - 将每个
替换为 。
构造一个操作序列,使
Solution
最初
最终操作后的序列为 0 或 1。若所有元素都为 0 则已经满足要求,都为 1 则还需要操作 1 次。
若最初的数字为奇数,则最终操作后的序列
若最初的数字为偶数,则操作后的
void solve() {
int n;cin >> n;
vector<int> a(n + 1);
for (int i = 1;i <= n;i++) {
cin >> a[i];
}
for (int i = 2;i <= n;i++) {
if (abs(a[i] - a[i - 1]) & 1) {
cout << "-1\n";return;
}
}
cout << 30 + (a[1] % 2 == 0) << '\n';
for (int i = 29;i >= 0;i--) {
cout << (1 << i) << " ";
}
if (a[1] % 2 == 0) {
cout << 1;
}
cout << '\n';
}
D. Prime XOR Coloring
给你一个无向图,图中有
用最少的颜色给图中的所有顶点着色,使得由边直接连接的两个顶点没有相同的颜色。
Solution
若 1 2 3 4
轮流交替,这样每两个相同的数字之间就相差 4,两个数相异或则不可能是质数 (这样二进制后两位一定是相等的,异或后后两位则都为 0,不可能为质数)
若
void solve() {
int n;
cin >> n;
if (n < 6) {
if (n == 1)
cout << 1 << '\n' << "1" << '\n';
else if (n == 2)
cout << 2 << '\n' << "1 2" << '\n';
else if (n == 3)
cout << 2 << '\n' << "1 2 2" << '\n';
else if (n == 4)
cout << 3 << '\n' << "1 2 2 3" << '\n';
else if (n == 5)
cout << 3 << '\n' << "1 2 2 3 3" << '\n';
} else {
cout << 4 << '\n';
for (int i = 1; i <= n; i++)
cout << i % 4 + 1 << ' ';
cout << '\n';
}
}
E. Coloring Game
这是一个互动问题。
考虑一个由
爱丽丝和鲍勃正在玩一个由
- 爱丽丝选择两种不同的颜色。
- 鲍勃选择一个未着色的顶点,并用爱丽丝选择的两种颜色之一为其着色。
如果存在连接两个相同颜色顶点的边,则爱丽丝获胜。否则,鲍勃获胜。
我们给你这个图。您的任务是决定您想扮演哪位玩家并赢得游戏。
Solution
若给定图不是二分图(即含有奇环),Alice 必赢,Alice 不断输出 1 2 即可,由于是奇环,最终必然会有矛盾
若给定图是二分图,Bob 必赢,将 1 ,2 的部分分开顺序填入即可。
EDU:本题的二分图判定方式值得学习
void solve() {
int n, m;cin >> n >> m;
vector<vector<int>> g(n + 1);
for (int i = 1;i <= m;i++) {
int u, v;cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
bool ok = 1;
vector<int> clr(n + 1);clr[1] = 1;
auto dfs = [&](auto self, int u) ->void{
for (auto v : g[u]) {
if (!clr[v]) {
clr[v] = 3 - clr[u];
self(self, v);
} else if (clr[v] + clr[u] != 3) {
ok = 0;
}
}
};
dfs(dfs, 1);
if (!ok) {
cout << "Alice" << endl;
for (int i = 1;i <= n;i++) {
cout << 1 << " " << 2 << endl;
int u, op;cin >> u >> op;
}
} else {
cout << "Bob" << endl;
vector<int> p1, p2;
for (int i = 1;i <= n;i++) {
if (clr[i] == 1) {
p1.push_back(i);
} else {
p2.push_back(i);
}
}
for (int i = 1;i <= n;i++) {
int clr1, clr2;cin >> clr1 >> clr2;
if ((clr1 == 1 || clr2 == 1) && p1.size()) {
cout << p1.back() << " " << 1 << endl;p1.pop_back();
} else if ((clr1 == 2 || clr2 == 2) && p2.size()) {
cout << p2.back() << " " << 2 << endl;p2.pop_back();
} else if (!p1.size()) {
int op = (clr1 == 1 ? clr2 : clr1);
cout << p2.back() << " " << op << endl;p2.pop_back();
} else {
int op = (clr1 == 2 ? clr2 : clr1);
cout << p1.back() << " " << op << endl;p1.pop_back();
}
}
}
}
F. Triangle Formation
给定
Solution
若区间长度大于
根据极端的情况就是斐波那契数列,在 45 项的位置就已经超过
对于区间长度小于
- 考虑枚举所有可能的 6 个连续小棒,检查能否组成两个三角形
- 考虑枚举所有可能的 3 个连续小棒,检查能否两个不相交的集合使得分别形成三角形
若不满足这两点,就一定不存在两个三角形。
证明:?
jiangly 的代码:
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, q;
std::cin >> n >> q;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
while (q--) {
int l, r;
std::cin >> l >> r;
l--;
if (r - l > 100) {
std::cout << "YES\n";
continue;
}
std::vector b(a.begin() + l, a.begin() + r);
std::sort(b.begin(), b.end());
bool ok = false;
int L = 1E9, R = -1;
for (int i = 0; i + 2 < b.size(); i++) {
if (b[i] + b[i + 1] > b[i + 2]) {
L = std::min(L, i);
R = i;
}
}
if (R - L >= 3) {
ok = true;
}
for (int i = 0; i + 5 < b.size() && !ok; i++) {
if (b[i] + b[i + 1] > b[i + 3] && b[i + 2] + b[i + 4] > b[i + 5]) {
ok = true;
break;
}
if (b[i] + b[i + 2] > b[i + 3] && b[i + 1] + b[i + 4] > b[i + 5]) {
ok = true;
break;
}
if (b[i + 1] + b[i + 2] > b[i + 3] && b[i] + b[i + 4] > b[i + 5]) {
ok = true;
break;
}
if (b[i] + b[i + 1] > b[i + 4] && b[i + 2] + b[i + 3] > b[i + 5]) {
ok = true;
break;
}
if (b[i] + b[i + 2] > b[i + 4] && b[i + 1] + b[i + 3] > b[i + 5]) {
ok = true;
break;
}
if (b[i + 1] + b[i + 2] > b[i + 4] && b[i] + b[i + 3] > b[i + 5]) {
ok = true;
break;
}
if (b[i] + b[i + 3] > b[i + 4] && b[i + 1] + b[i + 2] > b[i + 5]) {
ok = true;
break;
}
}
if (ok) {
std::cout << "YES\n";
} else {
std::cout << "NO\n";
}
}
}