题目链接 这道题也是蛮有趣的。 有$2^n$个内存位，每个位置可以放一个数字，范围为$[0,2^m)$，第$i$个位置放$j$可以得到$w(i,j)$的收益，每个位置还有一个临界值$t_i$以及一个$u_i$。 除此之外，一旦有两个位置$a,b$满足以下两个条件，可额外获得$u_a$ xor $u_b$的收益。 $a$和$b$在二进制下只有一个bit不同。 $a$位置放的数不小于$t_a$或者$b$位置放的数不小于$t_b$。 求最大收益的一组方案。 如果不考虑额外收益，显然每个位置$i$放的都是使得$w(i,j)$最大的$j$。而考虑额外收益后，需要分两种情况，放的数小于等于$t_i$以及大于$t_i$。每种情况保留下来的一样都是使得$w(i,j)$最大的$j...

题目链接 还是一个很有趣的题。 有一个hash函数，方法为对一个数做至多40次诸如+= -= &= |= ^=..某个数的操作，求hash函数的最大值。 如果没有+=/-=那么这个题是非常轻松加愉快的，每一位是独立的，可以分开考虑。 但有+=/-=就有了进位的问题，就不是完全独立的了，但可以考虑把-=当做+=来看，每个加法是否进位状压一下，但N最大会有40，直接压需要$2^{40}$。 然后发现只要把相邻的加法合并起来，就只有不超过20个加号了。 设f[i][mask]为现在做到第i位，第i位上加法的进位的情况为mask的最大值。只要枚举一下这一位输入0还是1，就可以得到i+1位的进位情况，转移到下一层。 最后就是时限非常紧，而状态非常稀疏，需要好好优化一下。 ...

题目链接 坐标系上给定两个不相交的圆，求所有过一定点且与这两个圆都外切的圆。 反演 如果把以那个定点为原点进行反演变换，那么过定点的圆就变成了直线，不过定点的圆还是圆，问题就转化成了求那两个圆的公切线。求出所有公切线再反演回圆再判是否都是外切。 然后就没什么了。 233 Written with StackEdit.

题目链接 这也是个非常有趣的题。 有n个点，m条单向边，所有的边有一个流量限制，表示单位时间内只能通过那么多人。有K个人要从0点到n-1点，求最小时间，走过任意一条边的花费时间都为1。 这种模型肯定与网络流有关系。 如果从s到t就只有一条长度为d，流量为c的边。那么显然：从d时刻开始，每秒都会有c个人到达t点。 现在我们的问题就是把原网络拆成很多条这样的路径(d,c)。使得其效率最高。显然的是路径之间不会有任何影响。 可以注意到，路径的长度看起来是越短越优，越短就可以提前把人送到t点，就提醒到每次都要找尽可能短的增广路径，而这个就是最小费用流能解决的问题。在原图上跑最小费用流，每次增广一出一条路径，就把这条路径的属性(d,c)记下来，每次增广出来的d都是不下降的。这样就实现...

题目链接 A.Always Cook Mushroom 给定一个1000x1000的点阵，m组询问，每次询问一个由(0,0)、(x,0)点一以及从原点出发的方向向量(a,b)构成的直角三角形包围的点的权值和。 预处理出这1e6个点的极角关系序，离线，将询问也按(a,b)的极角排序。然后只需想象一根表针在逆时针的扫，把扫过的点的权值加到树状数组中，对于每一个询问也仅仅是一个前缀和。 这题其实还是挺简单的啊……前期读错题了到后面也没来得及看。 叉姐说存在一个枚举1000x1000个点极角序的方法，就免去了排序的过程。(法雷序列) B.Building 平面上有n个建筑，每个建筑由$(x_i,h_i)$表示，m组询问在某一个点能看到天空的视角范围大小。 离线。可以看出对...

FD大法好!买买买！ A.Post Robot 买买买！索尼大法好！ 每个需要识别的串长度最长只有6，暴力就好啦。 B.Boring String Problem 在线询问给定字符串的字典序第K小的子串，需要去重，相同输出左边界最小的。用后缀数组来做最好理解，排好序后每个后缀对子串的贡献为$|S|-sa[i]-height[i]$。就可以用二分来定位子串在哪以及长度$len$。 但对于相同的还要输出最靠左的，如果找到的子串的位置并不是$sa[i]$最小的，更小的只可能出现在$i$位置的下面。所以再进行一次二分，找到LCP为$len$能伸到的最大后缀，再区间取$sa[]$的$min$。 C.Paint Pearls 有一段序列，涂连续一段子序列的代价为该子序列出现不同数字个数的平...