【咕】2025 Beijing WC (CNUHS) B

2025/02/05 (贪心 凸性 拟阵)

$n$ 个区间，选出尽可能多个两两不交的区间。

$n\le5\times10^4$。

---

实现来自 AzusidNya，拜谢。

$n$ 个区间，选出尽可能少个区间覆盖 $1\sim m$。

$n\le10^5$。

---

$n$ 个点 $m$ 个区间，选出尽可能少个点覆盖所有区间。

$n,m\le10^6$。

---

$n+m$ 个点的二分图，左侧第 $i$ 个点与右侧第 $1\sim p_i$ 个点连边。求最大匹配。

$n\le10^6$。

---

$n+m$ 个点的二分图，左侧第 $i$ 个点与右侧第 $l_i\sim r_i$ 个点连边。求最大匹配。

$n,m\le10^6$。

---

$n+m$ 个点的二分图，左侧第 $i$ 个点与右侧第 $j$ 个点连边，其中 $j$ 满足 $x_j\le a_i$ 且 $y_j\le b_i$。求最大匹配。

$n\le10^6$。

---

$n+m$ 个点的二分图，左侧第 $i$ 个点与右侧第 $1\sim p_i$ 个点连边。右侧点有点权 $a_j$。求点权和最大的匹配。

$n\le10^6$。

---

给定 $n$ 个 01 序列 $a_i$，将他们以任意顺序拼接，最小化逆序对数。

$n\le10^6$。

---

$n$ 个点的有根树，有点权 $a_i\in\{0,1\}$。每次可以选择没有父亲的点删除，并且其点权加入序列末尾。最小化序列逆序对数。

$n\le2\times10^5$。

---

---

$n$ 个奖池，第 $i$ 个奖池的奖金是 $p_i$，其他人已押入 $l_i$ 张彩票。

$t$ 张彩票，将彩票分配到这些奖池中，需要保证你在第 $i$ 个奖池中押入的彩票数 $t_i$ 不能超过 $l_i$。对于第 $i$ 个奖池，中奖概率为 $\frac{t_i}{t_i + l_i}$。若中奖，则获得这个奖池的全部奖金 $p_i$。

$q$ 次事件，每次事件会使某个 $l_i$ 加 $1$ 或减 $1$。询问在最佳分配方案下获得的奖金总数的最大期望值。

$n,t,q\le2\times10^5$，$p_i,l_i\le 10^3$，答案精度误差 $\le10^{-6}$。

---

题意较复杂，不多赘述。

---

思路来自 gcz，拜谢。

$n$ 个二元组 $(v_i,w_i)$。对于正整数 $s$，执行操作：

• 对于每个二元组，记 $f_i(s)$ 表示二进制下的 $s\text{ bitand }w_i$ 中 $1$ 的个数，则令 $v_i\gets(-1)^{f_i(s)}\cdot v_i$。

构造 $s$，使得操作前后 $\sum v_i$ 符号相反。

$n\le3\times10^5$。

$$\text{ans}_s=\sum_{i=1}^n(-1)^{f_i(s)}\cdot v_i$$ $$\sum_{s=0}^{2^{62}-1}\text{ans}_s=\sum_{s=0}^{2^{62}-1}\sum_{i=1}^n(-1)^{f_i(s)}\cdot v_i=\sum_{i=1}^n\sum_{s=0}^{2^{62}-1}(-1)^{f_i(s)}\cdot v_i$$ $$\sum_{s=0}^{2^{62}-1}\text{ans}_s=\sum_{i=1}^n\sum_{s=0}^{2^{62}-1}(-1)^{f_i(s)}\cdot v_i=\sum_{i=1}^n0=0$$ $$d(l,r)=\sum_{i=1}^n\sum_{s=l}^r(-1)^{f_i(s)}\cdot v_i$$

---

题意较复杂，不多赘述。

---

To be continue.

---

---

---

2025/02/06 (DP 及其优化)

$n$ 个集合 $S_i$，满足 $S_i\subseteq[1,m]\cap\Z$。其中有些集合未确定，你可以自行钦定。

设可重集 $T$，初始为 $\varnothing$。依次遍历每个集合，同时向 $T$ 中加入 $S_i$ 中的所有元素。若 $T$ 包含重复元素，则令 $T\gets\varnothing$。

钦定未确定的集合，求 $|T|$ 的最大值。

$n,m\le2\times10^5$。

• 位置 $j$ 可被清空，即 $f_j=1$；
• 区间 $(j,i)$ 中无重复元素，即 $\bigcap\limits_{j<k<i}S_k=\varnothing$；
• 到位置 $i$ 时有重复元素，即 $\left(\bigcup\limits_{j<k<i}S_k\right)\cap S_i\ne\varnothing$。

---

$n$ 件物品，背包体积为 $A$，有 $B$ 个货币。第 $i$ 个物品价值 $p_i$，体积 $a_i$，每用 $b_i$ 个货币可以使其体积减少 $1$。求最大价值。

$n,A,B\le2\times10^3$。

---

长为 $n$ 的序列 $a_i$，消除长为 $x$ 的连续同色段的分数为 $x^2$。求最大分数。

$n\le200$。

$$f_{l,r}=\max_{l\le i_1<i_2<\cdots<i_k\le r}\{f_{l,i_1-1}+f_{i_1+1,i_2-1}+\cdots+f_{i_k+1,r}+k^2\}$$

---

$m$ 个三元组 $(a_i,b_i,c_i)$。构造长为 $n$ 的序列 $\{p_n\}$。若 $\min\limits_{a_i\le j\le b_i}p_j\le c_i$ 则产生 $\min\limits_{a_i\le j\le b_i}p_j$ 的贡献，否则没有贡献。试最大化贡献。

$n\le50$，$m\le4\times10^3$。

$$f_{l,r,k}=\max_{l\le p\le r}\{f_{l,p-1,k}+f_{p+1,r,k}+\text{cnt}(l,r,p,k)\cdot k\}$$

• $[a_i,b_i]\subseteq[l,r]$；
• $p\in[a_i,b_i]$；
• $c_i\ge k$。

• $[a_i,b_i]\subseteq[l,r]$；
• $c_i\ge k$。

$$\text{cnt}(l,r,p,k)=s_{l,r,k}-s_{l,p-1,k}-s_{p+1,r,k}$$

---

同 AT_arc169_c [ARC169C] Not So Consecutive。

有长为 $n$ 的值域为 $[1,k]$ 的序列 $\{a_n\}$，其中有些位置未填。填入这些数使得不存在长为 $l$ 的连续同色段，求方案数。对 $998244353$ 取模。

$n\le10^5$，$k\le100$。

---

---

---

---

---

---

---

2025/02/07 (模拟赛 树)

---

2025/02/08 (链剖 树上启发式合并 Prufer 点分治 边分治)

---

---

2025/02/09 (模拟赛 线段树)