wrpwrpのBlog

B 给一个整数数组 $a$，和一个整数 $x$， 求 $a$ 有多少子序列满足任意两个数异或和大于 $x$ 。 经典结论是异或最小值在相邻点取到， 排序以后用 Trie 优化 DP 即可。 I 给你一棵树， 要你猜一个点 $x$, 你要在 $4 \log_2 n$ 次操作中把 $x$ 猜出来。 每次操作是你给一个点 $t$ 和一个集合 $V$， 交互库告诉你 $t$ 到 $x$ 的距离是不是小于 $V$ 中所有点到 $x$ 的距离。 $n \leq 10^5$ 好像很 shaber， 直接点分治， 然后对儿子集合二分一个前缀就可以找到点在哪个子树里面了。 复杂度上界 $\log_2^2 n$, 但是好像非常松。 按照经典 DS 套路把二分过程加权， 然后玛德怎么过不了 然后开始 diff 各种题解， 发现我的二分会莫名奇妙多算一次。 以后写点阳间的二分吧。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061 ...

A, B, C, D诶呦怎么做来着？ E这玩意一看就是排序以后选若干连续段。从大到小选， 直接状压DP就完事了。注意不从小到大因为最小值可能不选但是最大值一定选。 F诶呦怎么做来着？

A随便判断一下。 B显然排序以后取前 $n$ 个和后 $n$ 个。 C存一个 $cnt[size][sum]$ 表示有多少串在强制前一半长度是 size ， 需要剩下一半的和是 sum。直接处理以后枚举即可。 D显然确定了 $b_1$ 就全确定了，而且题目保证有解， 那我们只需要判断每个数是不是都比 $n$ 小， 这个东西就是枚举 $b_1$ 放 Trie 上查询最大值就行了。 E选了一个以后下一步其实是确定的， 设选 $i$ 以后下一张牌是 $to_i$， $i$ 往 $to_i$ 连边建图即可简单判断。 F因为 $x$ 很小， 可以猜到是不是 $x$ 小的时候有神秘做法， 于是河里猜想容斥一下， 计算 $\min {a_i} \leq x + k - 1$ 的答案， 减去 $\max_{a_i} \leq x - 1$ 的答案。 $\min { a_i } \leq x + k - 1$ 这个条件实际上是容易计算的， 因为限制是关于差的， 考虑构造差分数组进行计数， 那么一共有 $(2k + 1) ^ {n - 1}$ 个不同的差分数组， 求前缀和放到平面上考虑就是一条折线， 因为 ...

A, B, C, D, E略。 F考虑每次合并两个子树， 定义一个合并 Tag (rest, max_merge) 表示子树里面有多少点， 最多可以合并出来多少对， 这个 Tag 支持合并， 直接合并即可。 G1, G2这题有非常显然的线段树优化建图的做法。 看了一眼 Jiangly 代码， 发现有个哈希， 突然发现原来每个颜色只会出现两次， 那么序列就是若干不相交的段， 对于一个分段点， 这个前缀中每个数出现次数应该都是恰好一次。 答案就是分段点的个数， 每个段里面选法其实是固定了一些颜色的一些点， 但是先后选无所谓， 把这些点拿出来， 点个数乘积就是答案，

A枚举所有方向即可。 B一眼顶针， 排序以后处理即可。 C观察到三次操作以后答案是 $0$。一次操作的可以暴力， 两次操作的枚举所有的差， 搞个 $set$ 存一下数就行。 D首先判 $a_i > b_i$ 就是不合法。然后从小到大对 $(a_i, b_i)$ 按照 $b_i$ 为第一关键字按顺序贪心即可。 E其实发现就是到一个点最远的点一定是直径端点， 问题转化为维护直径。ban 一个点其实就是 ban 一段连续的 dfs 序， 使用线段树维护直径即可。 Fshaber 题， 随便倍增或者线段树优化建图以后拓扑排序即可。

A, B, C略。 D感觉晚上的 wrp 是超级逆天。显然最后的序列两个相邻的数中间不能有小于这两个数的数， 设 $f_i$ 表示钦定选 $i$ 这个位置上的数， 考虑 $i \rightarrow j$ 的转移， 转移合法当且仅当 $r_i \geq l_j - 1$, $l, r$ 表示这个值作为最小值的区间。 可以写个 BIT 就过了。 一个经典的做法是， 可以在求 $L, R$ 的过程中顺带实现这个转移， 前缀和可以做到线性。 E傻逼题， 一眼就是全变成0然后 行列建立点， 原图中一个位置对应一条边， 要么贡献 + 1, 要么贡献 -1， 跑最小费用最大流即可。 F考虑计算两部分贡献， 一个是修改一个字符会增加多少回文串， 一个是修改一个字符会减少多少回文串。 维护 $add[i][j]$ 表示把 $i$ 这个位置字符改成 $j$ 会多多少回文串， 这个东西就是枚举每个回文中心， 考虑两端的字符， 使用二分+哈希求LCP即可实现。 维护 $del[i]$ 表示修改 $i$ 这个位置字符会少多少回文串， 那就枚举所有回文中心， 发现其实是回文中心左边右边分别加等差数列的形式， ...

vp赛时通过六题。 M考虑每个菜对人的贡献， 人不变， 那就让菜贡献尽量大。所以对于每个位置计算这个位置放辣菜可以被几个人吃， 从多往少选位置放辣菜就行。 J显然在叶子节点考虑问题就可以了， 因为要是出去了总是会到叶子节点。不难发现就是匹配叶子节点， 但是如果匹配的这两个叶子节点就是兄弟节点的话， 可以发现其实根本跑不动， 所以让叶子个数是 $a$， 子节点中叶子节点个数最大的那个点的子节点个数是 $b$，答案是 $\max ( \frac{a + 1}{2}, b ) $ 。 C看到这个直接考虑数位 DP 就行了。 F比较两个数可以利用前缀和差分就可以算出来。$[p_l > p_r] = f(l, r) - f(l + 1, r) - f(l, r - 1) + f(l + 1, r - 1)$ 。直接用这个排序次数会用多， 从左往右做插入排序可以减少一半询问， 就可以过了。 H直接 dfs 就完事了。 I可以发现， 一旦发生两个人重合， 那就直接走最短路。 所以答案一定是走到 $k$ 点范围内一个点， 然后走出去范围以后一路走最短路。 所以只需要在范围内跑 $dij ...

A略。 B略。 C玛德被爆了。其实你可以发现因为第一次找出来的就是最长的那个子序列， 所以操作完以后其实就是把那个子序列 reverse 了， 唯一的坑点在于有多个最大值的时候不用移动长度次， 移动长度减去最大值个数加一次就可以了。 D玛德被爆了。发现删掉第一个然后加到最后一个位置， 维护所有mex就是一个后缀赋值然后最后加一个的问题， 使用 deque 维护所有连续段就行。 E总共大小不同的子树不超过 $\log_2 n$ 个是线段树的经典结论。考虑贡献始终是关于根节点的一次函数， 维护 $F(x) = kx + b$ 这个函数的系数即可， 这个理解挺精巧的。 F最重要的观察是， 好点 $i$ 一定有 $i = p_i$， 那显然就只有 $2n$ 对可能的交换, 因为你交换总得能新产生一对才优秀， 那么考虑要么把 $i$ 归位， 要么 $i$ 已经归位了， 调整前后最大最小值的位置使得 $i$ 满足条件。 暴力判断这 $2n$ 对即可。 玛德这 shaber 题怎么打成这鸟样的啊。

G显然答案就是固定的， 就是两个序列分别求相邻两个数绝对值的差加起来就可以了。 A构造考虑让所有 gcd 都是1， 那么对角线上面按照往左， 往下， 往左， 往下连续放数就好了。 D显然是每个优惠券用在其区间种最便宜的那个身上。 暴力用然后对所有的物品从小往大排序取就可以了。 F结论 （波利尼亚克猜想）： 对于任意奇偶性相同的 x, y, 存 在无穷个 z, 使得 x + z, y + z 为质数. 设 f(i, j) 表示填到 i， a[i] 是不变还是变成1还是变成偶数还是变成大于1的奇数， 转移即可。 J直接状压DP。 I把元素按照 $(\frac{x}{k}, x \mod k)$ 处理， 维护右边一列和已经加入最右边一列的倒数第二列， 使用 pbds :: tree 可以简单完成。 12using namespace __gnu_pbds;tree <std :: tuple<i64, int, i64>, null_type, std :: less<>, rb_tree_tag, tree_order_statistics_node_upda ...

每次打牛客 Debuff 拉满， 受不了。 K签到题。 F签到题。 L简单题。因为 $n$ 很小， 考虑直接暴力枚举两个颜色是否有 $i > j$, 如果有就连边 $j \rightarrow i$ 。把 $1, 2$ 看成同一个点跑拓扑求最长路即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include <bits/stdc++.h>#define rint register intusing namespace std; const int N=1005;int n,r[N],g[N],b[N],rd[N],ans[N],vis[N][N];vector<int> e[N];queue<int> q; void Add(rint x,rint y){ if(x==2) x=1; if(y==2) y=1; if(vis[x ...