什么泄出题人比赛开始了两个小时才改好题面。 首先枚举连续睡觉时间的开始，则可以算出在这一段时间内吵闹的人转移到的可行区间。 这样问题就变成每次有一段可行区间求区间最小值。 直接st表肯定是不行的，但是注意到每次睡觉时间只会往后移动1，那么吵闹的人转移到的可行区间的l和r也只会变化1。 这样我们可以用单调队列维护，具体的在时间1把可行区间里的所有吵闹的人加入单调队列，然后右移左右端点，加入右端点的权值，更新即可。 注意到每个人对答案的贡献是独立的，所以可以每个人分开算，即每个人算出睡眠左端点为i时的最小值，最后把所有人的答案相加即可。 然后这题是个环，为了方便处理可以断环成链。 /* _...

wdnmd真就自闭了，上次数组开小1扣了15分痛失阿珂，这次一样扣了15分。 对于出租车类型为1的边，连边方式同普通无向图。 对于公交车连类型为2的边，建两个虚点1和2，先把所有站点向虚点1连边权为0的单向边，再从虚点1向虚点2连边权为c的单向变，再从虚点2向所有站点连边权为c的单向边。 这样每次就从a开始跑dijkstra。 但是注意到题目的计费方式出租车和公交车不同，所以要对距离开结构体dis表示当前距离为k*r+p。 这样可以重载加号和小于号来做到连续坐出租车的更新，当出现一条类型为2的边，把距离的p设为0，即从出租车上下来了上了公交车即可。 注意因为新建了虚点和新连了边，所以数组要略微...

要是早点写这题就能赛时调过了，就能Rank2了(痛哭 看到题目先来化一波式子： 为了简化式子，令，， 发现长得都很像，所以其实只要求出形如的东西就行了。 考虑每个位置的权值对这个式子上面的指数的贡献，我们可以得知这个式子就等于 。 组合意义是每个位置选或者不选的所有情况，最后再减去空集。 发现这个就很好拿线段树维护了。 具体的，线段树上每个节点维护区间所有前缀积的和，区间所有后缀积的和，区间所有数的乘积，区间以及所有子区间的答案。 那么的时候，有 然后就是一开始线段树上每个位置的初值如何处理，开个结构体代表某个数是的形式，重载运算符和就行。 根据数的运算规...

首先因为能走过的边的边权是递增的，那么经典套路是枚举最大的边的长度然后用并查集合并图上点的连通性。 按照题意，当困难度为的时候的答案就是将所有边权的边加进去之后起点所在的连通块中不同类型点的数量。 注意类型数量比较少只有种，所以可以直接对每个并查集用维护并查集里出现的点的类型情况。 发现有多次询问，只有当加入的边的最大边权变化时获得的愉悦值才会改变，所以先把边权离散化，从小到大枚举加边做前缀和。 具体的设离散化后一共有种边权，将第小的边加进去之后获得的愉悦值是，设表示从最开始到现在获得的愉悦值的前缀和，则。 这样对于输入的和有三种情况： 那么答案就是。 设所有边权中第一个大于等于的边是第大...

先吐槽一波出题人( 数据强度属实不行，同学写的暴力竟然拿了。 读完题发现可以点分树做掉，但是不大会写，所以写了对操作序列分块的做法。 考虑朴素判断某个点是否染色，遍历上次清零操作之后的所有插入操作，如果，那么现在的点可以被染色。 这样考虑对操作序列分块，块大小为，插入操作对某个询问操作的影响分为两种：同在一个块内的和在之前的块里的。 对于这两种插入操作的影响分别计算，对于在同一个块内的就按照上面所说的朴素做法遍历所有在它之前的插入操作；对于块外的插入操作，如果能算出仅有那些操作当前点最早能在什么时间被染色就可以判断。 假设该块之前的都已经算完了，那么现在只需要把当前块的所有操作加入影响中，我们...

主席遗留下来的遗产~ \(Day5\) 杜爷删代码的时候找到了一个去年他不会的题，所以拿来看看觉得还挺有意思，就是\(C\)。 然后切完\(C\)就顺便把\(A\)和\(B\)也补了。 吐槽下奇怪的难度顺序：\(B > A > C\) \(A\) 如题每个连通子图最后只会剩下\(n - 1\)条边，所以答案就随便算了。 #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 100000; const ...

Description 传送门 Solution 首先每个连通块之间是独立的，也就是说算出每个连通块的\(sg\)值异或起来就行。 那么每个连通块单独考虑，进行一次题目中的操作后，会产生一些新的连通块，假设当前节点为\(x\)，它能到达的所有点的\(sg\)值都已经算出来了，那么如果选择的是\(x\)，下一个状态的\(sg\)值就是所有能到达的点的\(sg\)值的异或和；否则就是选一个能到达的点从它的子树中删除一个点，再异或上其他没有选的点的\(sg\)值，而我们可以开一个集合把每个点的子树里的所有点的\(sg\)值都记录下来，这样每次就相当于对一个集合里的所有数异或某个数，还要支...

难题做不动就去翻去年的洛谷csp题做，实在是水啊~ 第一次 (A) (dp_{i, j})表示使用(i)个色子得到点数为(j)的概率，这样求出(dp_x)和(dp_y)两个(dp)数组后就可以枚举(x)个色子得到的点数，(y)个色子得到的点数是一个前缀，枚举即可。 #include #include #include using namespace std; int x, y; double dp[1050][6050], sum[6050]; int main() { scanf("%d%d", &x, &y); for (int i...

\(A\) 传送门 用哈希表去下重即可。 #include <iostream> #include <cstdio> #include <cstring> using namespace std; #define ll long long const int MOD = 1000037; const int jia = 1000000001; int n, x0, y0, xt, yt, ans; ll tmpx, tmpy, to[1000050]; int head[MOD + 50], nxt[1000050], num; void...

\(U\) 传送门 矩阵的范围比较小只有\(5000\)，但是操作次数比较多有\(3e5\)，最后只需要查询一次。 操作次数多查询少，我们首先就会想到差分。 那么由于操作的图形不是传统的正方形而是三角形，所以需要在原本的二维差分上进行膜改。 考虑二维差分的意义，因为最后每个点的值是他左上方的所有数的前缀和，那么在差分数组上某个位置修改，就相当于对那个位置到矩阵右下角的一个正方形修改。 这样子我们就可以发现三角形就是将那条对角线上的每个点的查分数组加上\(s\)，相邻的一条对角线减去\(s\)，三角形左下角减去\(s\)，三角形右下角加上\(s\)。 那么在对每条对角线维护一个差分...

\(Day2\) \(A\) 概率期望经典入门题，根据期望的线性性，答案就是每个点被选到的期望之和，每个点的贡献为一，所以只需要求每个点被选到的概率即可，每个点必须在它的子树中的点被选之前选，所以概率是\(\frac{1}{size_i}\)。 #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MOD = 998244353; const int N = 10000000; int n, head[N + 50], num...

\(Day2\) \(A\) 注意到排序后每次是选一个前缀，所以可以在线段树上二分，每次全局加上可以拿的物品，选了的清零即可。 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define ll long long const int INF = 0x7fffffff; const int N = 200000; int n, m, pos, c[N + 50]; ll sum[N...

\(A\) \(10pts\) 暴力即可。 \(50pts\) 发现这就是一条链的情况，也就相当于本题搬到了序列上。 根据后缀最大值的定义，不难发现序列上的后缀最大值的权值是递减的，而且后缀最大值的位置是递增的，这启发我们用单调栈维护所有后缀最大值。 具体的，单调栈内按权值递减的维护元素，当加进当前位置的元素时，所有权值小于它的栈内元素都不再是后缀最大值，将他们全部从栈内弹出。 最后单调栈内剩下的权值都是后缀最大值，时间复杂度\(O(n)\)。 \(100pts\) 树可以看做一些链并在一起，所以我们只需要对树进行\(Dfs\)，即可将树上问题变成序列上的问题。 然而树上\...

\(About\) 感觉做题思维很差，很多题算法都会但就是想不到（捂脸。 滚来做\(CF\)题锻炼思维力。 \(Codeforces\ Round\ \#665\ (Div.\ 2)\) \(A\) 分两种情况讨论。 若\(k >= n\)，那么将\(A\)移动到\((k, 0)\)为最优。 若\(k < n\)，解方程\(n + (n - b) = k\)，解得\(b = \frac{2 \times n - k}{2}\)，如果\(b\)为整数则答案为零，否则无解。 \(B\) 发现只有\(a_i = 2, b_i = 1\)的时候可以使答案增加，所以贪心的先...