⊙__⊙
⊙__⊙
全部文章
题解
归档
标签
去牛客网
登录
/
注册
⊙__⊙的博客
愿,自己不再辜负自己,奇迹不再辜负奇迹
全部文章
/ 题解
(共23篇)
最长树链
题意: 给出一颗树,请你找出最长的一条链,这条链上所有数值的GCD要大于1.并输出最长链的长度。 这题参考了 小熠小熠很不容易 大佬的思路。 思路就是,先建一棵树,然后从根开始搜索,这里要注意根不一定是1,要自己找根。 然后再搜索的时候,每次计算下GCD,如果GCD大于1,那么是满足条件的...
2021-01-14
0
883
筱玛爱线段树
题意: 一个长度为n的数组,初始值都是0,给出2个操作:操作1: 区间[l:r] 加1操作2: 执行操作编号在[l,r]内的所有操作各一次 求最后序列是多少? 分析: 1、首先操作2是在之前操作再进行一次,所以我们可以先统计当前这个位置被操作了多少次,怎么统计呢,每个2的操作是对前...
2020-10-13
3
675
网络优化(贪心算法)
首先做这题的时候,题目就吸引了我,梦三国这游戏正好在玩!!! 题意:有n名游戏玩家,现在有m个服务器,每个服务器能服务区间[l:r]里面的人,并且有人数限制问你如何安排使得游戏玩家同时在线人数尽可能多? 分析: 首先,我们肯定是编号小的塞到前面的区间,把当前编号的人塞到右区间靠前的区间里,这里...
2020-10-03
4
777
[SCOI2009]游戏
题意: 给出一个长度为n的序列 n<=1000 ,存在一个置换。 按照置换规则重新变成1-n 需要多少次? 对于所有可能的对应关系,有多少种可能的排数? 例如 原序列是1 2 3 给出置换规则 1->2 2->3 3->1 1 2 3 ...
2020-09-21
1
1305
联合权值
题意: 给出n个顶点,n-1条边的树,问节点间距离为2的权值乘积和,最大权值乘积是多少? 思路: 遍历每个节点,每个节点的儿子节点的的距离就是2,把儿子节点的权值乘起来就好。 类似于 ab+ac+ad=a(b+c+d) 的思路去写。 代码: #pragma GCC optimize(1) #pr...
2020-09-18
0
754
区间权值
题意 : 给出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了。...
2020-07-20
0
912
点权和
感谢sunsetcolors大佬的博客,提供思路 首先题意需要仔细看,大致就是,给你一棵树,开始每个点权都是0,m次操作,每次操作会把这个点在树上距离小于等于1的点权都加1. 并且把这个点权和距离小于等于1的点权都加起来为k, ans=k*i。 i表示每次操作的编号 分析: 由于m=1000000很...
2020-07-15
2
1130
[SCOI2007]压缩
题意:给出一个小写字符串,让你按照题目规则压缩成最短的字符串。压缩规则: 重复的部分可以压缩在一起,M表示重复部分开始标记,R表示从M开始的部分重复一次。 分析: 如果没有M的条件,我们考虑区间dp[i][j][0]表示区间[i:j]没有M,那么我们就直接压缩dp[i][j][0]=min(dp[...
2020-07-14
0
899
[SCOI2009]生日快乐
这题看了好久,没什么想法,看完大佬们的题解说是暴力搜索dfs。 题意: 给出一个矩形蛋糕,长x,宽y 。要求份给n个人,切n-1刀,要求每个蛋糕面积一样,求每个蛋糕的长比宽的最大的最小值。 分析: n最大才10,可以考虑搜索来解决。可以分成2中情况,第一种就是平行x轴切,第二种就是平行y轴切,每一...
2020-07-14
0
767
「火」皇家烈焰
这是一道动态规划的题。 题意:给出一个长度为n的字符串,n最大1000000。 每个字符代表一种特殊含义。 0:这个格子没有烈焰,且其左右两个格子均没有烈焰1:这个格子没有烈焰,且其左右两个格子中只有一个烈焰2:这个格子没有烈焰,且其左右两个格子中均有烈焰*:这个格子有烈焰?:未告诉你本格情况 求所...
2020-07-10
0
920
首页
上一页
1
2
3
下一页
末页