好吧我会写游记。Click More

不能更水的一道题。

记录[tex]aaaaa\cdots \rightarrow current[/tex](即我们当前DP到的串)的[tex]first[/tex](第一个数),[tex]last[/tex](最后一个数),[tex]cnt[/tex](数的个数),[tex]sum[/tex](数的和)以及[tex]ans[/tex](这段的答案)。往上做时可以直接合并信息。

需要预处理某一位为[tex]x[/tex]接下来的位任意的时候的信息。

一血!!

首先枚举[tex]{threshold}_A[/tex],然后二分算出最小的[tex]{threshold}_B[/tex]。判断可行性时可以用2-SAT。

这样是[tex]O(n^4log(n))[/tex]的。注意到可能的[tex]{threshold}_A[/tex]只可能是矩阵的最大生成树中的边和对最大生成树黑白染色以后同色之间的最大权值，这样复杂度就变成[tex]O(n^3log(n))[/tex]了。

250:

首先对原数列进行排序，然后对每一个数[tex]ai[i][/tex]枚举[tex][ai[i]-k,ai[i]][/tex]作为序列的起点，然后变过来的数一定是原数列的一段。接着[tex]O(n^2)[/tex]爆搜即可，总复杂度[tex]O(n^2 k^2)[/tex]。

600:

把所有的障碍和每一个障碍[tex](x,y)[/tex]的周边[tex]x-1[/tex]、[tex]x+1[/tex]、[tex]y-1[/tex]、[tex]y+1[/tex]一起离散化，建图以后跑SSSP即可。

1000:

首先自己必须赢两局。能造成影响的只有[tex][yourScore+1,yourScore+6][/tex]这段区间，所以二分放出去的队数，剩下的贪心判断。证明我还不会，会了以后发上来("你还欠着一个呢!!!")。

250:

贪心即可。每次找到所有没有被覆盖的区间的右端点的最大值，然后找到所有能够覆盖这个点的区间中右端点最右边的区间，干掉它。

500:

先检查所有点是否有对应位置，算出平移向量，然后判断一个三元一次方程有没有整数解。要做两种情况，分别是正的和负的。

900:

容斥+状压。先枚举st,表示st里的没有访问两次，别的不管。然后用[tex]O(B_{popcount(st)})[/tex]暴力枚举拆分，计算对答案的贡献。首先预处理满足包含[tex]i[/tex]且被[tex]j[/tex]包含的方案数目[tex]pre[i][j][/tex]，这一步竟然是[tex]O(4^n)[/tex]的……

http://adf.ly/1AMzrK = (http://cleverbot.com)

可以和一个什么都懂*的机器人聊天！

*不一定什么都懂，肯定不懂逗逼问题

首先统计[tex]Circle \rightarrow Square \rightarrow Circle[/tex]的情况([tex]Square \rightarrow Circle \rightarrow Square[/tex]可以对称算)。首先求出每个[tex]Circle[/tex]里面有几个[tex]Square[/tex]和每个[tex]Square[/tex]在几个[tex]Circle[/tex]里面(坐标变换+扫描线即可)。每个[tex]Square[/tex]对答案的贡献是[tex]- \frac{Count \times (Count-1)}{2}[/tex](因为下一步要重复计算)。此扫过所有的[tex]Circle[/tex](假设现在要求[tex]min[/tex]),[tex]Circle[i][/tex]对答案的贡献是[tex]\sum_{j=1}^{i-1}min(Count[i],Count[j])[/tex]。这个用树状数组就行了。[tex]max[/tex]同理。

这饼图被我搞得太可怕了。

鸣谢xyz111提供主要想法。 orz xyz111

首先求出每一层有多少个节点。如果一层中的个数[tex]num[i] \leq k[/tex]，那么这一层可以直接一次运行完毕。如果[tex]num[i]>k[/tex]，那么就开始一段，直到这一段的平均数小于等于[tex]k[/tex]，对答案的贡献是[tex]\lceil\frac{sum}{k}\rceil[/tex]（sum是这一段的和）。证明Under Construction，好了以后会写上来的。

然后就是求出[tex]k=1 \rightarrow n[/tex]的答案。注意到对于一个[tex]k[/tex]，最多只有[tex]\frac{n}{k}[/tex]个段起始点，所有的段长度的和也最多只有[tex]\frac{n}{k}[/tex]，所以使用链表维护段起始点可以做到[tex]O(nlog(n))[/tex]的时间复杂度。