题解 BZOJ 1089 [SCOI2003]严格n元树

设$f[i]$表示深度不超过i的严格n元树的数量。 有$f[i]=f[i-1]^n+1$。 $Ans=f[d]-f[d-1]$ 递推式很显然。 代码: n,d=map(int,raw_input().split()) f=[0]*17 f[0]=1 for i in range(1,d+1): f[i]=f[i-1]**n+1 print f[d]-f[d-1] 这个题目答...

三月 24, 2015 · 1 分钟 · 100 字 · Ruotian

题解 BZOJ 3586 字符串生成器

题意: 有一个字符串生成器,初始时生成的字符串为空串,它每次按照给定概率随机生成一个小写字母,加在当前已生成字符串的后面。 给定N个长度为L的字...

三月 21, 2015 · 1 分钟 · 469 字 · Ruotian

题解 BZOJ 3489 A simple rmq problem

给出M个询问:在[l,r]之间找到一个在这个区间里只出现过一次的数 强制在线。 设$p[i]$为$a[i]$上一次出现位置,$q[i]$为$a[i]$下一次出现位置。 每次查询的就是 $ max _{l<=i<=r} a[i] $ 且$q[i] >r$ , $p[i]< l $。 可以排序然后树套树做。 偷懒写了KD-TREE。。复杂度$O(n^{5/3})$,不强制在线的话可以做到$O(n^{3/2})$ 。 ...

三月 20, 2015 · 1 分钟 · 332 字 · Ruotian

题解 BZOJ 2280 [Poi2011]Plot

给出一系列点p_1, p_2, … , p_n,将其分成不多余m个连续的段,第i段内求一个点q_i,使得q_i到这段内点的距离的最大值的最大值最小 最大值最...

三月 20, 2015 · 1 分钟 · 412 字 · Ruotian

题解 BZOJ 3611 [Heoi2014]大工程

去年省选的题。 突然发现还没有A这个题。 就抽时间写了写。 询问的那个树形dp很好搞。 我们把原树中有用的点(被选的点,和他们之间的lca)拿出来,...

三月 18, 2015 · 1 分钟 · 295 字 · Ruotian

题解 BZOJ 2212 [Poi2011]Tree Rotations

学习 http://www.docin.com/p-598829500.html 线段树合并中的一道例题。 详细见那个课件。 复杂度$O(nlgn)$. 需要注意下空间 code: #include<cstdio>#include<cstring>#include<algorithm>using namespace std; typedef long long LL; int n; int LS[400005],RS[400005]; int cc; int Root; int w[400005]; int siz[400005]; int ls[15000500],rs[15000500],sum[15000500]; int num; int stk[15000500],top; int...

三月 18, 2015 · 1 分钟 · 180 字 · Ruotian

题解 BZOJ 2758 Blinker的噩梦

题意: 给你n个不相交的凸多边形或圆,每个图形有一个权值。 询问m次,从一个点到另一个点,穿越过的图形的权值异或和。 题解: 扫描线+树链剖分。 这些...

三月 17, 2015 · 2 分钟 · 831 字 · Ruotian

bzoj-problem-chooser

今天上午无聊写了这个。 BZOJ抽题助手。 估价函数综合 AC率,AC人数,提交人数,随机因素。 还能指定难度。 记录已A的题,跳过设置的黑名单。 计算...

三月 12, 2015 · 1 分钟 · 149 字 · Ruotian

题解 BZOJ 3460 Jc的宿舍

贪心一下。 接水的时候肯定是从小到大接。 好像没什么性质。莫队好了。 观察到奇怪的强制在线方法。。。 类似[糖果公园/苹果树]做法。 块大小没仔细算,...

三月 12, 2015 · 1 分钟 · 399 字 · Ruotian