考虑类似 bfs 的过程，通过一个队列去扩展我们的答案就好。 一个格子被感染，可以影响到它周围的 444 个格子，而一个格子周边一旦存在 ≥2\ge2≥2 个格子被感染那么它也会被感染，这个直接建图，类似一个拓扑排序，入度 =0=0=0 就拓扑过去就好了。 时间复杂度 O(nm)O(nm)O(nm)。 #include<cstdio> int init(){ char c = getchar(); int x = 0, f = 1; for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1; ...

考虑直接模拟，把所有可能的十进制数扔到 map 里面去。 由于 10002=1061000^2=10^610002=106，所以把所有 666 位数以下的数字全部扔进去就可以了。 复杂度 O(Nlog⁡N)O(N\log N)O(NlogN)，其中 N=6nN=6nN=6n，因为顶多存在 6n6n6n 种可能的十进制数。 扔进去之后，暴力枚举即可找到我们要的数字。 #include<map> #include<cstdio> int init(){ char c = getchar(); int x = 0, f = 1; for (; c < '0' ||...

一个明显的想法，就是对 aia_iai​ 排序，然后从后往前扫，取连续 333 位进行判断。 在这个基础上，特判一下哪根木棍被取走了即可。 看起来这个过程复杂度是 O(n2)O(n^2)O(n2)，但是实际上由于我们只要找到解就 break，复杂度是接近于斐波那契数列增长速度的，可以视作一个 log⁡\loglog，即 O(nlog⁡n)O(n\log n)O(nlogn)。 #include<cstdio> #include<algorithm> #define int long long int init(){ char c = getchar(); int x...

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

由异或的性质，两个数 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(b−a+1)×(d−c+1)\dfrac{\min(b,d)-\max(a,c)+1}{(b-a+1)\times(d-c+1)}(b−a+1)×(d−c+1)min(b,d)−max(a,c)+1​（重合段的长度除以总个数） #include<cstdio> #define int ...

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

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

这道题需要格外注意一句话： 不区分大小写。 所以考虑设 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 个字符的方案数。 然后稍微压一下状态，写出状态转移方程：（代码中才是正确的，下面的稍微简化了一下书写，意会一下即可） dp0←dp0+(s[i]=′c′)dp1←dp1+dp0×(s[i]=′w′)dp2←dp2+dp1×(s[i]=′b′)dp3←dp3+dp2×(s[i]=′c′)\begin{aligned}dp_0&\leftarrow dp_...

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

考虑直接对输入的序列 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​，那么按照这个序列逐个奇数位置递减偶数位置递增的方式，不难得到： RiR_iRi​ 两边的贡献和 RjR_jRj​ 两边的贡献必然没有伸展到最开的位置。 不妨把这个信息扔到一个数轴上看一看，我们最初的排列方式，实际上就是在数轴上的两个最远点、再到次远点，这样来回穿梭： 如果改变某两个 RiR_iRi​，Rj...

感觉这个数据范围是假的。 明明 T≤109T\le10^9T≤109，然后最后遍历的过程 O(T)O(T)O(T) 居然跑得飞快（狂笑）。 好吧，来说说正解思路，其实直接考虑把两种播放的方式按照时间排个序，然后每个时间“点”选择最佳的播放方式（如果没有 ≥0\ge0≥0 的就不选，这里我处理成了和 000 取 max⁡\maxmax）。 由于之前已经给这个节目排过一次序，直接双指针扫描即可。 #include<cstdio> #include<algorithm> #define int long long int init(){ char c = getchar()...

输入的是一个树的结构，她的家在 PPP 点，就以 PPP 为根，dfs 求出每个点到 PPP 的距离 dis\text{dis}dis，然后以 dis\text{dis}dis 来排序，找到离她家第 KKK 远的点即可。 求距离的时候可以用到公式：（假如 uuu 是一个结点，vvv 是 uuu 的孩子结点） dis(v)=dis(u)+value\text{dis}(v)=\text{dis}(u)+valuedis(v)=dis(u)+value，其中 valuevaluevalue 是 u↔vu\leftrightarrow vu↔v 之间的距离。 #include<cstdio&g...

考察结构体排序，给每个选手记一个结构体，存放他的答案、得分、名字，在排序的时候自定义一个 < 运算，如果分数相同按照姓名的字典序排序即可。 对于计算分数，我们可以考虑把 100100100 分分成 nnn 份，每答对一道题就分配 100n\dfrac{100}{n}n100​ 分给这位同学即可，由于 nnn 并不大，我的精度设置成 1e-9 绰绰有余。 #include<cmath> #include<cstdio> #include<string> #include<iomanip> #include<iostream> #i...

感觉和上一题考察点有一些重复，都是最基础的博弈论。 解决这题我们需要知道下面的两点： 如果我走了一步，对方处于“必败”境地，那么我就处于“必胜”境地。 如果我的所有下一步状态都是“必败”态，那么我就会输，只要有一个“必胜”的我走那一条路就可以。 所以既然它就是个树形结构，直接遍历这棵树，把所有孩子结点的答案向上合并即可！ #include<cstdio> #include<vector> int init(){ char c = getchar(); int x = 0, f = 1; for (; c < '0' || c > '9'; c = ...