ZJOI 2012 Round 1 Solution

Problem 1: Ai,Ai+1可以由Ai/2,Ai/2+1推出。递归即可。

Problem 2:我们将所有相邻的3角形间连一条边,容易看出答案是最长链长度+1。

Problem 3:

我们反过来计算所有内部为空的矩形个数。

我们一行行扫描,计算底边在当前行的空矩形个数。

令hc为第c列往上,在碰到障碍或底边之前,有几个空格子。

那么h1,h2,…,hm就决定当前的图。

拿个个图画一下,从最底下往上考虑,可以发现这构成了一个树形结构。

注意到将全体h+1很好实现,将一个h改成0,就意味着把树切成了两部分,由于随机数据,树高是logn的。。

复杂度就是nlogn。

SRM 537 solution

275:

注意到其实只要X,Y能够凑出A和B就行了。。。

那么如果只用X就能凑出A和B,答案显然是-1

否则的话Y的值肯定在1到200之间。。枚举即可。

500:

注意到xor的性质,每一位是独立的,分别计算dp就行了。。。

975:

这个题目是个挺显然的网络流问题。。具体是怎么建图。。

我们讲(a->b)容量c的边,拆成(a->b)容量1,费用正无穷的边,和(a->b)容量c-1,费用1的边。

这样就能保证一条边至少经过一次。

求出这个图的无源汇最大费用流即可。

可以使用消圈算法。

不过要判断一下不连通的情况。。。

Codeforces Round #110 (Div. 1) Solution

A:暴力水题。
B:暴力水题。
A,B具体可参考我CF上的代码。

C:注意到只要两个串长度相等且各个数位的和相等,就可以互相转换,所以简单的dp预处理就能O1询问答案。
D:公式题,http://hi.baidu.com/wjbzbmr/blog/item/5aa2143735bc450391ef3953.html 有证明。

E:我们不妨直接暴力dp,考虑数位d,假设n在d下有len位,那么状态就是(d+1)^len (每位是?或者[0,d-1]),注意到d=2的时候。。状态数非常多,我昨天晚上的想法是固定前几位然后后面再dp,tourist的算法就是这个,我比较弱没写出来。。不过,注意到我们可以一次算很多个素数!比如我们可以计算余2*3*5*7*11的结果。。。。这样再暴力dp。。能卡过。。。