CF1361C. Johnny and Megan’s Necklace

Solution

真duliu，快做吐了。。。

剛開始想了一個假做法（但前面還是很真的）。

假的做法大概是你發(fā)現(xiàn)這個東西具有傳遞性，因此你考慮把$a_i$翻轉(zhuǎn)后在后面補0直到20位之后，從小到大枚舉$i$，驗證答案是否為$20?i$。

然后把從高到低的$20?i$位相同的點之間都連上邊。

因為一些特殊的傳遞性（$axorb\ge 2^x,bxorc\ge 2^y\to axorc\ge 2^{min(x,y)}$），所以我們只需要相鄰連邊，并查集維護，然后就可以縮點，在新圖上有若干條邊，要把它們都接起來。

然后就假在我以為這題性質(zhì)特殊，可以直接用set模擬一遍求出方案。但實際上這是一個歐拉回路問題，我們把邊連上之后有解的條件為存在包含所有邊的歐拉回路，因此我們連邊之后跑歐拉回路即可。

時間復(fù)雜度$O(n\log n)$。（記得加當前弧優(yōu)化！）。

Code

#include <bits/stdc++.h>using namespace std;template<typename T> inline bool upmin(T &x, T y) { return y < x ? x = y, 1 : 0; } template<typename T> inline bool upmax(T &x, T y) { return x < y ? x = y, 1 : 0; }#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondtypedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int, int> PR; typedef vector<int> VI; const lod eps = 1e-9; const lod pi = acos(-1); const int oo = 1 << 30; const ll loo = 1ll << 60; const int mods = 998244353; const int MAXN = 2200005; const int INF = 0x3f3f3f3f; //1061109567 /*--------------------------------------------------------------------*/namespace FastIO{constexpr int SIZE = (1 << 21) + 1;int num = 0, f;char ibuf[SIZE], obuf[SIZE], que[65], *iS, *iT, *oS = obuf, *oT = obuf + SIZE - 1, c;#define gc() (iS == iT ? (iT = ((iS = ibuf) + fread(ibuf, 1, SIZE, stdin)), (iS == iT ? EOF : *iS ++)) : *iS ++)inline void flush() {fwrite(obuf, 1, oS - obuf, stdout);oS = obuf;}inline void putc(char c) {*oS ++ = c;if (oS == oT) flush();}inline void getc(char &c) {for (c = gc(); (c < 'a' || c > 'z') && c != EOF; c = gc());}inline void reads(char *st) {char c;int n = 0;getc(st[++ n]);for (c = gc(); c >= 'a' && c <= 'z' ; c = gc()) st[++ n] = c;}template<class I>inline void read(I &x) {for (f = 1, c = gc(); c < '0' || c > '9' ; c = gc()) if (c == '-') f = -1;for (x = 0; c >= '0' && c <= '9' ; c = gc()) x = (x << 3) + (x << 1) + (c & 15);x *= f;}template<class I>inline void print(I x) {if (x < 0) putc('-'), x = -x;if (!x) putc('0');while (x) que[++ num] = x % 10 + 48, x /= 10;while (num) putc(que[num --]);}struct Flusher_{~Flusher_(){flush();}} io_Flusher_; } using FastIO :: read; using FastIO :: putc; using FastIO :: reads; using FastIO :: print;vector<int> Ans; int start[MAXN], a[MAXN], b[MAXN], vis[MAXN], d[MAXN], head[MAXN], id[MAXN], n, N, edgenum, Num, opt = 0; struct enode{ int nxt, to, u, v; } e[MAXN];void add(int u, int v, int U, int V) {e[++ edgenum] = (enode){head[u], v, U, V}, head[u] = edgenum; } void dfs(int x) {for (int &i = start[x]; i ; i = e[i].nxt) {int t = i;if (vis[t]) continue;vis[t] = vis[t ^ 1] = 1;dfs(e[t].to);if (opt) Ans.PB(e[t].v), Ans.PB(e[t].u);else ++ Num, ++ Num;} } int check(int t) {edgenum = 1;for (int j = 0; j < 1 << 20 ; ++ j) head[j] = d[j] = vis[j] = 0;for (int j = 1; j <= n ; ++ j) {int x = (b[j * 2 - 1] >> t), y = (b[j * 2] >> t);add(x, y, j * 2 - 1, j * 2);add(y, x, j * 2, j * 2 - 1);++ d[x], ++ d[y];}int flag = 0;for (int j = 0; j < 1 << 20 ; ++ j) flag |= (d[j] & 1), start[j] = head[j];if (!flag) {Num = (opt ? INF : 0);dfs(b[1] >> t);if (Num < N) return 0; return 1;}return 0; } signed main() { #ifndef ONLINE_JUDGEfreopen("a.in", "r", stdin); #endifread(n), N = n << 1;for (int i = 1; i <= n ; ++ i) read(a[i * 2 - 1]), read(a[i * 2]);for (int i = 1; i <= N ; ++ i) for (int j = 0; j < 20 ; ++ j) b[i] = b[i] << 1 | (a[i] & 1), a[i] >>= 1;int l = 0, r = 20;while (l < r) {int mid = (l + r) >> 1;if (check(mid)) r = mid;else l = mid + 1;}opt = 1, check(r);print(20 - r), putc('\n');for (auto v : Ans) print(v), putc(' ');return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF1361C. Johnny and Megan‘s Necklace(构造，欧拉回路，传递闭包)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。