题意: 给出一颗树，请你找出最长的一条链，这条链上所有数值的GCD要大于1.并输出最长链的长度。 这题参考了 小熠小熠很不容易 大佬的思路。 思路就是，先建一棵树，然后从根开始搜索，这里要注意根不一定是1,要自己找根。 然后再搜索的时候，每次计算下GCD，如果GCD大于1，那么是满足条件的，我们继续往下搜索。如果等于1，那么说明当前长度不能继续变长了，我们就重置这个树链长度为1.  这种思路应该非常好理解的，就相当于暴力的搜索下去，边搜边记录答案即可。 还有一种求质因子的方式本弱还没弄明白。。。。 AC代码: #include <bits/stdc++.h> #define int...

题意： 一个长度为n的数组，初始值都是0，给出2个操作：操作1： 区间[l:r] 加1操作2： 执行操作编号在[l,r]内的所有操作各一次 求最后序列是多少？ 分析： 1、首先操作2是在之前操作再进行一次，所以我们可以先统计当前这个位置被操作了多少次，怎么统计呢，每个2的操作是对前面操作的重复，所以我们把操作从后往前跑，维护差分数组，求后缀和。 2、其次我们计算答案的时候，也是维护差分数组。最后答案就是前缀和跑一下。 详细看代码： #include <bits/stdc++.h> #define int long long using namespace std; const in...

首先做这题的时候，题目就吸引了我，梦三国这游戏正好在玩！！！ 题意:有n名游戏玩家，现在有m个服务器，每个服务器能服务区间[l:r]里面的人，并且有人数限制问你如何安排使得游戏玩家同时在线人数尽可能多？ 分析: 首先，我们肯定是编号小的塞到前面的区间，把当前编号的人塞到右区间靠前的区间里，这里我们用优先队列来实现，优先队列里的排序规则先按照右端点小的排序，再按照服务器承载人数小的来排序。 读入的区间我们也需要排序，按照左区间、右区间、区间承载人数依次排序即可。 最后从编号为1的游戏玩家开始遍历到n的游戏玩家，每次需要需要再队列头判断，当前游戏玩家编号是不是大于队列顶端的r值，如果大于，说明当前...

题意: 给出一个长度为n的序列 n<=1000 ,存在一个置换。 按照置换规则重新变成1-n 需要多少次？ 对于所有可能的对应关系，有多少种可能的排数？ 例如 原序列是1 2 3 给出置换规则 1->2 2->3 3->1 1 2 3 2 3 1 3 1 2 1 2 3 我们发现，置换了3次就恢复原序列了。  分析: 感谢sunsetcolors大佬的思路, 我们可以把这个置换看做一个图, 那么我们可以发现，置换必定出先循环节上面这个1 2 3 例子，置换的循环节就是3.也就是说，我们要恢复，需要3次 = 循环节长度。 再举个例子，例如 1->2->3-&g...

题意: 给出n个顶点，n-1条边的树，问节点间距离为2的权值乘积和，最大权值乘积是多少？ 思路: 遍历每个节点，每个节点的儿子节点的的距离就是2，把儿子节点的权值乘起来就好。 类似于 ab+ac+ad=a(b+c+d) 的思路去写。 代码： #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC opt...

题意 : 给出2个序列，一个是a序列，一个是w序列。 定义：f(l,r)=区间[l,r] ai*Wr−l+1让你求的是L:[1-r] R:[L-r] 所有f(l,r)求和 分析: 一开始由于没看n的大小，暴力维护所有区间的值，前缀和来统计。但是n=3e5的话，复杂度就是 (n+1)*n/2妥妥T了。  通过手写前几项，可以发现一定规律当n=3 ans= (a1+a2+a3)w1+(a1+2a2+a3)w2+(a1+a2+a3)w3当n=4 ans= (a1+a2+a3+a4)w1+(a1+2a2+2a3+a4)w2+(a1+2a2+2a3+a4)w3+(a1+a2+a3+a4)w4当n=5 a...

感谢sunsetcolors大佬的博客，提供思路 首先题意需要仔细看，大致就是，给你一棵树，开始每个点权都是0，m次操作，每次操作会把这个点在树上距离小于等于1的点权都加1. 并且把这个点权和距离小于等于1的点权都加起来为k， ans=k*i。 i表示每次操作的编号 分析: 由于m=1000000很大。建树暴力加是妥妥TLE了。本人亲测只能对30。 那么这题的突破口就是树上距离小于等于1的点，可以从每个点影响周围点的贡献入手。 一个点无非就是影响他的儿子，他的父亲，他自己。 所以只要把 这个点父亲节点的贡献+这个点儿子节点的贡献+这个点本身的贡献 就完事了 定义数组 now[x] 表示节点x被...

题意:给出一个小写字符串，让你按照题目规则压缩成最短的字符串。压缩规则: 重复的部分可以压缩在一起，M表示重复部分开始标记，R表示从M开始的部分重复一次。 分析: 如果没有M的条件，我们考虑区间dp[i][j][0]表示区间[i:j]没有M，那么我们就直接压缩dp[i][j][0]=min(dp[i][j][0],dp[i][k][0]+j-k) k属于[i,j) j-k表示后半段的长度 如果有M的条件，我们考虑dp[i][j][1]，分成2段来压缩，中间加个M.所以转移方程dp[i][j][1]=min(dp[i][j][1],min(dp[i][k][0],dp[i][k][1])+min...

这题看了好久，没什么想法，看完大佬们的题解说是暴力搜索dfs。 题意: 给出一个矩形蛋糕，长x，宽y 。要求份给n个人，切n-1刀，要求每个蛋糕面积一样，求每个蛋糕的长比宽的最大的最小值。 分析: n最大才10，可以考虑搜索来解决。可以分成2中情况，第一种就是平行x轴切，第二种就是平行y轴切，每一次切都会变成2个蛋糕。 设计一个函数 dfs(double x,double y,int k) x表示长， y表示宽， k表示还要分成k个蛋糕。dfs里面枚举每一刀的位置。每一块的长最小是x/k，宽最小是y/k。那么每一刀的位置也就是x/k和y/k的倍数，只要枚举这个倍数，然后对应计算出位置即可。 A...

这是一道动态规划的题。 题意:给出一个长度为n的字符串，n最大1000000。 每个字符代表一种特殊含义。 0：这个格子没有烈焰，且其左右两个格子均没有烈焰1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰2：这个格子没有烈焰，且其左右两个格子中均有烈焰*：这个格子有烈焰？：未告诉你本格情况 求所有的方案数 分析: 可以发现，第i位方案数，和前一位和后一位有关系。 前一位可以通过转移方程来解决，所以还剩下当前位i、当前位i是否有火、i+1位是否有火。  所以我们需要一个三维数组来表示dp  dp[i][0/1][0/1]  i:表示第i位第一个[0/1]: 表示第i位有没有火，有火就用1来表...

这是一道经典dp 的题目！ 题目意思大致就是: 给出一个序列，问你任意删除m个字符，有不同种方案？ 每个数字的范围在k之内。 我们可以设 dp[i][j] 表示前i个元素删除j个元素后的方案数 很容易推出dp方程: dp[i][j]=dp[i-1][j-1]+dp[i-1][j]意思就是 前i个元素删j个=要么我这个i位置的数不删，那么就从前i-1个数中删j个，或者我这个i位置给他删掉，那么就从前i-1个数中删j-1个，(因为i位置被删了，所以只要删j-1个就够了) 但是会出现重复的情况，比如 下面这个例子 1 2 4 5 6 7 4  比如我们i跑到了第7个位置，此时a[7]=4.我们可以发...