Posts

需要更早的更新或需要修正请联系我。 一些无关紧要的更新不会写，部分更新会加上个人看法。 初来建议从下往上读，下面的一些专有名词在上面不做解释。 有时候会修改下面更新的某些内容，我会用加粗标出来。 【20250401】杂项更新 生物战利品调整： Beetle（沙漠甲虫）掉落物Ankh（安卡）改为Privet（硬币女贞子）。 Soldier Termite（白兵蚁）掉落物Privet（硬币女贞子）改为Triangle（三角形）。 花朵： 玩家全部名称形象改为M28（估摸着限时 【20250331】三角形更新 更新新花瓣Triangle（三角形）。 外观是一个略微倾斜的三角形，伤害为 $\dfrac{D}{3}$，耐久为 $H$。 可以由Soldier Termite掉落，掉率应该和之前Bone掉率一样，算正常。 特殊效果是每多装备一个三角形，每个三角形都可以加相当于其原本伤害 $0.8$ 倍的伤害，装备 $3$ 个每个都可以加 $2$ 倍，以此类推。 冷却是 $2s$，比大多数花瓣短。 经过我一通猛算，发现无论带多少个Triangle，单个伤害都无法达到高等级硬币伤害。 并且如果带 $9$ 个Triangle $+$ $1$ 个Faster，会比 $8+2$ 的DPS略大，如果你把转速天赋点满的话。反正全青Triangle抢不到Super就是真理。 【20250318】沙漠新区更新 从沙漠出生点附近的竖直道延伸出一个区域，外观为一个金字塔（据猜测是新地图的入口，暂时不能进去），其门口会低频刷低级（绝大多数为Common、Unusual）木乃伊甲虫。 据说如果门口有 $200$ 人新区域就会开放。 更多信息敬请期待。 现在已经开放，具体信息未知。 【20250316】绷带更新 更新新花瓣Bandage（绷带，忘了啥意思的建议重学八下英语）。 外观是一个被绷带缠绕着的球，没有伤害、耐久、冷却（有点像Antennae等显示在花朵表面的花瓣）。 可以由木乃伊甲虫掉落，掉率与火蚁掉落骨头一样，最低稀有度Mythic，其他掉落和同级甲虫完全一样，极其稀有（猜测和邪眼甲虫一样的生成概率）。 20250318更新：木乃伊甲虫掉落改变，bgg（Bettle Egg）掉率极低，Ankh掉率高。 其作用是在花朵濒死的时候触发，可以让花朵无敌一段时间，无敌时间结束后必死（暂不确定若此时有剩余血量是否仍然会被击杀），且在一段时间内无法被ygg。 因为维基还没更新，目前暂不知道其具体数据，这也是我咕这么久的原因之一。 【20250308】骨牌更新 更新新花瓣Domino（音译“多米诺”，即骨牌）。 我们统一把一个等级Coin的伤害、耐久为同等级的标准伤害、耐久，表示为 $D$、$H$。 外观类似两个Dice的结合，伤害为 $\dfrac{D}{15}$，耐久为 $H$。 可以由Centipede (Hel)掉落，掉率低的离谱，和原本它掉落Chip掉率是一样的。 每次Reload后随机上下两片的点数，其上下两片点数之积即为伤害倍率，最高可造成 $6 \times 6=36$ 倍伤害，冷却 $2s$（不是 $2.5s$）。 以下是数学方法计算该花瓣的强度以及和其他花瓣的对比： 下面统一忽略florr判定伤害的时长 $0.04s$，也就是实际上每 $0.04s$ 才会执行一次伤害判定，但有些时候（如计算Corn的时候）因为造成伤害次数过多会算上。 ...

前言 这部电影可以说是当之无愧的科幻电影中的第一名，没有之一。 如果有朋友喜欢看科幻电影，我一定会推荐这部片子。 下面我将为你解说这部电影，并分析它到底好在哪里。 话不多说，我们直接开始。 注：下面假设你已经至少看过一遍该电影，所以部分易懂的情节就不会说了。 角色&名字对照 男主角（宇航员&家长）：约瑟夫·库珀（简称“库珀”） 女主角（宇航员）：艾米莉亚·布兰德（简称“布兰德”） 男主角的女儿（幼年&成年&老年）：墨菲·库珀（简称“墨菲”） 女主角的父亲（教授）：约翰·布兰德（简称“布兰德教授”） 第一个星球上在巨浪中身亡（宇航员）：道尔 第二个星球上在爆炸中身亡（宇航员）：罗米利 男主角的儿子（幼年&成年）：汤姆·库珀（简称“汤姆”，跑龙套） 开头 电影一开头播放了一些口齿有些不清的老人的录音，根据内容可以推断出，在未来地球早已不宜居。 记住这些录音，在后面还会提到。 之后是主角的家里，可以发现当时几乎所有的作物都已经灭绝，注意是灭绝，包括小麦在内。 此时唯一幸存的就是玉米。 之后又放了一段校内让库珀去参加家长会的场景，有些人可能对此不管，但这里埋了几个伏笔： 墨菲在校内的成绩不太好。 墨菲在校内传一本关于阿波罗登月的书籍。 至于在之后哪里照应，我先卖个关子，我们继续。 发展 在看球赛的时候突然一场沙尘暴刮来，在回到墨菲房间的时候突然出现了一个非常奇幻的景象——沙子开始以反重力的形式下落。 墨菲称此为“幽灵”，随后在当晚去了汤姆的房间。 次日，库珀通过在地上沙子的厚薄用二进制（binary）的形式分析出了一个数字——$33$。 随后他便驾车顺着地图前往了那个位置，发车前女儿还混上车了。 到了位置之后，库珀尝试用老虎钳打开铁门，但是被抓了个现行。 随后画面一闪便到了他被一个机器人审问的场景。 机器人名叫TARS（塔斯），这个在后面会发挥大作用。 辗转之后有一个很小的场景，就是说玉米也被blight（枯萎病）所影响，不久也会灭绝，到时候地球将彻底不适合生命体生存。 显然执行所谓的A、B计划刻不容缓，所以库珀便到了家里对墨菲做了最后的告别。 在这段内，库珀给了墨菲一块手表，说“等到我（库珀）回来的时候，也许你（墨菲）会和我一样大”。 在此时，墨菲也说墙上的书经常倒下，根据这个破译出来的摩斯密码写着“STAY（留下）”。 但最终还是没能留住库珀。 航行 一段剪辑之后，库珀驾驶飞船升空。 虫洞 他们根据预定的路线来到了土星旁边的虫洞，根据前文，这是“they（他们）”放的，记住这个单词，之后会多次提到。 显然这个虫洞是有人在帮助当时的人类，以更快达到其他的星系。 这里的虫洞场景其实是根据现代的科学能够证实的，这也是剧组细心的一处。 在虫洞内有一个细节可能大家不会在意，就是此时女主把手伸到了窗户旁边，然后手扭曲了。 她称此为“handshake（握手）”。 在之后还会提到这次握手。 第一个星球 经过一段讨论后航行组去了第一个星球，在此提到了一个非常惊人的数据——“因为离黑洞太近了，所以在星球上的一个小时相当于地球上的七年”。 我大概算了一下，相当于时间变慢了六万倍，过一秒地球上就过去了十七个小时。 于是他们便派了男主、女主、道尔去上面。 到了星球发现全是水。 在这上面他们尝试找到发送的数据，但最后因为大浪袭来，道尔没来得及上飞船，在巨浪中身亡。 也因为这个大浪，最后过了一个小时才把引擎的水排完，最后安全回到母舰。 到了母舰上发现时间已经过去了几十年。 争论 但其实这些都是小事，最重要的是，此时他们燃料已经不足，剩下两个星球只能去一个。 而此时男主和罗米利都同意去一直在发送消息的星球A，女主要去已经杳无音讯的星球B。 最后少数服从多数，去了星球A。 第二个星球 到了这个星球后发现有冻云，顾名思义可以发现这里特别冷。 之后根据在这个星球上休眠的人（下称C）所说，这个星球的空气也不适合人类呼吸，但在下面存在氧气。 但辗转几番发现，其实C说的都是骗人的，他的实际目的是为了把库珀骗走杀了，然后在基地内引爆炸弹把剩下两人杀了，最后自己一个人乘飞船逃走。 正如他说的“但我知道，我只要按下那个按钮（应该指的是发送数据的按钮），就一定会有人来救我”。 最后库珀拿到了通信器，女主去救库珀躲过一劫，罗米利则不幸遇难。 此处可见人性的险恶，但显然TARS发现的比其他人早。 最后C没有和永恒号对接上而爆炸。 男主在经过一段时间相对静止的对接后成功让永恒号远离星球A的大气层。 真相大白 在这段时间内有个插曲，就是布兰德教授去世了。 在去世之前，他给墨菲说了事件的真相，其实A计划根本不存在，他们出去了大概就再也回不来了，实际上只有B计划。 他制造A计划是为了让那些人为了拯救自己的家人而行动，激发他们的行动力。 ...

普通莫队算法 概览 莫队其实是分块的变化版，没有完全分块。 但莫队的题目一般比分块的题目比较好看一些，其中的“好看”指的是很好看出这是个莫队/分块的题。 接下来说一下莫队能解决的题型。 解决题型 莫队一般解决以下问题： 给你一些信息，和 $q$ 次询问，每次询问可以抽象为一个区间。 而且这个问题还要满足一些条件： 可以离线 不能有修改（当然带修莫队支持修改，不过普通莫队就不行了） 从 $[l,r]$ 的答案可以很快转移到 $[l-1,r]$、$[l+1,r]$、$[l,r-1]$、$[l,r+1]$ 的答案 解决方法 这种题型有个解决方法。 还是先从暴力说起。 暴力做法 看见这个问题的最后一个条件没？这个条件就启发我们从第一个问题的答案，暴力调整左、右端点，去得到第二个问题的答案，以此类推。 这种暴力做法的复杂度一般为 $O($ 任意相邻两个问题的左、右端点差之和 $)$。 而这个算法可以用一种数据卡掉： 左、右端点的值的最大值 $n$ 调到最大，把询问次数 $q$ 也调到最大。 然后的 $q$ 次询问里，交替询问 $1 \sim n$ 和 $n \sim n$。 于是，复杂度被卡到 $O(qn)$。 一次优化 这个做法的复杂度是无法接受的，所以我们考虑优化。 我们不如把所有询问离线，然后考虑交换询问处理的顺序以减少复杂度。 一种方式就是把左、右端点分别作为第一、二关键字，然后做排序。 但这样就会被排序后所有询问的右端点一大一小的数据卡到 $O(qn)$ 的复杂度。 二次优化 这样排序还是不好，还是会被卡掉，于是我们考虑变换比较函数。 直接双关键字比较不好，那我们就分块后进行双关键字比较。 具体地，遇到两个询问，先按左端点所属块编号从小到大排序，如果相同，则按右端点（不是所属块编号，是原本的下标）从小到大排序。 这样的话，复杂度就是 $O(n \sqrt n+q \sqrt n)$ 的复杂度了。 ...

赛时记录 比赛一开始（$11$ 分钟）就过了A。 后来一直在B题思考正解。 在比赛达到 $2h$ 之后，我发现正解已经没希望了，结论假了。 所以改成了暴力。 事实上我先写的C，因为感觉B不太有希望，C一眼 $20$ 分。 之后回头看B，干了最低档。 最后是D，思考了一下可以做 $45$ 分，搞了。 此时里比赛结束还有 $27$ 分钟，所以回头看了一下，发现C题的暴力很多。 先后搞了子任务 $1 \sim 3$，总共 $70$ 分。 然后比赛就结束了。 估分 VS 结果 估分：$100+10+70+45=225$ 结果：$100+25+0+30=155$ 挂分原因 关于B为啥多了 $15$ 分，我也不知道。 C很复杂： 子任务1 $T \leq 100,n \leq 10$ 挂了：赋值消耗时间复杂度太多，在swap的时候回溯写挂了。 子任务2 $k=0$ 挂了：赋值消耗时间复杂度太多。 子任务3 $k=1$ 挂了：做法假了 D： 子任务3 $T=1,k \leq 15$ 挂了：实现的时候没有预处理 $s$、$e$ 的答案，导致询问次数太多TLE。 策略 感觉还是卡B太久。 事实上这次A非常确信做法正确，事实就是正确的，但后面的题没有对拍，导致总共挂了 $85$ 分。 之后无论对于正解还是暴力都得对拍，如果认为有挂的概率的那种。

跳题 如果一道题认为难写，先看后面的题，也许有好写的部分分甚至是正解 如果一道题写完了挂了，认为很对： 找不到错误数据，就规定一段时间（一般为5~10分钟，或者直接执行），然后立刻跳题 找到了错误数据，就可以调时间长一些 如果要在开场把所有题读完（OI赛制专用），遇到难读的题目可以先不读 如果要把剩下的时间全部用在一道题上，先去吃其他题的保底，再开始写这道题 对拍（OI赛制专用） 如果说一道题强数据好造、暴力好写，那么一定要对拍 即使是模拟赛也要对拍，不止是正式比赛，把模拟赛当做正式比赛认真对待 总结 比赛后写一下总结，包括以下内容： 赛时记录，什么时候在干什么 估分 VS 得分 挂分原因（BBE） 赛后想一下赛时没有想到的部分分/满分/更优做法 策略总结+调整

网址 每天北京时间0点整会更新所有测验。 这里只说部分，其他的自行摸索。 猜城/猜城3D/猜国/猜旗/天眼/乡音/城景 线索 会给你关于这个行政区/国家的信息（如果是猜旗则随着你的猜测会逐步揭开）。 你有 $6$ 次机会去猜，输入方式是类似于查找然后点击的方式（可以自己试试就知道是啥意思了）。 判题 每次猜完后会告诉你答案在你猜的答案的（大致）哪个方位（八方向），以及距离是多少。 天眼不会告诉你方位，只会告诉你距离，所以非常难猜，没有足够实力不要去挑战。 不用管后面的百分比，这个是接近程度，按照距离除以一个很大的数去计算。 一旦猜对则游戏结束。 填省/填国/填歌 线索 给你一个表格，表头有限制条件。 判题 需要在表格内每一个方格填入数据库内同时满足行、列表头上的条件的元素。 尝试机会有限，看最上面的生命值。 填完则游戏结束。 猜Word 线索 跟Wordle一模一样。 判题 跟阴阳小游戏很像，但不同的是可以告诉你每个位置是匹配还是错位。 匹配显示为绿色，错位则是黄色，没有则是灰色。 歌词/诗文 线索 一开始所有格子都是黑色的状态。 你有无限次机会，每次可以输入一个字，然后这个字在这首歌（包括歌名、歌手、歌词）或诗（包括诗名、作者、内容）内出现的所有位置都会揭开。 判题 如果猜的字没有出现，则会提示“未出现”并将该字以红色背景显示在最底下。 如果猜过，则会提示“猜过”并不执行任何操作。 将歌名或诗名完全揭开即可。 连句 规则 给你一个表格，你要在里面找到固定数量（可以看最底下）的诗句或者歌词。 可以通过八方向的一条链表示该诗句，连接的时候可以交叉，可以自己玩一下。 每个字只能使用一次。 判题 尝试机会有限，看最上面的生命值。 如果连句成功则会标记为绿色，并不能再选。 全部为绿色则游戏结束。

更新中…… 稀有度 Common：绿 Unusual：un/黄 Rare：蓝 Epic：紫 Legendary：l/红 Mythic：m/青 Ultra：u/ul/粉 Super：s/书青 合成 合成Mythic：合青 合成Ultra：合粉/河粉 合成Super：合苏（su） 合成Ultra并失败：冒青烟 合成Super并失败：冒粉烟 用x个花瓣合成并成功：x=1（如5=1） 用x个花瓣合成并失败：-数字（如-2，但通常此处x=5） 花瓣 默认可以叫花瓣的英文名和大家普遍公认的中文名。 Ant Egg：agg/egg Antennae：ante/触 Basil：比勒（一般不叫它罗勒） Beetle Egg：bgg Bone：骨/装 Bubble：泡 Claw：头发（一般不叫他爪子/蟹爪） Dandelion：dande Dice：色（shǎi） Faster：罚 Iris：毒药 Lightning：lāi Magic Eye：me/魔眼 Magnet：mag Mana Orb：orb（拼写式读法） Pincer：品色/拼刺儿 Powder：pow Rice：米 Shovel：铲 Sponge：海 Third Eye：te/三眼 Uranium：uran Wing：羽毛 Yggdrasil：ygg（一般不叫它世界树） Yucca：于夹（一般不叫它丝兰） 生物 Queen Ant：queen Starfish：兴（xìng）禹（yú） 黄色瓢虫：shiny

前言 2-SAT中的SAT是适定性（Satisfiability）问题的简称，一般形式为 $k$ - 适定性问题，简称 $k$ - SAT，但由于 $k>2$ 时问题为NP完全问题（只有指数级别复杂度的解法，或者多项式级别复杂度的相似解法），而 $k=1$ 时都不用解了 （废话） ，所以下面全部考虑 $k=2$ 的情况。 定义 2-SAT问题简单来说就是，有 $n$ 个集合，每个集合包含两个元素（集合 $i$ 包含元素 $2i-1$ 和 $2i$，但其实编号是无关紧要的，任意都行），你必须要在每个集合里分别选择刚好一个元素，但某些元素之间可能有矛盾，即这两个元素不能在一种方案里被同时选择，问你是否有解，报告出来，如果有解，输出一种方案（可能不用输出）。 题目 看上面的定义可能有点难懂，这里举个题目。 有一场宴会，这场宴会只有 $n$ 对幸运夫妻可以参加，每对夫妻里只能选择刚好一个人去参加这场宴会。 但部分人之间可能有矛盾，会给出所有有矛盾的两人编号。 问你，是否可以构造一种合法方案，如果不行，报告无解，否则输出一种方案。 解法 （下面统一默认要解决的是实际问题，不是定义里的问题） 定义点、边 我们考虑把夫妻编个名字： 第一对夫妻：A男、A女 第二对夫妻：B男、B女 第三对夫妻：C男、C女 以此类推 然后，我们考虑建图。 但这个建图就要用到一点思维了。 我们不以其他的定义定义点，我们就把一个点当做一个现实。 比如： $1$ 号点代表第一对夫妻是A男参与宴会，$2$ 号点代表A女参与宴会 $3$ 号点代表第二对夫妻是B男参与宴会，$4$ 号点代表B女参与宴会 $5$ 号点代表第三对夫妻是C男参与宴会，$6$ 号点代表C女参与宴会 以此类推 边的定义也很难思考出： 一条有向边 $u \to v$，代表现实 $u$ 满足了，现实 $v$ 也要满足。 举个例子 所以，如果说A男和B女、C男和A女之间都有矛盾，那么就需要在： ...

basic BSGS算法英文名叫“baby-step giant-step”，又称“大步小步算法”。 这个算法听名字似乎是个随机化算法，但实际上是数论算法。 具体地，这个算法解决的是 $a^x \equiv b \pmod{p}$ 的解，其中 $a$、$b$、$p$ 是已知的（$0 \leq a,b<p$，保证 $\gcd(a,p)=1$），$x$ 是要求的。 这个算法甚至可以求出所有的 $x$，但为了好讲，我们先考虑如何求出是否有解，以下代码中YES就代表确定有解了。 force algorithm 首先，有一个暴力算法： rep(x, 0, INF) if(ksm(a, x, p) == b) YES 但这个算法是 $O(\infty)$ 的，我们考虑优化。 optimization algorithm 1 我们考虑 $x$ 的上界，根据欧拉定理，$a^{\varphi(p)} \equiv 1 \pmod{p}$，我们就可以确定，$x$ 的上界就是 $\varphi(p)$（准确来说减 $1$ 也彳亍），因为如果 $x>\varphi(p)$，那么 $a^x$ 就等于 $a^{x-\varphi(p)}$，也就成为了一个循环，所以上界就是 $\varphi(p)$。 由于 $\varphi(p)<p$，所以可以把 $p$ 当做是质数，$x$ 的上界也就是 $p-1$ 了。 所以： rep(x, 0, p - 1) if(ksm(a, x, p) == b) YES optimization algorithm 2 (BSGS) 但这个算法还是可能会TLE，我们继续考虑优化 我们定义 $q=\left\lceil \sqrt{p} \right\rceil$，那么我们其实就可以把 $x$ 表示为 $q$ 进制下的两位数，具体地，我们把 $x$ 表示为了 $Aq+B$（$0 \leq A,B<q$），然后上述公式就可以化成 $a^{Aq+B} \equiv b \pmod{p}$，即 $a^{Aq} \times a^B \equiv b \pmod{p}$。 ...

CDQ分治是一种解决三维、四维偏序的算法。 三维偏序 三维偏序问题形如： 有 $q$ 次询问，每次询问有两种： 修改：会给定 $t$、$x$、$y$、$v$，表示在时刻 $t$，在二维坐标 $(x,y)$ 上加上权值 $v$，修改会永久改变权值 （废话）。 查询：会给定 $t$、$x$、$y$，表示求在时刻 $t$ 时，所有满足 $x’ \leq x$，$y’ \leq y$ 的二维坐标 $(x’,y’)$ 上的权值和。 $q \leq 2 \times 10^5$ $t,x,y \leq 2 \times 10^5$ $v \leq 10^9$ 这种问题都有一个通用的解决方法，就是CDQ分治，接下来我们讲一下算法的原理。 我们先把所有的询问离线下来，然后按时刻（第一维）升序排序，显然排序前和排序后，相同询问答案不变。 接下来我们定义函数 $\text{solve}(l,r)$，代表只考虑 $l \sim r$ 内的修改，然后准确回答 $l \sim r$ 内的询问。 既然是分治，我们就要构建好整个分治思路，像这道题，就这样做： 找到 $mid$ 为区间 $[l,r]$ 的中点 $\left\lfloor \dfrac{l+r}{2} \right\rfloor$。 考虑 $l \sim mid$ 内的修改对 $l \sim mid$ 内的询问的影响：递归调用 $\text{solve}(l,mid)$。 考虑 $mid+1 \sim r$ 内的修改对 $mid+1 \sim r$ 内的询问的影响：递归调用 $\text{solve}(mid+1,r)$。 考虑 $l \sim mid$ 内的修改对 $mid+1 \sim r$ 内的询问的影响： 把 $l \sim mid$ 内的修改，和 $mid+1 \sim r$ 内的询问，统统存入一个数组 $b$。 把 $b$ 中所有元素按 $x$ 坐标（第二维）升序排序。 有人对这一步的正确性有疑问，此处解释一下。 ...