暴力进前五 /cy
选数
Arisu 选一个数
Bob 会在某个时刻,将
Arisu 想要最大化最后的
求最后的
记
(
发现
问题变成了有若干个数,选一个数使得该数异或上这些数都某一个数的最小值最大。
把所有的
typedef pair<int, int> pii;
const int MAXN = 1e5 + 10, MAXLOG = 30;
int n, m, arr[MAXN], pre[MAXN], suf[MAXN], ans1 = -1, ans2;
int get(int x) {
return ((x >> (n - 1)) | (x << 1)) & ((1ll << (n)) - 1);
}
#define get_bit(S, i) ((S >> i) & 1)
struct Trie {
int node_cnt;
struct Node { int ch[2], is_leaf, f, cnt; } t[MAXN << 4];
void ins(int num) {
int cur = 0;
per(idx, 30, 0) {
int val = get_bit(num, idx);
if (!t[cur].ch[val]) t[cur].ch[val] = ++node_cnt;
cur = t[cur].ch[val];
}
t[cur].is_leaf = true;
}
void dfs(int cur, int idx) {
if (idx == 0) return t[cur].cnt = 1, void();
if (t[cur].ch[0]) dfs(t[cur].ch[0], idx - 1);
if (t[cur].ch[1]) dfs(t[cur].ch[1], idx - 1);
if (!t[cur].ch[0] || !t[cur].ch[1]) {
t[cur].f = t[t[cur].ch[0]].f + t[t[cur].ch[1]].f + ((idx < n) ? (1 << (idx - 1)) : 0);
t[cur].cnt = t[t[cur].ch[1]].cnt + t[t[cur].ch[0]].cnt;
} else {
t[cur].f = max(t[t[cur].ch[0]].f, t[t[cur].ch[1]].f);
t[cur].cnt = (t[t[cur].ch[0]].f == t[cur].f) * t[t[cur].ch[0]].cnt + (t[t[cur].ch[1]].f == t[cur].f) * t[t[cur].ch[1]].cnt;
}
}
} trie;
int main() {
IO::read(n), IO::read(m);
rep(i, 1, m) IO::read(arr[i]), pre[i] = pre[i - 1] ^ arr[i];
per(i, m, 1) suf[i] = suf[i + 1] ^ arr[i];
rep(i, 0, m) trie.ins(get(pre[i]) ^ suf[i + 1]);
trie.dfs(0, 31);
printf("%d\n%d\n", trie.t[0].f, trie.t[0].cnt);
return 0;
}
模板
一棵树,每个节点有一个容量上限。每次操作
最后询问每个点里面有多少种颜色的点。
本题的大题思路非常明确:处理出每个点被装满的时刻,然后依次进行操作,并将该时刻对应装满的点答案求出来。点-根路径加颜色,求点颜色个数非常经典,set
和 BIT 就行。
问题是如何求出被装满的时刻。
这道题毒瘤之处在于,是父亲继承所有儿子,而不是儿子继承父亲。所以普通的可持久化线段树继承父亲在这里并不适用。
自然的,想到 dsu on tree。线段树该节点子树内第
时间复杂度
更好的做法是,我们完全可以用可持久化线段树处理出每个时刻上的前缀区间的操作情况(同上面一样),并且查询的时候我们只关注该点的子树内的那个区间就行。这样区间求第
typedef pair<int, int> pii;
const int MAXN = 1e5 + 10;
int n, m, q;
int head[MAXN], ecnt;
struct Edge { int nxt, to; } e[MAXN << 1];
void add(int u, int v) { e[++ecnt].nxt = head[u], e[ecnt].to = v, head[u] = ecnt; }
int dtp[MAXN], tim[MAXN];
struct Vertix { int dfn, sz, son, top, dep, fa; } vtx[MAXN];
int dfsclock;
void dfs(int u, int fr) {
vtx[u].sz = 1, dtp[ vtx[u].dfn = ++dfsclock ] = u, vtx[u].dep = vtx[ vtx[u].fa = fr ].dep + 1;
for (int _ = head[u], v; _; _ = e[_].nxt) {
v = e[_].to;
if (v == fr) continue;
dfs(v, u);
if (vtx[vtx[u].son].sz < vtx[v].sz) vtx[u].son = v;
vtx[u].sz += vtx[v].sz;
}
}
void getTop(int u, int top) {
vtx[u].top = top;
if (vtx[u].son) getTop(vtx[u].son, top);
for (int _ = head[u], v; _; _ = e[_].nxt) {
v = e[_].to;
if (v == vtx[u].fa || v == vtx[u].son) continue;
getTop(v, v);
}
}
int LCA(int u, int v) {
while (vtx[u].top != vtx[v].top) {
if (vtx[vtx[u].top].dep < vtx[vtx[v].top].dep) swap(u, v);
u = vtx[vtx[u].top].fa;
}
return vtx[u].dep < vtx[v].dep ? u : v;
}
struct PersistentSegmentTree {
#define mid ((l + r) >> 1)
#define qls t[cur].ls, l, mid
#define qrs t[cur].rs, mid + 1, r
int node_cnt, rt[MAXN];
int& operator [](const int& x) { return rt[x]; }
struct Node { int ls, rs, dat; } t[MAXN * 20];
void ins(int pre, int& cur, int l, int r, int pos, int val) {
cur = ++node_cnt;
t[cur] = t[pre], t[cur].dat += val;
if (l == r) return ;
if (pos <= mid) ins(t[pre].ls, qls, pos, val);
else ins(t[pre].rs, qrs, pos, val);
}
int query(int pre, int cur, int l, int r, int k) {
if (l == r) return k > 1 ? m : l;
int cnt = t[t[cur].ls].dat - t[t[pre].ls].dat;
if (cnt < k) return query(t[pre].rs, qrs, k - (t[t[cur].ls].dat - t[t[pre].ls].dat));
else return query(t[pre].ls, qls, k);
}
} sgt;
struct BIT {
int bit[MAXN];
void add(int x, int val) { for (; x < MAXN; x += x & -x) bit[x] += val; }
int query(int x) { if (!x) return 0; int ret = 0; for (; x; x -= x & -x) ret += bit[x]; return ret; }
} bit;
int ans[MAXN], table[MAXN], R[MAXN];
pii opt_arr[MAXN];
int r_num[MAXN], k[MAXN];
vector<int> opt[MAXN];
vector<int> tim_vtx[MAXN];
set<int> col_dfn[MAXN];
int main() {
IO::read(n);
rep(i, 1, n - 1) {
int u, v; IO::read(u), IO::read(v);
add(u, v), add(v, u);
}
dfs(1, 0), getTop(1, 1);
rep(i, 1, n) IO::read(k[i]);
IO::read(m);
rep(i, 1, m) {
int x, c; IO::read(x), IO::read(c), table[i] = c;
opt_arr[i] = make_pair(x, c);
opt[vtx[x].dfn].push_back(i);
}
rep(i, 1, n) {
R[i] = R[i - 1];
for (auto cur_opt : opt[i]) {
++R[i];
sgt.ins(sgt[R[i] - 1], sgt[R[i]], 0, m, cur_opt, 1);
}
}
rep(i, 1, n) {
tim[i] = sgt.query(sgt[R[vtx[i].dfn - 1]], sgt[R[vtx[i].dfn + vtx[i].sz - 1]], 0, m, k[i]);
tim_vtx[tim[i]].push_back(i);
}
sort(table + 1, table + m + 1); int tablesize = unique(table + 1, table + m + 1) - table - 1;
rep(i, 1, m) {
int cur_col = lower_bound(table + 1, table + tablesize + 1, opt_arr[i].second) - table, cur_u = opt_arr[i].first;
if (!col_dfn[cur_col].count(vtx[cur_u].dfn)) {
col_dfn[cur_col].insert(vtx[cur_u].dfn); int pre_node = 0, nxt_node = 0;
auto p = col_dfn[cur_col].find(vtx[cur_u].dfn);
if (p != col_dfn[cur_col].begin()) pre_node = *(--p), ++p;
++p;
if (p != col_dfn[cur_col].end()) nxt_node = *p;
bit.add(vtx[cur_u].dfn, 1);
if (pre_node) bit.add(vtx[LCA(dtp[pre_node], cur_u)].dfn, -1);
if (nxt_node) bit.add(vtx[LCA(dtp[nxt_node], cur_u)].dfn, -1);
if (pre_node && nxt_node) bit.add(vtx[LCA(dtp[pre_node], dtp[nxt_node])].dfn, 1);
}
for (auto cur : tim_vtx[i]) {
ans[cur] = bit.query(vtx[cur].dfn + vtx[cur].sz - 1) - bit.query(vtx[cur].dfn - 1);
}
}
IO::read(q);
rep(i, 1, q) {
int x; IO::read(x);
printf("%d\n", ans[x]);
}
return 0;
}
总结
这场全是暴力,进了前五。暴力都是用了一些普及组的数据结构之类的。
原来只要没挂分分数就会很高。