BZOJ水题乱斗3

继续开坑~

余28

相对重要的部分

新技能点:

斯坦纳树 (bzoj 4006,bzoj 2595,bzoj 3205)

Yen's Algorithm (bzoj 1073)

数位dp 简单题模板 (bzoj 4029,bzoj 3329,bzoj 1833)

块状树(bzoj 3720,bzoj 3731)

块状树与树上莫队(bzoj 4129,bzoj 3757)

Keep Continue...

AC problems SHOW~

进度:37/22
[upd 10.30] 囤题开始

[upd:10.31] 今天要屯10道题

1089: [SCOI2003]严格n元树\(f_i=f_{i-1}^n,ans=f_d-f_{d-1}\) ,BigInteger大法好

4698: Sdoi2008 Sandy的卡片:建立SAM,然后对每个串的每个子串暴力更新

1059: [ZJOI2007]矩阵游戏:考虑换完后的图的对角线,发现上面所有点在换后不在同行换前也不在同行,列同理,二分图匹配

1047: [HAOI2007]理想的正方形:先跑单调队列压行,再对列跑单调队列

1052: [HAOI2007]覆盖问题:贪心,用一个矩形把点框起来,显然第一个正方形摆在其中一个角,剩下的递归。

1037: [ZJOI2008]生日聚会Party: dp,\(f_{i,j,k,l}\)表示前i个数有j个1时,后缀的1的个数-0的个数最多为k最少为 l的方案数,然后4维dp

1202: [HNOI2005]狡猾的商人:带权并查集

1213: [HNOI2004]高精度开根:python跑高精

1093: [ZJOI2007]最大半连通子图:tarjen,topsort,dp

3223: Tyvj 1729 文艺平衡树:splay

[upd:11.2 4节课我上~不下去]


10题gets

3994: [SDOI2015]约数个数和大爷证明

[upd 11.3] 再做11题就能屯50了……太快了点

1483: [HNOI2009]梦幻布丁:一开始以为和sdoi的染色差不多,后来发现随便拿2个set直接启发式合并就行,其实还能拿链表启发式合并,复杂度O(nlogn)。

3999: [TJOI2015]旅游:树剖,考研手写能力的时候到了~

4006: [JLOI2015]管道连接:斯坦纳树~现以加入模板豪华午餐

2595: [Wc2008]游览计划:把边权挪到点上,注意

输出具体的图……spfa时存一下路径

3205: [Apio2013]机器人:斯坦纳树,应为边权均为1所以要用BFS代替SPFA.

4029: [HEOI2015]定价:枚举……如现在的数为140,那么141,142,……,149显然都可以跳过;现在的数为10000,那么10001,10002,……,19999都可以跳过

3329: Xorequ:数位dp也需要板子的

1833: [ZJOI2010]count 数字计数 :求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次。

我有板~

4590: [Shoi2015]自动刷题机:二分


3812: 主旋律:论文题啊~http://blog.csdn.net/PoPoQQQ/article/details/45059247

[upd 11.8]1个星期过去屯了2/5,有进步

1055: [HAOI2008]玩具取名:区间dp

4001: [TJOI2015]概率论:生成函数论文题,可以找规律\(f[n]=\frac {n(n+1)} {2(2n-1)}\)

1081: [SCOI2005]超级格雷码:打表找规律

这么明显的规律……

1082: [SCOI2005]栅栏:USACO原题

题解By me:http://blog.csdn.net/nike0good/article/details/51887253#g-gzp-bureaucracy-and-girlfriend

1207: [HNOI2004]打鼹鼠\(f[i]=max(1,f[j]+1) (dis(i,j)<=t[i]-t[j])\)

1054: [HAOI2008]移动玩具:状压BFS

2956: 模积和:枚举\((n/i)\),\((m/i)\)

2958: 序列染色:dp,\(f_{i,j,k}\)表示第i位为k且目前进展到(未进展,B进展,BW均进展)

1073: [SCOI2007]kshortYen‘s Algorithm 解决 简单路第k短路 加入豪华午餐


CF 734F】:Anton and School 重要公式get \(a\&b+a|b =a+b\)

CF 734E】:Anton and Tree 把树相同颜色连通块缩为一个节点,则不难发现答案为该意义下的直径一半(向上取整)

1196: [HNOI2006]公路修建问题:克鲁斯卡尔算法

1083: [SCOI2005]繁忙的都市:克鲁斯卡尔算法

1094: [ZJOI2007]粒子运动:强行运动规划

3720: Gty的妹子树块状树,支持

  • 树上点权修改
  • 询问以u为根的子树中,严格大于x的值的个数。
  • 添加一个编号为"当前树中节点数+1"的节点,其父节点为u,其权值为x。

n,m<=100000

块状树 版题

3731: Gty的超级妹子树:在上题基础上支持删边

显然删边后只要对把一个块拆成2块,算上排序,复杂度为O(blogb),b为块大小

3757: 苹果树:先按块状树分块,然后以编号为关键字对询问跑莫队, 注意将一条链跳到令一条链上的方法

假设是 (l,r) -> (u,v)

先对链(l,u)上的元素存在性取反,

对链(u,v)上的元素存在性取反,

证:

我们用(l,r)表示当前l到r这条链上的答案(不包括lca),现在考虑从(l,r)转移到(L,R) 
我们发现,(l,r)=ans(root,l) xor ans(root,r),这样正好去掉了lca 
那么我们这样考虑:(root,l)−>(root,L)
(root,l)=ans(root,root) xor ans(root,l)
(root,L)=ans(root,root) xor ans(root,L)
(root,l) xor (root,L) = (l,L)

继续观察发现,(root,l)−>(root,L)是将(l,L)反色了 

交不了...不过应该是对的

3759: Hungergame:gauss消元

证明:http://blog.csdn.net/popoqqq/article/details/41519895

CF 739B】:Alyona and a tree 树上dp+差分序列,读错题目好气啊

CF 739C】:Alyona and towers 线段树要维护7个值,没时间了好气啊

1177: [Apio2009]Oil:分6种分割情况讨论


1264: [AHOI2006]基因匹配Match:由于只有\(a_i=b_j\)的时候才更新,那么直接维护\(f[i][]\)表示上一个字符到第i个时下面的串,这显然可以用树状数组维护

1293: [SCOI2009]生日礼物:先将序列离散化,从左到右枚举起点,终点显然在后面可以用双指针推,由于有k个颜色那么设k个指针。复杂度\(O(nk)\)

1306: [CQOI2009]match循环赛:搜索+剪枝,考虑

  • 一支队搜完后是后分数正确

  • 搜索中途胜分不可超出

  • (不一定要加)剩下的局全赢是否能凑够分

1296: [SCOI2009]粉刷匠:每一层dp,再对所有层背包

1218: [HNOI2003]激光炸弹:暴力

3505: [Cqoi2014]数三角形:简单统计

1297: [SCOI2009]迷路:如果所有边权为1,那么原题可用经典的矩阵乘法解决。现在考虑对原图重构以”还差k秒到达第i个点”为\(P(i,k)\),然后建图即可。

3107: [cqoi2013]二进制a+b:构造题,方法见http://blog.csdn.net/PoPoQQQ/article/details/48006557

1210: [HNOI2004]邮递员:插头dp,ans=矩阵的哈密尔顿单回路数*2,记得特判n=1或m=1的情况。

3125: CITY:插头dp,有一些块只可上下,左右通过,分类讨论