P6106 [Ynoi2010] Self Adjusting Top Tree 题意 给出平面直角坐标系上若干不与坐标轴平行的处于第一象限的互不相交的线段，多次询问平面中一个第一象限的矩形与这些线段相交部分的长度长度和与所有线段长度和的比值。给出的所有坐标 \(\in[1,10^6]\)。 思路 假设所有线段的斜率都是正的，考虑将询问差分成四个前缀矩形。我们只需要考虑统计若干斜...

P5471- K-D tree优化建图-弹跳 优化建图是一种思想。 题意 有\(n\)个城市分布在小鸟岛上，有\(m\)个弹弓分布在这些城市里。因为弹弓体积大，固定麻烦，所以每个弹弓只能把小鸟弹飞到一块固定的矩形范围内的城市，同时小鸟会在空中滞留\(t_i\)的时间。闪电黄的家在1号城市，追求速度的它想知道，若只使用弹弓出行，它从家到其他所有城市的最短时间花费是多少。 抱歉魔...

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

P6295 有标号 DAG 计数 题意 求 \(n\) 个点有标号弱联通 DAG 数量。 推导 设 \(f_i\) 表示 \(i\) 个点有标号 DAG 数量（不保证弱联通），有： \[ f(i)=\sum_{j=1}^i\binom ij(-1)^{j-1}f(i-j)2^{j(i-j)} \] 意义为选至少 \(j\) 个度数为零的点，向剩下的 \(i-j\) 个点随...

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

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\) 为某个区间的按位与的和，...

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

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

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