linux 做网站,中铁建设集团有限公司招聘,怎么开一个平台,sem投放是什么意思CF1361C. Johnny and Megan’s Necklace
Solution
真duliu#xff0c;快做吐了。。。
刚开始想了一个假做法#xff08;但前面还是很真的#xff09;。
假的做法大概是你发现这个东西具有传递性#xff0c;因此你考虑把aia_iai翻转后在后面补0直到20位之后#xff0…CF1361C. Johnny and Megan’s Necklace
Solution
真duliu快做吐了。。。
刚开始想了一个假做法但前面还是很真的。
假的做法大概是你发现这个东西具有传递性因此你考虑把aia_iai翻转后在后面补0直到20位之后从小到大枚举iii验证答案是否为20−i20-i20−i。
然后把从高到低的20−i20-i20−i位相同的点之间都连上边。
因为一些特殊的传递性axorb≥2x,bxorc≥2y→axorc≥2min(x,y)a\;xor\;b\geq 2^x,b\;xor\;c\geq 2^y\to a\;xor\;c\geq 2^{min(x,y)}axorb≥2x,bxorc≥2y→axorc≥2min(x,y)所以我们只需要相邻连边并查集维护然后就可以缩点在新图上有若干条边要把它们都接起来。
然后就假在我以为这题性质特殊可以直接用set模拟一遍求出方案。但实际上这是一个欧拉回路问题我们把边连上之后有解的条件为存在包含所有边的欧拉回路因此我们连边之后跑欧拉回路即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn)。记得加当前弧优化。
Code
#include bits/stdc.husing namespace std;templatetypename T inline bool upmin(T x, T y) { return y x ? x y, 1 : 0; }
templatetypename 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 pairint, int PR;
typedef vectorint 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;}templateclass Iinline 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;}templateclass Iinline 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;vectorint 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;
}
