【UOJ Round #6】懒癌 / 题解

Posted on

Hat puzzles are logic problems that date back to as early as 1961.[1] Such hat puzzles, frequently contextualized as prisoners and hats puzzles, are induction puzzles (a kind of logic puzzle) that involve reasoning about the actions of other people, drawing in aspects of Game theory sometimes called the hierarchy of beliefs. There are many variations, but the central theme remains the same.

Featured

【杂谈】Boy Erased: Some Thoughts

Posted on

在电影的这个故事里,Jared 经历了自我接受,完成了矛盾化解,但帮助过 Jared 的 Cameron 在最终结束了自己的生命。而电影之外,世界更多社会里,LGBTQ 社群的成员们则在更阴暗的角落里饱受折磨,他们离 Love, Simon 很远,离 Brokeback Mountain 更近,他们的生活是黑暗一片。

【笔记】映射方法在几何计数中的应用

Posted on

作者:余不悔,高二,2018 年 CMO 铜牌获得者。 对于两个有限集合 $A$ 和 $B$,如果存在一个一一映射:$f:A \rightarrow B $,那么就有 $|A|=|B|$。 在某些情况下,如果 $A$ 的元素个数不好求,那么我们可以寻找一个集合 $B$,并建立起 $A$ 到 $B$ 的一个一一映射,然后去计算集合 $B$ 的元素个数,从而将问题解决。在这个过程中,寻找到容易计算元素个数的集合 $B$ 是至关重要的一步。 譬如下面这个大家都很熟悉的例子: 在 $6 \times 6$ 的方格表中,从左下角的 $A$ 点到右上角的 $B$ 点沿方格表的最短路径有多少条? 容易发现,从 $A$ 点到 $B$ 点的最短路径中,全部由 “向上” 和 “向右” 的线段组成,且各有六条。因此,我们建立起集合 $B$,定义它包含 “在 12 条线段中,选择 6 条作为向上线段的方法”。这样,对每一个确定的 $B$ 的元素,都可以唯一对应一种 $A$ 的方法,而对于 $A$ 的每一种方法都可以唯一的生成一个 […]

【Tips】NOIp 防翻车指北

Posted on

写代码时请注意: 是否要开 long long?数组边界处理好了么? 实数精度有没有处理? 特殊情况处理好了么? 数组是否足够或者过大? 做一些总比不做好。 当你把你的暴力程序改成正解时,记得扩大数组。 思考提醒: 最大值和最小值问题可不可以用二分答案? 有没有贪心策略?否则能不能 dp? 考场调整: 写下代码前,必须保证有充足的思考时间,有成熟的想法后再动手; 写代码前,尽量用多而强的数据去测试想到的算法,毕竟代码写完后再测试就浪费很多时间了; 不能想一点写一点,就算是输入部分也要在整体思路理清后再写; 永远别去写从未接触过的算法/数据结构; 有多余时间可以尝试进行对拍,即 3 个程序:生成数据、朴素算法(暴力算法)、准备交的算法; 如果你发现你旁边的人写得很快,请你放心,他的算法十有八九是错的,神仙没有你想象中那么多; 交之前 5 分钟千万不要再改动代码,主要留意代码中是否还有测试程序时留下的痕迹; 走出考场后,除非已经是 Day 2,永远别对答案。 其他注意事项 作者:lornd

【JOI 2011/2012 春季トレーニング合宿】Fish / 解法

Posted on

問題文 日本の解説のための Algoogle に感謝します。 問題概要 N匹の魚がいる. これらは赤, 青, 緑のいずれかの色になっている. 魚は体長が自分の2倍以上ある魚に食べられてしまうので一緒にできない. 一緒にできる魚の色の組合せを求めよ (中文概述) N条鱼,鱼有身长和三种不同的颜色, 给定身长和颜色,挑一些鱼,三种颜色的鱼的数量构成三元组, 身长差距超过两倍的鱼不能在一个组内, 求可能的三元组个数。 解法 etにalgorithmのlower_boundを使っていてTLE死した. ある魚に対してそれより小さい魚のうち一緒にいられる魚を考える. この時赤がr匹, 青がb匹, 緑がg匹いるとするとその選び方は3辺の長さがr, b, gの直方体の内部の格子点の数に一致する(=3辺がr+1,b+1,g+1の直方体の体積). これは赤, 青, 緑の選ぶ数に対して頂点が選べることからわかる. この組は魚の体長をソートしておけばしゃくとり法する感じで求められる. よってそのようなものを全て列挙して, 直方体を重ねあわせた体積を求める問題になる. 上から下に積分していけば, 各イベント点(各直方体のてっぺん)で長方形の和をとっていくことで断面が求められる. 各直方体は軸に接するように置いていると考えれば, 断面の長方形の和は各長方形の右上を保存しておけばよい. この点列は内部に含まれるものを除けば階段状になっているので, 長方形を追加するときにすぐ下の段(右の段)にくる長方形は2分探索で求められる. そこから1つずつ左に見ていき, 高さを積分していくことで増加分の面積を求める. すぐ上の段を見つけたら間に今作った新しい段に完全に含まれる段を取り除く. (中文概述) 首先我们现将鱼的身长 $p$ 从大到小排一下序,此时我们可以求出对于每一个 $i$ 它的极大三元组,就是对于每一个 $i$,求一个最大的 $j$,使得 $p_j<p_i*2$。那么统计 $i$ 到 $j$ 中的 $r, b, g$ […]

【正睿 OI】2018 提高组十连测 Day 6 / 题解

Posted on

Tiny Counting 题目描述 给定长度为 $n$ 的数组 $S$,下标为 $1∼n$,你需要统计有多少个四元组 $(a,b,c,d)$ 满足:$1 \leq a < b \leq n; 1 \leq c < d \leq n; S_a < S_b; S_c > S_d$,且 $a,b,c,d$ 互不相等。 思路 首先我们预处理每个点前后比它大 / 小的数字数量,同时计算所有的顺序对和逆序对个数,令答案为两者之积,然后把出现重复数字的四元组从答案里删去。 代码

Medium Counting 题目描述 这里你需要解决一道中型计数题——关于捉摸不定的字典序。 有 $n$ 个字符串,分别记为 $S_1,S_2,⋯,S_n$,它们由小写字母和 $?$ 组成,你需要给每个 $?$ 都填上一个小写字母。 你需要统计,有多少种不同的给 $?$ 填上字母的方法,使得对于每个 $i \in [1, […]