2024.7.2

2024.7.2

T1

题面

总共 \(n\) 个数与 \(m\) 个限制，第 \(i\) 个限制给定 \(k_i\) 个数，表示这些数两两不能分为一组，问最少可以分为几组。

\(1\le k\le n\le 10^5,1\le m\le 4\)

题解

把每个人的参赛情况用一个 \([0,15]\) 中的整数 \(s\) 表示，再按照 \(\operatorname{popcount}(s)\) 从大到小贪心凑即可。（求证）复杂度 \(\mathcal O(2^{4m}+nm)\)

方法

• 贪心

T2

题面

给定一棵 \(n\) 个点的树和整数 \(k\)，边有边权。
定义一个树上连通块的权值为其中边权之和，你需要求满足「至多包含一个度数 \(>k\) 的点」的树上连通块的权值最大值。
注意，条件中的度数指连通块中的度数，而非原树中的度数。

\(1\le n\le 2\times 10^5,0\le k<n\)

题解

设 \(dp_{x,0/1}\) 表示以 \(x\) 为根的子树中 没有/有 度数 \(>k\) 的点，注意向上转移应该算上与父亲的边，与字数内答案不完全一样，转移即可

复杂度 \(\mathcal O(n)\)

方法

• 树形 DP

T3

题面

称一个正整数对 (a,b)合法，当且仅当存在正整数 \(k\) 和 \(k\) 组正整数对 \((h_i,w_i)\)，使得

• \(\sum_{i=1}^kh_iw_i=a\)

• \(\sum_{i=1}^kh_i+w_i=b\)

给定 \(n,m\)，求满足 \(a\in[1,n],b\in[1,m]\) 的正整数对中有多少是合法的。

\(1\le n,m\le 2\times 10^5\)

题解

这里是 \(c,s\le 6\times 10^3\) 的 \(49\) 分做法

令 \(dp_{a,b}\) 表示 \((a,b)\) 是否合法，则

\[dp_{a,b}=\mathop{\Large\land}\limits_{h\ge1,w\ge1,hw\le a,h+w\le b}dp_{a-hw,b-w-h} \]

可以 bitset 优化，这是 \(18\) 分的。

很难不借助打表注意到，\(\exist w\in \N^*,\forall a\in[1,n],b\in [w,2a],(a,b)合法\)

利用Excel 可得， \(w\approx 2.6\sqrt{n}\)，打表可得当 \(n\le 6\times 10^3，w\) 可取 \(200\)

于是只需要存储小于 \(w\) 的数据时间变为 \(\mathcal O(\frac{w^2n}{32})=\mathcal O(n^2)\)

可以过 \(49\) 分数据

正解：

方法

• 打表

  这种连数竞选手都不一定能证明的结论，不用计算机辅助证明还能用什么。

T4

题面

对于一个元素互不相同的序列 \(a_1,a_2,\cdots,a_n\)，定义一次合法的操作为：

• 选择一个 使得 \(i\in [2,n-1]\) 使得 \(a_{i-1}<a_i<a_{i+1}\) ，将 \(a_{i+1}\) 移动到 \(a_{i-1}\) 之前。

我们定义一个序列是合法的，当且仅当它能够由一个严格单调上升的序列通过有限多次操作得到。

给定排列 \(p_{1\sim n}\)。有 \(q\) 次修改，每次修改形如交换 \(p_x\) 和 \(p_y\) 的值。你需要在每次修改后，回答最小的正整数 \(k\)，满足 \(p_{k\sim n}\) 为一个合法的序列。

\(2\le n\le 10^5,1\le q\le 10^5,1\le x,y\le n,x\not=y,p是一个n阶排列\)

题解

考虑从一个严格递增序列开始操作的过程，发现操作过程中每个数右侧小于它的数的个数始终为偶数，并且显然任意满足这个条件的序列都合法，所以这个条件是充要的。

便有了 \(\mathcal O(n^2)\) 做法

考虑用分块维护这个信息。设 \(i\) 右侧有 \(r_i\) 个 \(<p_i\) 的数。假设交换 ，那么 \(x,y\) 所在的块可以暴力重构;对于中间的块，影响是一个值域区间内的 \(r\pm1\)。

于是可以想到每个块内部先排序，然后维护 \(r\) 的差分。这样的话发现需要对中间每个块做 lower_bound ，而块内是可以线性重构的。直接做时间复杂度\(\mathcal O(n\sqrt{n\log n})\)为 ，已经足以通过。

方法

• 模拟操作过程