小猫，面前有一排小鱼干，每个小鱼干上标着甜度数字。你要找出最长的一串相邻小鱼干，要求它们之间的甜度差不超过1（也就是差不多甜）。比如甜度是 2 3 2 1 4：第一串：2、3、2、1 甜度差都≤1，即长度4第二串：4 单独一个，即长度1所以最长的是4个～代码里的小猫就一个接一个舔过去：如果当前小鱼干和上一个“口味接近”（差≤1），就开心地继续舔，段长+1。如果突然遇到一个口味差别大的，就伤心地结束当前段，把长度记下来，然后从这颗新的开始重新数。最后，它就会告诉你，它最长一口气舔了多少个相邻的小鱼干～(≧▽≦) #include <bits/stdc++.h> using names...

今天的题也是简单到不行喵！集训室里有 n 只打卡丘的小猫，每只小猫都有自己的理想温度 a[i]。如果室温 K 和它的理想温度差太多（|a[i]−K| > p），它就会炸毛喵！ 所以作为队长的猫猫，要找一个神奇的室温 K，让尽可能多的猫咪同时舒服地打卡丘～(≧▽≦)解释时间喵！把猫咪们的理想温度写在标签上，按从小到大的顺序排排坐（排序）。现在我们要找一段最长的连续猫咪队伍，它们之间的理想温度差不能超过 2p（因为 K 可以取中间值，让最左和最右的猫咪都不炸毛）。想象一下，猫咪们按理想温度站成一排，你手里有一根伸缩逗猫棒（滑动窗口），棒子的两端就是左爪 l 和右爪 r。一开始，棒子只够到第一...

这道题就是一个简简单单的贪心喵~简单引导一下喵如果值全是非负数的话，比如“0，2，4，5”来说，答案肯定是把所有数加起来就行了喵！只要有负数的话，比如“-2，-1，3，29，33”来说，想得到最小答案就有点绕了喵。第一步肯定是把后面所有数全部和第一个-2加一起才对喵。这样-2对答案影响最大喵！就变成“-3，1，27，31”.同样的还可以变成“-2，24，28”再到“22，26”.发现又变成全是非负数形式啦！猫猫发现了它的策略应该是从最小值开始，如果是负数就全影响后面。如果是正数就已经全部求和了喵！每次都改变后面的数肯定不现实喵~所以猫猫想到可以记录下来后面一共被减了多大的数值喵!代码思路喵～先...

这道题非常简单喵！只需要会简单的拓扑排序加dp就可以了喵！什么是拓扑排序喵？拓扑排序是对有向无环图（DAG）的一种顶点线性排序，使得对于每条有向边 u→v，顶点 u 在排序中都出现在 v 之前。简单说，就是按依赖关系排个序——先处理没有前置依赖的点，再逐步去掉它们，直到所有点处理完。实现方法：计算每个点的入度（指向它的边数）。将入度为0的点加入队列。取出队首，将它指向的所有点的入度减1，如果某点入度变为0则入队。重复直到队列为空。怎么做喵？题目给了捕食关系：输入 u v 表示生物 v 捕食生物 u，所以有向边是 u→v（从猎物指向捕食者）。那么：生产者：不会捕食别人 → 入度为0（没有猎物指向...

这道题好难喵！给猫猫做傻了喵！借用了蒟蒻果冻01大佬的O(n) 思想，仅仅只是为了让更多人和猫猫一样理解他的思想喵！猫猫解释时间到！(≧▽≦)第一步：看看 t 的开头有几个相同的小可爱设定一个 z 来统计 t 开头有多少个连续相同的字符 int z = 1; while (z + 1 < n && t[z] == t[z + 1]) ++z; 就像在数一群小猫咪，看看它们是不是都穿着同样的衣服。比如 t = "aaab"，前三个都是 'a'，所以 z = 3。这个信息后面有大用处喵！第二步：从尾巴开始，数一数 s 和 t 有多少连续相同的位置也就是数组...

这道题简直超级简单喵！我们只要学会临界检测就可以了喵！因为m最大只有1e5.所以我们只需要直接列一个大小为m的数组用来存储安全牌被保证的次数喵~假如对于每个num，可以保证它前后的num-3和num+3是安全牌。对于每个牌，我们只需要改变num-3和num+3的安全牌被保证的次数就可以了喵！当安全牌被保证的次数从0到1或从1到0的时候安全牌的数量才会发生变化喵!所以思路已经变得很清晰了喵!看代码喵~ #include <bits/stdc++.h> using namespace std; using ll=long long; int main() { cin.tie(0)-&g...

这道题其实很简单喵~首先我们让牌沿着位置顺序排序喵！（最简单的操作）本喵从左到右挨个看小骨头：如果它是第一个小骨头，或者它站的位置比当前小团体能倒到的最右边还远，说明它不能和前面的小骨头一起倒，那就重新开一个小团体。否则，它就能加入当前的小团体，并且要更新最右边位置（如果它倒的范围比现在的更远的话）。小金最多能推 m 个小骨头，每个小团体只要推最左边的一个，整个团就全倒，所以当然选最大的 m 个小团体最划算！把 duan 里前 m 个（如果不足 m 个就全取）加起来就是答案啦~看代码喵！ #include <bits/stdc++.h> using namespace std; u...

这道题其实挺简单的喵！注意长度小于等于 2 的子区间和不等于 0喵！我们就可以知道相反数不能相邻喵！这就非常简单了喵！假如数组里有0的话，一定NO喵！因为相同的数分散开是不利于满足题意的！所以我们可以把相同数放在一起，看作一个数喵！其实就是去重喵！假设去重后数字大于2的话，就一定是YES！因为有多组相反数可以交叉排列。比如：-1，1，-2，2可以排列为：-1，-2，1，2。而只有一组相反数的话也可以拿其他数把它隔开。所以说猫猫的代码中不是完全去重，而是保证大于2就可以了喵！假设去重后数字等于2的话，必须是相反数才能NO哦。其他都是YES喵！看代码！ #include <bits/stdc...

这道题简单喵！我们只需要知道：对于每个数字 0~9，它最终能变成哪些数字（包括它自己），然后把 x 的每一位的可能性乘起来，就得到总数喵！用 to[a][b] 表示是否有直接能力把 a 变成 b 喵~输入 n 条规则，就把对应的 to[a][b] 设为 true。传递闭包（Floyd-Warshall）因为能力可以重复使用，所以如果 a 能变成 c，c 能变成 b，那么 a 也能变成 b。这就像朋友的朋友也是朋友一样喵~我们用三层循环： for (int k = 0; k < 10; k++) // k 是中间人 for (int i = 0; i < 10; i++) // i ...

这道题其实很考验思路喵~ 要用到动态规划才能优雅解决呢！经过猫猫的细心观察发现，如果把字符串中连续的 0 或 1 看作一个“大块”，那么华撃串恰好需要分成 4 个大块 喵！比如 000110111 可以分成 "000"、"11"、"0"、"111" 这四大块，相邻对数量就是 3 啦（每两个块之间产生一个“01”或“10”）。是不是觉得 DP 也没那么难啦？来看看猫猫的思路吧：我们定义两个数组 f1 和 f0，分别表示以 1 开头和以 0 开头的字符串，下标代表当前已经分成了多少个大块。例如 f1[2] 表示当前前缀...

猫猫真傻，真的。猫猫还以为是小d只能烧除自己以外的其他联通快呢喵。然后费劲巴拉的模拟了一个只排除@其他地方全烧的代码喵！结果发现是只烧自己的连通块喵！甚至就算我误解的题面，也只用全体减去小d所在的连通块就可以了喵！猫猫真傻，真的。。。其实这道题是一道简单的bfs连通块问题喵~（连通块的意思是没有被石头阻挡的空地组成的一大块）因为火的蔓延方式等同于在该地方重新放置炸弹喵！所以在一个连通块里边在哪里放火都无所谓喵！又因为小d只能在本连通块上放炸弹，所以答案就是在小d所在连通块上的草地的数量喵~接下来实现代码就非常简单了喵~直接看代码就可以了喵。猫猫提供了详细的注释喵~ #include <b...

这道题其实简单喵~只需要用广度优先搜索（BFS）就可以探索所有可能的状态了喵！用结构体 zu 记录当前两个数的值 a、b 和已经操作的次数 cishu。从初始状态 (a, b) 开始，不断尝试对其中一个数删除每一位，生成新的数对，并记录步数。用 set<pair<int,int>> 记录已经访问过的状态，避免重复探索喵~如果不写的话会爆掉的！如果当前两个数能整除（一个数是另一个数的倍数），就输出当前步数，并结束。如果队列空了还没找到，就输出 -1，表示猫猫没招了喵！有思路了就去写喵！如果只是不会写就看猫猫的代码喵~ #include <algorithm> ...

这道题是一道简单的数学题喵~因为数组里只有0和1，所以当1占k的一多半的时候中位数必定是1喵！中位数是0的情况不考虑喵~因为对结果没有贡献。这道题好贴心的让k是奇数了喵~所以1最少数量是k/2+1。假如1的数量是 i 个，那么0的数量是 k-i 个。那么答案就会加上喵！把 i 的数量全部遍历一遍就可以了没想到最难的居然是逆元和的函数应该怎么写喵！ #include<bits/stdc++.h> using namespace std; using ll = long long; const ll mod=1e9+7; vector<ll> jie(2e5+1); ll ...

好简单的数学题喵~先说结论喵！不管是什么坐标都会在有限次内变成（0，0）喵！所以直接求面积就可以了喵！接下来解释为什么喵！如果想要无限次变化需要满足每次变化都是他自己喵所以x^y==x且x==2y。简单运算可得只有（0，0）符合喵！欸！这个时候就要小猫要说啦。“猫猫猫猫！有没有可能（x，y）转换成（y，x）呢？”有道理，猫猫一算。欸！发现它至少需要满足x^y==y且y==2x。这和上一个没区别呀喵！所以所有的坐标都会在有限次内变成（0，0）喵！那么剩下的难点（？）就是求面积啦喵~还不会可以私信猫猫喵~ #include<bits/stdc++.h> using namespace ...