http://codeforces.com/problemset/problem/923/D
A
良問。どこまで減らせるかが貪欲で求まる。
B
雪山について独立に考えれば。
C
よくあるbitのやつ。これtrieでやるのかなぁ…segtreeっぽくしちゃったけど。また使いそうなので貼っときます。
int K = 1; struct node { int lat, rat, sum; node() { lat = -1, rat = -1, sum = 0; } }; node seg[30 * MAX_N]; void update(int a, int v, int k, int l, int r) { //a.. at, k... segat // debug(a, v, k, l, r, seg[k].lat, seg[k].rat); if(r - l == 1) { seg[k].sum += v; } else { int m = (l + r) / 2; if(a < m) { if(seg[k].lat == -1) { seg[k].lat = K; K++; } update(a, v, seg[k].lat, l, m); //k } if(m <= a) { if(seg[k].rat == -1) { seg[k].rat = K; K++; } update(a, v, seg[k].rat, m, r); } seg[k].sum = seg[seg[k].lat].sum + seg[seg[k].rat].sum; } } int get_min(int a, int bat, int k, int l, int r) { if(bat == -1) return l; if(!(a & (1 << bat))) { //bat is 0. 0 is preferred if(seg[k].lat != -1 && seg[seg[k].lat].sum) { return get_min(a, bat - 1, seg[k].lat, l, (l + r) / 2); } else { return get_min(a, bat - 1, seg[k].rat, (l + r) / 2, r); } } else { if(seg[k].rat != -1 && seg[seg[k].rat].sum) { return get_min(a, bat - 1, seg[k].rat, (l + r) / 2, r); } else { return get_min(a, bat - 1, seg[k].lat, l, (l + r) / 2); } } } void seg_show(int k, int l, int r) { debug(k, l, r, seg[k].lat, seg[k].rat, seg[k].sum); if(seg[k].lat != -1) { seg_show(seg[k].lat, l, (l + r) / 2); } if(seg[k].rat != -1) { seg_show(seg[k].rat, (l + r) / 2, r); } } int N; int A[MAX_N], B[MAX_N]; const int mv = 30; void solve() { cin >> N; rep(i, 0, N) cin >> A[i]; rep(i, 0, N) { cin >> B[i]; update(B[i], 1, 0, 0, (1 << mv)); } // seg_show(0, 0, (1 << mv)); rep(i, 0, N) { int t = get_min(A[i], mv - 1, 0, 0, (1 << mv)); cout << (A[i] ^ t) << "\n"; // debug(A[i], t); update(t, -1, 0, 0, (1 << mv)); } }
D
B->Cとできるし、Bの偶数個だけ数えれば良いやんと思ったらいろいろ考えてないケースがたくさんあって場合分け地獄にハマった…
煩雑になったら、何で場合分けするかちゃんと考えなおしたほうがいいですね。