写一篇不需要转化原图的题解。 直接根据数字三角形的思路，原图的结构模拟这一过程 dp 即可，注意我们 dp 的过程可以分为下面三段： 上图是我自己画的。 第一部分是一个裸的数字三角形，注意这里每一行可以通过上一行和上两行转移过来即可。图中的数字表示行号。 第二部分是一个 n−1,nn-1,nn−1,n 交替的结构，第三部分是一个倒着的数字三角形，根据图即可观察得出转移方程： 第一部分：a[i][j]←max⁡(a[i−2][j−1],max⁡(a[i−1][j−1],a[i−1][j]))a[i][j] \leftarrow \max(a[i - 2][j - 1], \max(a[i - ...

考虑把逃亡的过程分成三段： 在第一行 1→2→3→⋯→i1\rightarrow2\rightarrow3\rightarrow\cdots\rightarrow i1→2→3→⋯→i 在第二行 i→⋯→ji\rightarrow\cdots\rightarrow ji→⋯→j 在第三行 j→⋯→nj\rightarrow\cdots\rightarrow nj→⋯→n 然后顺理成章地想到前缀和一下，推一推式子： 假设第一行前缀和 s1i=s1i−1+a1,is1_i=s1_{i-1}+a_{1,i}s1i​=s1i−1​+a1,i​ 假设第二行前缀和 s2i=s2i−1+a2,is2_...

接着上一篇题解的分析过程，我们还是考虑把操作离线下来看看怎么搞一搞。 注意到我们可以更改排序的 cmp 顺序，原来是从小权值到大权值，这是为了方便进行区间推平。 现在我们换过来，从大权值到小权值，这样做的好处就是保证每个位置至多被修改一次，链表维护一下下一个被修改的位置就好了。 时间复杂度 O(n)O(n)O(n)。 #include<cstdio> #include<algorithm> #define int long long int init(){ char c = getchar(); int x = 0, f = 1; for (; c < '0...

每个位置有很多种放字符的方法，把初始的字符也离线下来，同时作为操作一起排序。 考虑到不管什么位置，我只要排过一遍序，后来者一定比先覆盖上去的严格不劣，所以直接进行区间覆盖单点查询即可。 代码实现细节的话也没啥好说的，就是无脑堆板子就好了。 时间复杂度 O(nlog⁡n)O(n\log n)O(nlogn)。 赛时的话，正好昨天白天刚做过一道类似的题，就直接把区间修改单点查询的板子复制过来用了，好像也是有些同学罚时比我高的原因（？ #include<cstdio> #include<algorithm> #define int long long int init(){ ...

分析 首先考虑 m=2m=2m=2 是平凡的情况。 每次物品分成 m+1=3m+1=3m+1=3 堆，最劣状态时一定有：每次目标物品出在最大的一堆，所以平均分，并上取整。 所以 nnn 下降的方式即为 ⌈⌈⌈⌈nm+1⌉m+1⌉m+1⌉m+1⌉⋯\left\lceil\dfrac{\left\lceil\dfrac{\left\lceil\dfrac{\left\lceil\dfrac{n}{m+1}\right\rceil}{m+1}\right\rceil}{m+1}\right\rceil}{m+1}\right\rceil\cdots⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢...

喵喵喵~

题意：对于一个保证 ∑i=1nai=0\sum\limits_{i=1}^{n} a_i=0i=1∑n​ai​=0 的序列 {an}\{a_n\}{an​}，求划分出的最大段数使得每一段区间和均为 000。 考虑前缀和，对于一个区间 [l,r][l,r][l,r]，如果 sl−1=srs_{l-1}=s_rsl−1​=sr​ 代表区间和为 000： sl−1=a1+a2+⋯+al−1s_{l-1}=a_1+a_2+\cdots+a_{l-1}sl−1​=a1​+a2​+⋯+al−1​ sr=a1+a2+⋯+ars_{r}=a_1+a_2+\cdots+a_{r}sr​=a1​+a2​+⋯+ar...

先引用一段百度百科对哈夫曼树的介绍： 在计算机数据处理中，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 据此我们可以知道，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码 可以使得我们对字符的编码的 字符串的平均长度、期望值降低。 事实上根据本题样例，手玩一下也能得到类似的结论：如果某个字符老是出现，那么它一定不能用太长的编码表示，否则我们的消耗实在太高了。 ...

首先是两个众所周知的结论： 杨辉三角代表了组合数，而杨辉三角中第 nnn 行就是 C(n−1,k)C(n-1,k)C(n−1,k) 其中 k∈[0,n−1]k\in[0,n-1]k∈[0,n−1]，这 nnn 个数。 另外一个就是组合数的公式： C(n,m)=n!m!(n−m)!C(n,m)=\dfrac{n!}{m!(n-m)!}C(n,m)=m!(n−m)!n!​ 有了这两个结论，再一看数据范围 n≤106n\le10^6n≤106，一个合理的 O(n)O(n)O(n) 做法就随之而生。 下面介绍一下【模逆元】的相关知识。 求阶乘逆元，线性时间内算出 1!∼n!mod  P1!\sim n...

对于一个数 ggg，最大的自然数 kkk 满足 gmod  2k=0g\mod 2^k=0gmod2k=0，就是找 ggg 包含质因子 222 的个数。 那么如果是一些数 aia_iai​ 乘起来得到 ggg 呢？ 实际上也是一样的，分别统计它们包含的质因子 222 的个数，加起来就好了。 考虑证明：对于两个数 x,yx,yx,y，如果 p,qp,qp,q 分别是最大的 p,qp,qp,q 满足 xmod  2p=0,ymod  2q=0x\mod 2^p=0,y\mod 2^q=0xmod2p=0,ymod2q=0： 那么 p+qp+qp+q 一定是最大的数，满足 x⋅ymod  2p+q=...

呼，剩下两个题实在是知识点超过我的能力范围了……等学到了再补吧……

首先扔一个结论：记最终答案是 ansansans，另外 S(n,m)S(n,m)S(n,m) 表示前 nnn 个 自然数 的 mmm 次幂和： S(n,m)=∑i=0n−1imans=n−S(n,m+1)S(n,m)\begin{aligned}S(n,m)&=\sum_{i=0}^{n-1}i^m\\ans&=n-\dfrac{S(n,m+1)}{S(n,m)}\end{aligned}S(n,m)ans​=i=0∑n−1​im=n−S(n,m)S(n,m+1)​​ 考虑如何计算它：观察到 m≤5000m\le5000m≤5000，可以考虑拉格朗日插值（一个 mmm 次幂和的...

错题都被补掉咯 ~

一道模拟题。 模拟题重在如何实现，接下来挑出几个难以实现的地方说一说： 判断死活。 对于一块棋，有「气」就能活，没有「气」就会死。下面的 bool live(int, int, char) 处理了这个过程： 从一块棋的某个点开始找联通快，只有与自己相同的点才能相连。 另外，如果超出边界，按照围棋规则不算「气」；如果碰到不同色棋子，按照围棋规则同样也不算「气」。 如果碰到 . 就代表找到了至少一口气，就是暂时活棋。 落子。 考虑到围棋还有一个落子问题，也就是说不一定是落子之后自己没有「气」就会死，而是对方有「气」并且自己没有才会死。 这里采用的判断方法也很巧妙： 首先落下这颗子； ...