小琢卷不动

分类

未归档(10) 题解(72)

/ 注册

全部文章（共80篇）

题解 | #自杀游戏#

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

C++

2021-11-23

2 395

题解 | #送分题#

不知道题面中的代码是什么逻辑。但是可以通过尝试，发现只要 n≥20182017n\ge20182017n≥20182017 时的输出均为 201820172018201720182017，据此模拟这个过程即可。（只需要把题面中给的代码加上一个特判，时间复杂度即为正确的） #include<...

C++

2021-11-23

1 440

题解 | #强迫症#

考虑这个操作的本质，就是任意选一组 i,ji,ji,j，令 ai←ai+aja_i\leftarrow a_i+a_jai←ai+aj。那么一次至多消除一个重复的数字，所以最优的次数就是重复数字的个数。（例如 1 1 1 11~1~1~11 1&nbs...

C++

2021-11-23

1 278

题解 | #浮点数输出#

按照题意原样输出即可。 #include<cstdio> char str[100]; int main(){ scanf("%s", str + 1); printf("%s\n", str + 1); }

C++

2021-11-23

2 552

题解 | #病菌感染#

考虑类似 bfs 的过程，通过一个队列去扩展我们的答案就好。一个格子被感染，可以影响到它周围的 444 个格子，而一个格子周边一旦存在 ≥2\ge2≥2 个格子被感染那么它也会被感染，这个直接建图，类似一个拓扑排序，入度 =0=0=0 就拓扑过去就好了。时间复杂度 O(nm)O(nm)O(nm)...

C++

2021-11-23

3 433

题解 | #博弈论#

考虑直接模拟，把所有可能的十进制数扔到 map 里面去。由于 10002=1061000^2=10^610002=106，所以把所有 666 位数以下的数字全部扔进去就可以了。复杂度 O(Nlog⁡N)O(N\log N)O(NlogN)，其中 N=6nN=6nN=6n，因为顶多存在 6n6n6...

C++

2021-11-23

4 372

题解 | #三角形#

一个明显的想法，就是对 aia_iai 排序，然后从后往前扫，取连续 333 位进行判断。在这个基础上，特判一下哪根木棍被取走了即可。看起来这个过程复杂度是 O(n2)O(n^2)O(n2)，但是实际上由于我们只要找到解就 break，复杂度是接近于斐波那契数列增长速度的，可以视作一个 log...

C++

2021-11-23

2 287

题解 | #旅游#

本质上就是一个没有上司的舞会。不能同时选相邻的两个点，另外根结点必选，直接考虑套没有上司的舞会的模板即可： f[u]f[u]f[u] 表示 uuu 必选，以 uuu 为根的子树的答案； g[u]g[u]g[u] 表示 uuu 不选，以 uuu 为根的子树的答案； f[u]←g[v]f[u...

C++

2021-11-23

2 370

题解 | #异或#

由异或的性质，两个数 x,yx,yx,y 异或和等于 000 当且仅当 x=yx=yx=y。所以在区间 x∈[a,b],y∈[c,d]x\in[a,b],y\in[c,d]x∈[a,b],y∈[c,d] 中选择两个相同的数的 x,yx,yx,y 的概率： min⁡(b,d)−max⁡(a,c)+1...

C++

2021-11-23

3 292

题解 | #妹纸#

和上一道题的思路类似，把相同的答案合并到一起计算。官方题解也说了，需要巨大多分讨，将原序列分成若干个连续的求和段即可。 #include<cstdio> #define int long long int init(){ char c = getchar(); int x = 0,...

C++

2021-11-23

1 396