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;
}