[JOI2022Final]让我们赢得选举(Let'sWintheElection)/選挙で勝とう(Let'sWintheElection)首先由\[\min\left(\fracab,\fraccd\right)\le\frac{a+c}{b+d}\le\max\left(\fracab,\fraccd\right)\]得出，集中力量办大事，得到的支持者一定要和本人在同一州进行演讲。

NOIP模拟18最近老是犯唐，这次也是。T1图容易得到暴力代码：namespaces1{ boolsta[MAXN*MAXN]; boolS[MAXN],T[MAXN]; strings; intans; intmain(){cin>>n>>m; for(inti=1;i<=m;++i){ cin>>s; memset(S,0,sizeof(bool)*(n+5)); memset(T,

[NOIP2016普及组]回文日期题目背景NOIP2016普及组T2题目描述在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。牛牛习惯用888位数字表示一

提高组数学专题1T1[CF1909F1]SmallPermutationProblem(EasyVersion)将排列的每项\(p_i\)记成\((i,p_i)\)的形式，则问题转化为：在一个\(n\timesn\)的棋盘上放置\(n\)个車，使这些車互不攻击，且满足题目中\(a\)的限制。题目中\(a_i\)的限制实际上就是限制了左上角

[CF1935E]DistanceLearningCoursesinMAC难度正常的一道题。首先我们发现“挑选若干个区间”就是一句废话，因为按位或只会贡献答案而不会减小答案。所以我们需要在\([L,R]\)的每个区间都挑一个数，使得最终的按位或最大。想办法让尽可能多的二进制位都变成\(1\)，且越是高

P2123皇后游戏/[USACO12JAN]MountainClimbingS/P1248加工生产调度先来看P2123。我们把这个特别重要的公式打出来：\[c_{i}=\begin{cases}a_{1}+b_{1}&,i=1\\\displaystyle\max\left\{c_{i-1},\sum_{j=1}^{i}a_{j}\right\}+b_{i}&,2\leqi\leqn\end{

T3[ABC213G]Connectivity2题意：给定一张无向图\(G\)，将其删去\(0\) 条及以上的边构成一张新图，求对于所有点\(k\in(1,n]\)，使\(k\) 与\(1\) 连通的新图的个数。比较套路的一道状压DP。尽管刚开始思考毫无头绪。Step1.令\(f_S\)表示点集为\(S\)的连通子图的个数，\(

T2[TJOI2019]甲苯先生的字符串矩阵乘法优化DP，所以一般来说这种DP都不怎么难。30pts的DP是裸的：设\(f_{i,j}\)为前\(i\)位、最后一位是\(j\)的方案数，则有转移方程：\[f_{i,j}=\sum_{k=0}^{25}f_{i-1,k}\landk\nej\]想要矩阵优化，我们想到构造答案矩阵：\[\mathit{an

T7[USACO23FEB]HungryCowP这题就比较正常了，蓝紫之间的水平。我们发现Bessie能活\(10^{14}\)天（，导致我们不好直接按照值域来维护。发现给某一天送干草，影响到的是后面很多天，这是个区间问题。所以考虑动态开点线段树。线段树的每个节点维护\(\mathit{ans},\mathit{cnt},\ma

CSP-S模拟赛35rnk14，\(45+45+15+18=123\)。T1送花愚蠢题。看到区间想到线段树，预处理出每个位置的颜色上一次出现的位置，记为\(\mathit{las}_i\)。从左到右扫右端点，给\([\max(1,\mathit{las}_{\mathit{las}_i}),\mathit{las}_i]\)减去\(d(c_i)\)，给\((\mathit{las}_i,i]\)

加塞rnk7，\(100+30+10+15=155\)。题目来源：2022牛客OI赛前集训营-提高组（第三场）T1一般图最小匹配说的很复杂，实际水题。就是从\(n\)个数中选\(2m\)个数，两个两个求差后，求这个差的和的最小值。显然排序之后求差是最小的，但显然不能直接贪心，考虑DP。先排序，然后设\(\mathit

T1[USACO22DEC]BreakdownP比较显然的一点是，一次加一条边/一次删一条边，显然转化，这是显然的一条套路。这题的\(K\le8\)，很有意思的数据范围，然后调用我们聪明的人类大脑得知需要用到折半搜索。所以我们只考虑\(K\le4\)的情况，令\(\mathit{st}\)表示折半搜索中考虑的起点。维

无限纸牌游戏题目描述Monocarp和Bicarp正在玩一个纸牌游戏。每张牌都有两个参数：攻击值和防御值。如果一张牌$s$的攻击值严格大于$t$的防御值，那么这张牌$s$就能打败另一张牌$t$。Monocarp有$n$张牌，其中第\(i\)张牌的攻击值为$\mathit{ax}_i$，防御值

注意：本文只针对无向图。对于无向图，显然不能只考虑简单的连通关系，应该研究一些更强的连通关系：双连通。前置芝士点双连通分量：若一个连通分量任意两点间都存在至少两条不经过（除起点和终点外）相同点的路径，我们就称这个连通分量为点双连通分量。边双连通分量：同理，若一个连通分量

前言为什么用dfs序求LCA而不用欧拉序？帅常数小，也就一半好玩反正没什么正经理由。正文定义dfs序是指对树进行深度优先遍历后得到的节点序列。\(\mathit{dfn}_i\)是节点\(i\)在dfs序中的位置（从\(0\)或\(1\)开始无影响）。LCA是最近公共祖先。深度\(\ma

前言为什么用dfs序求LCA而不用欧拉序？帅常数小，也就一半好玩反正没什么正经理由。正文定义dfs序是指对树进行深度优先遍历后得到的节点序列。\(\mathit{dfn}_i\)是节点\(i\)在dfs序中的位置（从\(0\)或\(1\)开始无影响）。LCA是最近公共祖先。深度\(\ma

20240320每日一题题解Problem阿克曼（Ackermann）函数\(A(m,n)\)中，\(m,n\)定义域是非负整数（\(m\le3\)，\(n\le10\)），函数值定义为：\(\mathit{akm}(m,n)=n+1\)；（\(m=0\)时）。\(\mathit{akm}(m,n)=\mathit{akm}(m-1,1)\)；（\(m>0\)、\(n=0\)时）。\(\mathit{akm}(m,n)=

分析考虑区间DP。定义状态函数\(\mathit{f}_{l,r,1/0}\)表示在\(P_l,P_{l+1},\dots,P_r\)这些点中，\(P_l\)是或不是唯一（子）树根时的答案。对于\(\mathit{f}_{l,r,1}\)，\(P_l\)的第一个儿子一定是\(P_{l+1}\)。所以有：\(f_{l,r,1}=f_{l+1,r,1/0}\)（\(P_{l+1}\)是或不是\(P

感谢@\(\color{#AEF}{\texttt{CelestialCyan}}\)大神对我的骚扰帮助。分析一眼DP。对于求最大满足条件区间数，我们定义状态函数\(\mathit{f}_{i}\)表示在第\(1\)到\(i\)个区间中选择，且必选第\(i\)个区间能够得到的最大长度。有转移方程：\(\mathit{f}_{i}=\max\{f[j]|

分析一眼莫队（虽然通过这题的范围显然看出出题人用的不是莫队）。我们定义\(\mathit{cnt}_{i}\)表示数字\(i\)出现的次数。在指针的拓展增加\(x\)时，若有\(\mathit{cnt}_{x}+1=1\)，则表示在在这个区间里，\(x\)是第一次出现的，我们可以将答案加\(1\)；在指针的收缩减去\(x\)时，

分析一道差分约束题。我们令\(\mathit{sum}_{i}\)表示\(1\)到\(i\)中，\(1\)的数量，根据题意可得：\(\mathit{sum}_{l_i-1}+x_i\le\mathit{sum}_{r_i}\)\(\mathit{sum}_{l+1}+(-1)\le\mathit{sum}_{l}\)\(\mathit{sum}_{l}+0\le\mathit{sum}_{l+1}\)因为我们要尽

分析线段树模板题。一眼DP。定义状态函数\(\mathit{f}_i\)表示前\(i\)个数中，必选\(\mathit{A}_i\)时\(B\)的最大长度。则有转移方程：\(\mathit{f}_i=\max\{f_j|((1\lej\lei-1)\land(-k\leA_i-A_j\lek))\}+1\)。答案就是\(\max\limits_{i=1}^{n}\mathit{f}_i

分析分块。我们定义\(\mathit{cnt}_i\)表示房子\(i\)是否出现过，\(\mathit{sum}_i\)表示在第\(i\)个块内没有被摧毁的房子数量，维护的房子是\((i-1)\timesS-1\)到\(i\timesS\)，其中\(S=\sqrt{n}\)也就是块长。操作\(1\)。写一个栈，根据后进先出的特点，讲摧毁的房子

分析用势能线段树。对于一段数字\(a_l\)到\(a_r\)，每次全部除以一个大于\(1\)的数，不难发现最多除以\(\logx\)次就会使\(a_l\)到\(a_r\)全部变成\(0\)，其中\(x\)是区间最大值。所以，在没有操作\(2\)的情况下，我们可以在每次操作\(1\)的时候都单点修改，只要在某个

分析没脑子的题目。一眼换根DP。定义\(\mathit{f}_{i}\)表示\(i\)到\(i\)为根子树中某一个节点的距离最大值；\(\mathit{g}_{i}\)表示\(i\)经过其父节点到某个节点的距离最大值。那答案就是\(\max(\mathit{f}_i,\mathit{g}_i)\)。考虑转移。\(\mathit{f}_i\)的转移很