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

兔子的区间密码 思路 结论显然，我们从的二进制最高位出发，碰到的第一位不同的数即可得到从这一位向下，所有的二进制数位都可以得到为，因此我们只需要从高位开始枚举即可，然后得到第位是第一个不同位然后即可得到答案。 代码 #include <bits/stdc++.h> #define mp make_pair #define pb push_back using namespace std; typedef pair<int, int> pii; typedef long long ll; typedef unsigned long long ull; const doub...

Xor Path 思路 先是看错题目，以为是所有的路径异或值的和，然后好像用了个假的print函数，一直wa，，， 既然是异或，那么当一个点出现的次数是偶数次的时候它会被自己异或成零，也就是队整体的答案没有贡献度，所以我们只要统计有多少条路经过了这个点就行了。我们得到一个节点的每一个儿子的节点数量，然后再剩下不是当前节点中选择一个节点，两个建立一条边，计算得到当前节点的儿子连儿子构成的最短路对这个点的贡献度，然后再加上这个点与其儿子链接的贡献度即可，如果是奇数则异或上我们的答案，否则这个点将会对答案没有贡献。 代码 /* Author : lifehappy */ #pragma GCC op...

[CQOI2007]涂色PAINT 思路 显然我们可以考虑用来求解问题，碰到那种一眼没思路的题稳是没跑了，那么我们就往方面去考虑吧。 我们定义，表示把这个区间涂上颜色要用多少步，显然有， 接下来我们考虑如何使这个状态进行转移，当有两个邻近的颜色使一样的时候，我们可以把它们当成一种颜色一起涂色，所以当时，显然有，同样的这个性质可以拓展到整条链上，当，我们一定有。 这里我们已经把大多的情况给考虑完了，还剩下一种，这个时候我们显然要把这个区域分成两份来进行涂色，这个时候我们就可以枚举端点，然后取这些断点和的最小值就行。 代码 /* Author : lifehappy */ #pragma GCC ...

乌龟棋 思路 最优值问题，显然可以通过解决，我们定义表示到达这个点之前已经走过的价值最大的值(分别是走一步，走两步，走三步，走四步的数量)，显然这个点我们可以从或或者或者或者转移过来，因此我们只需要用四重循环来进行即可得到我们的最优值，同时输出答案加上点的权值即可。 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n'...

小A的柱状图 思路 经典的单调栈题目，对于每一个位置，我们维护他以当前高度可以到达的最左方，以及他当前高度可以到达的最有方，显然就有以他的高度的矩形块的面积就出来了，所以我们只需要统计n个矩形的最大值就行。 具体细节操作看代码注释。 代码 /* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> #define mp make_pair #define pb push_back #define endl '\n' using namespace ...

Rinne Loves Data Structure 思路 我们插入的位置大概分了四种：第一种  显然我们找到比当前插入的值的pre，也就是比当前节点大的最小值。第二种  我们只要找到当前节点的suc，也就是比当前节点小的，最大值。 第三种  我们只要找到当前节点的suc，也就是比当前节点小的，最大值。 第四种   显然我们找到比当前插入的值的pre，也就是比当前节点大的最小值。 综上，一，三我们可以直接去第二种是没有的，我们也可以直接特判，得到它的，更新第四种是没有的，我们可以直接特判，然后得到它的，所以 插入第一个元素的时候我们既没有前驱，也没有后驱，需要单独考虑。 最后加一个相同值的判定...

题目链接 思想 显然我们后面的决策是跟前一步相关的，因此我们可以考虑DP，可以用一个15维的数组来进行转移，但是这样显然回mle，所以我们考虑如何压缩状态，由于，所以我们可以有dp数组: ，表示可以涂1块木块的有多少种颜色，以此类推，表示上一次用的是可以涂个木块的颜色。 接下来就是考虑dp方程的转移了。举个例子：假设上一次用的颜色是可以涂5个块的，那么下一步的状态转移就会变成：  之所以是因为，上一步选的是5，所以转移过来的时候，这里面有一个是跟上一个块同颜色的，所以需要减去，其他情况同理。 考虑到数据比较小，并且这个dp方程有点难转移，因此我们可以考虑用记忆化搜索来进行dp转移。 代码 /*...