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

NOIP 模拟赛八

A.

\(\oplus\) 有一个很好的性质,操作两次相当于没变。

考虑增量构造。

x y z 变成 x x c

x y^z y^z

x^y^z y^z x^y^z

x x x^y^z

\(3\) 次操作做到。

最后会剩下 \(n\) 无法操作,判断此时是否合法,如果否,通过类似上面的操作将 \(n\)\(1\) 交换位置。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inline
#define cmx(a, b) ((a) > (b) ? (a) : (b))
#define cmn(a, b) ((a) < (b) ? (a) : (b))
#define gmx(a, b) a = cmx(a, b)
#define gmn(a, b) a = cmn(a, b)template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int LN = 3e5 + 7;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;int n, a[LN];
std::vector <PII> ans;bool ENDPOS;il void op(int x, int y) { if (a[x] == a[y]) return; a[x] ^= a[y], a[y] = a[x], ans.push_back({x, y}); }int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock();std::cin >> n;lep(i, 1, n) std::cin >> a[i];lep(i, 2, n - 1) op(i, i + 1), op(i - 1, i + 1), op(i - 1, i);if (a[n] < a[1]) op(n, 1), op(n - 1, 1), op(n - 1, n);std::cout << (int)ans.size() << '\n';for (auto t : ans) std::cout << t.first << ' ' << t.second << '\n';#ifdef DEBUGstd::cerr << clock() - c1 << " ms " << fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << " MB\n";
#endifreturn 0;
}

B.

简单的想到如果我们有一个递增的序列在首,可以如下操作。

bcd A a B

B A a bcd\(a\) 接到 \(bcd\) 前面,这时再将 abcd 放到队首,就可以 \(\Theta(2\times n)\) 解决。

但这样还不够,发现队尾时可以通过类似的方法往后面接。

提示我们初始从 \(\frac{n}{2}\) 开始接,交替往前后接,这样就可以做到 \(\Theta(n)\) 次了。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inline
#define cmx(a, b) ((a) > (b) ? (a) : (b))
#define cmn(a, b) ((a) < (b) ? (a) : (b))
#define gmx(a, b) a = cmx(a, b)
#define gmn(a, b) a = cmn(a, b)template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int LN = 2e5 + 7;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;int n, a[LN], cur[LN];
int sz[LN], fa[LN], ls[LN], rs[LN], rt, x, y, z;
unsigned rnd[LN];
std::vector <std::array<int, 3> > Ans;
std::vector <int> pos[LN];bool ENDPOS;il int pu(int p) {sz[p] = sz[ls[p]] + sz[rs[p]] + 1;if (ls[p]) fa[ls[p]] = p; if (rs[p]) fa[rs[p]] = p;return p;
}
void slk(int p, int k, int& x, int& y) {if (!p) return x = y = 0, void();if (k <= sz[ls[p]]) y = p, slk(ls[p], k, x, ls[y]);else x = p, slk(rs[p], k - sz[ls[p]] - 1, rs[x], y); pu(p);
}
int mrg(int x, int y) {if (!x or !y) return x | y;if (rnd[x] > rnd[y]) { rs[x] = mrg(rs[x], y); return pu(x); }ls[y] = mrg(x, ls[y]); return pu(y);
}
int rank(int x) {int ans = sz[ls[x]] + 1;while (x) {if (rs[fa[x]] == x) ans += sz[ls[fa[x]]] + 1;x = fa[x];}return ans;
}
std::mt19937 rd(time(0));
il void ins(int x) { sz[x] = 1, rnd[x] = rd(); rt = mrg(rt, x); }
void op(int a, int b, int c) {Ans.push_back({a, b, c});slk(rt, a + b, x, z), slk(x, a, x, y);rt = mrg(mrg(z, y), x);
}int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock();std::cin >> n;lep(i, 1, n) std::cin >> a[i], pos[a[i]].push_back(i);lep(i, 1, n) std::cin >> a[i], a[i] = pos[a[i]][cur[a[i]]++];lep(i, 1, n) ins(i);int l = (n + 1) / 2 + 1, r = (n + 1) / 2, cnt = 0, k;while (cnt < n) {if (!(cnt & 1)) {k = rank(a[--l]), op(cnt, k - cnt, n - k);++cnt;} else {k = rank(a[++r]), op(k - 1, n - cnt - k + 1, cnt);++cnt;}}std::cout << (int)Ans.size() << '\n';for (auto t : Ans) {for (auto v : t) std::cout << v << ' ';std::cout << '\n';}#ifdef DEBUGstd::cerr << clock() - c1 << " ms " << fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << " MB\n";
#endifreturn 0;
}

C.

分奇偶性如下构造即可。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inline
#define cmx(a, b) ((a) > (b) ? (a) : (b))
#define cmn(a, b) ((a) < (b) ? (a) : (b))
#define gmx(a, b) a = cmx(a, b)
#define gmn(a, b) a = cmn(a, b)template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int LN = 2e5 + 7;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;int T, n;bool ENDPOS;int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock();std::cin >> T;while (T--) {std::cin >> n;if (n == 1) {std::cout << "0 0 1 1\n0 1 1 0\n";} else {std::cout << "0 " << n << ' ' << n << ' ' << n - 1 << '\n';std::cout << n - 1 << ' ' << n << ' ' << n << " 0\n";if (n & 1) {std::cout << "0 0 " << n << ' ' << n - 1 << '\n';std::cout << "0 1 " << n - 1 << ' ' << n << '\n';lep(i, 1, n / 2 - 1)std::cout << i * 2 << " 0 " << n << ' ' << n - 1 - i * 2 << '\n',std::cout << "0 " << i * 2 << ' ' << n - 1 - i * 2 << ' ' << n << '\n';} else {std::cout << "0 0 " << n << ' ' << n << '\n';lep(i, 1, n / 2 - 1)std::cout << i * 2 - 1 << " 0 " << n << ' ' << n - i * 2 << '\n',std::cout << "0 " << i * 2 - 1 << ' ' << n - i * 2 << ' ' << n << '\n';}}}#ifdef DEBUGstd::cerr << clock() - c1 << " ms " << fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << " MB\n";
#endifreturn 0;
}

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

相关文章:

  • 第三篇
  • 基于cloacked-pixel隐写工具爆破项目
  • 随便写的
  • Bcliux-docker-nacos2.2.0升级至2.2.3版本
  • 社交网络架构。京东场景题:亿级用户100Wqps 社交关系如何设计?如何查看我的关注,关注我的?
  • go 面试题
  • 事件和图形界面(暂未完成)
  • 什么是sql 慢日志。哈罗面试:没开sql慢日志,怎么发现慢 sql?
  • Spring连环炮。哈罗面试:Spring Bean生命周期,Spring怎么创建Bean的,BFPP和BPP的x别
  • redis 大 key 优化。哈罗面试:redis 有个大 key需要在线优化, 不能影响现有业务,请求不能大量到库,怎么优化?
  • ACL高可用架构。希音面试:第三方挂了,我们总在背锅。来一 靠谱的 高可用方案,让 外部依赖 稳如泰山
  • 软工9.24
  • 2025CSP-S模拟赛51
  • 2025年9月24日 - 20243867孙堃2405
  • 【星海随笔】RabbitMQ开发篇 - 教程
  • P13754 【MX-X17-T3】Distraction
  • 2025.9.24
  • 初学汇编
  • 架构图设计还得是华为 - 智慧园区
  • 解决zsh: corrupt history file /home/sgud4h5gh/.zsh_history的办法
  • StarRocks GitHub 工作流程
  • 对象初始化器的使用方法
  • C++、Java 和 Python 在输入输出差别
  • 我的学习记录之自我介绍、思维导图和监督措施
  • 用 Java 和 Tesseract 进行验证码识别:基础实现与优化
  • Java第二次实验
  • 详细介绍:【2025PolarCTF秋季个人赛】WEB方向wp
  • 英语_阅读
  • Nuget安装以及西门子PLC通信
  • 每日反思(2025_09_24)