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

Codeforces Round 1056 (Div. 2) A~D

A - El fucho

模拟。

胜者组共有 \(n-1\) 队进入败者组,进入败者组的会淘汰 \(n-2\) 队,最后剩两组再进行一场,总场数 \(2n-2\)

不会算也可以直接模拟。

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

B - Abraham's Great Escape

构造。

只要有两个就可以构造出 \(\text{LR}\) 这样的循环,然后其他的可以在第一排放 \(\text L\) 指向它,然后再在下面的排放 \(U\) 指向它,其他走出迷宫放 \(D\) 即可。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, k;std::cin >> n >> k;if(n * n - k == 1) {std::cout << "NO\n";return;}k = n * n - k;std::vector<std::string> ans(n, std::string(n, 'D'));if(k) {k -= 2;ans[0][0] = 'R', ans[0][1] = 'L';for(int i = 2; i < n && k; i += 1, k -= 1) {ans[0][i] = 'L';}for(int i = 1; i < n && k; i += 1) {for(int j = 0; j < n && k; j += 1) {ans[i][j] = 'U';k -= 1;}}}std::cout << "YES\n";for(int i = 0; i < n; i += 1) {std::cout << ans[i] << "\n";}}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}

C - The Ancient Wizards' Capes

思维。

通过手玩可以发现答案只有三种,限制太强;对于 \(|a_i-a_{i-1}|\ge 2\) 这种直接不存在,假设 \(a_i > a_{i-1}\),那么除去 \(a_i\)\(a_{i-1}\)\(a_{i-1}\) 至少也能看见 \(a_i - 2\) 个,加上它自己,只能是比 \(a_i\) 多一或者少一。

\(a_i=a_{i-1}\) 时,\(a_i\)\(a_{i-1}\) 是相反的,因为它们都能看见除掉它们两个之外的其他,它们相等,所以它们得互防;\(a_i > a_{i-1}\ \text{or}\ a_i < a_{i-1}\) 也是同理,它们之间会因为朝向而每防住另一个,此时朝向的是固定的。

所以可以枚举 \(a_1\) 作为 \(\text{LR}\),然后得出其他数的朝向,最后对每个数算一下左右两边看见和 \(a_i\) 是否相等即可,这里是用线段树进行维护。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;template<class Info>
struct SegmentTree {int n;std::vector<Info> info;SegmentTree() : n(0) {}SegmentTree(int n_, Info v_ = Info()) {init(n_, v_);}template<class T>SegmentTree(std::vector<T> init_) {init(init_);}void init(int n_, Info v_ = Info()) {init(std::vector(n_, v_));}template<class T>void init(std::vector<T> init_) {n = init_.size();info.assign(4 << std::__lg(n), Info());std::function<void(int, int, int)> build = [&](int p, int l, int r) {if (r - l == 1) {info[p] = init_[l];return;}int m = (l + r) / 2;build(2 * p, l, m);build(2 * p + 1, m, r);pull(p);};build(1, 0, n);}void pull(int p) {info[p] = info[2 * p] + info[2 * p + 1];}void modify(int p, int l, int r, int x, const Info &v) {if (r - l == 1) {info[p] = v;return;}int m = (l + r) / 2;if (x < m) {modify(2 * p, l, m, x, v);} else {modify(2 * p + 1, m, r, x, v);}pull(p);}void modify(int p, const Info &v) {modify(1, 0, n, p, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l >= y || r <= x) {return Info();}if (l >= x && r <= y) {return info[p];}int m = (l + r) / 2;return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n, l, r);}template<class F>int findFirst(int p, int l, int r, int x, int y, F &&pred) {if (l >= y || r <= x) {return -1;}if (l >= x && r <= y && !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findFirst(2 * p, l, m, x, y, pred);if (res == -1) {res = findFirst(2 * p + 1, m, r, x, y, pred);}return res;}template<class F>int findFirst(int l, int r, F &&pred) {return findFirst(1, 0, n, l, r, pred);}template<class F>int findLast(int p, int l, int r, int x, int y, F &&pred) {if (l >= y || r <= x) {return -1;}if (l >= x && r <= y && !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findLast(2 * p + 1, m, r, x, y, pred);if (res == -1) {res = findLast(2 * p, l, m, x, y, pred);}return res;}template<class F>int findLast(int l, int r, F &&pred) {return findLast(1, 0, n, l, r, pred);}
};struct Info {int cnt[2] {};
};Info operator+(const Info &l, const Info &r) {return {l.cnt[0] + r.cnt[0], l.cnt[1] + r.cnt[1]};
}void solve() {int n;std::cin >> n;std::vector<int> a(n);for(int i = 0; i < n; i += 1) {std::cin >> a[i];}for(int i = 1; i < n; i += 1) {if(abs(a[i] - a[i - 1]) > 1) {std::cout << 0 << "\n";return;}}SegmentTree<Info> seg(n);int ans = 0;for(int x = 0; x < 2; x += 1) {int lst = x;seg.modify(0, {1 - x, x});for(int i = 1; i < n; i += 1) {int now;if(a[i] == a[i - 1]) {now = lst ^ 1;} else if(a[i] > a[i - 1]) {now = 0;} else {now = 1;}seg.modify(i, {1 - now, now});lst = now;}bool ok = true;for(int i = 0; i < n; i += 1) {auto res = seg.rangeQuery(0, i + 1);auto res2 = seg.rangeQuery(i, n + 1);if(a[i] != res.cnt[0] + res2.cnt[1]) {ok = false;break;}}ans += ok;}std::cout << ans << "\n";}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}

D - Batteries

思维。

把电池按顺序摆放成一个环,每次选相邻两个数可以确定相邻两个是否存在一对好电池,同理选相隔一个的可以确定每三个是否存在一对好电池,假设两好电池间的最短距离长度为 \(l\),这样最多在第 \(l\) 轮就能找到,设好电池数量为 \(a\),则最短区间距离最大为 \(\lfloor\frac{n}{a}\rfloor\),每个数找一次,这样最多 \(n\times\lfloor\frac{n}{a}\rfloor\) 次就能找到,满足 $n\times\lfloor\frac{n}{a}\rfloor\le \lfloor\frac{n^2}{a}\rfloor $。

可能更严谨的证明(?
\(q = \lfloor\frac{n}{a}\rfloor\),则有 \(q\le \frac na< q+1\),由 \(q\le \frac na\),可得 \(nq\le \frac{n^2}a\);又因为 \(nq\) 是整数,\(\lfloor\frac{n^2}{a}\rfloor\) 是小于等于 \(\frac{n^2}a\) 的最大正整数,所以 $nq\le \lfloor\frac{n^2}{a}\rfloor \rightarrow n\times\lfloor\frac{n}{a}\rfloor\le \lfloor\frac{n^2}{a}\rfloor $。

点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;auto ask = [](int x, int y)->bool{std::cout << x << " " << y << std::endl;int res;std::cin >> res;return res;};for(int i = 1; i <= n; i += 1) {for(int j = 1; j <= n; j += 1) {int to = j + i;if(to > n){to -= n;}if(ask(j, to)) {return ;}}}}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}
http://www.hskmm.com/?act=detail&tid=28028

相关文章:

  • 现代软件工程阅读和提问作业-1
  • 一种CDN动态加速回源白名单选路及降低源站探测量的方法
  • Windows系统-应用问题全面剖析Ⅰ:德承工控机DA-1200在Windows操作系统下[开机黑屏]的解决方法 - Johnny
  • 某中心在旧金山设立AGI实验室专注长期AI研究
  • Appcrawler自动遍历工具-智能遍历测试与测试用例生成
  • [USACO20FEB] Clock Tree S
  • 光储充一体化 + MyEMS:新能源场站的 “能源管家” 是这样工作的
  • idea插件Doc View
  • PGSQL + patroni + timescaledb 集群搭建
  • 随着种植精细化需求提升,草莓滴灌管、圆柱式滴灌管及 PVC 滴灌管成为节水灌溉核心装备,盘点五家实力厂家的特色产品
  • 2025 年最新推荐 OCR 图片识别软件厂商榜单:全面解析文字识别与格式转换服务商技术实力及服务能力ocr图片转excel/ocr图片转word厂商推荐
  • 2025 年高纯硼酸生产厂家最新推荐榜单:覆盖多领域优选,助力企业精准找高性能产品制造商核级/半导体/医用/电子/颗粒高纯硼酸厂家推荐
  • 计数集锦2
  • app.Environment.IsDevelopment()了解
  • 2025 年最新注浆管生产厂家综合实力排行榜:聚焦高精度与国企合作案例的优质厂家推荐管棚管/地质/边坡支护/袖阀/锚杆/岩心注浆管厂家推荐
  • 微算法科技(NASDAQ:MLGO)基于任务迁移的弹性框架重塑动态扩缩容,赋能边缘智能计算
  • 从小时级到分钟级:多点DMALL如何用Apache SeaTunnel把数据集成成本砍到1/3?
  • 2025 最新隔音棉生产厂家口碑推荐榜:甄选实力与品质兼具的品牌,含西南 / 昆明高性价比厂商最新推荐防火墙/内衬/鸡蛋/聚酯纤维/装修/吊顶隔音棉厂家推荐
  • 2025 升降杆厂家TOP 榜:梁山信达恒泰,专注多领域设备供应,气动型升降杆源头厂家推荐!
  • Playwright MCP 与 Claude 的完美协作:打造网页操作智能体
  • 2025 年高强钢板厂家最新推荐排行榜:聚焦国内优质企业,涵盖多型号产品,助力工业采购精准选型Q550D/合金/HG785D/ Q690D/S960QL/700L高强钢板厂家推荐
  • 2025 年最新推荐耐磨钢板生产厂家排行榜:涵盖高锰 / 堆焊 / 双金属 / NM 系列及无磁类型,解决采购难题助力企业选高性价比品牌
  • 高纯气体管道工程安装公司厂家推荐/管道施工队哪家好?
  • 找ant组件库对应样式
  • 指针
  • 达芬奇中文入门到精通视频教程DaVinci Resolve常用快捷键
  • 2025 年最新推荐!涵盖系统智能断桥窄边等多类型铝门窗厂家榜单,优秀生产厂家实力盘点智能/断桥/窄边/定制/全景/阳光房/隐框铝门窗厂家推荐
  • 读书笔记:**Oracle 中的数字类型:怎么选?怎么用?**
  • 什么是Symbol?
  • 2025 年门窗厂家推荐排行榜,新标门窗从型材到成品实现全链新标造铝合金门窗 / 系统门窗推荐这十家公司