前置知识：2-SAT题意[XIXOpenCup,GrandPrixofKorea]Dev,PleaseAddThis!在一张网格上有以下几种物品：空地（.）墙（#）星星（*）一个球（O）现在你要玩一个游戏。你可以让球朝上下左右某一个方向移动，但是一旦移动就必须走到底，也就是说直到前面是墙或者边界才能停。另外，如果你走

Link。考虑次小生成树的大小，显然如果加了一条边后再删一条边，删的边权值一定要严格小于加的边，所以就求出所有加的边和删的边权值相同可以加的边数。为何不考虑加的边权值小于删的边？如果存在这种边，显然最小生成树不优。Link。答案显然能取到下限，因为有\(t_j<a_{s_j}\)。Link

[ABC274G]SecurityCamera3给你一个\(n\timesm\)的网格图，\(n,m\le300\)，每个空地上可以放任意多个任意方向的监控，一个监控视野覆盖对应方向最长连续空地，问监控覆盖所有空地最小化监控数量。对于一个极长的连续空地，我们一定是在边边放置一个监控，而且两边是一样的，因此我们只

\(A.\)考虑合法的b序列长什么样，我们倒着做，把+变成-，在所有\(b_{i}>b_{i+1}\)的\(i\)操作\(b_{i}-b_{i+1}\)次前缀，后缀同理，最终要求b全部相等非负即满足条件。考虑前缀(后缀)操作本质是从某个地方开始后下降次数，那么我们设\(b_{0}=b_{n+1}=inf\)，最终只需要判断\(\sum|b_{i}-b_{i+1}

题目链接：镜中的昆虫经典题了，我们首先回顾下颜色数的常见做法统计：对每个位置维护一个\(pre_i\)，表示与当前位置相同的颜色上一次出现位置。那么我们分讨一下。查询\([l,r]\)得到颜色数，对于\(pre_i<l\)的\(i\)点，显然它就是这个区间内\(a_i\)对应颜色出现的第一个位置，我们

here首先根据题意，我们不难有数字是连续的这种感悟。而且限制是值域上的，从下标入手发现难以突破，便从值域上入手。从小到大考虑每个数字，然后dp，可以参考这篇题解。至于方案的输出，有两种情况。只有自己\(i\)和\(i-1\)，直接输出即可。有自己和\(i-1\)的环，定义print输出环，且最大

分析先对每一列都做DP寻找极长单调不降区间，能够得到若干极长单调不降区间，只要询问的区间是这些区间的子区间，那么说明在这个区间内必有一列的这个区间是单调不降的。思考如何快速判断子区间。用\(f_{x}\)表示以\(x\)为所有左端点为\(x\)的区间的右端点最大值，那么对于

概念以下看似毫不相关的问题均属于Catalan数列：\(n\)个节点构成的无标号、区分左右儿子的二叉树数量为\(Cat_n\)\(n\)个节点构成的无标号、区分儿子的有根树数量为\(Cat_{n-1}\)\(n\)个左括号与\(n\)个右括号组成的合法序列有\(Cat_n\)种\(n\)个元素按照大小进

「JOISC2020Day2」遗迹题目大意：给定长度为\(2n\)的序列\(h_i\)，满足对于所有\(k\in[1,n]\)，均存在两个\(i\)满足\(h_i=k\)，定义“地震”为如下操作：对于所有\(i\in[1,2n]\)，当且仅当\(h_i>0\)且对于所有\(j>i\)都有\(h_i\neqh_i\)时，\(h_i\leftarrowh

ABC297Ex-DiffAdjacent题目链接。\(\text{difficulty}=4.5,3\)。\(\text{tags}=多项式,生成函数,容斥\)。首先如果直接计数不相邻的那么至少需要记录当前的和以及最后一个数是什么，复杂度无法接受。那么考虑容斥。接下来对于一个固定的序列\(a_1,a_2,\dots,a_m\)考虑。

u群看到的一道题挺好玩的，写篇博客参考资料：20210620省队互测-qwaszx题解,qwaszx;某篇没有链接的知乎回答,EI,Rebelz.定义一个\(1,2,\cdots,n\)的排列是好的，当

上午题题目：AGC058D虑定义一个连续的\(abc,bca,cab\)是极长的上升子段，考虑若干个极长的上升子段一定是不交的，所以这么定义没有问题。考虑容斥，顷定有\(k\)个极长上

思路考虑\(DP\)转移，设\(F[i]\)表示长度为\(i\)序列的期望分数。得到如下转移：\(F[i]=(F[i-1]-A[i-1]+A[i])p_i+F[i-1](1-p_i)\)其中\(A[i]\)的意义是：以\(i\)