A - Browser Games 题意：按顺序往集合中插入字符串，要求输出最少的前缀串数量，使得这些前缀串能匹配出所有已经加入集合的字符串，并且不能匹配出未加入集合的字符串。题目保证任一字符串不是其它字符串的前缀。 思路：如果不卡空间的话，光字典树就有许多不同的做法。一种是从上到下做，但是这种做法需要表示出每个节点的儿子有哪些，就比较浪费空间。对于一棵树来说，每个节点的父节点是唯一的，压缩字典树的时候应从这一点考虑。所以尝试先写写从下到上的做法。 建立字典树之后，记录每个字符串的尾节点的位置，然后从下往上走。如果遇到的节点只有当前字符串一个儿子，那么就可以继续往上走。当遇到有分叉的节点时，我...

C - Cells 题意： 给出二维坐标上个点，对于第个点要到达，只能向下走或者向右走，求路线不相交的方案总数。 题解： 考虑引理，引理可以用于在上求解不相交路径方案数问题 表示这条路径上的边权之积,解决路径计数问题时通常设为 表示到的每一条路径上的值之和 答案就是矩阵的行列式 代入本题，答案就为 则对于每一列，我们都乘，这样最后的行列式就扩大了, 然后我们利用初等列变换将前一列消掉靠后的列，可以得到可以发现这是个范德蒙德行列式，可得行列式为$j!\prod_{1 \leq i < j \leq n}(a_j - a_i)n^2NTTn\log{n}$ #include&lt...

A - Ares, Toilet Ares 题意：厕所战神已经A了道题了，接下来要写'k'题，能上次测所，第次上厕所能获得行代码，所有相加就是最终的代码，但有每次获得的代码都有概率是错误的，问厕所战神最终能A出题目数量的期望。 思路：阅读理解题，前期一直没开，开了之后联系下沈阳实际情况，立马就懂了，一开场就开或许能抢个一血？（雾） 特判下行代码即可。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define dbg(x...) do{ cerr << #x << &...

B - xay loves monotonicity 题意：给你两个序列，其中第二个为序列。每次单点修改第一个序列；区间修改第二个序列，让区间所有数字；进行区间询问。 询问的规则是，从左端点开始，往右找第一个大于等于它的值的位置，然后接着找，直到不能找为止。然后把这些位置的数组对应的值取出来，如果相邻的值不相同，那么就会有一个贡献。输出贡献和。 思路：洛谷上有原题，先丢个链接P4198 当时写完原题，我就觉得原题会写，这道题就一定会写，只是多了些东西恶心你。 然后我就被卡了 本人习惯做线段树pushUp，合并两个区间维护时回传结构体，然后就写得很麻烦。这里传个指针就很简单了。 先写原题，再写这...

A - Contracting Convex Hull solved by Tryna.(-) 题意： 许多半平面正在匀速移动，每次询问给定一个时刻，求该时刻下半平面的交构成的凸包的面积 题解： 凸包收缩时每个顶点都是沿着角平分线移动的，当运动到相邻两个对角线相交的顶点，就会两点重合，凸包的形状就会发生变化 对于当前这个凸包，我们找到最近的那个使凸包发生变化的顶点，我们已知移动的距离，可以通过三角函数求出运动的时间，知道了时间就可以以同样的方法求出其他顶点运动的距离，新的凸包就是已知的，然后就重复操作 对于每次变化，凸包总有一段时间形状不变，然后我们就可以求出在这段时间之内的询问，面积是关于...

B - Boxes solved by Tryna.(-) 题意： 给出若干个盒子，盒子里面只有一个球，颜色为黑或白，每拆开一个盒子有一个花费，还可以通过花费一次来知道盒子内总共有多少黑球，求知道所有盒子中是什么球的花费的最小期望 题解： 不询问，所有盒子都开一遍，花费为 询问一遍，按花费从大到小开盒子，开到第个盒子能直接判定的前提是后面全部同色并且第个盒子与后面异色，所以一共需要个球为或者，这两种情况出现的概率都为,相加后为，排序后处理一下前缀和即可 #include<bits/stdc++.h> using namespace std; #define dbg(x...)...

J - Counting Triangles 题意：给定一张完全图，边权只有两种，问全三角形和全三角形数量。 思路：题解好简单，我写得好麻烦QAQ。两种权值，三条边，那么对于不合法的三角形来说，会拥有两个边权不同的角，将原有答案减去不同边权角数量的一半就行了。 #include <bits/stdc++.h> using namespace std; #define endl "\n" #define dbg(x...) do{ cout << #x << " -> "; err(x);} while (0) v...

I - Kuriyama Mirai and Exclusive Or 题意：序列上两种操作，对异或上，对异或上，问最后序列的样子。 思路：区间修改，只问最后长啥样，试试看异或差分。操作直接搞就行，操作显得很复杂，看起来只能单点修改。观察这个式子。当时，这个式子等价于，也等价于，看看能否把这个异或的式子加入到异或差分中。那么首先对于这个区间，我们先对其整体异或上，然后问题就转换成了对这个区间异或上。首先肯定不能一个个推过去，这样和前面暴力是没有区别的。设，把异或的值都拿出来，得到。我们以为中间的边界，可以把右边的值写成。相当于从原本要异或的值中取出前一半，复制一份给后一半，同时将后一半的区间整...

F - 24dian 题意：用张纸牌计算，这张纸牌所有可行的计算过程中都得包括一个小数，按字典序输出方案。 思路：很容易推出是一定无解，至少可以通过排列好计算顺序，使得小数不存在。其余情况时，暴力枚举计算顺序和符号即可，枚举计算顺序时括号也就能被考虑进去了。每次从剩余集合内任意挑选两个数出来进行计算，算完再丢回去，进行下一轮计算，直到只剩下一个数为止。因为太菜写了结构体 #include <bits/stdc++.h> using namespace std; #define endl "\n" typedef long long ll; const int ...

E - Math 题意： 求的答案 题解： 打表找规律，找到两种 第一种是形如这样的二元组，预处理内的立方即可 第二种是一个递推的关系, 也预处理一下即可 计算过程中会爆，开__int128即可 #include <bits/stdc++.h> using namespace std; #define endl "\n" #define dbg(x...) do{ cout << #x << " -> "; err(x);} while (0) void err() { cout << endl;...

J - Product of GCDs 题意： 给出一个数组，求这个数组里所有大小为的子集的的乘积。 题解： 我们考虑通过枚举来求得答案，也就是对于每个，我们需要求有几个集合的为。 我们考虑枚举的倍数，这样只可能为或者的倍数。但这样会有一个问题，会把为的倍数的集合也筛选进来。我们可以从大到小枚举，然后减去为的倍数的集合。考虑组合数，为的倍数的个数。假设为的集合个数为，最后答案就是 但是因为会很大，所以没办法直接求上述式子。故我们考虑扩展欧拉降幂，因为模数并没保证是质数。但是模数又来到了很大的，所以我们无法通过线性递推来求欧拉函数，我们得借助分解质因数和容斥原理来求欧拉函数。因为要分解质因数...

G - League of Legends 题意：有个人，要分组，每个人有自己的空闲时间，一个组里可玩耍的时间是组内所有人时间的交集，要求至少为。问最优情况下，所有组能玩耍的时间之和最大是多少。 思路：我们发现能覆盖别的小区间的大区间十分特殊。如果和别人放在一起，大区间一定会覆盖组内的交集，可以看做对答案没有贡献；如果单独放为一组，贡献就很大了。所以考虑优先处理大区间，把它们筛出来，可以求出将个大区间单独设为组能取得的最大贡献。 对于剩下来的小区间，我们转换一下，每个组的贡献就是每个组之中最小的右端点减去最大的左端点，且贡献一定要大于。我们先按左端点进行排序，再按右端点排序（其实右端点的排序是...

F - Girlfriend 题意： 给出四个点以及，求点集构成的几何体相交部分的体积 题解： 口胡了一下两个几何体是球，事实上也可以用配方法证明是球 容易求出两个球的球心和半径 然后就是求两个球相交部分的体积了 还需判断两个球的位置关系 #include <bits/stdc++.h> using namespace std; #define dbg(x...) do{ cout << #x << " -> "; err(x);} while (0) void err() {cout << endl;} tem...

J - Journey among Railway Stations 题意：个点，每个点的合法时间是，第i个点到下一个点的需要的最短时间为，每次询问从点出发到r点是否合法，或者修改值，、值。 思路： 要从点到点，可以列出式子 在合法情况下，如果到不了，那么就直接取到，否则就取。也就是说，我要在前面找一个点，这个点到当前点需要的最小时间最大，再判断当前的合法性。 设点和点，点到点时的最小时间是，点到点的最小时间是。一路加过来显然不合理，除自身点值外，两者仅相差，也看出了两者的左端点是确定的，但是右端点会随着点的改变而改变，那么不如将所有点的右端点均设为，把所有和都加上相应的，变成和，重新带回到...