B、白魔法师 并查集其实很容易知道，如果你处理到一棵树父节点的最大白色数量，子节点最大白色连通数量，那么对这个点的操作之后的答案，就很好找了。现在问题回到，怎么去处理白色棋子在各个连通块里面的数量，这就要设计一个数据结构，并查集我们输入一串字符，对应树中结点颜色，那么在不操作的情况下，每个连通块可以预处理出来。如果子节点和自己都是白棋子，那么这里要比普通的并查集麻烦一点的就是，要把父节点有方向的去规定，吧连通块白棋子小的合并到大的里面去。这样可以保证同一个连通块只加一次，不会重复累加。具体可以手动去写写康康，很容易发现这个BUG的。那么后面只要去枚举黑色的点更新答案即可，吧各个方向上的白连通块...

A、AOE还是单体？ 发现的时候直接单体伤害最优。那么其他时候就是调整让它和相同即可，剩下的单体即可。 #include <bits/stdc++.h> #pragma GCC optimize(2) #pragma GCC optimize(3) using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) typedef long long ll; const ll MOD = 1e9 + 7; inline ll read() { ll s = 0, w = 1; cha...

A、小V和方程 给定了n和m，问 的方法数，并且注意 0 1与1 0 是同一种方案那么我们知道，根号是不能通过加法去掉根号的，所以我们对m进行化简把完全平方数提出去得到前面的系数x。比如 我们得到2， 我们得到2那么题目就变成了，我们有x个苹果放在n个盘中里面的模型，允许有盘子是空的。解题分析：设f(m,n) 为m个苹果，n个盘子的放法数目，则先对n作讨论，当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m)  当n<=m：不同的放法可以分成两类：1、有至少一个盘子空着，即相当于f(m,n) = f(m,...

解题方法 给定地图，0代表没有地雷，1代表有地雷，我们每次选取的范围，问选定范围有地雷的区域数量。 1、首先我们尝试纯暴力，直接枚举全部的左上角点，这里要,再去枚举区间是否有地雷，如果取到最大的数据所要的时间这时间复杂度太爆炸了。 2、我们想想办法改进下，我们发现，每更换一个左上角的点，我们都要对区间全部的点重新计算，这里太花时间了。有没有办法让我们在的时间里面知道这里面有没有地雷呢？是有的，那就是二维前缀和。根据下面的图，我们知道，前区间有没有地雷只要即前缀和数组，是地图数组，为0没有地雷,为1既有地雷。这样预处理之后，我们就可以通过下面式子查询为左上角，的矩阵中如果下面式子不为0即有地雷。...

解题思路 前缀和，千万千万注意减法取模……我半个多小时。。区间问题，居然要全部转移那么最简单模拟的话，出题人变态一点，每个区间都是最左端和最右端。时间复杂度毫无疑问爆炸了这时候，昨天的直播课，雨巨小姐姐刚好又说到了区间问题的解决办法！！吹爆。每个步骤都去模拟太蠢了，想想能不能用前缀和代替一下。区间问题解决办法一般有前缀和，树状数组，线段树，码量也是依次增大，当然能力也是依次增大。放到这个题目上，给出每个相邻点距离，我们选取1作为源点，一次前缀和，可以得到每个点到1的距离。第二个是物品数量，那么一次前缀和就可以得到区间内有多少物品。第三个，这个也是比较不好想的也是本题解题的关键。新开一个数组，存...

解题思路 思维转换，从地图起点找终点退出来，因为存在传送机，具体不能一遍普通的bfs跑出来，需要比较细心的处理细节。那么我们换个角度，如果我们把这个地图里的每个位置当作一个节点，去创建一个图会怎么样呢？初始化地图输入时，每一个可以转移的小数点，边权是1，这里注意一个细节，别建反图，没什么意义。q次输入，传送机起点和终点，边权是3。这样，这个问题就转换成了一个单源最短路，从的单源最短路了。/--------------------------------------------------------------------------------------------------------...

B、华华对月月的忠诚 辗转相减法（更相减损术），gcd与斐波那契数列的关系。先介绍下辗转相除法之外的辗转相减法。gcd(a,b)如果a>b那么会等于gcd(a-b,b)。如果b>a那么会等于gcd(a,b-a)，如果a，b相等此时就是gcd。还有一个结论就是 gcd(2a,2b) = 2gcd(a,b)多用于高精度，代替复杂的取模运算。先给结论 题目要求的答案 证明如下： import math a,b,n = map(int,input().split()) print(math.gcd(a,b)) C、Game 给定n，每次可以把n拆分成两个数相乘，第二个人对拆分出来的...

A、青蛙过河 是不是乍一眼看起来像哈诺塔……恭喜你被骗了。汉诺塔可以随意移动，虽然也有一定前提。但是对这个题目来说最要命的约束条件就是到了对面就不能动了。所以就决定了，一定是重的青蛙先跳去对面。所以我们从几个极端来看。如果给出莲叶数是n，石头数目是m。如果m是0，那么最多可以允许 n + 1 个青蛙，n个青蛙填满莲叶，最后一个青蛙跳过去。如果m是1，那么最多允许 n + 1 个青蛙先填满莲叶，在去石头上面过渡，另外的 n + 1 个青蛙根据 m = 0 的情况跳。所以一共 （n + 1） * 2……所以得到 n m 和答案的关系 每多一个垫脚石 答案乘个2。 #include <bit...

解题思路 区间dp又又又是区间dp；看来是个极其重要的动态规划模型吖！这里给出的数据规模小于等于30，很明显可以开下很多维的数组，运行的时间复杂度也很高。题目第二行给出的是每个节点的初始值。我们要找到一个前序序列，让题目给出的函数值最大。根据题目给出中序序列为 1 2 3 4 5 6 7 …… n那么树的样子一定是固定了的，与平衡树类似左子树的全部节点一定小于根节点，右子树大于。那么在知道这个前提下就很好去进行递推了。首选区间dp。从这里看出允许使用不带优化的区间dp，直接 怼上去就行了我们二维数组 dp[i][j]表示从 i 到 j 满足题目中序遍历为(i i+1 …… j)的最大值。那么状...

解题思路 终于有一个简单模拟了。虽然这题介绍一大堆，总结起来就是几句话，给出地图n列，前4行是a的地盘，后四行是b的地盘，每个人地盘上面有星号代表大炮。大炮会 3 * 3的波及周围，会一直传递，b先手，a立刻反击b出手的大炮，问b能不能消灭a全部的大炮，如果能最后剩余最大大炮数是几。那么很显然，我们发现a处于究极被动方，b是无敌主动方，我们通过方便一次跑图，把攻击一个地方，波及到周边的大炮都合并到一个点去。我们发现如果a最后的点数大于b的点数，那么b永远消灭不完a，输出-1。否则，对于b来说，反正我都要把你a消灭干净，谁先谁后没得关系。但是出手的大炮却可以控制，把一个点上大炮数量最少的拉上去当...

C、张老师的旅行 区间dp，动态规划众多模型中的一种，解决区间问题上有广泛的应用。基本思想就是一重循环枚举长度，还要一重循环枚举起点，终点就已经确定。关于决策点根据题目是否需要枚举或者优化成记录这里不展开。本题不需要枚举决策点，因为老师需要花费时间最短一定是从区间这一边一直走到另一边。 那么我们根据题目意思找到n小于等于1000，可以开下2维的数组，我们就通过区间dp去解题。使用一个三维数组，前两维表示左端点和右端点最后一个表示最后落点，0代表左端点，1代表右端点。它的值记录最短花费时间。那么我们可以发现状态转移分别是： 从左端点继续向左 从右端点继续向右 从左端点一路向右到右端点后一个位置...

给出的仅为我的做题顺序，与题目难度不一定匹配 F、排列计算 前缀和给定区间，可以控制区间元素加1，最后把区间元素的染色次数排序，从次数最大开始填最大的数。具体区间元素+1，又不用模拟去实现，直接在左端点处加1，右端点后面一个点减1即可。最后求前缀和就行。再把求好的前缀和数组排个序，大功告成 #include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #pragma GCC optimize(3) typedef long long ll; #define INF 0x3f3f3f3f const int...

F、牛牛的树行棋 博弈论sg函数与dfs。前导知识sg函数：SG函数： 首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。 对于任意状态 x ， 定义 SG(x) = mex(S),其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c)，那么SG(x) = mex{SG(a),SG(b),SG(c)}。 这样 集合S 的终态必然是空集，所以SG函数的终态为 SG(x) = 0,当且仅当 x ...

D、牛牛的01限定串 简单动态规划如果你学过这个或者见过这个模型的动态规划那么这题就是个很简单很简单的dp。）当然我不会，看了题解补提才马后炮的。题解表示，这种两种状态的字符串，特别是给定的长度，每位个数是多少个的，转换到一个n + 1,m + 1的棋盘去看。例如这题的第一个样例。转化成一个 7 行 3列的棋盘， 下标从0开始。先对模式S串处理，S串遇见一个0，我们把画笔向下画一格，S串遇见一个1，我们把画笔向右画一格。这样我们走到 (i , j)这个位置的时候就能很清楚的知道有几个 0 和几个 1 。那么在走的时候，再去赋值，棋盘把这些地方值改成对应的前缀值。后缀值就是反着过来一遍，把这些地...