[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\)的转移很

分析接着这个说。现在我们需要优化\(\mathit{nxt}_{i}\)。重新定义一下，\(\mathit{nxt}_{i,j}\)表示在后\(i\)个数中，\(j\)第一次出现的位置，且\([i+1,\mathit{nxt}_{i+1,a_i}-1]\)是一个合法串。这玩意很像一个DP，所以完全可以按照DP的转移思路转移：\(\mathit{nxt}_{i,j}=

什么是强化学习（reinforcementlearning）?假设一个场景，一个智能体(agent)和环境（env）交互，智能体基于当前环境\(S_t\)每产生一个动作\(A_t\)，环境便给它一个反馈，也被称为奖励(reward)\(R_{t+1}\),随后，智能体的状态变为\(S_{t+1}\).这样生成了一系列状态\(S_t,A_t,R_{t+1},S_{t+1

[NOIP1999普及组]导弹拦截题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套

首先先写dp方程非常简单\(\mathit{f}_{i}=\min(\mathit{f}_{j}+(\mathit{c}_{i}+i-j-1-L-\mathit{c}_{j})^2)\)(其中\(\mathit{c}_{i}\)表示长度前缀和）然后发现括号