2021牛客暑期多校训练营10 AC代码 A. Browser Games 字典树原题，只不过空间缩写，无法存下 $nm$ 个节点。考虑将无用节点剪去，并将只有一个儿子的节点进行压缩，这样只需要 $n$ 个节点。 F. Train Wreck 每一时刻进行入栈或出栈，对入栈元素进行排序使得没有任意时刻栈内序列相同。首先计算栈内每一层需要入栈的次数，…

2021牛客暑期多校训练营7 AC代码 F. xay loves trees H. xay loves count I. xay loves or 已知 $x,s$ ，求 $x|y=s$ 成立 $y$ 取值的数量。需要注意 $y$ 要求是正整数。

AC代码 A. Ares, Toilet Ares 虽然这题出题的本意是好的，但是英语水平堪忧，只能说也是个脑瘫谜语题。 读懂之后就是个签到题，但是要注意特判去厕所获得0行代码的特例（不管有没有成功都不会对结果产生影响）。 D. OR 可以对每一个二进制位进行分析，可以得出左右两边1的数量之和。然后从头精选枚举取值的可能性即可。 E. Rise o…

2021牛客暑期多校训练营6 AC代码 C. Delete Edges 构造题，要求在点数为 $n$ 的完全图上选出三角形，使得剩余边数小于 $n$ 。在比赛过程用想出了一种构造方法，但在几种特殊取值的情况下会发生错误。赛后在结合相关的构造论文，找到了最大匹配数的解法。 D. Gambling Monster FWT与分治结合题。在比赛时求出了题目…

AC代码 C. Cells 给定大小为 $N$ 的数组 $A$ ，询问 $N$ 个人分别从点 $(0,A_i)$ 出发前往 $(i,0)$ 且路径不相交的方案数。 $N\leq 5\times 10^5, A_i\leq 10^6$ 。 光从题面考虑，这就是LGV引理的模板题，但是求行列式的复杂度高达 $N^2(N+\log MOD)$ ，因此难以…

2021牛客暑期多校训练营5 AC代码 B. Boxes 箱子中有黑或白的球，开箱需要花费，也可以花费一定代价询问剩余箱子中黑白球的数量，求解要知道所有球颜色的代价的期望。首先考虑把所有箱子打开的代价，其次考虑一开始进行询问后代价花费的期望。通过找规律可以得到询问后每个箱子需要打开的几率，然后取两种方式较小值的答案。 C. Cheating and…

2021牛客暑期多校训练营4 AC Codes B. Sample Game C. LCS 构造 $3$ 个长度为 $n$ 的字符串 $s_1,s_2,s_3$ ，使得 $LCS(s1,s2)=a,LCS(s2,s3)=b,LCS(s1,s3)=c$ ，$a,b,c$ 是给定的数字且 $a,b,c\leq n$ 。LCS是最长公共子序列。 先提取公…

2021牛客暑期多校训练营3 AC代码 B. Black and white 首先尽可能要减少我们选择的点的个数，然后思考本题的条件：如果一个矩形的三个角都有已被选择的点，那么剩下的那个点将被自动选择；这个条件实际上说明了一个事实，我们选择的点集不含有偶数环。同时注意到这个网格图可以建图为一个二分图，因此本题只需要在二分图上跑最小生成树。 C. M…

2021牛客暑期多校训练营2 仍然是单打的一场。 这场题目还很恶心，全是工地英语和毒瘤题，体验极差。 AC Codes C. Draw Grids 容易发现能画的边数一定是 $nm-1$ ，判一下奇偶性就好了。 D. Er Ba Game 小模拟。 F. Girlfriend 注意到题目中的定义与阿波罗尼斯圆是一致的（因为 $\frac{AP}{P…

2021牛客暑期多校训练营1 队友跑路，痛苦单打。 AC Codes A. Alice and Bob Alice和Bob从两堆石子（石子数分别为 $n,m$ ）中取石子，Alice先手选择一堆，从中取 $k(k>0)$ 个；Bob后手只能选择另一堆，从中取 $sk(s\geq 0)$ 个，谁不能取就输了。询问谁必胜？ $T(T\leq 10^4)…