小琢卷不动

题解

未归档(10)

/ 注册

全部文章 / 题解（共71篇）

题解 | #切圈圈#

题意：对于一个保证 ∑i=1nai=0\sum\limits_{i=1}^{n} a_i=0i=1∑nai=0 的序列 {an}\{a_n\}{an}，求划分出的最大段数使得每一段区间和均为 000。考虑前缀和，对于一个区间 [l,r][l,r][l,r]，如果 sl−1=srs_{l-1}...

C++

2021-11-11

2 409

题解 | #作弊#

先引用一段百度百科对哈夫曼树的介绍：在计算机数据处理中，哈夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达...

C++

2021-11-11

3 327

题解 | #杨辉的行积#

首先是两个众所周知的结论：杨辉三角代表了组合数，而杨辉三角中第 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)=\df...

C++

2021-11-10

2 743

题解 | #我不是酸菜鱼#

对于一个数 ggg，最大的自然数 kkk 满足 gmod 2k=0g\mod 2^k=0gmod2k=0，就是找 ggg 包含质因子 222 的个数。那么如果是一些数 aia_iai 乘起来得到 ggg 呢？实际上也是一样的，分别统计它们包含的质因子 222 的个数，加起来就好了。考虑证明...

C++

2021-11-10

1 573

题解 | #排名估算#

首先扔一个结论：记最终答案是 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...

C++

2021-11-09

2 515

题解 | #围棋#

一道模拟题。模拟题重在如何实现，接下来挑出几个难以实现的地方说一说：判断死活。对于一块棋，有「气」就能活，没有「气」就会死。下面的 bool live(int, int, char) 处理了这个过程：从一块棋的某个点开始找联通快，只有与自己相同的点才能相连。另外，如果超出边界，按照围...

C++

2021-11-09

6 754

题解 | #牛牛的树#

解题思路首先澄清一点，不「重要」的边可以是亮着的，也可以是灭着的，这个题目里没说，只能通过样例 #1 去理解，希望后续有人来修复一下。考虑从所有的叶子结点开始向上考虑。对于一个点到自己父亲的边，(u,fau)(u,fa_u)(u,fau)，我们考虑：如果这条边不「重要」，我们不需要管它的...

C++

2021-11-08

2 409

题解 | #买面包#

感觉题意挺意识流。所以解法也应该是意识流解法。首先根据题意，手上有 aaa 元钱，每 bbb 元钱买一个面包，所以原价能买 ⌊ab⌋\left\lfloor\dfrac{a}{b}\right\rfloor⌊ba⌋ 个面包。然后是原价购买的面包中，每 ccc 个面包能换 ddd 个面包，所以能...

C++

2021-11-08

1 503

题解 | #3的倍数#

题意：给定 TTT 组询问，每组询问给出两个正整数 L,RL,RL,R，求 x=L(L+1)(L+2)⋯R‾x=\overline{L(L+1)(L+2)\cdots R}x=L(L+1)(L+2)⋯R 是否是 333 的倍数。首先是一个广为人知的结论：判断一个数 xxx 是否是 333 的倍数...

C++

2021-11-08

1 439

题解 | #盾与战锤#

首先选择的是子序列，考虑对原序列排序没有影响。理由是选择子序列相当于可以任意选数，所以排序之后从大到小取可以双向规约。另外考虑对于不同的 kkk，首先对排序后的攻击序列做一遍前缀和，便于查询它们的区间和。如果我们直接枚举不同的 kkk，然后考虑每一个长度为 kkk 的区间：实际上这个区间的直...

C++

2021-11-03

1 341