House_of_Fan

CF2157B Expansion Plan 2 题意 从原点 $(0,0)$ 这个正方形开始，有两种扩展，分为 $4,8$，分别代表向四个方向和八个方向扩展一个正方形。 求点 $(x,y)$ 是否被包含在扩展图形内部。 思路 观察样例发现，不论如何扩展，最后的区域均为一个大正方形的四角分别往内凹进一个等腰直角三角形。 又发现四个象限的本质相同，可通过旋转使它们重合。 简单推理可得等腰直角三角形的边长为字符串中 $4$ 的出现次数。 综上，我们可以对每个点的 $x$ 和 $y$ 取一次绝对值，使这个点变成第一象限点，再根据它的坐标模拟即可。 具体的： 若 $x>n$ 或 $y>n$，则单个坐标轴已经超出上限，显然不在扩展图形内部。 若 $x,y$ 之和比 $8$ 的出现次数加上总括展次数还大，则不在扩展图形内部。 其余情况均在扩展图形内部。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<...

P2651 添加括号III 思路 思路较为简单。因为要使得结果为整数，则最优方案是只将 $a_2$ 设为分母，其它均为分子。这里不做过多赘述，详见其他题解。 具体实现 $a_i$ 的范围非常大，显然不能直接累乘（除非你写高精度）。 注意到其它所有题解在约分时均使用了 $\gcd(a,b)$ 来约分，而它的最坏时间复杂度为 $O(\log \min(a,b))$。 这并不优秀，它使得整体的时间复杂度最坏为 $O(T\cdot n \cdot \log\min(a,b))$ 而我们有一种更优的做法，时间复杂度为 $O(T\cdot n)$。 原理很简单，在每一次累乘后直接将乘积对 $a_2$ 取模即可。 证明 这题的结果由 $(\prod_{i=3}^{n} a_i)\cdot a_1$ 能否整除 $a_2$ 决定。 若我们在每一步后对乘积取模： 设当前乘积为 $m$，要乘 $a_t$，则分配率易证 $m\cdot a_t\equiv m\cdot (a_t\bmod a_2) \pmod {a_2}$。 同理对 $m$ 取模同样不影响结果。 所以我们在过程中可以任意取模，比每次约分...

CSP-S 破鼎记 省流：100+48+35+8=191（细节回文暗广） 此文章由两个不同人格撰写，第二人格写的已被划掉 Day -42 初赛 在cw初中部进行 简如单，预估 $80.5$ upd: $77.5$ Day -1 看模板，背线段树 把所有学过的图论算法全打了一遍（伏笔） Day 0 我们伟大的母校也是成为考点了好吧 感谢欧欧镑大人让我们周五中午放学 直接回家玩一下午饥荒 但是两个大手子DimStar Gaochenxi103_QWQ还要留校，默哀 Day 1 正式考试 我不考J组，所以上午还是在家 先买巧克力再说复习一下线段树 这不玩暗区再背快读快输 好，现在可以5min打完缺省源，感觉全部都稳辣再开一把 中午小睡30min 起来才1:00，问题不大，这不玩饥荒和家里养的犭苗玩了20min（注意，这不是小犭苗女良） ok直接出发（一阵劲爆的音乐响起） 1:50到达cw初中部门口，神人保安不让进 并非偶遇了 IGpig pylktz Mary3327 Getaway_car等奆佬（此处按时间顺序排列） 发现街对面的 ztyroy Solil1019 WBJ0429 等...

P7056 Insider’s Information 题目大意 给定 $m$ 个三元组，你需要给出一个序列满足其中的任意至少 $\lceil \frac{m}{2} \rceil$ 个三元组。 思路 定义每个三元组为 $[a_i,b_i,c_i]$，则满足的条件是 $b_i$ 处于 $a_i$ 与 $c_i$ 之间。 不难发现若仅计算这一个三元组对答案产生的贡献，则 $a_i$ 与 $c_i$ 是等价的，交换它们的位置不会影响贡献。 不难想到对所有点进行拓扑排序，确定 $b_i$ 一定在 $a_i$ 与 $c_i$ 后被填入。 所以分别连 $a_i$ 到 $b_i$ 的边及 $c_i$ 到 $b_i$ 的边，每个三元组中的 $b_i$ 入度每次加二。 然后进行拓扑排序，但在减去删去点的关联点入度时判断是否已经被减过（先遍历到了另外一端的端点），若未被减过，则将其入度减二，否则不减。 在拓扑排序后考虑按拓扑序填入答案，记 $ord_i$ 为拓扑序的第 $i$ 个数，计算其放在前端和后端分别能产生多少贡献，从两边往中间填充。 Code 12345678910111213141516...

CF2159A MAD Interactive Problem 思路 注意到题目要求在 $3n$ 次查询内得到结果，考虑用 $2n-1$ 次得到 $n$ 个值，再用 $n$ 次得到另外 $n$ 个值，最后刚好 $3n-1$ 次。 具体实现 第一问 我们从第 $1$ 个值开始，到第 $i$ 个值结束，其中 $i$ 是从 $2$ 到 $2n$ 的值，每次将它们之间的所有还未确定的值进行询问得到 $res$ 值。 若 $res$ 等于 $0$ ，说明查询的所有值各不相同 在 $i$ 到了某个值时 $res$ 突然不为 $0$ ,说明新增的这个值等于 $res$ 第二问 在第一问中，我们确定了 $n$ 个互不相同的数，考虑将它们提取出来，组成一个序列，且此序列恰好包含了 $1$ 到 $n$ 间的所有值，考虑将剩下还未确定的值枚举，在此序列基础上每次加入一个，则枚举的这个值为 $res$。 证明 第一问 记 $1$ 到 $i$ 中还未确定的值组成的序列为 $D_{i}$。 若询问 $D_{i}$ 的 $res$ 不为 $0$,且询问 $D_{i-1}$ 的 $res$ 为 $0$， 则...

思路 因为从 $x$ 到 $y$ 的时间与从 $x$ 到 $z$ 再到 $y$ 的时间相同 $(x \le z \le y)$ ; 而如果直接从 $x$ 到 $y$ 的话，有一段时间还在比 $z$ 低的 $x$ ，显然劣于从 $x$ 到 $z$ 再到 $y$ ; 所以直接从当前塔一路向更高的塔走，直到某一刻水升上来所需时间小于传送所需时间，就会被水淹没。 实现 将塔的高度排序，把比初始点还低的塔排除掉，再遍历一遍即可。 代码 12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>#define int long long#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i>e;i--)#define rep(i,s,e) for(int i=s;i<=e;i++)#define per(i,s,e) for(int i=s;i&g...