搜索结果
查询Tags标签： 题解，共有 1043条记录-
洛谷P2458题解
题面 和这个题很像，但是本题有一个花费而那一题没有，所以我们要把 \(f\) 数组开大一维。 \(f_{i,j}\) 表示节点 \(i\) 为根的子树在 \(i\) 点是 \(j\) 状态下的最小花费。 状态可以参照我的题解。 那一个题解写得很含糊，这里再讲一遍。 分三种状态：让父亲覆盖自己； 自…
2021/8/14 6:05:45 人评论 次浏览 -
Dance with a stick 题解(思维)
题目链接 题目思路 居然是个imo题目链接 感觉应该不会再有了吧。。。。 结论就是经过某个点的直线，使得左右两侧的点个数相同 向量取\((-1,1e9)\) 代码 #include<bits/stdc++.h> #define fi first #define se second #define debug cout<<"I AM HERE&qu…
2021/8/13 23:08:38 人评论 次浏览 -
Dance with a stick 题解(思维)
题目链接 题目思路 居然是个imo题目链接 感觉应该不会再有了吧。。。。 结论就是经过某个点的直线，使得左右两侧的点个数相同 向量取\((-1,1e9)\) 代码 #include<bits/stdc++.h> #define fi first #define se second #define debug cout<<"I AM HERE&qu…
2021/8/13 23:08:38 人评论 次浏览 -
【NOIP2016提高A组模拟9.9】Brothers 题解
【NOIP2016提高A组模拟9.9】Brothers Description 在遥远的西方有一个古老的王国，国王将他的王国分成了网格状，每一块称之为一个城市。在国王临死前，他将这些城市分给了自己的N个儿子（编号为0到N-1）。然而这N个王子的关系不是很好，0讨厌1，1讨厌2，2讨厌3……N-1讨厌…
2021/8/13 23:07:12 人评论 次浏览 -
【NOIP2016提高A组模拟9.9】Brothers 题解
【NOIP2016提高A组模拟9.9】Brothers Description 在遥远的西方有一个古老的王国，国王将他的王国分成了网格状，每一块称之为一个城市。在国王临死前，他将这些城市分给了自己的N个儿子（编号为0到N-1）。然而这N个王子的关系不是很好，0讨厌1，1讨厌2，2讨厌3……N-1讨厌…
2021/8/13 23:07:12 人评论 次浏览 -
CF219D题解
题面 一道看上去像道换根DP但可以用其他方法水过去的题目，正解显然是换根DP。 考虑换根DP两个步骤，一个是求 \(f_1\) ，第二是由 \(f_u\) 推出 \(f_v\) 。 先是状态的定义。 \(f_i\) 表示以 \(i\) 为根的答案。 然后考虑"反向边"怎么存，因为不能不存。这个可…
2021/8/13 6:06:01 人评论 次浏览 -
CF219D题解
题面 一道看上去像道换根DP但可以用其他方法水过去的题目，正解显然是换根DP。 考虑换根DP两个步骤，一个是求 \(f_1\) ，第二是由 \(f_u\) 推出 \(f_v\) 。 先是状态的定义。 \(f_i\) 表示以 \(i\) 为根的答案。 然后考虑"反向边"怎么存，因为不能不存。这个可…
2021/8/13 6:06:01 人评论 次浏览 -
题解 P3224 [HNOI2012]永无乡
题目链接 前置知识：kruskal 重构树，主席树 来讲一种目前题解区里没有，使用 kruskal 重构树和主席树，且时间复杂度为一个 log 的做法。 题目大意是给定一张点数为 \(n\) ，初始边数为 \(m\) 的无向图，图中每个点有一个权值，然后有 \(q\) 个操作，每个操作可能…
2021/8/12 23:07:16 人评论 次浏览 -
题解 P3224 [HNOI2012]永无乡
题目链接 前置知识：kruskal 重构树，主席树 来讲一种目前题解区里没有，使用 kruskal 重构树和主席树，且时间复杂度为一个 log 的做法。 题目大意是给定一张点数为 \(n\) ，初始边数为 \(m\) 的无向图，图中每个点有一个权值，然后有 \(q\) 个操作，每个操作可能…
2021/8/12 23:07:16 人评论 次浏览 -
最大数maxnumber - 题解【树状数组】
原题：现在请求你维护一个数列，要求提供以下两种操作： 1、 查询操作。语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。 2、 插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行…
2021/8/12 6:07:53 人评论 次浏览 -
最大数maxnumber - 题解【树状数组】
原题：现在请求你维护一个数列，要求提供以下两种操作： 1、 查询操作。语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。 2、 插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行…
2021/8/12 6:07:53 人评论 次浏览 -
题解 Cicada 拿衣服
传送门 神仙题！ 听@Yubai给我讲了半个下午，快%@Yubai见到这些奇奇怪怪的题是不是应该试着证下状态数上界啊首先观察题目里给的柿子，可以发现 \(or-and\) 单调增， \(min-max\) 单调减 神仙思路，发现对于一个给定的左端点，我怀疑出题人是左撇子，不同的 \(or-and\) 最…
2021/8/11 23:07:12 人评论 次浏览 -
题解 Cicada 拿衣服
传送门 神仙题！ 听@Yubai给我讲了半个下午，快%@Yubai见到这些奇奇怪怪的题是不是应该试着证下状态数上界啊首先观察题目里给的柿子，可以发现 \(or-and\) 单调增， \(min-max\) 单调减 神仙思路，发现对于一个给定的左端点，我怀疑出题人是左撇子，不同的 \(or-and\) 最…
2021/8/11 23:07:12 人评论 次浏览 -
洛谷P2395题解
题面 看到数据范围显然是个状压DP。 考虑记录两个数组， \(dis\) 和 \(f\) 。\(dis\) 数组表示当前状态走了多少路程， \(f\) 数组表示当前状态有多少种走法。 显然 \(dis\) 数组可以随便推，在当前状态中随便取一位 \(p\) ，然后计算 \(dis_s=dis_{s-p}+dis_p\) 即可。 但…
2021/8/11 6:05:50 人评论 次浏览 -
洛谷P2395题解
题面 看到数据范围显然是个状压DP。 考虑记录两个数组， \(dis\) 和 \(f\) 。\(dis\) 数组表示当前状态走了多少路程， \(f\) 数组表示当前状态有多少种走法。 显然 \(dis\) 数组可以随便推，在当前状态中随便取一位 \(p\) ，然后计算 \(dis_s=dis_{s-p}+dis_p\) 即可。 但…
2021/8/11 6:05:50 人评论 次浏览
