分层图前言在一次模拟赛中，我遇到了[USACO15JAN]GrassCownoisseurG这道题，当时不知如何下手，和边上的同学偷偷讨论，听别人说是分层图，建两份图然后连一层反向边即可，当时对这个图论建模大为惊叹（不亚于我在学网络流时学到拆点拆边），故专门写一篇博客记录之。算法思想分层图是图论

T1.涂色游戏（paint）可以按照题意模拟，每一次暴力对于每一行列染色，时间复杂度\(O(qn)\)。可得60pts。因为颜色可以覆盖，某一格的颜色往往取决于最后一次被染到的颜色。于是我们采用打标记的方式。每一次染色（行或列）就在当前行列打标记，记操作时间戳\(t\)。最后输出答案时枚举每一格

利用Splay进行序列操作时，将数组坐标整体平移1，给0留出空间，并在操作过程中始终保持0号节点的特性用#define语句和struct的构造函数简化编程复杂度对名字空间(namespace)有了更深刻的理解Splay的常数较大，难以通过1e6规模的数据在建树时，根据Splay的特性，直接建出一条只有右儿子的

T2调了1h没调出来，丢了一坨没分的shi扔了。我想放一下作为开头：include<bits/stdc++.h>#defineintlonglongusingnamespacestd;inlineintread(){intw=1,s=0;charch=getchar();while(!isdigit(ch)){if(ch'-')w=-1;ch=getchar();}while(isdigit(ch)){s=s10+(ch-

题意多组数据。数轴上有\(n\)个点，编号为\(1\simn\)，对这些点做$m$次操作。每次操作给出三个整数\(a_i(1\lea_i\len)\\\d_i(1\led_i\le10)\\\k_i(0\lek_i\len)\)。将点\(a_i,a_i+d_i,a_i+2\timesd_i,a_i+3\timesd_i,\cdot\cdot\cdo

智障行为+1T1T2T3T450100500T150pts【问题描述】现在有

Rank打得还可以总A.构造字符串签，但是挂了40pts。发现判条件只有相等和不相等，于是想到并查集维护连通块，将强制相同的两个位置的连通块合并，强制不同的先记下，最后统一判断。重点在细节处理，合并连通块时要将位置靠后的合并到靠前的上，注意\(LCP(x,y)=z\)在\(x+z,y+z\le

如果不能越级打怪还叫什么主角#include<bits/stdc++.h>namespacemy_std{ usingnamespacestd;#definerep(i,x,y)for(inti=(x);i<=(y);i++)#definedrep(i,x,y)for(inti=(x);i>=(y);i--)#definego(x)for(inti=head[x];i;i=edge[i].nxt) constlonglongmod

概念在C语言中，共用体（Union）是一种特殊的数据类型。它可以在不同的时刻存储不同类型的数据，但所有成员共享同一块内存空间。这与结构体不同，结构体的每个成员都有自己独立的内存空间。定义和声明定义共用体的定义形式与结构体相似，使用关键字union。例如：unionData{int

Preface北京市赛（×），小WF（确信）感觉这场题总体都挺难的，除了前1h出了两个题后，后面基本上都是1h出一题然后最后1h发生了经典的我和徐神B,F双开双会，最后开始抢机时，最后经典的一个没写出来赛后发现F赛时代码改个初值就能过了，而徐神多花了半小时也是成功把B过了只能说还

题目链接点击打开链接题目解法真难啊/yun把区间染成红色看作区间\(+1\)，染成蓝色看作区间\(-1\)，要求是每个点上的数\(\in\{-1,0,1\}\)可以选择的数有\(-1,1\)不太好做，我们考虑将限制变成每个点上的数只能为\(0\)我们记经过点\(x\)的线段数量为\(cnt_x\)如果\(cnt

这次状态不是很好，冲着T1磕了4个小时，后仨题看都没看。。。A.median去他丫的容斥，考虑排序，一个数作为中位数的方案数就是他左边有俩不同类型的数和右面有俩不同类型的数的总和枚举哪些类型左边哪些右边，对每一位计算贡献就可以了，要提前预处理出来个数。（有没有好心人看看我代码哪

这可能也是一个关于匹配的经典trick。题意给定常数\(C\)，你需要维护一个集合\(S\)，支持以下操作：1x，加入数\(x\)，保证\(x\)之前不存在。2x，删除数\(x\)，保证\(x\)之前存在。每次操作后你需要回答$$\max_{i,j\inS,i\not=j}(i+j)\bmodC$$\(Q\le5\times10^5\)，强制在

如果你要，拿走不谢#include<bits/stdc++.h>//#pragmaGCCoptimize(2)#defineintlonglong#definepiipair<int,int>#definetpituple<int,int,int,int>#defineilinline#definep_qpriority_queue#defineu_munordered_map#definebtbitset

A.赛事找规律找到了，可惜差一步，然后用了oies。欧拉定理：若\(gcd(a,m)=1\)，则\(a^{\phi(m)}\equiv1(mod\m)\)。发现1和\(2n\)永远都不会动，并且当2归位时，整套牌也都归位了，所以先只考虑2的位置变化。如果\(n\)无线大，第\(i\)次操作后2的位置为\(2^i+1

[介绍（百度百科）](笛卡尔树_百度百科(baidu.com))笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围\(top_k\)查询（rangetopkqueries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结

T1一般图最小匹配点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=5000+107;intn,m,a[N];intread(){ intf=1,s=0;charch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=ge

T1光我们来考虑一个格加\(4\)或者减\(4\),这样有一个比较好的性质，它能提供\(4,2,2,1\)的贡献还不会溢出，这样我们就有一个比较好的思路，我们枚举\(4,2,2,1\)所无法造成的贡献，很明显只有\(16\)种，然后我们就可以再枚举\(4,2,2,1\)来算贡献.点击查看代码#include<bits/

移动题意有一个\(n\timesm\)的网格图，有\(k\)个点不能走。每次移动可以向右或向下走，只能走两次。求能走到的点的个数。思路可以发现只能是从第一排向下走或从第一列向右走。统计上下走能到的点和左右走能到的点，减去重复的即可。扫描\(x\)，使用线段树维护\(y\)每一个

楼房重建题意小A在平面上\((0,0)\)点的位置，第\(i\)栋楼房可以用一条连接\((i,0)\)和\((i,H_i)\)的线段表示，其中\(H_i\)为第\(i\)栋楼房的高度。如果这栋楼房上任何一个高度大于\(0\)的点与\((0,0)\)的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。

A一般图最小匹配首先排完序后肯定选连续两个。直接DP，\(f_{i,j}\)就是表面意思，\(f_{i,j}=min(f_{i-1,j},f_{i-2,j-1}+a_i-a_i-2)\)。差分后发现问题转化成了选择的数不能相邻，这时候也可以直接考虑DP，但是这是一个经典的反悔贪心。记下\(pre\)和\(nex\)，直接扔到堆里，选择一

扫描线-学习笔记引言：扫描线算法用于解决给出多个矩形组成的图形求解其面积、周长等问题。时间复杂度常见为\(O(n\log_2^n)\)级别，空间复杂度略大于\(O(n)\)，属于线段树的一种运用。一、求面积题目：P5490【模板】扫描线&矩形面积并求\(n\)个四边平行于坐标轴的矩形的面积

\(Prüfer\)序列可以适用于很多树上计数问题转化（无根树到\(Prüfer\)序列）：给定一颗树，将树变成\(Prüfer\)序列，盗图！！！嘿嘿1.找到一个度数为\(1\)的点，且编号最小的点（编号最小保证了\(Prüfer\)序列的唯一对应性)2.把这个点的父亲节点加入序列，然后把这个点删除重复进行这两个操作，

$\quad$说一个随机数据很快的方法。$\quad$考虑优化\(O(Tn^2)\)的暴力，首先枚举删数的位置，然后求出此时的最小序列。$\quad$我们发现，当此时枚举的序列已经大于答案序列了，再去枚举该位置就毫无意义了，直接停止枚举即可，这样就会有70分。$\quad$那么还可以怎么优化呢？$\q

又是乌云明媚的一天。[ARC042A]掲示板本来想用两个容器分别维护修改元素和未修改元素，但是遇到有重复操作的元素时会假。看样例发现是把操作倒着输出，遇到重复元素就输出第一次出现的，其余先不管，用一个桶标记一下，最后一并输出。因为元素和下标书写错误WA了一发。点击查看代