洛谷P2607 [ZJOI2008]骑士
DP 题解 OI https://www.luogu.org/problemnew/show/P2607https://www.luogu.org/problemnew/show/P2607 经典题，n个点n条边的图一定是一个基环树森林，于是可以先DFS一遍把环找出来，再断环（在环上随便找一条边，强制两个端点之一不选），就变成了一个没有上司的舞会了。 123456789101112131...
洛谷P3195 [HNOI2008]玩具装箱TOY
DP 题解 OI https://www.luogu.org/problemnew/show/P3195https://www.luogu.org/problemnew/show/P3195 经典的一道斜率优化DP,很久以前写的,现在再拿出来复习一下 简单读题可以得出本题的DP方程是 但是这样转移的复杂度高达,5e4的数据不能接受,需要优化. 为了简便计算,令. 假设存在决策和(),...
Codeforces Global Round 2
题解 OI 人生第一次rated的CF比赛，难度Div2到Div1都有，题比较多，像我这种蒟蒻就只能做前五道题了…… 感觉做前面的题的时候要相信直觉，不要想太多（时间只有两小时） A. Ilya and a Colorful Walk 签到题，直接两边各自往中间走就对了 123456789101112131415161718192021222324252627#include <ios...
CF733E Sleep in Class [思维题]
思维题 题解 OI https://www.luogu.org/problemnew/show/CF733Ehttps://www.luogu.org/problemnew/show/CF733E 题意 一个人站在楼梯上，楼梯编号1到n，每一层楼梯上面都有着标识，'U'代表这个人上楼，'D'代表这个人下楼，每当这个人离开这一层楼梯，这层楼梯的标识改变，U变成D，D变成U。 现在的问题是，询问...
CF786A Berzerk
博弈论 题解 OI https://www.luogu.org/problemnew/show/CF786Ahttps://www.luogu.org/problemnew/show/CF786A 切着切着搜索水题就做到它了。鉴于我还没有正式的学过博弈论，就写篇题解纪念一下吧。 题意 有一个物品放在n个排成一圈的点上，初始放在第2到n号点，甲乙各有一个数集，每次操作时可以将这个物品向后移动s格(s是集合中的数)，判断物品位于每个起始位置时，二人的胜负情况。
CF95B Lucky Numbers [毒瘤分类讨论贪心/DFS]
思维题 贪心 题解 OI https://www.luogu.org/problemnew/show/CF95Bhttps://www.luogu.org/problemnew/show/CF95B 其实代码用不着这么多goto，不过写着方便~ 详细分析有时间再写吧 123456789101112131415161718192021222324252627282930313233343536...
CF696A Lorenzo Von Matterhorn
思维题 题解 OI https://www.luogu.org/problemnew/show/CF696Ahttps://www.luogu.org/problemnew/show/CF696A 我打赌这道题如果n=1e5，绝对八成的人都会打树剖 然而n高达1e18，所以建图是不可能的了。注意观察q只有1000，就是说只会涉及最多2000个点，因此就可以离散化+LCA瞎搞。然而这是一颗...
CF832D Misha, Grisha and Underground
LCA 题解 OI https://www.luogu.org/problemnew/show/CF832Dhttps://www.luogu.org/problemnew/show/CF832D 简单LCA求距离，令a为汇合点，那么答案就是(dis(a,b) + dis(a,c) - dis(b,c)) / 2 + 1，dis用lca求出，枚举a就好。 当然也可以一一讨论abc的位置关系，...
CF932D Tree
LCA 题解 OI https://www.luogu.org/problemnew/show/CF932Dhttps://www.luogu.org/problemnew/show/CF932D 题意 一棵树开始只有一个1号点，权值为0，两种操作： 1 R W 在R号点下面加一个cnt+1号点 2 R X 从R号点开始向祖先走，依次选择R的祖先，要求权值依次增大，且已选择的点权值之和小于...
洛谷P2783 有机化学之神偶尔会做作弊（水黑题系列）
SCC LCA 题解 OI https://www.luogu.org/problemnew/show/P2783https://www.luogu.org/problemnew/show/P2783 这个题看上去好像是tarjan缩点后直接LCA判距离，其实也是这样…… 但是一般的tarjan求SCC写法过不了，题目也强调了两个碳不成环，因此可以 先DFS一遍双向边变单向边 或者tarj...