小琢卷不动

分类

未归档(10) 题解(72)

/ 注册

全部文章（共80篇）

题解 | #博弈#

其实这个游戏跟双方是否“绝顶聪明”无关，因为方案都是唯一的，只需要判断一下到底谁会赢就好了。考虑分类讨论，类似整除分块的思路：每个数变成 kkk 个 ⌊nk⌋\lfloor\dfrac{n}{k}\rfloor⌊kn⌋ 当 n∈[k0,k1−1]n \in [k ^ 0, k ^ 1 - 1...

C++

2021-11-23

1 440

题解 | #躲藏#

这道题需要格外注意一句话：不区分大小写。所以考虑设 dpi,0/1/2/3dp_{i,0/1/2/3}dpi,0/1/2/3 表示以 iii 结尾，最后一位恰好匹配到 cwbc 的第 0/1/2/30/1/2/30/1/2/3 个字符的方案数。然后稍微压一下状态，写出状态转移方程：（代码...

C++

2021-11-23

2 420

题解 | #音标#

考虑直接模拟，用一个 for 循环去找，从某个字符 c = s[i] 开始，一直减一，直到找到某个元音字母就停止并输出这个字母即可。 #include<cstdio> #include<cstring> const int N = (int) 1e6 + 5; char s[...

C++

2021-11-23

1 481

题解 | #美#

考虑直接对输入的序列 RRR 排序，然后 R1,Rn,R2,Rn−1,⋯R_1,R_n,R_2,R_{n-1},\cdotsR1,Rn,R2,Rn−1,⋯ 这样交替排列下去就好了。考虑证明：（官方题解中好像没写明白哎）假如我们任意交换某两个 Ri,RjR_i,R_jRi,Rj，那么按照...

C++

2021-11-23

1 303

题解 | #艺#

感觉这个数据范围是假的。明明 T≤109T\le10^9T≤109，然后最后遍历的过程 O(T)O(T)O(T) 居然跑得飞快（狂笑）。好吧，来说说正解思路，其实直接考虑把两种播放的方式按照时间排个序，然后每个时间“点”选择最佳的播放方式（如果没有 ≥0\ge0≥0 的就不选，这里我处理成了和 ...

C++

2021-11-23

2 296

题解 | #武#

输入的是一个树的结构，她的家在 PPP 点，就以 PPP 为根，dfs 求出每个点到 PPP 的距离 dis\text{dis}dis，然后以 dis\text{dis}dis 来排序，找到离她家第 KKK 远的点即可。求距离的时候可以用到公式：（假如 uuu 是一个结点，vvv 是 uuu 的孩...

C++

2021-11-23

1 447

题解 | #文#

考察结构体排序，给每个选手记一个结构体，存放他的答案、得分、名字，在排序的时候自定义一个 < 运算，如果分数相同按照姓名的字典序排序即可。对于计算分数，我们可以考虑把 100100100 分分成 nnn 份，每答对一道题就分配 100n\dfrac{100}{n}n100 分给这位同学即可...

C++

2021-11-23

1 423

题解 | #黑黑白白#

感觉和上一题考察点有一些重复，都是最基础的博弈论。解决这题我们需要知道下面的两点：如果我走了一步，对方处于“必败”境地，那么我就处于“必胜”境地。如果我的所有下一步状态都是“必败”态，那么我就会输，只要有一个“必胜”的我走那一条路就可以。所以既然它就是个树形结构，直接遍历这棵树，把所有孩...

C++

2021-11-23

2 428

题解 | #是是非非#

经典的 Nim 游戏。对于原问题，我们认为当 XORi=1n ai=0\text{XOR}_{i=1}^{n}~a_i=0XORi=1n ai=0 时先手必败，反之先手直接取掉等于 XORi=1n ai\text{XOR}_{i=1}^{n}~a_iXORi=1n...

C++

2021-11-23

1 303

题解 | #虚虚实实#

根据欧拉定理，我们知道当一个无向图的奇点个数为 000 或 222 时它就可以被一笔画出。另外这个题数据不保证图是联通的，并查集判断一下就好。想简单地说说这个遍历的方法，奇点为 000 不用说，一条入边一条出边，总有办法遍历掉，如果有两个奇点，遍历的时候就必须以其中一个为起点，另一个为终点，否则...

C++

2021-11-23

3 489