bzoj刷题计划B

我已经做了26/50

UPD1:2017/7/22 开坑

UPD2:弃坑


1032: [JSOI2007]祖码Zuma

好神QAQ,区间dp,先把同色缩在一起,如果大小为1f[i][i]=1,反之为f[i][i]=2,考虑枚举区间断开点,然后特殊情况是端点颜色一样,考虑如果在一起>=3的话,直接f[s+1][t-1],反之为f[s+1][t-1]+1,这题数据有误,正确做法是还要去中间看下是否有与两端同色,有的话仍然是f[s+1][t-1]


4094: [Usaco2013 Dec]Optimal Milking

线段树,考虑每个区间维护1.选左不选右的答案2.选右不选左的答案3.选右选左的答案4.不选右不选左点的答案,然后合并的话自己yy下,修改就是找到那个叶节点,然后一路修改上去即可。时间复杂度O(n\log n)


1067: [SCOI2007]降雨量

由于有些年份未知(而且很大),做起来有点麻烦,我用的trick是,把每个已知年份、该年份+1、该年份-1,以及询问的年份,进行离散化。考虑没有被给定的年份,直接把他赋值为INF。然后建立ST表,维护区间最大值,这里需要两个,一个是只考虑已知年份,一个还要考虑没有出现的但实际存在的年份。

对于年份Y是自年份X以来降雨量最大,有几种情况

1.Y<X,显然输出false

2.Y,X年份的降雨量均未知,输出maybe

3.X年份降雨量已知,那么由于Y年份的降雨量一定不会超过X,如果两者年份之间,存在一已知年份的降雨量大于或等于X年份的降雨量,输出false,反之为maybe

4.Y年份降雨量已知,考虑两者年份之间已知的年份的降雨量是否有比Y大或等于的即可。没有的话考虑是否有未知年份,有的话maybe,没有就是true

5.如果X,Y都已知,那么同样要考虑两者年份之间已知的年份的降雨量是否有比Y大或等于的,在这之上还要满足Y年份降雨量比X年份降雨量小或等于。


1070: [SCOI2007]修车

每个工作人员拆成N个,每个表示该工作人员倒数第i个修某个人的车,费用为i*w表示这个点对后面(包括自己的贡献),然后直接最小费用最大流即可。


1072: [SCOI2007]perm

大力状压即可


1079: [SCOI2007]着色方案

大力DP,直接做状态太大,但是反过来设就够了,niubi


1084: [SCOI2005]最大子矩阵

m那么小直接分情况dp就行了。


1087: [SCOI2005]互不侵犯King

f[i][s][j]表示第i层的状态,前i层一共放了j个国王的方案数。大力转移即可。


1085: [SCOI2005]骑士精神

启发式搜索


1269: [AHOI2006]文本编辑器editor

大力splay


3875: [Ahoi2014]骑士游戏

一开始以为在环上的点都必须用魔法做掉,结果是我石乐志。。

很简单的DP,后效性用SPFA消去就行了。


1821: [JSOI2010]Group 部落划分

二分+并查集傻逼题


1068: [SCOI2007]压缩

区间DP即可。


1090: [SCOI2003]字符串折叠

同上


1196: [HNOI2006]公路修建问题

二分+并查集


1191: [HNOI2006]超级英雄Hero

匈牙利算法裸题


1103: [POI2007]大都市meg

修改父亲边,影响的一定是子树,以DFS序建立树状数组维护差分序列即可。


1095: [ZJOI2007]Hide 捉迷藏

妈妈我会写动态点分治啦~!

挺简单的QAQ,就是每个点向父重心连边,然后考虑每个点维护两个堆,再维护一个全局堆即可。


2299: [HAOI2011]向量

显然最终情况是每个坐标都可以表示为(\alpha 2a+\beta 2b)再加上单次的向量

用裴蜀定理即可。


2429: [HAOI2006]聪明的猴子

容易知道答案一定是一个后缀,把猴子的跳跃距离排序,n^{2}构造出需要的边,然后把边按边权排序,双指针扫描,第一个次弄出最小生成树的时候就是OK了。


2748: [HAOI2012]音量调节

无脑DP


2750: [HAOI2012]Road

考虑枚举每个点作为起点跑堆优化dijkstra

常用套路,考虑每条边的两端信息,如果知道起点到左端有多少条最短路,从右端出发,在当前起点的最短路图上有多少条最短路,且这条边在这张图里是一条最短路边,那么答案就是左右两端的值相乘。

考虑怎么去求这个值,第一个值显然可以直接DP,按照什么顺序?由于最短路要满足dist[u]+w=dist[v],所以我们大可以按照点到原点的距离来排序,顺着一遍DP。

怎么求第二个值,考虑倒着DP,每个点初始化为1,同样的方法去计算。

时间复杂度O(nm\log n)


2751: [HAOI2012]容易题(easy)

先考虑DP的做法,我们通过小情况很容易发现,答案满足f[i]=f[i-1]*C[i],其中f[i]表示n=i的答案,c[i]表示A[i]能取的值的和。

然后问题就转化为,求每个位能取的数之和的乘积

对于没有约束的位,显然就是\frac{(1+m)\times m}{2}

对于有约束的,直接减掉即可。

我用了三个map,一个维护标号,一个维护和,一个维护某个数是否出现过来做的,然后用个set记录下出现的数,我太懒了QAQ

没有约束的部分用快速幂来算即可。1A好开心~


1257: [CQOI2007]余数之和sum

我姿势还是太弱了QAQ

k\;mod\;i=k-\left\lfloor\frac{k}{i}\right\rfloor\times i

于是很容易发现\left\lfloor\frac{k}{i}\right\rfloor相同的时候是等差数列

显然只有根号段,暴力计算即可。


1912: [Apio2010]patrol 巡逻

考虑连接树上两个点,一定会形成一个环,这个环的长度就是这两个点树上的距离+1

通过观察我们发现,最优方案中,环上的边只会走一次,其他边均会走两次

那么我们的最优方案一定是最大化环的大小,那么第一个环肯定是树的直径

第二个环怎么办呢,我们把第一个环上的边都标为-1,这样就可以处理两个环相交的情况,交集照样走两次。

第一个树的直径可以用两次BFS求出,第二个因为有-1,不能BFS,用树形DP求即可(好像两个放一块也行,我为了方便标号。。就BFS了)


1123: [POI2008]BLO

答案为每个割点在生成树上的儿子的大小相乘,注意还要乘2以及算上自己和别人的边。在tarjan的时候直接做即可。


2730: [HNOI2012]矿场搭建

求出割点,看每个双联通分支能到达几个割点然后分类处理即可。


 

发表评论

电子邮件地址不会被公开。 必填项已用*标注