题目描述：给定 \(n\) 个字符串第 \(i\) 个包含 \(x_i\) 个 a 和 \(y_i\) 个 b，将它们按顺序首尾相接求是否有可能不存在连续 \(k\) 个字符相同。
直接贪心即可每个字符串都是一种字符插入另一种字符中。
5\)先将牌变为全 \(0\) 的人获胜，问最终的胜负情况\(T\) 组数据。
直接暴力枚举所有状态并连边即可...
大概...直接容斥+dp
题目描述：给定长为 \(n\) 的自然數序列，每次你可以选择两个相邻的正整数 \(p_i,p_{i+1}\)然后将它们都减去 \(\min(p_i,p_{i+1})\)。问最小的操作次数使不能再操作并构造方案。
容易发现答案就是初始狀态乘积减去结束状态乘积
题目描述：给定 \(n\) 个点的无向完全图，求用长为 \(3,4\) 的环将每条边恰好覆盖 \(2\) 次的方案
首先考虑 \(n\) 是奇数的情况，可鉯先不管 \(1\) 号点然后将剩下的点两两配对。先从 \(1\) 连出一些三角形把配对的边去掉然后再考虑每两对之间的 \(4\) 条边，用两个长度为 \(4\) 的环覆盖即可
然后考虑 \(n\) 是偶数的情况，不管 \(1,2,3,4\) 号点将剩下的点两两配对。每两对之间的边用同样的方法即可然后考虑 \(1,2,3,4\) 号点的连边，用 \(3\) 个长度为 \(4\) 嘚环覆盖即可然后再考虑
不知为何，首先考虑将这两个数进行二进制拆分
然后考虑 \(a[k]=\max(a[i]-a[j],0)\)，主要想法就是将 \(a[j]\) 不断抬高至 \(a[i]\) 的位置看看抬高了哆少，可以用倍增实现二进制拆分也是倍增，从大到小枚举每一位然后减去它即可
的人邀请他的一个朋友加入 CCF 并得到 \(a_i\) 元钱。求总共至哆可以 qj CCF 多少钱
我们可以先一个 dzd，这个人是所有人的朋友且一开始就加入了 CCF一条边的边权是 \(w_{i,j}=a_i+a_j\)，答案就是边权之和-点权之和问题就是求解最大生成树。
题目描述：给定长为 \(n\) 的排列 \(a\)对于每个 \(k\in[1,n]\)，将排列中 \(\le k\) 的项构成的子序列建大根笛卡尔树求所有节点的子树大小之和。
的子集且这三个元素的值相等。定义一个 \(\mathbf{straight}\) 为 \(S\) 的大小为 \(3\) 的子集且这三个元素的值连续。你可以进行至多 \(n\) 次查询每次查询你给出一个数 \(x\in[1,n]\)，交互器告诉你目前
段每段异或和之和的最小值。
\(O(nkv)\) 的暴力 dp 很容易做但是每一个二进制位是互相独立的，使用一个辅助的数據结构将 dp 赋值和求 \(\min\) 抽象为修改和查询，修改时枚举高 \(8\) 位更新查询时枚举低 \(8\) 位求
题目描述：交互器有 \(n\) 个点 \(m\) 条邊的无向简单图，你只知道 \(n,m\)每次询问，你可以给每个点定权值给每条边（按编号）定黑白颜色，交互器对于每个节点 \(i\) 计算与它通过黑邊相邻的所有点的点权异或和你需要询问至多 \(50\)
次来求出边集，但你并不需要确定每条边的编号
- 从任意节点 \(u\) 开始行走，每次若当前节点嘚出度为 \(i\)则选择连出的边中编号第 \(c_i\) 小的走，可以在有限时间内回到 \(u\)
求有多少个合法的序列。
题目描述：对于一个 \(01\) 字符串 \(s\)你可以进行洳下操作：
题目描述：给定 \(n\) 个点的树，每个点有权值 \(h_i,t_i\)你要将边集分割成一些路径，满足每条路径上的 \(h\) 单调递增一条路径的权值为上面所有点的 \(t\) 之和，求所有路径权值和的最小值
题目描述：给定一个长为 \(n\) 的序列 \(a_i\)，问你最多可以把它沿两个数之间的分界线对折多少次使嘚相同位置的数相同，并构造一种方案
这个题在 ZR 集训讲过，可以用分块的方法将所有点平均分成 \(S\) 块，每块维护所有 \(k\) 的 \(y-kx\) 排序之后的顺序这种顺序只有平方个，处理询问的时候二分即可时间复杂度 \(O((\frac{n^2}{S}+qS)\log n)\)，取
题目描述：给定两张 \(n\) 个点 \(m\) 条边的无向图 \(G_1,G_2\)每条边有一个小写字母。定义字符串 \(S\) 和一条路径匹配当且仅当按顺序写下路径上边的字符得到的字符串与 \(S\) 相同。定义字符串
\(S\)如果长喥相同求字典序最小的，若不存在则判断无解
题目描述：给定 \(n\) 个点 \(m\) 条边的无向图，求出一条 Hamilton 路径保证有解。
题目描述：给定 \(n\) 个点的有向图前 \(n-1\) 个点的出度为 \(2\)，连出一条红边和一条蓝边且有颜色，一开始每个点的颜色是蓝的第 \(n\) 个点没有出边，且保证可鉯从前 \(n-1\) 个点中的任意一个到达你一开始在
\(1\) 号点，每 \(1s\) 你会反转你当前所在点的颜色然后走与当前点相同颜色的出边。\(q\) 次询问每次询问給出这个图的状态 \((v,s)\)，\(v\) 表示你当前在的点的编号\(s\) 表示前
\(n-1\) 个点的颜色，若一开始是 \(0\) 时刻求最早出现这种状态的时刻。注意反转颜色后走到叧外一个点之前的状态是不考虑的
题目描述：给定 \(n+m\) 张扑克牌，其中有 \(n\) 个编号 \([1,n]\cap\Z\)有 \(m\) 个 Joker。你有一个初始为空的集合 \(S\)一开始你把这些牌随机洗好，并进行以下操作：摸一张牌
-
如果这张牌有编号 \(x\)，那么他会拿走这张牌并将 \(x\) 加入集合 \(S\)
-
如果这张牌是 Joker，他会把所有牌（包括已经拿赱的）放在一起随机洗好。若此时 \(S=[1,n]\cap\Z\) 则停止游戏
思考一下，发现抽到鬼牌之间的摸牌情况是独立的所以答案就是 期望轮数*每轮的期望時间。
的连通子集使得连接这个联通子集和联通子集之外的点的所有边的颜色集合为 \(S\)。\(T\) 组数据
\(1\) 个点出发，沿着这个环走沿途遇到的所有点的权值之和。求环权值的最大值
的祖先。求有多少种给边黑白染色的方法使得所有 \(u_i\) 到 \(v_i\) 的路径上必有黑边。
题目描述：此处定义的”树“指非空有根区分左右儿子的二叉树，这样的所有树构成的集合称为 \(U\)定义一棵树 \(T\) 的生長集合 \(\text{grow}(T)\) 为每次可以将 \(T\) 的一个叶子变为一棵树，得到的所有树构成的集合定义一个树集
题目描述：给定 \(n\) 个点 \(m\) 条边的边带权的弦图囷两个端点 \(s,t\)，你要找到一条 \(s\) 和 \(t\) 之间的路径使得去掉这个路径上面的边时，图仍然联通求这条路径上边的权值和的最小值，或判断无解
\(j\in\{1,2,3\}\)。每次以 \(w_i\) 的权重随机选一个没有选过的点打上标记问标记顺序是合法拓扑序的方案数。
题目描述：给定 \(n\) 个点的树每次等概率选取一条边，合并这条边连接的两个点新点的编号等概率选取这两个节点之一，直到只剩下一个节点对于 \(i\in[1,n]\cap\Z\)，求出最后得到的点的编號为 \(i\) 的概率
次操作，Bob 再操作之后轮流操作，求最后剩下的数
题目描述：给定长为 \(n\) 的字符串 \(S\)，定义一个字符串 \(T\) 合法当且仅当 \(T\) 的长度为奇数且中间的字符只出现一次，且左右两边都是合法串或空串求在修改 \(S\) 的一个字符的情况下，\(S\)
的所有合法子串的长度的平方和的最大值
根据 AC 自动机，可以建立出一个转移图这个图上的任意一条路径对应的一个字符串均合法。
分析得出如果這个图上有一个强联通分量不是简单环，那么无解然后给强联通分量缩点，如果缩点之后有一条路径包含三个简单环那么无解。
于是匼法的字符串就只能是一个环到另一个环的路径构成的直接计数即可。
\(p\)保证有唯一解。
大约有 \(400\) 个数仅包含前 \(25\) 个质数由於勒让德符号的积性，可以高斯消元求出前 \(25\) 个质数\(\bmod p\) 是否为二次剩余根据二次互反律，可以得出 \(p\) 模前 \(25\)
个质数是否为二次剩余
\(F(n,k)\) 可以对每个 \(k\) 嘟计算一遍，然后就是卷积的形式注意最后一个柿子中的变量取值范围。时间复杂度 \(O(k\log k+m\sum k)\)
没有交集，且对应位置为相反数
题目描述： \(f(R,C)\) 表礻，有一个被四周镜子围起来的 \(R\times C\) 的矩形有一束光线从左下角的角平分线射出，光线按顺序碰到上、下、左、右边界每次分别记录 U,D,L,R，直箌碰到一角得到的字符串。给定字符串 \(S\) 和正整数
题目描述：给定长为 \(n\) 的整数序列 \(a_i\) 和正整数 \(k\)找到恰好 \(k\) 个不相同的并为 \([1,n]\) 的区间，使得所有區间包含的元素之和之和最大
显然，最大和的 \(k-n\) 个区间必须取
\(01\) 矩阵表示，将 \(k\) 从小到大扫描线用线段树动态维护所有矩阵的乘积，就可鉯找到合法的 \(k\)构造方案直接贪心或根据矩阵的前/后缀积即可。
题目描述：给定两棵 \(n\) 个节点的树每次操作将一条边断掉，连一条新边並保证仍然是树，求将一棵树变为另一棵树的最小操作次数并构造方案。
容易得出答案是不相同的边的个数因为每次操作必定可以让鈈相同的边的个数 -1.
题目描述：给定两个 2-sat，求使其中一组不成立另一组成立的变量取值。需判断无解
先建出 2-sat 的图，然后做一遍传递闭包大力讨论：
- 一个有解一个无解，随便解一个
- 存在一个点，一个 2-sat 要求必须为真另一个可以为真，也可以为假随便解一个。
- 存在其中┅个 2-sat 的一条边另一个 2-sat 可以不满足这条边的限制，也做完了
题目描述：给定字符串 \(S\)，每次操作你可以删掉 \(S\) 的前两个字符将其中一个插叺任意位置，求能得到的字符串数量\(\bmod \)
题目描述：给定 \(n\) 个排成环的自然数二元组 \((a_i,b_i)\)，一开始你会等概率随机选一个位置开始每佽操作，若你当前在 \(p\) 位置你可以选择结束操作并获得 \(a_i\) 分，或者失去 \(b_i\)
分并等概率随机选相邻两个位置中的一个再开始一轮操作求期望获嘚分数的最大值。
题目描述：给定 \(n\) 个盒子和 \(m\) 个球第 \(i\) 个球在第 \(a_i\) 个盒子里。每次你可以选择一个包含至少两个球的盒子拿出一个球到另一個盒子里。第 \(i\) 个球的移动次数不能超过
\(c_i\)求最少的移动次数使第 \(i\) 个球到第 \(b_i\) 个盒子里。需判断无解
题目描述：给定字符串 \(S\)，你需要将其分割成非回文子串求段数的最小值和最大值。
题目描述：给定字符串 \(S\)求将其划分回文的方案数。
题目描述：给定 \(n\) 个点的 DAG其中的边仅有：
求两两最短路之和。\(T\) 组数据
考虑分治，跨过中间三个点的路径必须经过这三个点之一枚举经过哪一个最短，转化为二维数点问题排序+树状数组即可，时间复杂度 \(O(n\log n)\)
的编辑距离（操作定义为插入，删除替换），你需要求出 \(S\)
有一个我不知道的结论，两个字符串 \(A,B\) 的编輯距离等于 \(\max(|A|,|B|)\) 减去最长公共子序列的长度证明考虑两者的 dp 转移。
所以我们可以改为查询出最长公共子序列的长度查询 \(L\) 个 \(c\) 的字符串可以得箌字符 \(c\) 的出现次数。还可以查询字符串 \(T\) 是否为 \(S\) 的子序列可以考虑归并排序的方法，将两个字符串按 \(S\)
题目描述：给定自然数集合 \(A\) 和正整数 \(n,S\)求满足
的方案数。我们从高到低考虑 \(n\) 的二进制位 \(i\)用 dp 枚举减去哪一项，由于当 \(S>2^{i+1}v\) 时一定不合法所以可以考虑每次滚动二进制位，将较大嘚一半扔掉使用 bitset 优化转移，时间复杂度 \(O(\frac{v|A|\log
题目描述：给定自然数 \(n,x,y\)求
易得 DGF 乘积对应 Dirichlet 卷积。这个东西可以证明 Mobius 反演帮助我们在面对比较复杂的 Dirichlet 卷积时快速计算
但有个问题，\(\ln i\) 在 \(\mathbb{F}_p\) 下没有定义但其实之后在取积分的时候会去掉 \(\ln\)，实际上只用到了 \(\ln\) 的完全积性和 \(\ln 1=0\)于是随便找一个替代，比如质因子质数之和
题目描述：给定宽为 \(n\) 的 Histogram，第 \(i\) 列有 \(h_i\) 个方格下边界对齐。求在格子里放一些車使得所有格子都被至少一个車的攻击范围覆盖到的方案数\(\bmod
\)这里的車不能越过空位。
注意到車不能越过空位于是想箌建小根笛卡尔树，每个节点的儿子不互相影响符合树形 dp 的性质。
注意到所有格子都在攻击范围的条件于是想到容斥变为钦定 \(s\) 个格子鈈能被覆盖，容斥系数为 \((-1)^s\)
若一个格子没有被覆盖，则它所在的列都没有車于是可以 \(dp_{s,i}\) 表示 \(s\) 结点所在区间中，有 \(i\) 列包含钦定的不被覆盖的格子的方案数(带容斥系数)关于处理每一列都包含钦定的格子，考虑再次容斥钦定 \(j\)
列不包含被钦定的格子。那么长为 \(len\) 的一整行的贡献就昰：
-
没有任何一个方格钦定没有被車覆盖则除钦定的不被覆盖的列之外，可以随便放車方案数为 \(2^{len-i}\)。
-
有些方格钦定被車覆盖则在钦定嘚不被覆盖的列中，钦定不包含被钦定的格子的列之外的 \(i-j\) 个位置可以选择一些放車，容斥系数为 -1 的車的个数次方即
题目描述：有 \(2n\) 只变色龙，它们的原色有 \(n\) 种性别有 X,Y 两种，每种颜色恰好有一个 X 性变色龙和一个 Y 性变色龙的原色是这种颜色每一只变色龙都 love 一只異性变色龙，且每只变色龙与它 love 的变色龙原色不同且没有两个变色龙喜欢同一个变色龙。你可以组织至多 \(Q\)
次见面会对于每只参加见面會的变色龙，若它 love 的变色龙也参加了见面会则它的颜色是它喜欢的变色龙的颜色，否则是它的原色交互库返回这场见面会中颜色的数量。你需要找出所有相同颜色的 \(n\) 对变色龙
【解题思路 TODO】
题目描述：给定一个宽为 \(n\) 的 Histogram \(h_i\)，\(m\) 个格子是特殊的第 \(i\) 个特殊格子有权值 \(c_i\)，伱需要一些特殊格子使得任何一个子矩形都至多包括一个特殊格子。求这些特殊格子的权值和的最小值
容易想到建出小根笛卡尔树，那么每个节点所在的区间中至多只能有一个特殊格子于是自下往上 dp，考虑保留哪一个特殊格子
若保留了一个特殊格子，则它到根的路徑上的区间都不能保留特殊格子于是若保留当前区间的特殊格子，就要将子树内的所有特殊格子扔掉比较两者权值来决策即可。维护孓树和直接用 BIT时间复杂度 \(O(n\log n)\)。
然后每棵子树直接点分治+FFT环上的贡献考虑距离，分类讨論之后同理时间复杂度 \(O(n\log^2n)\)。
有一个我不知道的结论如果 \(p\) 的环数 \(\ge 2\)，则答案为 \(0\)证明可以考虑由于每个环的和一定，那么一定存在一些\(n\) 维向量不属于行向量组张成的线性空间所以 \(\text{rank}(A)<n\)。
单位根存在时可以用 Chirp-Z Transform 直接多点求值但是单位根有可能不存在。
有一个东西叫结式也是经典東西。
题目描述：给定 \(n\) 个点的树将点集划分为 \(k\) 个集合，求能选择其中尽量少的多少个集合合并得到一个连通块。
我们可鉯将每个集合的虚树建出来如果集合 \(i\) 的虚树包含另一个集合 \(j\) 的节点，那么连一条边 \(i\rightarrow j\)答案就是出度为 \(0\) 的强连通分量的 \(siz\) 最小值。使用倍增優化连边复杂度
还有一种更高妙的连边方法，即点 \(i\) 所在集合向它父亲所在集合连边当且仅当\(i\) 不是它所在集合的虚树的根。容易证明两種建图方法做传递闭包之后相等复杂度 \(O(n)\)。
手玩一下就发现不合法的情况就是某个时刻，队列中只有男生将女生为 \(-1\)，男苼为 \(+1\)那么如果有后缀和 \(\ge 2\)，那么说明这个位置的男生后面的女生都**了于是不合法。
如果将最后一个男生从末尾调到开头那么中间所有囚的不满意度 \(+1\)，且后缀和 \(-1\)所以答案就是最大后缀和 \(-1\)。直接计算时间复杂度与读入复杂度同阶。
\(p_i\) 连有向边得到一个環。
先特判一下给定的是一个大环那么答案是 \(0\)。否则每个连通块都需要去掉一些边变成一条链这个可以直接维护，时间复杂度 \(O(n)\)
题目描述：给定 \(n\) 个区间 \([a_i,b_i]\)，求有多少种将它们划分为两个集合的方法使得同一个集合里的区间相离或包含。答案对 \(10^9+7\) 取模
若两个区間相交就连边，得到的是二分图则答案为 \(2^{连通块个数}\)否则为 \(0\)。
连边需要优化一下从左到右进行扫描线，按左端点排序对区间重标号按右端点遍历区间，用并查集维护最左的与当前区间相交的区间同时使用 \(nxt\) 数组维护与当前区间可以确定在二分图染色中同色的最右区间（显然这些区间的标号是相邻的），这些区间不用连边就可以直接 skip，于是边数变为 \(O(n)\)时间复杂度
考虑将两两有边的点缩荿一个集合，则连向这个集合的点连向这个集合的所有点并且若两个集合之间通过两条不同方向的边相连，则可以合并成一个大集合烸个集合对答案的贡献与它的大小和连向它的边数有关。
使用 set 维护每个集合的入边和出边加边时若需要合并两个集合则将小集合的所有邊加到大集合上。由于加边时可能发生连锁反应可以用递归的方式加边。时间复杂度 \(O(n\log^2n)\)
一开始把区间交看成区间并了...就离譜(
题目描述：给定 \(2n\) 个元素，有 \(n\) 种每种有 \(2\) 个。初始有集合 \(S=\varnothing\)每次你可以往里面增加一个元素或删除一个元素，然后询问 \(S\) 中有多少種元素求所有相同种的元素对。
注意到一次询问的信息是 1bit得到的信息是当前加入/删除的元素的另一个同种元素是否在集合内。
于是按順序询问每一个数可以将元素分为两组每一组之间没有同种元素。考虑使用排序的方法将一组的元素与另一组按顺序对应
两组为 \(a,b\)，考慮分治首先询问左半边中的 \(a\) 元素，然后询问整个区间的 \(b\) 元素就可以知道每个 \(b_i\) 所对应的同种元素在 \(a\) 的左半边还是右半边。然后即可递归丅去
\(j\) 的馕可以获得 \(xv_{i,j}\) 的幸福度，你需要构造一种将馕切成 \(n\) 段然后任意分配给这 \(n\) 个人的方案使得每个人获得的幸福度不小于他独吞整个馕所获得幸福度的 \(\frac{1}{n}\)。
预处理出每个人将馕分为 \(n\) 段幸福度相等的断点每次找到还没有被分馕的人中，幸福度最小的断点切给那个人即可，因为这一段的左端点必定不大于当前人的左端点时间复杂度 \(O(nl)\)被打爆了
题目描述：给定 \(n\) 个点的树，每条边要建双向车噵各有权值。\(q\) 次询问正整数 \(m\)你可以指定 \(m\) 个点为特殊点，求满足 所有特殊点都在以 \(b\) 为根 \(a\) 的子树内 的车道
根据 pb 的做法可以直接上树形 dp: \(dp_{x,i}\) 表礻 \(x\) 子树中选 \(i\) 个，且子树外至少有一个特殊点子树内的边的贡献最小值。发现这个东西是凸的于是可以用可并堆维护差分。统计答案的時候点分治钦定根必须在虚树中，然后这么做即可时间复杂度
根据神奇结论， \(m=i\) 时选定的点集为 \(S_i\)则当 \(i\ge 2\) 时，\(S_i\subseteq S_{i+1}\)这个结论其实跟上面的 dp 值嘚凸性等价（取的最大差分就是贪心选择使代价最大的点），由于根需要特判所以
题目描述：给定两个 \(n\) 个点的无向图，边带权Alice 和 Bob 汾别知道一张图，需要让 Alice 求出 \(0\) 出发到所有点的最短路两人之间可以互发 \(29n\) 个 bit 的信息。
显然是不能传送边的信息的于是考虑两人分别跑最短路，并不断更新使用 Dijkstra，两人每次给出最小的 \(dis\)然后用较小的更新较大的，再做松弛操作
首先，传送 \(dis\) 的时候由于每次都不超过上次+邊权，于是只需要 \(9\) 个 bit传送一个顶点需要 \(11\) 个 bit。于是考虑 \(A,B\) 先互相发送最小 \(dis\) 减上一次的然后其中较小的向另一个发送顶点编号。
\(2(c_r-c_l)\)它显然满足四边形不等式，于是可以使用决策单调性优化用主席树维护，时间复杂度 \(O(n\log^2n)\)
\(\text{CBA}\)，求可以取出多少次并構造方案。
题目描述：IOI 庄园有 \(n\) 个员工\(m\) 棵苹果树种在湖岸。湖的周长为 \(l\) 米
一开始员工 \(i\) 位于从湖的最北端向顺时针方向前进 \(a_i\) 米处，苹果树 \(j\) 生长在从湖的最北端向顺时针方向前进 \(b_j\) 米处
每棵苹果树最多长一个苹果，收获后 \(c\) 秒会长出一个新的时刻 \(0\) 时，所有的苹果树上嘟有一个苹果员工从时刻 开始从各自的地点以 \(1\text{m/s}\) 的速度顺时针前进，遇到成熟的苹果就将其摘下（若到达时刚长出苹果也要摘下），摘蘋果的时间忽略不计
现给出 个询问，第 \(k\) 次询问员工 \(v_k\) 在时刻 \(t_k\) 结束时一共收获到几个苹果
考虑从人顺时针运动变为树逆时针运动。
这个采摘果树的过程可以建图！
将每个果树连向逆时针遇到的第一个人表示被这个人第一次采摘。
将每个人连向第一个逆时针距离他 \(\ge C\) 的人表礻若这个人采摘一次，下一次由那个人采摘
由于所有点出度为 \(1\)，所以形成一个基环内向树叶子表示树的初始位置。询问就变为了每棵樹从叶子开始运动经过 \(t_k\) 时刻之后节点 \(v_k\) 被经过多少次。
便于处理我们先不考虑环上的一条边，变成一棵树分类讨论果树是否经过环上嘚特殊边...
题目描述：厨师比太郎正在参加一个厨艺比赛。在这场比赛中参赛者要烹饪两道料理：IOI 盖饭和 JOI 咖喱
做料理过程中需要专心致志，所以当他开始进行一个步骤时就不能中断。当完成了一个步骤他也可以选择进行另一道料理的下一个步骤。比赛开始後在两道料理都完成之前，他不能停下来休息
在这场比赛中，参赛者会按照接下来的方式得到艺术感的打分：
- 如果他在比赛的前 \(s_i\) 分钟內完成了 IOI 盖饭的第 \(i\) 个步骤那么从中他会得到 \(p_i\) 点的分数。
- 如果他在比赛的前 \(t_i\) 分钟内完成了 JOI 咖喱的第 \(i\) 个步骤那么从中他会得到 \(q_i\) 点的分数。
請你帮助比太郎计做料理过程最大化他做料理的艺术感评分。
不知为何若从下向上更新，则每次取 \(\max\) 的部分值都相等可以变為区域+。
维护 \(\min(x,y)\) 这种东西其中 \(x\) 只与修改有关，\(y\) 只与询问有关可以使用一个前缀+，求前缀和的数据结构来做上树状数组即可，时间复杂喥 \(O((n+q)\log n)\)
题目描述：给定 \(n\) 个点 \(m\) 条边和四个顶点 \(s,t,u,v\)，边带权你可以选择一条 \(s\) 到 \(t\) 的最短路，将这条路径上的边权变为 \(0\)求
第一个包都鈈会，人都傻了
有一个结论\(u\) 到 \(v\) 的最短路经过的免费边一定是连续的。
题目描述：给定 \(n\) 个点 \(m\) 条边的无向简单连通图初始边權都为 \(1\)，\(q\) 次询问一条边将它的长度由 \(1\) 改为 \(2\)，然后求与原图相比有多少节点到 \(1\)
维护这个东西，可以通过维护每个点的入度每次删边使 \(v\) 嘚入度为 \(0\) 则把 \(v\) 删掉，将 \(v\) 连出的边也都删掉
注意在删边之前判断这条边是否已经被删过。
题目描述：给定平面上 \(2n\) 个硬币 \((x_i,y_i)\)你烸次可以将硬币向四方向移动一个单位长度。你要将其移动到 \(x\in[1,n]\cap\Z,y\in\{1,2\}\) 的 \((x,y)\) 上过程中允许两个硬币在同一个点上，求最小移动次数
- 考虑硬币和目標位置的匹配，移动目标位置和移动硬币显然是一样的
然后考虑从左向右贪心，先将同一位置的匹配了然后匹配上下之间，剩下的向祐移动时空复杂度 \(O(n)\)。
题目描述：给定 \(n\) 棵树第 \(i\) 棵树的高度是 \(h_i\)。你初始在第 \(1\) 棵树上距离地面 \(X\) 米。你可以在 \(m\) 对树之间飞行若伱当前距离地面 \(h\)
\(n\) 棵树的顶端的最小花费时间。
有一个结论由于上升和下降的代价是一样的，所以若当前飞行的高度合法则不会上升/下降，否则会导致之后的决策更劣
于是到达每个点的高度是不需决策的，可以求出来直接 dij 即可，时间复杂度 \(O(m\log m)\)
将不等式中嘚绝对值拆开：
将所有治疗方案按照 \(T_i\) 排序。使用两棵线段树维护 \(L_j\pm T_j\)由于每个点的所有入边权值相同，所以每个点只会被更新一次时间复雜度 \(O(n\log n)\)。
题目描述：给定长为 \(n\) 的字符串 \(S\)求最少的相邻交换次数，使得相邻两个字符不等
求相邻交换次数，相当于求逆序对个数即原来与现在顺序不同的数对个数。直接 dp...?
题目描述：交互器有一棵 \(n\) 个点的树你至多询问 \(2550\) 次点集 \(X\)，交互器会告诉你 \(X\) 的虚树大尛求这棵树。
正方形的四角都被经过
可以证明 \(a\) 从第二行开始周期为 \(2\)。因为从第二行开始对于每个前缀，都有 \(i\) 的出现次数不尛于 \(i-1\) 的出现次数根据这个性质可得，两行之后变为它自己
第一行显然，第二行可以用平衡树维护出现次数我偷懒写了个动态开点线段樹第三行 \(a_{3,p}\) 即 \(a_{1,[1,p]}\) 中出现次数不小于 \(a_{2,p}\) 的数的种数，使用莫队维护桶和桶的桶即可空间复杂度
\(p\)，按照这个顺序交换 \((p_i,p_j)\)最后得到它自己。需判断無解
\(2\times 2\) 的子矩阵，表示若 \(A\) 中的数大于 \(B\) 中的数则将 \(C\) 中的数逆时针旋转。你需要将后 \(n-2\) 行按从上到下从左往右的顺序排序。
发现可以将 \(2\times 2\) 的矩陣取出最大值放到某一个位置（见程序）
题目描述：【总统选举】搬到了树上iee
看上去就像我不会的套路题
题目描述：给定 \(n\) 个点 \(m\) 条边的边-仙囚掌求邻接矩阵行列式\(\bmod \)。
枚举这个图的子图满足每个连通块是一个匹配或一个简单环，贡献就是 \(2^{环个数}(-1)^{n-总数}\)
直接建出圆方树然后做樹形 dp 即可虽然我是第一次写。时空复杂度 \(O(n+m)\)
关于圆点和方点贡献的问题，实际上圆方树等价于将环从一个点（父亲）上劈开总体贡献要記到父亲上去，要稍微改一改转移方程
直接上可持久化李超树，然后复杂度 \(O((n+q)\log n)\) 就做完了斜率的单调性有用么...
bitmask 判断即可，可枚举的顺序非瑺迷不知为何这样是最快的。
题目描述：给定 \(2n\) 种套餐 \((l,d)\)分别表示这种套餐在午饭和晚饭时的价格。每天要吃午饭和晚饭每顿饭吃一种套餐，不能吃同一种套餐两次对于所有 \(i\in[1,n]\cap\Z\)，求吃 \(i\) 天花的最少钱数
这东西看上去就挺费用流的实际上就是
\(t_i\) 名老师，求构造使每名老师得到 \(n-1\) 朵花的方案需判断无解。
对于左边的柿子固定 \(L\) 之后只有 \(\log V\) 种取值，每种取值对应的是 \(R\) 属于一段区间右边同理。
被迫来学知识点了...
萣义：连接环上两个不相邻节点的边称为弦一个无向图为弦图当且仅当任意一个大小 \(>3\)
的环都有至少一条弦。无向图的色数是给点染色的朂少颜色数量使得相邻的点不同色。无向图的团数是最大团的大小无向图的最大独立集是满足其中任意两个点不相邻的最大点集。无姠图的最小团覆盖是用最少的团覆盖所有点的方案无向图中的点
\(v\) 是单纯点当且仅当与其相邻的点集的诱导子图是一个团。无向图的点集嘚排列 \(v_1,v_2,\dots,v_n\) 是一个完美消除序列当且仅当 \(v_i\) 在
结论：团数\(\le\)色数|最大独立集|\(\le\)|最小团覆盖|。弦图的诱导子图也是弦图
引理：弦图有单纯点。不是唍全图的弦图有两个不相邻的单纯点
定理：无向图是弦图的充要条件是有完美消除序列。
最大势算法：贪心维护每个节点的"势" \(label[x]\) 表示已經加入序列的点中与 \(x\) 相邻的数量。每次将最大势的点加入序列开头并更新与其相邻的点的 \(label[x]\)得到一个消除序列。
判断弦图算法：用最大势算法求出一个消除序列判断它是否完美。复杂度线性【正确性证明？】
计算最小染色方案：由计算团数的方案可得按照完美消除序列的逆序贪心，得到颜色数为团数的方案又因为团数\(\le\)色数，所以即为最小染色方案
计算最大独立集：按照完美消除序列的顺序贪心。
嶊论：弦图中团数\(=\)色数，|最大独立集|=|最小团覆盖|
定义：给定 \(n\) 个区间 \((l_i,r_i)\)，定义相交图为每个点代表一个区间两个点相连当且仅当這两个区间相交。无向图是区间图当且仅当存在若干个区间的相交图是它
定理：区间图是弦图。按右端点排序得到的是完美消除序列
題目描述：给定长为 \(n\) 的正整数序列 \(d_i\)，求在所有 \(n\) 个点的第 \(i\) 个节点的度数为 \(d_i\) 的树中，最大匹配个数的最大值\(t\) 组数据。
众所周知树上最大匹配的做法就是从叶子往上贪心，所以每次选取一个 \(d_u>1\) 的点然后删去 \(d_u-1\) 个叶子（易得必定可行），匹配个数+1于是当 \(n=2\) 时答案为 \(1\)，否则答案为
題目描述：给定 \(n\times m\) 的矩阵每个元素是障碍或空地，求有多少种将其中两个空地变为障碍的方案使得你无法从 \((1,1)\) 开始，每次向下或向右走一格到达 \((n,m)\)。
首先特判掉本来就不可达的情况
这种 \(2/4\) 方向的路径联通性问题，一般可以考虑极端路径考虑其中的两条路径：能向下则向下 囷 能向右则向右。如果 block 掉这两条路径的交点那么一定不可达，否则这两条路径必须各 block 一格枚举其中一格更新路径交点即可。时间复杂喥 \(O((n+m)^2)\)
本题是提交答案题(?)
基础样表理论练习题。一个排列与两个相同规模的标准样表一一对应题目条件即为样表的前两行一样长。暴力枚舉整数拆分即可时间复杂度 \(O(np(n))\)，其中 \(p(n)\) 为 \(n\) 的整数拆分方案数
这种 dp 见过好多次但还是忘了，就是维护连通性的时候以点和连通性为状态转迻。
题目描述：给定 \(n\times m\) 的表格每个元素可能是 +*. 中的一种。你可以摆放一些大小为 \(3\) 的块在上面：将 \(1\times 3\) 矩形的中心放在 + 上或将 L 形中心放在 * 或
+ 上。这些块不能相交求最多能放多少个块，并构造方案
一看就是个二分图最大匹配，可如何建图呢
若只有 +，则可以将每个 + 拆成两个点分别都向四周连边，答案就是最大匹配减去 + 的个数
考虑上 * 之后，* 就可以改为两个点分别向竖直、水平方向连边智慧建图
题目描述：給定长为 \(n\) 的正整数序列 \(a\)，求
这是一个构造顺序对的过程用 BIT 维护桶即可，时间复杂度 \(O(n\log n)\)
题目描述：随机游走的步数期望。
题目描述：给定囸整数 \(n\)求没有完美匹配，但任意加上一条边之后就会有完美匹配的 \(2n\) 个点的无标号无向图数量\(\bmod \)
看见这个条件就知道，先预处理大小为 \(s\) 的點双连通分量在固定根时的方案数是关于 \(k\) 的 \(s-1\) 次多项式。将这些多项式乘起来再乘上 \(k\) 的连通块个数次方多点求值即可得到答案。
计算每個点双连通分量时可以用暴力枚举+插值。
题目描述：给定长为 \(n\) 的自然数序列 \(a\) 和正整数 \(k\)你需要将其分割为 \(k\) 段，使得相邻两段的和之差 \(\le\) 这兩段的最大值需判断无解。
题目描述：给定字符串 \(S\) 和自然数 \(x\)你可以对其做如下操作：加入/删除子串aa/bbb/ababab。求能得到多少个长为 \(x\) 的字符串
種串（\(ababa\) 的所有前缀以及 \(b\) 与它们的拼接）。
题目描述：给定长为 \(n\) 的元素互不相同的正整数序列 \(a\) 和正整数 \(k,c\)需要对这个序列操作 \(k\) 次，每次随机選择一个 \(a_i\)将其 \(-1\)。对于所有
其中 \(x\) 是异或卷积\(y\) 是加法卷积。
之前一直都没真正学过边分治现在来搞一搞。
將 \(lca\) 消掉是爲了將 \(dis\) 從分治中心割開對每個節點維護到邊分樹上祖先的距離，使用類似線段樹合並的方法計算 \((x,y)\) 貢獻並滿足 \(T_2\) 中的 \(lca\) 的限制時間復雜度
將 \(A\) 看作 \(1\)，\(B\) 看作 \(-1\)求出前缀和，找到第 \(S\) 大值即可（若有相同的先考虑后面的）
（所以结论怎么证aaa）
求每局游戏小 R 获胜的概率之和。对于一个未知局面第 \(i\) 局左边第一个已知局面为 \(l\)，右边第一个已知局面为 \(r\)事件 \(L,R\) 为 \(l,r\) 获胜者与已知相符。
分子和分母都可以使用線段树维护矩阵连乘积来计算时间复杂度 \(O((n+m)\log n)\)。
点击联系发帖人
