做题记录

date 题目 备注
09.04 BZOJ3999: [TJOI2015]旅游 直接树剖 就是区间的合并有顺序,注意一下就好了。
09.04 BZOJ2212: [Poi2011]Tree Rotations 线段树合并 算这个逆序对很方便,可以一个 \(log\)
09.04 BZOJ2632: [neerc2011]Gcd guessing game 有点神奇,仔细分析之后,差不多就是每次猜一个质因数集合,然后瞎贪心。
09.04 BZOJ3304: [Shoi2005]带限制的最长公共子序列 直接 \(n^3\) \(DP\) 滚动一下…
09.04 BZOJ2962: 序列操作 线段树直接维护 \(\prod(1+ax)\) ,区间加,区间取反都能直接算出系数的变化,直接打标记
09.05 BZOJ2555: SubString 直接 \(SAM+LCT\) ,码码码……
09.05 BZOJ3309: DZY Loves Math 先是套路反演,然后需要求 \(f*\mu\) 的前缀和,然后发现这个值与质因数有关,可以找规律然后分析,发现可以直接线性筛
09.05 BZOJ3600: 没有人的算术 之前写的,现在终于调出来了…… 就是替罪羊树维护实数 \(rank\) 的用法,可以快速比较两个节点的 \(rk\) 大小。
09.05 BZOJ2626: JZPFAR 这题不是 \(K\) 临近,而是第 \(K\) 远,但还是一样 \(kd tree\)
09.05 BZOJ2337: [HNOI2011]XOR和路径 这个异或不好列式子,其实把每位独立算贡献,就能高斯消元了。
09.05 BZOJ2152: 聪聪可可 合并子树是 \(O(1)\) 的,树形 \(DP\) 直接搞。
09.05 BZOJ3709: [PA2014]Bohater \(xjb\) 贪心就好了
09.06 BZOJ2142: 礼物 组合数取模,模数非质数。这题保证 \(pi^{c_i}\) 不大,可以 \(CRT\) 合并,然后需要在算阶乘的时候提取出 \(pi\) 。我怎么写这么久…
09.06 BZOJ4424: Cf19E Fairy 我自环没没判好, 调了 \(1h\) …… 就是在 \(dfs\) 树上用非树边覆盖,合法边一定被所有奇环覆盖,且不被偶环覆盖。
09.06 BZOJ2138: stone 肯定考虑 \(Hall\) 定理,一开始用点找区间发现做不了,然后考虑选某个区间的集合然后判断,显然只需对于任意一段相邻的区间都满足就可以了。推一下式子,发现直接线段树就可以维护了。\(RE\) 了好久,看 \(discuss\) 度神提醒有 \(m=0\) ,神 \(tm\) 都给 \(K[1],K[2]\) 了还会有 \(0\) ……
09.07 BZOJ1181: [CROATIAN2009]IZBROI选举 我太菜了写了半天。最大值直接把剩下票都给他然后模拟。最小值二分然后 \(DP\) 验证,其他人总席位数是否能达到 \(m-mid\)
09.07 BZOJ3214: [Zjoi2013]丽洁体 以前做的时候不会,现在发现是 \(sb\) 题。两边先贪心搞,中间 \(DP\) ,因为保证了出现次数,所以复杂度很对。
09.08 51nod1673 树有几多愁 一开始写了错的东西……首先要手玩一下,发现一个点一定比他子树内的都小,且小的尽量放下面。然后对叶子建虚树,然后 \(DP\) 。状态是哪些叶子已经填了,发现通过状态可以算出下次最多放什么数。
09.09 BZOJ1110: [POI2007]砝码Odw 我这题都没做过,就是类似进制下借位一样搞搞……
09.09 BZOJ3874: [Ahoi2014&Jsoi2014]宅男计划 以前就写过,实在调不出来就弃了。现在终于过了。就先三分,然后贪心。
09.09 BZOJ4804: 欧拉心算 先反演,然后要求 \(\phi*\mu\) 的前缀和,可以直接线性筛。貌似自己会了一种无脑筛积性函数的方法。
09.09 BZOJ1444: [Jsoi2009]有趣的游戏 先建出 \(AC\) 自动机。现在我们需要求停在每个终止节点的概率。然后发现不太好列式子,但如果求经过每个点的期望次数,就很容易高斯消元解。因为终止节点到了就停住了,所以经过他的期望次数即是停在这个点的概率。这样就好了。注意串长都相同,所以终止节点都在\(fail\) 树的叶子上。
09.10 Codeforces 1040E. Network Safety 数数题,比较套路。显然一个点集的贡献为从点集连出的边的种类数。考虑每类边的贡献,这些边组成一些连通块。补集转化一下发现每个连通块没有贡献只有全选或全不选两种方案,然后就好了。
09.11 BZOJ3681: Arietta dsu on tree + 主席树 优化网络流建图,具体见 这里。打了好久+调了好久……
09.11 BZOJ4025: 二分图 这里有个 \(LCT\) 的技巧,维护删边时间的最小生成树,这样保证删边时优先删非树边,删树边时一定没有非树边覆盖,这样就能很方便的删除了。
09.11 BZOJ4820: [Sdoi2017]硬币游戏 这题是bzoj1444加强版。上面的做法复杂度不对,考虑把非终止节点缩成一个点,但是这样转移就比较难写,看 这位大佬 的吧。
09.12 BZOJ3456: 城市规划 裸的多项式求 \(ln\) 。我 \(zz\) 了,求逆了之后乘还倍长…下次要注意。
09.12 BZOJ1455: 罗马游戏 可并堆…
09.12 BZOJ1367: [Baltic2004]sequence 可并堆经典应用。可以证明最优解是分成若干段,每段是中位数。中位数只会边小,合并维护中位值数可以可并堆。具体看论文。
09.12 BZOJ2982: combination 点开了道 \(lucas\) 模板题…
09.12 BZOJ2565: 最长双回文串 比较显然,回文树正反做两次,求出前缀后缀最长回文子串。
09.13 BZOJ2333: [SCOI2011]棘手的操作 随便弄个数据结构维护一下就行了…… 可并堆可以一个 \(log\) 。因为有从点往根爬的操作。需要用随机堆,删点的时候注意各种细节。
09.13 BZOJ4003: [JLOI2015]城池攻占 有些题可并堆真的很方便,自底向上合并就好了。没开 \(LL\) \(WA\) 了几发。
09.13 BZOJ5105: [CodePlus2017]晨跑 这么后面也有水题….