无限纸牌游戏题目描述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}\)表示长度前缀和）然后发现括号

本页面将简要介绍数位DP。引入数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是0~9，其他进制可类

\[\large\mathit{Some~deserts~on~this~planet~were~oceans~once}\]\[\large\mathit{Somewhere~shrouded~by~the~night,~the~sun~will~shine}\]\[\large\mathit{Sometime

\[\mathit{Switch~on~the~power~line}\]\[\mathit{Remember~to~put~on}\]\[\mathit{PROTECTION}\]\[\mathit{Lay~down~your~pieces}\]\[\mathit{And~let~^\primes~beg