当前位置: 首页 > news >正文

Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2) A~E

A - Increase or Smash

模拟。

对于每个不是最大值的来说,都会经历一次先置为零然后再加的操作,重复项只计算一次;而最大值不用置为零,所以最开始会有一次。

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i += 1) {cin >> a[i];}int Max = *max_element(a.begin() + 1, a.end());int cnt[101] {}, ans = 1;for (int i = 1; i <= n; i += 1) {if (a[i] != Max) {if (cnt[a[i]] == 0) {ans += 2;cnt[a[i]] += 1;}}}cout << ans << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

B - Catching the Krug

分类讨论。

以下以 \(A\) 代表抓的人,\(B\) 代表被抓的人。因为 \(A\) 可以斜着跑,所以只要 \(B\) 不在和 \(A\)\(x\) 轴或 \(y\) 轴上,\(A\) 都可以一边追的同时通过斜着跑移动到同一轴上,从而使得距离只到四个边界上就能抓住他,而 \(B\) 想要活久一点就只能朝相反方向跑,所以最后答案就是判断 \(B\) 朝与 \(A\) 相反的两个坐标轴跑, \(A\) 到达这两个坐标轴的最大距离。

image

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int n, k[2], d[2];cin >> n >> k[0] >> k[1] >> d[0] >> d[1];int ans = 0;for(int x = 0; x <= 1; x += 1) {if(k[x] < d[x]) {ans = max(ans, d[x]);} else if(k[x] > d[x]) {ans = max(ans, n - d[x]);}}cout << ans << "\n";}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

C - Triple Removal

前缀和/线段树。

手玩可以发现的是,如果存在两个相邻 \(0/1\),一定通过每次消耗 \(1\) 的代价可以将该区间全部消完(假设区间 \(0/1\) 个数为 \(3\) 的倍数),比如 \(1\textcolor{red}{00}1\textcolor{red}00101011\rightarrow \textcolor{red}{11}0\textcolor{red}{1}01011 \rightarrow \textcolor{red}{00}1\textcolor{red}011\rightarrow \textcolor{red}{111}\),只有 \(010101..\) 交替的时候需要多一次 \(1\) 的代价,后面就都是按照相邻的消法即可。

可以用前缀和维护存不存在相邻的 \(0/1\),我是直接上线段树了。

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;template<class Info>
struct SegmentTree {int n;vector<Info> info;SegmentTree(): n(0) {}SegmentTree(int n_, Info v_ = Info()) {init(n_, v_);}template<class T>SegmentTree(vector<T> init_) {init(init_);}void init(int n_, Info v_ = Info()) {init(vector(n_, v_));}template<class T>void init(vector<T> init_) {n = init_.size();info.assign((4 << __lg(n) + 1) + 10, Info());function<void(int, int, int)> build = [&](int u, int l, int r) {if (l == r) {info[u] = init_[l - 1];return ;}i64 m = (l + r) / 2;build(2 * u, l, m);build(2 * u + 1, m + 1, r);pushup(u);};build(1, 1, n);}void pushup(int u) {info[u] = info[2 * u] + info[2 * u + 1];}void modify(int u, int l, int r, int x, const Info &v) {if (l == r) {info[u] = v;return;}int m = (l + r) / 2;if (x <= m) {modify(2 * u, l, m, x, v);} else {modify(2 * u + 1, m + 1, r, x, v);}pushup(u);}void modify(int u, const Info &v) {modify(1, 1, n, u, v);}Info rangeQuery(int u, int l, int r, int x, int y) {if (l > y || r < x) {return Info();}if (l >= x && r <= y) {return info[u];}int m = (l + r) / 2;return rangeQuery(2 * u, l, m, x, y) + rangeQuery(2 * u + 1, m + 1, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 1, n, l, r);}
};struct Info {int cnt[2] {};int val[2] {};bool adj = false;
};Info operator+(const Info &l, const Info &r) {Info res;if(r.cnt[0] + r.cnt[1] == 0) {return l;}if(l.cnt[0] + l.cnt[1] == 0) {return r;}res.cnt[0] = l.cnt[0] + r.cnt[0];res.cnt[1] = l.cnt[1] + r.cnt[1];res.val[0] = l.val[0];res.val[1] = r.val[1];res.adj |= (l.val[1] == r.val[0] || l.adj || r.adj);return res;
}void solve() {int n, q;cin >> n >> q;SegmentTree<Info> seg(n);for(int i = 1; i <= n; i += 1) {int x;cin >> x;seg.modify(i, {1 - x, x, x, x});}while(q --) {int l, r;cin >> l >> r;auto res = seg.rangeQuery(l, r);if(res.cnt[0] % 3 || res.cnt[1] % 3) {cout << "-1\n";continue;}int ans = (r - l + 1) / 3;ans += res.adj != true;cout << ans << "\n";}}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

D. Division Versus Addition

思维,前缀和/线段树。

以下定义三类数,如果 \(a_i=2^k\),定义为 \(A\) 类型;\(a_i=2^k+1\),为 \(B\) 类型;其余为 \(C\) 类型,定义 \(|X|\) 代表 \(X\) 类型的数量。

\(A\) 类型比较好分析,\(+1\) 并不会增加代价,所以对面对 \(A\) 类型下手,跟着操作即可;\(B\) 类型,对面一旦下手,操作必定会增加一次,所以当对面对 \(B\) 类型下手,我也得去对其他 \(B\) 类型下手,尽可能减少对面能下手的数量,由于我是先手,一定尽可能对 \(B\) 先下手;\(C\) 类型,手玩了一下,感觉是一直操作一定会有一次操作后使得 \(a_i = 2^k-1\),这个时候对面操作就会增加一次了。

所以总的代价是 \(ans = \sum_{i=1}^n\lfloor \log_2{a_i}\rfloor + \lfloor\frac{|B|}2\rfloor+|C|\)

也可以前缀和,我还是直接上线段树了。

关于更具体的上下界分析,参考[1]

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;template<class Info>
struct SegmentTree {int n;vector<Info> info;SegmentTree(): n(0) {}SegmentTree(int n_, Info v_ = Info()) {init(n_, v_);}template<class T>SegmentTree(vector<T> init_) {init(init_);}void init(int n_, Info v_ = Info()) {init(vector(n_, v_));}template<class T>void init(vector<T> init_) {n = init_.size();info.assign((4 << __lg(n) + 1) + 10, Info());function<void(int, int, int)> build = [&](int u, int l, int r) {if (l == r) {info[u] = init_[l - 1];return ;}i64 m = (l + r) / 2;build(2 * u, l, m);build(2 * u + 1, m + 1, r);pushup(u);};build(1, 1, n);}void pushup(int u) {info[u] = info[2 * u] + info[2 * u + 1];}void modify(int u, int l, int r, int x, const Info &v) {if (l == r) {info[u] = v;return;}int m = (l + r) / 2;if (x <= m) {modify(2 * u, l, m, x, v);} else {modify(2 * u + 1, m + 1, r, x, v);}pushup(u);}void modify(int u, const Info &v) {modify(1, 1, n, u, v);}Info rangeQuery(int u, int l, int r, int x, int y) {if (l > y || r < x) {return Info();}if (l >= x && r <= y) {return info[u];}int m = (l + r) / 2;return rangeQuery(2 * u, l, m, x, y) + rangeQuery(2 * u + 1, m + 1, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 1, n, l, r);}
};struct Info {int sum = 0, B = 0;
};Info operator+(const Info &l, const Info &r) {return {l.sum + r.sum + (l.B + r.B == 2), (l.B + r.B) % 2};
}void solve() {int n, q;cin >> n >> q;SegmentTree<Info> seg(n + 1);for(int i = 1; i <= n; i += 1) {int x;cin >> x;int k = 0;while((1 << k + 1) <= x) {k += 1;}int y = x - 1;bool B = (y == (y & -y)) && (x & 1);seg.modify(i, {k + ((x != (x & -x)) && !B), B});}while(q --) {int l, r;cin >> l >> r;cout << seg.rangeQuery(l, r).sum << "\n";}}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

E. Monotone Subsequence

明天补下题解


  1. https://codeforces.com/blog/entry/146988 ↩︎

http://www.hskmm.com/?act=detail&tid=25187

相关文章:

  • k8s之基础概念
  • 251005
  • Java基础 Day26 - 详解
  • 14_mklink创建符号链接
  • 7_如何构建知识图谱
  • 点双连通分量例题:矿场搭建
  • MTK oppoR9m Smart Phone flash Tool 提示 ERROR: STATUS_UNSUPPORT_CTRL_CODE (0xC0010004)
  • 我开发的 Chrome 插件 SEO Tools Extension 今天上线了
  • Windows Server部署Vue3+Spring Boot项目 - 实践
  • 深入解析:阿里云无影云桌面深度测评
  • 2025.10.5模拟赛
  • C++/CLI
  • uboot 2020版本下gpio命令的使用
  • 盛世华诞 举国同庆|热烈庆祝 LEWISAK 英勇重创消火栓 1 周年!
  • 完整教程:<el-table>构建树形结构
  • 如何在markdown中插入折叠框
  • wqs二分
  • markdown语法详解
  • CF2115 VP 记录
  • 2-SAT模板
  • lab5
  • lab4
  • NumPy广播:12个技巧替代循环,让数组计算快40倍
  • 某中心2026年推出1111个技术实习岗位
  • 川土微变频器应用分享
  • POLIR-Society-Philosophy- Hegels 形而上学System Philosophy Dialectics 系统化哲学辩证法: 自由意志+封闭的绝对精神
  • 解决VLC 无法解码格式“h264” (H264 - MPEG-4 AVC (part 10))
  • CF2115 总结
  • luogu P8816 [CSP-J 2022] 上升点列 题解
  • CF558C Amr and Chemistry BFS解