int 模块规则： 类型只能用 int ； 出现的常数 \(C\in [0,255]\) ； 运算符只能出现 ! | & ~ ^ + << >> =，除了 = 以外都算一步。 1. bitOr 只能用 ~ & 实现 Or 典中典。 123456int bitOr(int x, int y) { int notX = ~x; int notY = ~y; int nandn = notX & notY; return ~nandn;} 2. anyEvenBit 判断是否有任意一个偶数位是 1 由于只能用 \(8\) 位的常数，我们考虑把所有位缩到后面八位上，再 and 一个 0x55 ，然后用两次 ! 转 bool 即可。 12345int anyEvenBit(int x) { int hb = (x >> 16) | x; int ans = ((hb >> 8) | hb) & 0x55; return !(!ans) ...

一个诡异的完全不知道询问次数的做法。 考虑一条链，我们显然二分。 然后考虑一棵树，显然树深度越小越好做，发现和深度有关，我们长剖！ 二分加上长剖，我们每次询问最长链中点，然后根据结果暴力维护就好了。 （维护方法：成功了就只留下询问节点的子树，失败了删掉所有叶子和询问节点子树，加入当前根的父亲。） （注意：失败的时候如果询问节点父亲只剩一个子树，需要删掉父亲） 虽然诡异但是还是有些道理的，这种做法可以在深度很大的时候一次保证删掉大量节点，在深度很小的时候随便找个地方问也比在叶子上浪费次数强。 实测能 \(80\) 次以内出解。 代码

whk 好无聊啊，根本不想写作业，遂写游记。 Day-2 的时候去到某酒店隔离，随便做了点题，大部分时间都在摆，最后一段 OI 日子还是摆得挺开心的 (?) Day0 的晚上吃了 cp 的自热火锅，然后调整了一下心态，因为第二天要早起所以十一点半就睡了，睡得也挺快的，然后半夜被冷醒了，因为某些原因不想盖酒店被子，被迫找了条冬装裤子穿了睡觉。 Day1 的 5:40 就被 cmb 使用酒店电话轰炸而醒，说要收拾东西跑路，非常火大，但是没有办法，领了早餐什么的上大巴，但是放好行李之后发现满了，被迫搬去另一个大巴。大巴湿的一批，跟贩卖人口似的。 到了考场外面，开始吃早餐，听了两首歌，看了会 oi-wiki ，然后就进考场了。 最后的时候 qifan 突然说要看重连通分量，我心想这有什么好看的不就tarjan吗。 开题，两层密码有点反常，但是密码挺有意思的。 看了 T1 ，发现十分傻逼，同时整个考场响起键盘敲击声。然后看 T2 ，发现是最讨厌的构造，直接跳掉，然后 T3 一眼秒了， T4 发现如果两边的 \(l,r\) 独立选的话就是纯傻逼题，然后认为原题也不难做 ...

直接快进到开题。 我直接开 E ,发现有点性质，可以搞，然后开 F ，一度以为傻逼，然后发现不会，发现旁边鸡空闲了，叫他来胡 E ，他推荐我去看 B 。 我们决定先看 E ，然后旁边 cp 转化完 J 扔给我们，感觉似曾相识但是很 hard ，继续搞 E ，两个人瞎几把贪心了一下，发现能过样例，简单组织一下，我直接上机写，写了个树状数组但是发现值域巨大，改成线段树，中途发现一车人过 L，让 cp 去想，+40min 左右交 E ，wa 掉，发现 - 打成 + ，然后过了。 cp 写 HL 的时候我会了 B ，但是巨臭，不敢写，看了 C 认为可做，然后上机写 B ，中途讨论 C 发现会了，开始写 C ，中途被 sb 监考搞了 30 min，精神状态不佳，写了 5 个拓扑的大臭代码，但是过掉了。 然后 cp 上机写他的 I ，我和鸡看 M ，发现 M 巨板，稍微搞了一下之后 cp 说他假掉了，让鸡上机写 M ，但是发现他不会写，我被迫上机写，过了一会 wa 掉了，发现取模少了，罚时++。 然后全队开始搞 I ，各种卷积和换根都不行，人傻掉了，然后 cp 和鸡 ...

给你一张正边权有向图，Alice 先手，从节点 v 开始，两个人每次沿一条边移动一步，没路走了就游戏结束。 Alice 想最小化经过边的权值和，Bob 想最大化，求最后经过的边的权值和。 \(n\leq 10^5\) 考虑设 \(f_i,g_i\) 分别表示两人先手，从这个节点出发所得到的分数。方程显然。 如果这是个 DAG 的话就做完了。 考虑使用 dij 进行转移 dij 的正确性来自于它每一次取出节点时确保了这个节点已经被完全更新，即权值已经确定。 另一方面，所有满足条件的节点都能够第一时间去更新其他节点。 于是我们每次取出最小的权值进行更新，如果更新的是 \(f_i\) 就直接入队，如果更新的是 \(g_i\) 的话就在它被所有能更新它的节点更新之后入队。 搬运自 Luogu Blog

远古 vp ZJCPC 的时候的一个题。 定义一个正整数的比较方式： 设两个整数为 \(x,y\) ，把所有质数在 \(x,y\) 质因数分解里的指数分别写出来，按质数升序分别排成两个数组，然后比较这两个数组的字典序。 现给你两个长度 \(10^5\) 的数组 \(A,B\) ，求第 \(k\) 大的 \(A_i*B_j\) ，值域 \(10^6\) 。 显然得筛出来每个数的质因数，然后两个数的积可以直接归并出来。 然后 \(k\) 没限制，一眼二分。 假设二分出了一个值，显然可以 two-pointers 搞出有多少个数比它小。 但是找不到第 \(mid\) 大的值。 于是考虑找出落在 \([l,r]\) 区间的有多少个，然后随机选一个。 这样子复杂度显然有保证，最后二分了一定次数后时最多剩下两个本质不同的值，两个都验一遍即可。 复杂度 \(O(n\times \log n\times \log v)\) 。 使用巨量 stl 的代码被卡爆了。 搬运自 Luogu Blog

题目链接 给你一个排好序的长度为 \(n\) 的自然数数组 \(A\)，保证 \(A_i\) 互不相同，Alice 和 Bob 轮流操作，每次把 \(A_{max}\) 变成一个更小的自然数，需要保证 \(A\) 中仍然没有相同的数，不能操作则输，问谁赢。 \(2 \leq n \leq 3 \times 10^5,\ 0\leq A_i \leq 10^9\) 考虑第一步每个状态之间的转移关系： 如果左边那一大坨有必败状态的话，我们显然可以直接转移过去。 否则由于 \(A_n=A_{n-1}+1\) 这个状态能转移到的全都是必胜状态，所以它自己就是必败状态。 于是我们发现先手必胜，但是要求 \(A_n > A_{n-1} + 1\)。 假如 \(A_n=A_{n-1}+1\)，那两个人永远都不会让 \(A\) 中最大的两个值相差大于等于二，进一步地，我们发现 \(A_{max}\) 每次操作之后都会且仅会减少 \(1\) ，于是我们判断一下 \(A_n-(n-1)\) 的奇偶性即可。 属于是一道加深对 SG 理解的好题。 搬运自 Luo ...

给你 \(n\) 个字符串，要求你选择 \(k\) 个字符串以任意顺序拼在一起，使最终的字符串字典序最小，输出最终字符串。 \(n,k,|s|\leq50\) 一个非常显然的 DP ：\(dp[i][j]\) 表示前 \(i\) 个串选了 \(j\) 个的最小字典序串，用上字典序的经典 trick ，每次转移把新串拼在前面。 但问题就在于可以任意顺序插入，必须给 \(n\) 个串先定个顺序。 字典序从大到小？ FAKE 。反例： \(ca,c\) 。 考虑排序是干嘛，其实就是为了任意两段交换不会更优，所以我们定义字符串 \(s < t\) ：字典序下 \(st < ts\) 。 为什么这样可以排序？ 把字符串换成 \(26\) 进制数。由于 \(|st|=|ts|\)，所以字典序下 $ st<ts$ 等价于 \(26\) 进制下的 $ st<ts$ 。所以有以下式子： $st<ts $ \(\Leftrightarrow s \times 26^{|t|} +t< t\times 26^{|s|}+s\) \ ...

一个方程： \[f_i = \min_{j=1}^{i-1}{\{f_j+w_j*l_i\}}\] 附加条件：\(w_j\) 单调递减，\(l_i\) 单调递增。 考虑固定 \(j\)，写出 \(f_i\) 随 \(i\) 的关系，观察到如果令 \(k=w_j,b=f_j\) ，则 \(f_i\) 与 \(l_i\) 成一次函数关系，并且随 \(j\) 的增加，这些直线的斜率单调递减。在同一直角坐标系中作出它们的图线，大概是这样的： 而我们最后会对所有 \(j\) 的答案进行一个 \(\min\) 的取，所以真正有用的是上图中的红色部分。 众所周知，斜率优化会用到单调队列，所以对出队和入队进行分析。 出队： 现在假设我们队列里有如图三条斜着的直线，而绿色的那条直线是当前的 \(l_i\) 。 对于队首的第一条直线，它和第二条直线的交点小于当前的 \(l_i\) ，第二条直线斜率又比它大，于是它成为了时代的眼泪，于是我们把它 pop 掉。 入队： 假设现在往队尾插入橙色直线。 我们发现橙色直线和队尾直线的交点比队尾直线和倒数第二条直线的交点 ...

测试文档 代码功能测试 123456789int read(){ int x = getchar(), ans = 0; while(x < '0' || x > '9') x = getchar(); while('0' <= x && x <= '9') ans = ans * 10 + x - '0', x = getchar(); return ans;} 公式测试 \(\sum^n_{i=1}\dfrac{1}{i}=\ln n + C\)