小琢卷不动

题解

未归档(10)

/ 注册

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

题解 | #区间 (interval)#

看完题第一反应线段树。然后 copy 了一个朴素板子过来发现数据范围 10610^6106，怀疑出题人可能卡常。然后就想到了 zkw 的非递归式写法，常数很小。复制完了模板之后反应过来好像可以差分数组 O(n)O(n)O(n) 做（大雾）线段树做法不讲了，来说说差分数组：设 d[i]=a...

C++

2021-11-24

1 358

题解 | #时间(time)#

根据题意模拟即可，注意以下几点：用 int 型存储，高位用 x / 10 取出来，低位用 x % 10 取出来。判断回文时第一个数的高位和第二个数的低位相同，反之亦然。向后枚举时碰到 24:0024:0024:00 就加一个 if 语句强制钦定成 00:0000:0000:00 即...

C++

2021-11-24

1 403

题解 | #最大公约数(lcm)#

(a,b)×[a,b]=a×b(a,b)\times[a,b]=a\times b(a,b)×[a,b]=a×b 证明：记 a=∏i=1kpiαi,b=∏i=1kpiβia=\prod\limits_{i=1}^{k}p_i^{\alpha_i},b=\prod\limits_{i=1}^{k}p...

C++

2021-11-24

1 314

题解 | #阶乘(factorial)#

考虑 x!→(x+1)!x!\rightarrow (x+1)!x!→(x+1)! 有什么贡献。首先 (x+1)!(x+1)!(x+1)! 一定包含了 x!x!x! 中所有的 555，也就是说直接把 x+1x+1x+1 自己里面的 555 加入到答案即可。时间复杂度不会算，但显然大于 O(n)O...

C++

2021-11-24

1 338

题解 | #无关(relationship)#

首先容斥。定义与 AAA 有关的数组成的集合是无关的补集。考虑如何求有关的数的个数，由 ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A∪B|=|A|+|B|-|A∩B|∣A∪B∣=∣A∣+∣B∣−∣A∩B∣ 可知，直接枚举所有 2k2^k2k 种情况并去掉重复的即可。考虑如何计算 L∼RL\sim...

C++

2021-11-24

1 393

题解 | #CSL分苹果#

01 背包模板。设 dpi,jdp_{i,j}dpi,j 表示前 iii 个物品是否能组成重量 jjj： dpi,j←dpi−1,j&nbs***bsp;dpi−1,j−aidp_{i,j}\leftarrow dp_{i-1,j}~\text{OR}~dp_{i-1,j-a_i}dpi,j←...

C++

2021-11-24

1 331

题解 | #BFS#

按照题意模拟即可。函数 B 用于判断一个字符是否是 B 的大小写。函数 O 同理。通过一个 for 循环找到我们要的答案，如果这一位是 b，下一个是 o，下下一个是 b 则输出当前位置。都没有找到就输出 -1 即可。 #include<cstdio> #include<cs...

C++

2021-11-24

2 417

题解 | #Applese的超能力#

若 n=1n=1n=1 则任务已经完成；否则，若 m=1m=1m=1 则任务无法完成；（做不了任何事情）否则，由于最终要消除恰好 n−1n-1n−1 个硬币，每次操作恰好消除 m−1m-1m−1 个硬币，只需要判断 m−1m-1m−1 是否能整除 n−1n-1n−1 即可。 #include&l...

C++

2021-11-24

1 334

题解 | #谁是神射手#

A 打中瓶子的概率是：第一次打中：a%a\%a% 第三次打中：(1−a%)×(1−b%)×a%(1-a\%)\times(1-b\%)\times a\%(1−a%)×(1−b%)×a%（第一、二次都没打中）第五次打中：(1−a%)×(1−b%)×(1−a%)×(1−b%)×a%(1-a\%)...

C++

2021-11-23

3 363

题解 | #自杀游戏#

基础的博弈论，如果我可以通过一个状态让对方必死，我就能活；反之我必死。值得注意的是：调快 [a,b][a,b][a,b] 秒，也可以不调。据此设 life(x)life(x)life(x) 表示剩余 xxx 秒时先手是否能活，加一个记忆化即可保证每个状态的计算只进行一次，据此复杂度为 O(...

C++

2021-11-23

2 395