题意: 有n×m的矩阵，有a个格子是染黑的，并在每个单位时间往外四个方向扩散。有b个格子是蓝墨水，他会在时间刻变白，在变白之前他不会被染黑，求整个矩阵全部染黑的时间。（蓝墨水变白的判定在染黑判定之前，换句话说如果蓝墨水旁边有个染黑的格子，假设蓝墨水到第5s变白，那他会被旁边的染黑格子在第5s染黑。） 知识点: BFS，图论 思路: 把每个染黑的格子放入优先队列里边BFS，并初始化染黑的格子为0，接着每次BFS都等于前一个格子+1，来模拟他的时间，当遇到蓝色墨水时，则等于max(下一秒,蓝墨水变白的时刻)，然后用一个maxn变量，在每次格子数值改变时记录下最大的时间就可以了。（不会BFS和优先队...

题意: 现有n把三角尺，我们得知第i个三角尺的直角边是，我们可以对任意三角尺的减去一个数，但不能是大于的数，且所有减去的长度总和不能大于w，使得最终所有三角尺的斜边长度总和最小。 知识点: 贪心，优先队列 思路: 我们可以把题意分解为一个一个减，通过优先队列来维护-1原先长度-现在长度的最大值，每减一次就更新一次。具体做法叙述如下: 创建一个倒序排序的三元组优先队列，依次按输入算出  并将其推入队列push({d,x,y});（因为数据范围规定输入的y>=1，所以不用担心直接减成负数的情况。） 接着进入循环，循环条件为队列非空以及i<w。 循环内取出栈顶元素的x和y，然后将元素出队...

题意: 现有初始x=0，以及两个长度为n的a，b数组，我们要进行n次操作，每次操作可以选择将x更新为max(x-a[i],0)或更新为x^b[i]。使得n次操作后最大化x。 知识点: 动态规划 思路: 从题意可以看出，他最终操作不会大于2^i（i是b数组中最大数的二进数位数），因为异或不会产生一个新的高位出来，减法更是只能减少。 所以我们可以考虑用值域动态规划，因为你直接从结果看，他第一轮产生2个结果，第二轮产生4个结果，第N轮产生个结果，所以他最大会产生2的几千次方个结果，但是其中大部分都是重复的，因为他不会超过2048。 因此用值域来搜索，每一次将上一轮产出的所有可能数按照max(x-a[...

题意: 请用n个字符组成一个字符串使得到的权值最大，其中仅有"td","qcjjkkt","qcjjkktd"这三个字符串有权值，每包含这样一个字符串的权值是b,a,a+b。 知识点: 贪心，动态规划 思路: 因为这题的数据范围很大，直接dp会超时，然后我们可以发现这三个字符串长度为2,7,8，他们的最大公约数是56，所以我们可以做到贪心出每56个字符所贡献的最大值是多少，也就是max(8a,28b,7(a+b))，但是如果直接把前56x个字符全部枚举完之后再去动态规划剩下的字符串就会出问题，比方说 tdtdtdtd 这是正好56个结束 假如后面还剩下3个位置 其中会出现把前面两个td删掉 换...

题意: 给出n组重量为，个数的果子，每一个果子为一堆，每次可以挑两个堆合在一起，合在一起的代价是这两个堆的重量之和，求全部果子合在一个堆里的最小代价。 知识点: STL，哈弗曼编码 思路: 这题我们只需要贪心思路，想要最小代价那就每次都挑最小的两个堆合并之后把新的堆放进容器里，再找两个最小的堆合并，而这题给的个数很大，所以我们需要用二元组来存储重量和个数来减小内存负担。 所以我们的处理就变成了找到最小重量的元素，使用优先队列做容器，出队查询栈顶元素他的个数是否大于1，如果大于1，自己直接合并，两两合并完之后如果还有剩的就插入到队列里，没有就不插入，如果个数等于1，那就接着在出队查询一个栈顶元素...

题意: 定义f(x)为x所有位的数字乘积，定义g(x)为 while(x!=f(x)){ x=f(x); }  的循环次数。 例如x=112333 第一轮 x=112333 f(x)=54 第二轮 x=54 f(x)=20 第三轮 x=20 f(x)=0 第四轮 x=0 f(x)=0 所以得出g(0)=0 g(20)=g(0)+1=1 g(54)=g(20)+1=2 g(112333)=g(54)+1=3  接着我们需要构造出在10^18范围内的正整数a,b且a≠b，使得最大化g(a)+g(b)。 知识点: 思维，递归，构造，打表，记忆化搜索 思路: 显然这题只要放两个数上去，所以你可以直接暴...

题意: 现有n*m的矩阵，将q次对单元格增加，求每次增加之后的曼哈顿距离不超过2的所有方格之和的最大值在哪个方格？ 知识点: 暴力 思路: 我们可以先暴力枚举出每一个方格曼哈顿距离不超过2的所有方格之和，接着在枚举的过程中顺手记录下其中和最大的方格下标。接着对于每个q来说，他增加的那个z也只有曼哈顿距离不超过2的单元格才会受到影响，只要直接预处理的和数组把曼哈顿距离不超过2的单元格和全部加上z就可以了。然后加的过程中再拿之前记录的最大值下标比较，并记录最新的和最大下标即可。 参考代码: #include<bits/stdc++.h> #define ll long long #de...

题意: 现有一个长度为n的01字符串，你可以跳跃选择任意字符组成字符串（需保证相对顺序不变），如果相邻字符互不相同则可以把他们01番置，求最少操作次数使原字符串相邻字符互不相同。 知识点: 动态规划，字符串，思维。 思路: 因为相邻字符串互不相同，则最终结果一定是010101...或者101010...的形式，所以我们可以拿这两个字符串和原字符串比较把需要变换的字符拿出来，得到两个新的字符串命名为c1和c2，接着我们在对c1和c2处理之后看看哪个需要的操作次数小就可以了。 我们得到需要变换的字符串后，想要把他们全部01反置，你就可以从当前位置一直往后找不同字符 比如需要反置的字符串为11010...

题意: 现有2*n的方阵，起点(1,1)，终点为最后一列任意一格，双方进行博弈，每一次双方都能放置一个障碍使得那一个格子不能进入（但必须留出一条路不能全堵上，也不能放置在起点或者已经放过障碍的地方），小红希望最短路径尽可能小，小紫希望最短路径尽可能大，双方都进行最优操作试问最终最短路长度是多少。 知识点: 博弈 思路: 小红想让路径最短所以他会尽可能使小小红走直线，所以他会尽可能把另外一条路堵上，小紫想让路径最长所以他会尽可能把当前的路增加障碍使得小小红疯狂拐弯。然后我们在进入一场博弈仔细观察下 小红为R，小紫为P，最短路为*，通路为0 先看n=5时 ****P 00R** 再看n=15时 *...

题意: 给出两个定点A(x1,y1),B(x2,y2)，试求第三点D(x,0)使得构成的三角形面积为2。 知识点: 数学，几何，构造 思路: 初中数学，没啥好说的，所以直接在题目的基础上把公式全推了给你们看吧。 设经过A,B两点的直线方程为L:y=kx+b   然后有了两个思路，一个是按正常思路，以A点到B点的距离为底，那么他的第三个点就要选在L的平行线，这个平行线和L的距离是，可以两个答案任选其一。 另外一个思路则是不用点到直线的距离公式和点到点的距离公式，而是通过凑一个好求面积的大三角形减去一个好求面积的小三角形得到我们的答案。如下图所示： 假设C点是L和x轴的交点（先不说L和x轴平行的情...

题意: 一个数字由七个灯管显示，七个灯管为一个显示器，给出8个有同样问题的显示器，给出每个显示器7个管不亮的概率，求前4个显示器和后4个显示器组成的数之和等于C的概率 知识点: 数学，概率论，快速幂 思路: 给出七个灯管的亮灭概率可以求出每个数字出现的概率，有了每个数字出现的概率就能枚举出A+B=C的每一种情况的概率，加起来就是最终的答案，同时我们只需要枚举A从[0,C]的范围即可，枚举每一个A并求B=C-A的B出现的概率。接着一直循环让ans加上A*B即可。 参考代码: #include<bits/stdc++.h> #define int long long #define e...

题意： 请尝试构造出一个长度为n的正方形01矩阵，使其中的每一行的元素之和属于[0,n-1]且每一行的元素之和都互不相等，使其中每一列的元素之和属于[0,n-1]且每一列的元素之和都不相等，并使0和1的连通块数目之和为n 知识点： 构造 思路： 很好发现的是 n=2时 00 01 n=3时 000 011 010 n=4时 0000 0111 0100 0101  这种一圈包裹着一圈的形式恰巧满足题目的要求，所以我们直接构造这种矩阵即可。我依照这种方阵的对称性进行构造，先赋值对角线为01循环a[i][i]=(i&1)，接着以对角线分开的右上角的三角形赋值，依旧是一行0一行1，而左下角的...

题意： 现有一个01矩阵，问是否能从矩阵的每一个点任选一个终点（不能选起点）拼成一个回文字符串。 知识点： 思维，优化 思路： 因为从起点开始，如果起点为1，下一个如果也为1，那么直接回文字符串结束，如果不是，则继续走，只要碰到一个1就是回文字符串，而因为题目没有设墙，所以我们可以达到任意点，也就是说，只要1的个数大于1，那么矩阵中的所有为1的单元格就都有解，0也是一样，0的个数大于1，那么所有为0的单元格都有解。（出题者你没有心，卡我endl，算了，当交学费了，因为endl是每次写入都要刷新缓冲区的，而'\n'不会，所以把endl替换成\n就会过qwq） 参考代码： #include<...

题意： 输出两个数a，b使gcd(a,b)=n，并最大化a^b。（gcd是最大公约数，^是按位异或） 知识点： 思维 思路： 通过枚举或者你惊人的注意力注意到max(a^b)=n，所以我们只要设法让a和b不相同的部分只有那个n就可以了，因为n<2^31，所以我们可以直接将x设为n算数左移32位，然后y=x+n这样前边都相同，只有后边的n的部分不相同，异或就等于n了，当然如果你闲的没事干你也可以自己算一下n的有效位数然后更优雅的在后边留够0能加上n而不进位。这里有两个函数可以帮到你__builtin_clz(n):这个函数会返回他在int中未占用的位数，使用32减去返回值就可以得到总位数，...