Blog E

路漫漫其修远兮,吾将上下而求索。

关于联名抗议 CCPC 全校禁赛的提议

联名呼吁已经在 2022 年 9 月 18 日通过反馈平台提交。 今天收到了 CCPC 组委会发布的以下通知: 我们理解并支持诚信参赛,公平竞争。对作弊行为必须零容忍,必须严格处理。对于作弊者,作弊队伍来说,一切后果都是咎由自取。但是,对于其他诚信参赛的队伍来说,这样“一人犯法,株连九族”的连坐,则极为不公平。 这样的连坐制,既不公平,也起不到相应作用,而且会起到反作用。 其一,对于没有违规的队伍是极度不公平,且没有意义的——本无过错却要接受严厉的惩罚。这样的处罚起不到杀鸡儆猴的作用——因为在赛前,学校老师学长等等都已经多次强调过参赛规则,然而还是有队伍明知故犯,以身犯险...

更换域名通知

重金购入 www.blog-e.top 域名!

freenom 的免费域名 www.blog-e.tk 用了一年,又过期了,而且无法免费续约。而且我也受够了一年换一次域名。终于咬咬牙,花了二十块巨款在腾讯云上面买了个 www.blog-e.top,最近还在配 DNS 解析什么的,访问和评论功能可能会有一些问题。

【题解】CF1710B Rain

抽象

说一个代码简单的做法。本题解数形结合,容易理解。 题解 首先,题目所求就是上述不等式对哪个 $i$ 成立。 发现式中只有第 $2$ 项是随着 $i$ 而变化的。而第 $1$ 项虽然不变,但是较为复杂,与第 $2$ 项相减的结果不好快速计算,因此不妨将第 $2$ 项移项到右边。 是不是突然发现这下不等式两边都比较简单了?如果看不出来,我们不妨把式子左右的图叠在一起看: 下文中称 $(x_i,p_i+m)$ 点为蓝色山顶(图中标出) 我们考虑右边能把左边盖住的条件: 对于左边高度小于等于 $m$ 的点,显然不用考虑 对于左边高度大于 $m$ 的某一点,蓝色...

NOI2016题解

题型新颖

T1 线段 题意 $n$ 个区间,从其中选出 $m$ 个,使得全部 $m$ 个线段交非空。求这 m 个线段长度极差的最小值。 \[m\le n \le 5\times 10^5\] 思路 线段按长度排序,随后双指针。开线段树表示每个位置被覆盖次数,最大值大于 $m$ 时合法。 T2 国王饮水记 (见之前题解) T3 旷野大计算 题意:略 一些关于 $S(x)$ 的性质(注意 S 函数非常有用): $S^\prime(x)=\frac{e^{-x}}{(1+e^{-x})^2}$ $\lim_{x\to 0}S(x)=\frac 12$ $\lim_...

PKUSC2021题解

T1T2

一棵树 题意 题解 $k=0$ 不难,略。 一个显然的想法是枚举断掉的边,然后看每条边的贡献。 贡献分为两类,一类是新加的边的块间贡献: 这个不难算,另外一类是原先的边的块内贡献。 不妨设虚线边断开,实线边把一个连通块分为大小为 $a,b$ 的两块,则这条实线边的贡献是上面的式子。 于是在枚举了虚线边之后,分子树内,祖先,既非子树也非祖先三种情况讨论,不妨设 a 是虚线边较深的端点,b 是实线边较深的端点: 可以发现,三个贡献的式子后两项都只和 a 有关,前两项都可以展开成和 b 有关的二次多项式,因此只需要维护下子树内,祖先上的 sz 的和,sz 的平...

【题解】P5979 [PA2014]Druzyny

考场上想出,挺有成就感

说一个 $O(n\log^2 n)$ 的 cdq 分治做法,常数不大,不用分类讨论,较为好写。 一些符号 记 $\operatorname{mxl}(l,r)$ 表示下标在 $l$ 到 $r$ 之间的所有区间的左端点最大值,$\operatorname{mnr}(l,r)$ 意义类似。 记 $\operatorname{rng}(l,r)=[\operatorname{mxl}(l,r),\operatorname{mnr}(l,r)]$。 暴戾 首先是一个简单的 $O(n^2)$ dp: \[dp_i=1+\max_{[j<i]\land [(i-j)\in...

【题解】丁香之路

奇妙

感觉这题的思路非常奇妙,就算会做了也完全不知道为啥要这么想。。。 题意 有一个 $n$ 个点的无向完全图,边 $i\leftrightarrow j$ 的边权为 $|i-j|$,强制经过指定的 $m$ 条边,求起点为 $s$,终点为 $i\in[1,n]$ 的最短路径。$n\le 2500,m\le \frac{n(n-1)}2$。 思路 考虑在一个可重无向边集 $E$,如果: $\text{必须经过的}\ m\ \text{条边}\subseteq E$ 存在一条 $s\leftrightsquigarrow i$ 的欧拉路径 那么就有符合题目要求的一条路径存在...

博科摆

物理作业

(所有插图系作者手绘,文字由作者原创) 假象一个小人站在一个逆时针转动的旋转木马上,小人会感受到一个远离旋转木马的中心的力。这就是离心力,并不存在一个实在的东西对小人施加这个力,但是由于小人站在旋转木马这个旋转参考系下,惯性会使小人感受到这种力,这种力就叫惯性力。 然而,如果小人还在旋转木马上走动,除了刚才的离心力小人还会受到另外一个力:它指向小人运动方向的的右侧,并与小人的运动方向垂直。这就是科氏力,另外一种惯性力。 万一旋转木马是顺时针转的呢?假如人在竖直方向也有运动呢(比如在旋转木马上跳来跳去)?科氏力的方向又会怎样变化呢?事实上,我们有一个通用的方法来判断。 首先...

讲题

P5323 光线 两个玻璃的透光率和反光率可以合并,如下列式解方程即可: \[\left\{ \begin{aligned} B&=Ap_1+Dq_1\cr D&=Bq_2\cr C&=Bp_2\cr E&=Dp_1+aq_1 \end{aligned} \right.\] 解得: \[\left\{ \begin{aligned} p_{12}&=\frac CA=\frac{p_1p_2}{1-q_1q_2}\cr q_{12}&=\frac EA=...

国王饮水记

一道 nb 题

题意 有一个长度为 n 的数组 H(元素互不相同),你可以进行 m 次操作,每次取若干元素,把他们都赋值为他们的平均值。求 $H_1$ 最终最大能达到多少,要求计算过程中保留到小数点后 p 位。 简单观察 贪心一下,大概就能感受出来最优解的搞法: 将 $H_{[2,n]}$ 排序,选一个后缀,并划分为 m 个区间。 把 $H_1$ 从小到大依次和这些区间内的数联通。 这个感觉是对的,但是严格证明需要以下结论: 小于等于 $H_1$ 的数没用(显然) 假如每次操作都包含 $H_1$,每个数不会选两次(操作过之后就小于等于 $H_1$ 了) 存在一个最优...

icon