mydcwfy's Blog

考完被抓回去学常规，现在稍微闲点，来补游记。

省流：$100 + 55 + 48 + 95 + 40 + 0 = 338$，看似问题不大。

题意：给定 $n$ 个数 $a_i$，每个数小于 $2 ^ m$，问对于每个 $i\in [0, m]$ 求出任意选出一些数使得异或和 __builtin_popcount 为 $i$ 的方案数。$n\leq 2\times 10 ^ 5$，$m\leq 53$。

题意：给定 $n$ 个数 $a_i$，每个数有一个代价 $c_i$，你可以选择一次集合 $S$，让集合内部的每个数都可以被一个 $\leq k$ 的因数除掉，选择的代价为 $|S|\sum_{i\in S} c_i$。要求使得操作过后 $\gcd_i a_i = 1$ 的最小代价。$n\leq 10 ^ 6$，$a_i\leq 10 ^ {12}$，$c_i\leq 10 ^ 9$。

题意：给定三棵大小为 $n$ 的树，求 $\min_{i < j} \{\text{dist}_1(i, j) + \text{dist}_2(i, j) + \text{dist}_3(i, j)\}$。$n\leq 10 ^ 5$，$w_i\leq 10 ^ {12}$。

题意：给定 $n$ 个人两两之间的认识关系，对于一个排列 $p$，设 $s_i$ 表示 $p_i$ 和 $p_{i + 1}$ 的认识关系。问对于每个 $s$ 有多少个 $p$ 能生成该 $s$。$n\leq 18$。

题意：给定一个长度为 $2n$ 的合法括号序列，每个左括号有一个权值，每次你可以把 $p(A)(B)q$ 改成 $p(A()B)q$ 的形式，代价为 $(A)$ 的第一个左括号乘 $x$ 加上 $(B)$ 的第一个左括号乘 $y$（$A, B$ 必须是合法括号序列，$p, q$ 无限制），或者任意交换相邻的合法括号序列，不需要代价。问最少需要多少代价才能使得括号序列不包含 $()()$ 的结构。$n\leq 4\times 10 ^ 5$，$0\leq x, y\leq 1$，$a_i\leq 10 ^ 7$。

题意：有 $n$ 个人发了 $m$ 条消息，消息分为“xxx 楼下”“xxx 楼上”和学术消息。你需要合理安排这 $m$ 条消息的顺序，使得符合实际条件的楼上、楼下型消息尽量多，需要给出构造。保证每个人至少发了一条学术消息。$n\leq m\leq 77777$，$\sum m\leq 2.5\times 10 ^ 5$。

省选完了直接回去 whk 了，后面逐渐忘了这场比赛，现在校内重做才来改题。

题意：有 $m$ 张卡牌分为 $k$ 种，每种都是偶数张，你需要顺次把 $m$ 张放进 $n$ 个栈，如果存在一个栈相邻两个种类相同，那么立刻消去。同时你可以选择两个栈，他们的底部卡牌种类需要相同，然后消去这两张卡牌。要求放完 $m$ 张卡牌过后 $n$ 个栈都是空的。请给出一个构造方案。$m\leq 2\times 10 ^ 6$，$n\leq 300$，$k = 2n - 2$ 或者 $k = 2n - 1$。

总算有时间来补 NOIp 了。

挂分场，差点送退役……

题意：给定一些区间的集合，最开始为空。给出 $q$ 次操作，会给出 $op, l, r$：

1. $op = 1$：向集合插入一个新的元素 $[l, r]$。
2. $op = 2$：对于集合的每一个元素，如果其与 $[l, r]$ 有交，就改为其与 $[l, r]$ 的交。
3. $op = 3$：查询集合中每一个元素与 $[l, r]$ 交的长度的和。

$[l, r]$ 的长度定义为 $r - l$。部分测试点强制在线。假设 $op = 1, 2, 3$ 的操作次数分别为 $k_1, k_2, k_3$，则有 $k_1, k_2\leq 10 ^ 5, k_3\leq 3\times 10 ^ 5$，$1\leq l\leq r\leq 2\times 10 ^ 5$。

题意：给定 $n$ 个数的序列，每次询问一段区间的乘积是不是立方数。$n, q\leq 2\times 10 ^ 5$，$A_i\leq 10 ^ 6$，3s。

题意：给定一棵 $n$ 的点的根为 1 的树，定义一次操作为把 $x$ 的所有儿子接到 $x$ 父亲处，并删除 $x$。$q$ 次询问给定 $u, k$，输出任意操作之后 $son(u) - mk$ 的最大值，$m$ 表示操作次数。$n, q\leq 2 \times 10 ^ 5$，6s。

中规中矩的一场……

没去打，赛后就做了 EFG 三个题。

题意：有 $n$ 种零食，每种零食有 $a_i$ 片，有 $m$ 个小孩，每种小孩每种零食最多拿 $b_i$ 片（$b_i$ 只和小孩相关），一共不能超过 $c_i$ 片。问最多能拿走的零食片。$n, m\leq 2\times 10 ^ 5$，$a_i, c_i\leq 10 ^ {12}$，$b_i\leq 10 ^ 7$。

题意：定义对序列 $A$（$A$ 包含整数二元组）操作一次为如下操作：选定任意两个相邻的二元组 $(a, b)$ 和 $(c, d)$，在他们中间插入 $(a + c, b + d)$。定义一个二元组序列的价值为从 $A = \{(0, 1), (1, 0)\}$ 开始至少要操作多少次才能包含序列中的所有二元组。如果无法的话价值就是 0。现给定一个长度为 $n$ 的二元组序列 $T$，问所有连续子序列的价值和，对 998244353 取模。$n\leq 10 ^ 5$，$a, b\leq 10 ^ 9$。

题意：维护一个集合 $a$，最开始有 $n$ 个元素，有 $m$ 次操作或者询问：

1. 将 $a_i\in [l, r]$ 的值全部与 $x$。
2. 将 $a_i\in [l, r]$ 的值全部或 $x$。
3. 将 $a_i\in [l, r]$ 的值全部异或 $x$。
4. 询问在 $[l, r]$ 中有多少个不同的 $a_i$。

$n\leq 2\times 10 ^ 5$，$m\leq 10 ^ 5$，$0\leq a_i < 2 ^ {20}$。

题意：交互题。给出一棵树的点数 $n$，你每次询问可以给出一个点集 $S$ 和一个点 $x$，可以得到 $x$ 是否在点集 $S$ 的最小连通块中，需要还原出树。$n = 1000$，你最多可以询问 22000 次。求构造方案。