贪心

仍然是中规中矩的一场模拟赛。前两题正解,第三题暴力,第四题不会。

简略题解

A – 激光

考虑是否有两条及以上双向连边,若是则无解,若有一条则枚举要将哪一侧的发射器旋转到哪一方向。简单模拟即可。

B – 碰撞

这类数轴上带标号小球相撞的题目都有一个经典套路:两球相撞调转方向时,我们不认为是球本身转向,而认为两球仍然保持原方向运动,而其编号交换(更多…)

More
  • 2022年11月20日

感冒咳嗽,头实在是太晕了,打完前两题和后两题的暴力之后跑去睡了会觉。结果考得还行。

一句话题解

A – 破坏

简单的 O(m2k)\newcommand{\bigO}{\operatorname{O}}\bigO(m2^k) DP。记录每个节点的路径数奇偶性考虑是否翻转即可。

B – 共识

std::bitset 写的暴力大家都会。不过如果你胆子大些,不判断是否为部分分数据范围直接提交(加入随机化的)暴力,将喜提 100 pts\text{100 pts}

命题:现有一个由 2n2n 个元素构成的集合,保证 2n2\mid n。有 n+1n+1 个大小恰为 nn 的子集 S1,,Sn+1S_1,\cdots,S_{n+1}。则至少存在 n/2n/2 对无序对 (i,j),ij,i,j[1,n+1](i,j),i\neq j, i,j\in[1,n+1],使得 SiSjn/2|S_i\cap S_j|\geq n/2

证明(引自宋佳兴学长):记元素 p,p{1,,2n}p,p\in\{1,\cdots,2n\} 在所有子集中出现的次数为 cnt(p)\newcommand{\cnt}{\operatorname{cnt}}\cnt(p)。则显然有“所有子集两两之交的大小” i=1nj=i+1n+1SiSj=p=12n(cnt(p)2)\sum_{i=1}^{n}\sum_{j=i+1}^{n+1}|S_i\cap S_j|=\sum_{p=1}^{2n}\binom{\cnt(p)}{2}

考虑计算该式最小为何。不妨先考虑 (ab)+(nab)\binom{a}{b}+\binom{n-a}{b} 在何时取最小值。

引理(ab)+(nab),bn,a0,an\binom{a}{b}+\binom{n-a}{b}, b\leq n, a\geq 0, a\leq na=n/2a=\lfloor n/2\rfloor 处取最小值。

(更多…)

More
  • 2022年10月26日

恕我语文不好,实在不晓得用何种词汇来描述看到下文的感受:

此比赛为正常的提高组难度,甚至可以用来作为普及组模拟赛。 请选手 AK 后不要大声喧哗,以免影响他人 AK。

尤其是这套题的出题人是张隽铠的情况下。当然,OI 圈风气本就如此,我也不好过多评价。No comment.

T1 还算顺利,半小时左右搞定。T2 是大分类讨论,足够恶心人,但好在有相当可观的可以通过暴力与观察拿到的部分分。T3 猜测与线性基相关,但没有相应知识储备,暴力跑路。

T4 就……反正出题人开心就好。到现在都没人改出来。

一句话题解

A – 序列

依次往某个子序列中添加元素。则添加的元素必然成为新的最大值/最小值之一,否则违背题意。

于是枚举子序列首元素,将以其开头的严格上升子序列数与严格下降子序列数相乘即可。使用树状数组转移即可。复杂度 O(nlogn)\operatorname{O}(n \log n)(更多…)

More
  • 2022年10月19日