题目大意：有一棵 n 个节点的树，每条边长度为 1，颜色为黑或白。 可以执行若干次如下操作：选择一条简单路径，反转路径上所有边的颜色。 对于某些边，要求在操作结束时为某一种颜色。 给定每条边的初始颜色，求最小操作数，以及满足操作数最小时，最小的操作路径长度和。 没想到还有人Day3能考285分 orz %%% 这道题看了题解也有点迷（主要是太短了）…

最近教练安排得比较紧，没时间更新博客了，最后10多天好好努力吧！不要让自己后悔！ 「同じ世界に、立っていたんだ」と “在同一个世界 站起来了” 「同じ未来に、立っているんだ」と “也会站在同一个未来” 距离NOIP2018还剩 [wpcdt-countdown id="415"]

一道水题，觉得用了点小技巧就放上来了。 首先是读入，前些天看了本省rank1的NOIP2017时间复杂度的代码，%%%全省最短（100分里面），读入用的是自定义的快读。说实话，以后字符串读入都用这种方式就好了，挺方便的。 还有就是用二进制表示状态，前几天考试也是靠这个骗了80分，最近还学了“位图”这种神奇的东西，感觉整个人都二进制了。 代码 [cr…

题目描述 在一个地区中有 n 个村庄，编号为 1, 2, ..., n。有 n – 1 条道路连接着这些村 庄，每条道路刚好连接两个村庄，从任何一个村庄，都可以通过这些道路到达其 他任一个村庄。每条道路的长度均为 1 个单位。 为保证该地区的安全，巡警车每天要到所有的道路上巡逻。警察局设在编号 为 1 的村庄里，每天巡警车总是从警察局出发，最终又回…

题目描述 在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件： 路径上的所有点的出边所指向的点都直接或间接与终点连通。 在满足条件 1的情况下使路径最短。 注意：图 G 中可能存在重边和自环，题目保证终点没有出边。 请你输出符合条件的路径的长度。 输入输出格式 输入格式： 第一行有两个用…

Q1:编译器是什么版本 by Chen_Xi 玄学，windows上应该都是MinGW5.x Q2:可以提前进机房嘛？ by Chen_Xi 好像是可以提前半个小时进去的。 Q3:看不懂题目怎么办？ by 匿名 建议学好语文。 Q4:关于SPFA已死怎么看？ by hzy 用于判断负环还是挺有效的，不过这种题目也挺少的吧。个人最短路径偏爱写Dijk…

zkw大佬的PPT——统计的力量 虽然说这里有一些错误，但是zkw神犇讲的东西还是挺让人震撼的。 操作一：区间查询，单点修改 练习例题 CodeVS1080 这大概是zkw线段树最简单的操作了 如果你看过PPT的话，会发现我们对树的结点的访问是根据结点的二进制数来实现的： 子结点是父结点右移1位得到的，其中右子结点+1 所以说，叶子结点的最左边的那…

题解 看到网上很多dfs，bfs，记忆化搜索的代码（其实这个主要也是深搜），但是本校大佬@Ajsoabk用了一个神奇的方法，把它转化成一个线段覆盖的问题。 首先用了一便深搜，如果所有的蓄水池都建了，能不能满足要求，不满足就直接输出，满足说明肯定有解，下一步。 确保了有解之后，我们就可以从每个能建蓄水池的城市出发，走到沙漠城市，能够走到的沙漠城市一定…

题目描述 H 国有 n个城市，这 n 个城市用 n−1条双向道路相互连通构成一棵树，1号城市是首都，也是树中的根节点。 H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注…

样例输入 [crayon-67ee4447ae31c133839702/] 样例输出 [crayon-67ee4447ae322862749479/] 题解 算法分析摘自《2013全国信息学奥林匹克年鉴》 算法分析 这道题主要考察同学们对最短路算法的理解。（我考试的时候怎么没看出来orz） 本题是一个很典型的最短路模型的题目。 假设我们把棋盘的局面…