⊙__⊙

题解

/ 注册

全部文章 / 题解（共23篇）

最长树链

题意: 给出一颗树，请你找出最长的一条链，这条链上所有数值的GCD要大于1.并输出最长链的长度。这题参考了小熠小熠很不容易大佬的思路。思路就是，先建一棵树，然后从根开始搜索，这里要注意根不一定是1,要自己找根。然后再搜索的时候，每次计算下GCD，如果GCD大于1，那么是满足条件的...

2021-01-14

0 866

筱玛爱线段树

题意：一个长度为n的数组，初始值都是0，给出2个操作：操作1：区间[l:r] 加1操作2：执行操作编号在[l,r]内的所有操作各一次求最后序列是多少？分析： 1、首先操作2是在之前操作再进行一次，所以我们可以先统计当前这个位置被操作了多少次，怎么统计呢，每个2的操作是对前...

2020-10-13

3 665

网络优化(贪心算法)

首先做这题的时候，题目就吸引了我，梦三国这游戏正好在玩！！！题意:有n名游戏玩家，现在有m个服务器，每个服务器能服务区间[l:r]里面的人，并且有人数限制问你如何安排使得游戏玩家同时在线人数尽可能多？分析: 首先，我们肯定是编号小的塞到前面的区间，把当前编号的人塞到右区间靠前的区间里，这里...

2020-10-03

4 767

[SCOI2009]游戏

题意: 给出一个长度为n的序列 n<=1000 ,存在一个置换。按照置换规则重新变成1-n 需要多少次？对于所有可能的对应关系，有多少种可能的排数？例如原序列是1 2 3 给出置换规则 1->2 2->3 3->1 1 2 3 ...

2020-09-21

1 1296

联合权值

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

2020-09-18

0 744

区间权值

题意 : 给出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 901

点权和

感谢sunsetcolors大佬的博客，提供思路首先题意需要仔细看，大致就是，给你一棵树，开始每个点权都是0，m次操作，每次操作会把这个点在树上距离小于等于1的点权都加1. 并且把这个点权和距离小于等于1的点权都加起来为k， ans=k*i。 i表示每次操作的编号分析: 由于m=1000000很...

2020-07-15

2 1119

[SCOI2007]压缩

题意:给出一个小写字符串，让你按照题目规则压缩成最短的字符串。压缩规则: 重复的部分可以压缩在一起，M表示重复部分开始标记，R表示从M开始的部分重复一次。分析: 如果没有M的条件，我们考虑区间dp[i][j][0]表示区间[i:j]没有M，那么我们就直接压缩dp[i][j][0]=min(dp[...

2020-07-14

0 887

[SCOI2009]生日快乐

这题看了好久，没什么想法，看完大佬们的题解说是暴力搜索dfs。题意: 给出一个矩形蛋糕，长x，宽y 。要求份给n个人，切n-1刀，要求每个蛋糕面积一样，求每个蛋糕的长比宽的最大的最小值。分析: n最大才10，可以考虑搜索来解决。可以分成2中情况，第一种就是平行x轴切，第二种就是平行y轴切，每一...

2020-07-14

0 763

「火」皇家烈焰

这是一道动态规划的题。题意:给出一个长度为n的字符串，n最大1000000。每个字符代表一种特殊含义。 0：这个格子没有烈焰，且其左右两个格子均没有烈焰1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰2：这个格子没有烈焰，且其左右两个格子中均有烈焰*：这个格子有烈焰？：未告诉你本格情况求所...

2020-07-10

0 908