小琢卷不动

分类

未归档(10) 题解(72)

/ 注册

全部文章（共80篇）

题解 | #简单题#

作为小白我们虽然看不懂第一个式子到底等于什么，但是也可以做这道题。考虑第二个式子和第三个式子，实际上就可以化成 β×θα\beta\times\theta^{\alpha}β×θα 的形式。然后把样例的两个值代入， {196×θ5=29089.060×θ3=1205.1322\begin{cas...

C++

2021-11-23

1 511

题解 | #小䓤的质因数#

D 简单的概率期望题。考虑把问题抽象成有 nnn 个牌堆，第 iii 个牌堆有 cic_ici 张牌，每次随机两个牌堆转移一张牌 i→ji\rightarrow ji→j，其中 i,ji,ji,j 任选。然后分别计算出无穷次操作之后哪个牌堆会拥有最后的 ∑ci\sum c_i∑ci 张牌的概...

C++

2021-11-21

3 430

题解 | #小䓤的一个数字#

C 其实本来这题是放在 B 题之前的，看题目名称就知道。可是考虑到种种原因，看上去这道题场切的人会比上一题少，所以就商量着把这道题放在 C 上来了。考虑到 n≤3000n\le3000n≤3000，我们可以给出一个 O(n2)O(n^2)O(n2) 的算法。首先预处理一下区间 min，一会方便...

C++

2021-11-21

2 349

题解 | #小䓤的一些数字#

B 考虑分类讨论： k=1k = 1k=1，高斯求和公式即可。 k=2k = 2k=2，平方和公式，∑i=1n=n(n+1)(2n+1)6\sum\limits_{i=1}^{n}=\dfrac{n(n+1)(2n+1)}{6}i=1∑n=6n(n+1)(2n+1)。 k≥3k \ge 3k≥...

C++

2021-11-21

2 345

题解 | #小葱的01串#

A 首先几个显而易见的结论：红 000 = 白 000，红 111 = 白 111，所以红 = 白。红 = 白，所以 len(红) = len(白) = n2\dfrac{n}{2}2n。据此，我们只需要找一段长度为 n2\dfrac{n}{2}2n 的区间，且区间和同样是 sum2...

C++

2021-11-21

3 879

题解 | #数字方阵#

来写一篇随机化做法的题解。尝试只用一次 std::random_shuffle 草过去，发现在一些小数据上确实挺容易爆炸。那么考虑这么个事情：当 nnn 很大的时候，在整个方阵中重复次数一定不会很多，而想让重复次数很多，就必须让 nnn 变小（这样碰撞概率才会大）。所以我们就得到了如下代码：（...

C++

2021-11-17

1 575

题解 | #あなたの蛙は旅立っています#

写一篇不需要转化原图的题解。直接根据数字三角形的思路，原图的结构模拟这一过程 dp 即可，注意我们 dp 的过程可以分为下面三段：上图是我自己画的。第一部分是一个裸的数字三角形，注意这里每一行可以通过上一行和上两行转移过来即可。图中的数字表示行号。第二部分是一个 n−1,nn-1,nn−1...

C++

2021-11-17

3 372

题解 | #监狱逃亡#

考虑把逃亡的过程分成三段：在第一行 1→2→3→⋯→i1\rightarrow2\rightarrow3\rightarrow\cdots\rightarrow i1→2→3→⋯→i 在第二行 i→⋯→ji\rightarrow\cdots\rightarrow ji→⋯→j 在第三行 j→⋯→...

C++

2021-11-13

5 385

题解 | #魔法学院(hard version)#

接着上一篇题解的分析过程，我们还是考虑把操作离线下来看看怎么搞一搞。注意到我们可以更改排序的 cmp 顺序，原来是从小权值到大权值，这是为了方便进行区间推平。现在我们换过来，从大权值到小权值，这样做的好处就是保证每个位置至多被修改一次，链表维护一下下一个被修改的位置就好了。时间复杂度 O(n)...

C++

2021-11-13

2 636

题解 | #魔法学院(easy version)#

每个位置有很多种放字符的方法，把初始的字符也离线下来，同时作为操作一起排序。考虑到不管什么位置，我只要排过一遍序，后来者一定比先覆盖上去的严格不劣，所以直接进行区间覆盖单点查询即可。代码实现细节的话也没啥好说的，就是无脑堆板子就好了。时间复杂度 O(nlog⁡n)O(n\log n)O(nlo...

C++

2021-11-13

1 525