P6753 [BalticOI 2013 Day1] Ball Machine 题意 给你一个树，每次从根节点放一个求，如果其子节点有空这个球会向下滚，若有多个节点为空则找儿子中以子树内编号的最小值为优先级从小到大找第一个为空的位置滚。 有两种操作，第一种插入若干个球，输出最后一个球到的节点编号；第二种删除一个位置，此时若有可以向下滚的球那么这个球就会滚，输出有多少个球滚了。 保证...

P6845 [CEOI2019] Dynamic Diameter 题意 一颗带权树，每次更改一条边的权，每次修改后求出最大直径。强制在线。 思路 \(O(n\log^2n)\) 的暴力做法。 根据经典结论，对于两个点集的树上最大直径（权值非负），并集点集的树上最大直径的端点一定是原四个端点中的两个。 那么我们就可以用线段树维护点集，合并时 \(O(\log n)\) 查询两点...

P7324 [WC2021] 表达式求值 闲话 WC2021 我只得了 20 分，三道题总共 20 分。我是下场了突然后知后觉这件事的，主要原因是我开了 C++11，然后 T1 T2 都没分了。在洛谷上测本来能拿银牌的。T1 的乱搞能拿 48，还挺高的。 幸亏咱们陕西省选不看冬令营成绩。幸亏是在省选前犯的这个错误。告诫后人和自己，写题前一定要看编译选项，否则只能后悔莫及。 T2 ...

P7003 [NEERC2013]Hack Protection 题意 给定一个序列 \(a\) ，求有多少个区间满足区间内的数的异或和等于与的和的值。 思路 首先我们求一个异或前缀和 \(s\)，对于每一个区间 \([l,r]\) ，它的贡献为区间内按位与的和等于 \(s_r \bigoplus s_{l-1}\) 的段的个数。 设 \(x\) 为某个区间的按位与的和，...

P6982 [NEERC2015]Jump 题意 给你一个未知的 01 串，每次可以输出询问一个 01 串，如果该串中正确的个数刚好等于 \(n\) 或者 \(n/2\) ，将会返回相应的答案，否则会返回 0 。求出这个串。（询问次数不大于 \(n+500\)，\(n\leq 1000\)） 思路 先无视询问次数，我们来想一下确定性算法怎么做。 第一步，我们来试着找出 \(...

P7473 [NOI Online 2021 入门组] 重力球 题意 给你一个正方形平面，某些位置有障碍，对于平面上两个球，每次你可以改变重力方向使两个球下落到最底端，求使两个球位置重合的最小改变重力次数。障碍固定，多次询问两个球的位置。 思路 考虑最暴力的想法，总共有 \(n^4\) 种状态，即两个球的坐标。 考虑优化状态数，发现只有障碍物（边界）旁边（四联通）的位置才有用。...

P7362 [eJOI 2020 Day2] XOR Sort 题意 给你一个长度为 \(n\) 的序列，每次操作可以将一个数异或上相邻的一个数，求将序列改为严格单调递增序列或严格单调不降序列的操作次数的操作序列。 注意，改为严格单调递增序列的数据 \(n\leq 200\) 且每个数不相同，改为严格单调不降序列的数据 \(n\leq 1000\)。 不要求操作次数最小，次数需...

poj1944 一道我不会做的贪心题。 （思维才是OI的重点） 但是if您也不会，那就来听我瞎扯吧。 首先，这个图是一个圈，只能连接邻点，使所有求的点联通。 我们先不考虑环，那么就可以想出一个假的做法：用一个a数组记录入度和出度，出度为正，入度为负，用一个sum=0从0遍历每个点记录当前出入度，每次加ai，若sum大于0给答案加上1就行了。 然后，我们来考虑环。我们发现。不管怎么...

因为是单向边，牛儿来回的路径长度并不相同，所以需要用两次 dijkstra，一次正向从 \(x\) 开始 dijkstra，再将边全部反向存再来一次。 因为是板子题比较良心 \(n\) 比较小，我们就可以用矩阵来存储啦。如果 \(n\) 比较大的话，我的想法是再造一个图，同时反向存边。内存可能占用比较大但是想起来简单。 代码很短。 12345678910111213141516...

对树状数组的理解加深了！ 转化题意 动态维护一个单调不降和一个单调不增序列，每次修改后输出两序列取最小值后的最大值和其最大位置。 思路 首先，阅读原题，知道最后答案一定是某个战士的温度，所以我们将温度离散化。 再次阅读，发现冰系是一个（以温度为自变量的）单调不降序列，每次修改一个战士就是修改一段后缀。火系相反，修改前缀。 深度阅读，发现题目其实就是求两个序列的交点。于是转化成上述...