注意原图上点的编号和dfn需不要搞反。样例太水了，我 $mp$ 数组和 $dfn$ 数组搞反了还能过。具体看代码。 ```cpp #include using namespace std; typedef long long ll; const ll mod=998244353,N=5e4+10; ll n,m,k,t…

不要像我一样傻，写了个区间赋值线段树...这题是区间加。

尽量吃 $a_{i+1}$，不够吃就吃 $a_i$。 记得 $a_{i+1}$ 不够吃要归零。 ```cpp ll cur=max(0ll,a[i]+a[i+1]-x); ans+=cur; if(a[i+1]>=cur)a[i+1]-=cur; else cur-=a[i+1],a[i+1]=0,a[i]-=cur;…

- 对于 $a_i<0$ 要把 $a_i$ 取反。 - 算出超速区间 $[l,r]$ 之后二分出对应的探测器区间 $[x,y]$ 然后一定要判断 $x\leq y$ 才是合法的。 - 排序是按照右端点排。 - long double 可能T，double 可能有精度问题。

仔细检查你的排序，不要想我一样写... ```cpp struct N{ ll l,r; friend bool operator<(N a,N b){return a.l==b.l?a.r<b.r:a.l<b.l;} }; ``` 应该是这样： ```cpp struct N{ ll l,r; friend bool…

注意枚举直径的每个点时，循环的终止条件，例如： ```cpp //c,cur是直径两端，f[i]代表i在直径上的前一个点 for(ll i=c;i!=cur;i=f[i]){ //..... } ``` 这样是错的，因为会少枚举到 $cur$ 这个端点。 ```cpp for(ll i=c;;i=f[i]){ //..…

在文章《题解：P13108 [GCJ 2019 #1A] Alien Rhyme》发表评论：

请问tmp有什么用啊？

在文章《题解：P1502 窗口的星星》发表评论：

是的是的，还有一处打错字了，应该是终点线。

```cpp #include using namespace std; typedef long long ll; ll n,m,ans; string s; const ll mod=10007; ll y[1010][1010],h[1010][1010],yu[1010],huo[1010],dp[18][40…

第二位可省略，数组便可少开一维 ```cpp #include using namespace std; typedef long long ll; ll n,ans=-1e18; ll a[110][110],b[110][110],f[1100010]; int main(){ ios::sync_with_std…

记得本题输入是小数

尝试将状态的定义中“最后一个单词的尾字母”改为“最后一个单词是第几个”

无论是dp还是记忆化，都可以尝试一下这种快速的遍历方法，理论上常数是其它做法的 $\frac{1}{4}$。 ```cpp #include using namespace std; typedef long long ll; ll n,ans=2e18; ll a[1010][1010],dp[1100010][23…

P1005 P3847 P12223

**记得将其他类型的变量处处强制转换为int128!**

# P12223题解 **by cwd2023** --- ## 思路： 首先，根据 $n$ 的范围，猜出复杂度大概是 $n^4$ 级别，有根据题意~~和标签~~看出是一道动态规划。 ### 设计状态： 首先，肯定要有子树大小，深度，因为它们分别与答案和判断条件有关。所以设 $f_{i,j}$ 表示有子树（或者就是整棵…

## P1502题解 **by cwd2023** --- ## 思路： 建议做之前先去做[扫描线板子](https://www.luogu.com.cn/problem/P5490)，如果你做过，不难联想到这个算法。回忆板子，我们发现特征是一条线按一个坐标轴扫，矩阵会被分成起始线，重点线，我们要实时更新线段树，查询全…

- 不要信楼下说的 L 作为第二关键字从小到大排序，应该由大到小处理边界重合，先加在减答案可能更大，不然 100->50或60。 - 如果你是复制了扫描线的板子，记得update时r对应的离散化后的值不用-1，因为这题是一个点对应一个离散值： ```cpp upd(1,1,n,ty[l],ty[r],lz); ```…

在讨论《警钟敲爆！》回复：

对了还要注意往上，往下两种转移，i的枚举顺序不同，要保证可以从更新过的转移到未更新的。

1. 如果你是那种f[i][j][0/1/2]的做法，在转移时记得加上**边界判断**，例如从i-1转移过来就要判断i>=2，否则就相当于从0这条横轴，也就是矩阵外面绕路走捷径过来。 2. 最终答案取不到f[n][m][2]因为这样会超出矩阵范围。 3. 记得赋最小初始值，转移时判断前一个状态是否合法。详见代码中的if…

# 多测清空！ > 有一些意想不到的地方也要多测清空，例如你的图。 > 还有更隐蔽的一点就是SPFA的队列，你可能认为while循环会将它清空，但如果你的写法是在while中直接return 1/0 ,while不能进行到底，就要清空（while(q.size()q.pop();）。 ~~以上两点样例均不能hack~~

不要开二维数组，一维才能AC!

### AT_abc405_f 题解 --- by cwd2023 --- 首先，经典地，拆环成链。不难发现，如果一条虚线与一条实线相交，那么在链上他们对应的两条线段相交。 但当两条线段重合时要注意，它们在环上是不相交的，不能计入答案。 所以可以通过树状数组快速求左端点在原始线段两个端点左边，右端点在其两个端点右边的线…

## AT_abc396_f 题解 ### by cwd2023 --- ### 思路： 首先，我们化繁为简，先正常求一遍逆序对数量，再枚举 $k$，想办法快速转移。 由于 $A$ 数组中的值每次会对 $m$ 取模，所以其中的元素是周期性的，当元素 $a_i+k$ 过大以至于大于等于 $m$，就会发生一些很神奇的变化了…

在文章《题解：AT_abc395_f [ABC395F] Smooth Occlusion》发表评论：

图解证明（其中一种情况）：https://www.tldraw.com/f/9D1VwtlmI7CedB8rcgsNW?d=v203.429.1914.1127.page

在文章《题解：AT_abc395_f [ABC395F] Smooth Occlusion》发表评论：

最初，让 u=d=∞ 对 i=1,2,…,N 重复以下步骤 更新为 ： u←min{u+X,U i },d←min{d+X,D i​ }

在文章《题解：AT_abc395_f [ABC395F] Smooth Occlusion》发表评论：

一旦找到这个值，就可以找到 H 的最大可能值 imin (u i +d i ) 。考虑到解决决策问题的算法管理的是 (H−d,u) 对而不是 (L,R) ，我们可以通过下面的算法找到 u i,d i。

在文章《题解：AT_abc395_f [ABC395F] Smooth Occlusion》发表评论：

观察结果表明，如果将 H 稍微变小，每个区间的下端也会减少相同的数量。 更严格地说，可以证明在第 i 次操作结束时，某个整数 (L,R)=(H−d i ,u i) 的列 ((u i,d i​)) i=1,2,…,N有 2 对(如果此时区间不为空)。

在文章《题解：AT_abc395_f [ABC395F] Smooth Occlusion》发表评论：

对于这种算法，请考虑当移动 H 时，每一步中 [L,R] 的值是如何变化的。

在文章《题解：AT_abc395_f [ABC395F] Smooth Occlusion》发表评论：

如果不为空，更新 L,R 使 [L,R]=I 为空。 如果过程结束到 i=N ，则存在满足条件的切割方法。