lifehappy

题解

未归档(1) 每日一题(2)

/ 注册

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

小A的最短路

小A的最短路思路树上问题求两个点的最短距离，显然能用来进行的查询，引入了两个无边权的点，所以我们的路劲就可以规划成三种，只要在这三个当中取一个最小值就行了。接下来就是考虑求了，有一种较为快速的求的在线方法，那就是树链剖分，于是套上去(个人认为树剖求较为好写)，然后就可以开始最短路求解了。代码 ...

2020-07-31

1 685

兔子的区间密码

兔子的区间密码思路结论显然，我们从的二进制最高位出发，碰到的第一位不同的数即可得到从这一位向下，所有的二进制数位都可以得到为，因此我们只需要从高位开始枚举即可，然后得到第位是第一个不同位然后即可得到答案。代码 #include <bits/stdc++.h> #define mp ...

2020-07-30

6 834

Xor Path

Xor Path 思路先是看错题目，以为是所有的路径异或值的和，然后好像用了个假的print函数，一直wa，，，既然是异或，那么当一个点出现的次数是偶数次的时候它会被自己异或成零，也就是队整体的答案没有贡献度，所以我们只要统计有多少条路经过了这个点就行了。我们得到一个节点的每一个儿子的节点数量，...

2020-07-29

2 680

[CQOI2007]涂色PAINT

[CQOI2007]涂色PAINT 思路显然我们可以考虑用来求解问题，碰到那种一眼没思路的题稳是没跑了，那么我们就往方面去考虑吧。我们定义，表示把这个区间涂上颜色要用多少步，显然有，接下来我们考虑如何使这个状态进行转移，当有两个邻近的颜色使一样的时候，我们可以把它们当成一种颜色一起涂色，所以当...

2020-07-27

1 737

乌龟棋(DP)

乌龟棋思路最优值问题，显然可以通过解决，我们定义表示到达这个点之前已经走过的价值最大的值(分别是走一步，走两步，走三步，走四步的数量)，显然这个点我们可以从或或者或者或者转移过来，因此我们只需要用四重循环来进行即可得到我们的最优值，同时输出答案加上点的权值即可。代码 /* Author :...

2020-07-24

1 684

小A的柱状图

小A的柱状图思路经典的单调栈题目，对于每一个位置，我们维护他以当前高度可以到达的最左方，以及他当前高度可以到达的最有方，显然就有以他的高度的矩形块的面积就出来了，所以我们只需要统计n个矩形的最大值就行。具体细节操作看代码注释。代码 /* Author : lifehappy */ #pr...

2020-07-23

3 759

Rinne Loves Data Structure

Rinne Loves Data Structure 思路我们插入的位置大概分了四种：第一种显然我们找到比当前插入的值的pre，也就是比当前节点大的最小值。第二种我们只要找到当前节点的suc，也就是比当前节点小的，最大值。第三种我们只要找到当前节点的suc，也就是比当前节点小的，最大...

2020-07-21

3 1027

[SCOI2008]着色方案(DP)

题目链接思想显然我们后面的决策是跟前一步相关的，因此我们可以考虑DP，可以用一个15维的数组来进行转移，但是这样显然回mle，所以我们考虑如何压缩状态，由于，所以我们可以有dp数组: ，表示可以涂1块木块的有多少种颜色，以此类推，表示上一次用的是可以涂个木块的颜色。接下来就是考虑dp方程的转移...

2020-07-17

0 659