昨天，一年一度的多校联合又开始了。第一场我们队仅做出三道题。其中两道是比较快就想到思路的，另外一道虽然刚开始就想到了正解，但由于感觉数据范围较大，所以纠结了好久才过。其他几题总是感觉思路欠缺一点。不过比去年做多校时的情况已经好了很多，至少赛后能够做出大部分题了。
1001. OO’s Sequence
简单的统计问题。
题目大意：给出数列a[1..n]，定义函数f(l, r)为在[l, r]区间内没有其他数是a[i]的因子的i(l <= i <= r)的个数。求 sum(f[i][j])(1 <= i <= n, 1 <= j <= n)
我们考虑每个数字a[i]对答案的贡献。即看他在几个区间内满足题目要求的性质。
我们可以找出他左边第一个是他的因子的数和右边第一个是他的因子的数的位置，分别记为l, r。那么他对答案的贡献就为区间的个数：(i - l) × (j - r)。
由于每个a[i]均不大，仅有10000，我们可以O(n*100)的时间内预处理出l r数组。
1002. Assignment
也是一道统计问题。
题目大意：对于给定的序列a[1..n]，求出其所有的满足区间中任意两数的差都小于k的区间个数。
我们当时是采用了一种比较丑的算法来解决这道题的。
我们枚举每个数，并强制认为它是区间中的最小值，然后看它前面和后面最长能延伸到哪，这个也可以采用和第一题相似的预处理。即预处理出每个数前后第一个比他大于等于k的数(在第一个比他大的数的基础上二分)和第一个比他小的数。之后区间个数的算法也和第一题相同。
标准解法是通过ST求出区间最大和最小值，枚举区间起点后根据ST函数二分区间终点，或根据单调性O(n)的推过去。
1003. Bombing plan
树形dp
题目大意:一个树,n~1e5个点,每个点有一个权值,表示可以如果炸掉它,就可以免费炸掉距离他小于等于w[i]的点.每个点的权值<=100; 问最少炸几个可以全部炸完.
首先是一个点有一定范围的树上的dp.以前做过的是可以开二维dp[i][j],i是被j点控制的,j不限于i的子树. 但是这道题不能开二维,但是因为权值小于等于100,所以 用g[i][j]表示i为根的子树,从外面获取了炸到i的fa j的长度的权利.
i点是1,i的儿子是2…. 这样j=0就是没有外界提供. 考虑转移g[i][j]:对于儿子v, 并不是单纯的g[v][j-1],而是对于v来说,从外界获取的小于等于j-1的g, 以及v可以向外面扩充的所有的j.(因为并不一定缺恰好i-1最好,我们先定义的都是恰好,可能反倒向外扩充一个东西更好).
所以我们要额外维护一个f[u][i],表示的是可以向外扩充i的距离的最小值.这样我们再根据实际重新定义下:f[u][i]指u点向外扩充大于等于i的最小值,g[u][i]表示u点从fa需要获取的小于等于i的长度的最小值,可能也往外放,(只要小于等于获取的值就行).
这样怎么转移? f[u][i]是横叉dp过去,强制当前的是要提供i的,其他的都用g[i]就行. g[u][i]每一个点都用g[v][i-1]. 然后重点来了,我们这样算出来的是恰好值,需要每一个点算完之后 都弄成实际意义的小于等于的值.
重点：
- 树上一个点有控制范围.多开一维描述范围.
- g不够用,想明白恰好和满足限制下最小值的区别,额外增加f
- f和g的转移,之后再取最值.
1004. Candy Distribution
一道比较难想的dp
题目大意：有n种糖果，每一种有ai 个，将糖果分给A，B两个人，两人得到的数量相同，问一共有多少种分法。N <= 200 ai <= 200
一共糖果的数量有40000种，考虑f[][][] 表示第i 种糖果分完时A有j 个糖果，B有k 个糖果状态太多。
因为只要求两者数量相同，f[][] 表示第I 种糖果分完时，两者糖果数量的差值。
但是直接求得话复杂度是nw^2.于是我们考虑每个f[i][j] 对 f[i+1][j] 的贡献。可以知道：
F[i][j] -> f[i+1][j] 的贡献是 f[i][j] * ((a[i]/2) + 1)
F[i][j] -> f[i+1][j-1] 的贡献是 f[i][j] * (((a[i]-1)/2) + 1)
F[i][j] -> f[i+1][j-2] 的贡献是 f[i][j] * (((a[i]-2)/2) + 1)
那么j的差值每增加2 贡献的倍数就少了1
分奇偶对下一层进行标记，例如1 2 3 4 3 2 1这样的等差数列，只需在1的时候另差值加一，在4的时候把差值减回来，相当于等差数列二次差分。
1005. Pocket Cube
不做评价
1006. Tree chain problem
树形dp+链上统计
题目大意：给出一棵树,n~1e5,然后给出m~1e5条特殊的链,每个链有一个权值.现在在树上挑选不相交的链,使得最后的拿到的权值最大.
看一个点,是树形dp,但是发现如果u是root,枚举过u的链,发现要暴力求和链上周围的点的dp和.这样会超时. 于是想到快速求一条链的和.
为了好写,我们把求链上连接的儿子的dp值的和转化到链上的权值. sum[u]指u的所有儿子的dp和,这个好想,那么一条链上的其实就是(sum[u] - 所有链上儿子d+链上儿子的sum-链上儿子儿子的d….),总结就是链上除了root,其他的点权值都是sum[v]-d[v].而root的权值是sum[root].
我们是算d[u]的时候才用的,当时d[u]肯定就是0. 所以求链上的权值和. 我们有两种求法
邓爷教的标序+lca. 这样求的是路径,我们用一种常用的方法,把i的值归到i到他fa的那条边上. 这样我们求路径+sum[root]就行了.
用树链剖分. 映射到树状数组上,每次求和.
1007. Tricks Device
基础图论
题目大意：对于给出的图，有一个人要从1走到n，并且他只会走最初的最短路。另一个人不想让他走到n，于是他需要删一些边。问最少删几条边第一个人就无法通过最开始的最短路走到n了，以及最多删几条边之后第一个人仍能通过最短路走到n。
首先，需要通过spfa找出所有的最短路。在找出所有最短路后，第二问就相当于将所有位于最短路上的边长视为1，再求一遍1到n的最短路。由于这个由最短路组成的是一个DAG，所以可以通过dp来解决这个问题。
对于第一问，这相当于求由最短路组成的图的最小割。我们虽然最开始就想到了用最大流来求，但由于数据范围较大，以为还会有其他的解法。于是YY了一个半dp半贪心的方法。交上去发现WA了，后来我们发现那种解法是错的，于是就改成了网络流，本来以为会TLE，不过发现居然A了……
1008. Unstable
计算几何
题目大意：平面上有四个点A、B、C、D，E、F分别是AB、CD的中点，已知AB、BC、CD、DA、EF的长度，求出满足该长度的A B C D四点坐标
根据中点的性质，做辅助线得到一个三边长度都已知的三角形，这样，我们固定两个点的坐标，即可得到第三点的坐标（通过求两个圆的交点）。之后做法类似。
这道题的重点是如何构造出一个三边均已知的三角形。
1009. Annoying problem
树上的统计问题。
题目大意：给出一个带边权的树，有两种操作：
- 将节点x放入集合
- 将节点x移除集合
问每次操作后，将所有在集合里面的点连起来的子树的权值和最小是多少。
这道题刚开始没什么思路。后来想到了用set来记录集合中的元素。如果要插入一个点x，就要看x和集合中所有点的LCA最近是多少，也想到了通过找比x小的最大的和比x大的最小的两个节点，然后比较他们的LCA，找出其中较近的LCA，之后在将对应边上的权值加上去。删点操作类似。
但是如何维护权值和的变化没有想清楚。LCA由于之前接触的较少(之前也是自己利用dfs序YY的一种野生写法)，写起来有点卡。
赛后发现我们的想法已经和正解非常接近了。我们通过维护每个点到根结点的距离dist就可以方便的维护权值变化。在找到比x小的最大的节点和比x大的最小的节点之后，不用比较两个LCA到底该取哪个，而是通过统一的公式dist[x] - dist[lca(l, x)] - dist[lca(r, x)] + dist[lca(l, r)]来计算权值和的增减。
1010. Y sequence
数学+迭代
题目大意：Yellowstar likes integers so much that he listed all positive integers in ascending order,but he hates those numbers which can be written as a^b (a, b are positive integers,2<=b<=r),so he removed them all.Yellowstar calls the sequence that formed by the rest integers“Y sequence”.When r=3,The first few items of it are：
2,3,5,6,7,10……
Given positive integers n and r，you should output Y(n)(the n-th number of Y sequence.It is obvious that Y(1)=2 whatever r is).
n<=2*10^18,2<=r<=62,T<=30000.
首先正着想,给出一个n,求出它里面有几个合法的数. 先去掉2, 再去掉3,在加上6…就是这样容斥. 和莫比乌斯函数一样.提供符号. 然后容次来算, 注意. 之后二分合法的x,就是结果.
但是
这道题时间卡的很紧,有下面的优化;
容斥大于62的值直接不算.因为只有1,那么我们把一都不算,他们就都是0了,因此容次就大约是60的复杂度.(用莫比乌斯打表也一样)
每次算不二分,而是用迭代. 最终结果x-f(x)=n, 我们写x=n+f(x).先把n当x算n+f(n),这个值一定小于等于x,那么就n+f(ans) 这个值也一定小于等于x,并且一直都是小于等于,并且一直再增加. 于是几次迭代就得到了.
重点：
- 发现容次直接可以正着算有几个.
- 容次的优化,去掉1之后很多0.
- 二分和迭代的学习
1011. Solid Geometry Homework
二分图染色
题目大意：三维空间中有一些无限的平面和球面，这些面将空间分为了几块，现在需要用红黄两种颜色对这些空间进行染色，并使相邻的两个空间的颜色不相同。此外，已经确定了一些点的颜色是黄色，问是否能够成功染色，以及另外一些点的颜色是什么。
由于比赛时通过的人数较少，当时并没有看这道题。
我们可以发现，如果平面全都是无限延伸的，那么将所有相邻的空间之间连边的话，所得的图是一个二分图。
我们仅需要考虑给出的点所在的空间。如果两个点所在的空间是相邻的，那么他们仅对一个曲面是在异侧的，对其余曲面皆在同侧。
因此我们将每一个点代入所有曲面方程，大于0返回1，小于0返回0，并将所有值异或起来，这样得到的函数即为这个点要染的颜色(因为这样满足相邻的点的函数值不同，且仅有两个函数值)。
之后我们可以检查所有颜色是黄色的点是否函数值相同，如果不相同则无解，如果没有给出颜色为黄色的点则解不唯一，否则可以判断出所有点的颜色。
这道题的难点主要在于用异或的形式来确定每个点所处空间的颜色。
1012. Circles Game
扫描线+树上SG
题目大意：在平面上有20000个圆，他们彼此之间没有交点，A，B两人进行博弈。其中一人选取其中的一个圆后，其中的每一个园（包括本身）都会消失。当其中一人没有圆可选，那么他就输了。
首先应该表示圆之间的位置关系。利用扫描线，首先将圆分为上半圆和下半圆，考虑任意的一个上半圆，如果在此时的x值（扫描线）下，他上面最近的一个圆弧是上半圆，那么它被这个圆直接包含。如果是下半圆，这个圆和这个圆被同一个圆包含，或是都没有被圆包含。下面离他最近的圆弧(不含它本身)，也是同样的考虑。
建立好圆之间的关系后可以发现，必然是多颗树。
这个时候利用树上nim计算sg 函数的值，先把每个根节点由同一个新建的节点为父节点。Sg ^= (sg[son] + 1);dfs一下就好。