[置顶] 做题记录

做题记录

date 题目 备注
Codeforces Round #467 (Div. 1) \(A\) 算出循环节,\(xjb\) 统计就好了。\(B\) 考虑建 \(2n\) 个状态,表示当前在某个点,谁先手。转移边可以建出来。然后就推一下,对于得不到答案的环上某些状态就定为和局,我可能还是没有太明白为什么一定平局,留坑... \(C\) 构造题。不算难,操作次数大概是 \(3n\) ,若能 \(3\) 次移动某一元素到构造中的串的下一个位置,而不动构造中的串,就可以了。我开始半天试不出来是因为我把待插入那些也不动了,具体方法看题解吧。\(D\) 挺好的 \(DP\) 题。主要思想是把攻击机会蓄着,走步数意味着充能,需要注意的是蓄攻击必须在同行,即换行就变成只有一发。然后离散一下 \(DP\)\(f_{i,j}\) 表示现在在 \(i\) 这个位置,蓄了\(j\) 发,就能转移了。\(E\) 留坑...
Codeforces Round #431 (Div. 1) \(A\) 容易发现每种字符是独立的,然后每次选最大的方案小于当前 \(K\) 的就行了。\(B\) 关键就是类似那种蚂蚁走来走去的题,相对位置是不变的。然后还需要想一想,先把起点平移去掉 \(t\) 。然后写写式子发现相碰的点一定 \(x+y\) 相等,这就比较好了,分成一些独立的集合,每个集合就通过相对位置不变判断就好了。\(C\) 想了一会才发现贡献可以写成 \(\sum i-lst_i\) ,然后瞬间就变成思博题了。一个点对有贡献满足在区间内,可以转化成二维数点,\(CDQ\) 分治就好了。\(D\) 加一个点后就出现两个独立的相同问题,显然可以 \(DP\) ,设 \(f_{i,j}\) 表示 \(i\) 次操作,最小割为 \(j\) 的方案数。转移题解很详细,注意细节。E 不会...
Codeforces Round #429 (Div. 1) VP A 猜个结论就行了,大对小最优,想想也感觉很对。B 先找个根,那么除了根其他的肯定能满足,根不合法需要找个无限制的点到根的链选一下。C 首先转化一下,考虑质因数的次幂,变成相邻两项异或不为0,即不相等,这样就好做多了,这种相邻有限制的计数题有个套路就是这种不断插入这样的过程的 \(DP\) 。容易写出 \(f_{i,j}\) 表示已经放了 \(i\) 种数,有 \(j\) 个相邻相同。\(D\) 注意到 \(K\) 很小,也就是答案在区间出现次数至少 \(\frac{len}{5}\) ,线段树暴力维护出现次数前 \(5\) 大,即可求出答案。还有一种做法是直接随机,每次 \(4/5\) 概率是错的,几百次就好了,这样很好写。E 分块好题,注意到这个 \(dis\) 会动很麻烦,考虑对位数分块,每个点维护往上 \(2^8\) 的信息,这样在这段高的 \(8\) 位是固定的,所以容易预处理 \(f_{i,j}\) 表示 \(i\) 往上 \(2^8\) ,高 \(8\) 位为 \(j\) 的最大值。这样询问就每次往上跳就好了。
Codeforces Round #411 (Div. 1) VP A 自己试试,最优方案显然是 \(1 \to n \to 2 \to n-1 \to 3 ...\) B 稍微想一下可以发现,\(b\) 最后都在左边,而且 \(b\) 每跨过一个 \(a\) ,就变成两个。所以就从右往左统计一下。C 题意有点绕,有个只有一句话的重要条件是同种元素所在点是一个连通子图,而且是图是个树,这说明不存在 \(\{ab\},\{bc\},\{ac\}\) 这样的情况出现,否则就成环了。这说明一个点中的元素两两异色瞎填,填色方案不会使其他块矛盾,直接搞就行了。D 比较套路,我可能只会这种题,就是直径合并时新的直径应该是类似 \(max\{lenx_i+leny_j,C\}\) 的形式,考虑启发式思想,可以对点数少的排序,然后再大的上面二分,这样每次询问复杂度是 \(O(\min\{cnt_x,cnt_y\}\log n)\) ,若记忆化重复询问的话,想想阈值复杂是正常的,两个块大于 \(\sqrt n\) 最多 \(n\) 对,所以总复杂度是 \(O(n\sqrt n \log n)\) ,而且实际达不到。E 构造题还是不太会啊,首先从交换次数奇偶考虑, \(n\equiv 0,1 \pmod 4\) 是合法的充要条件。然后先造出 n 为 \(4\) 的方案,剩下就基于这个做就行了,具体看题解。
Codeforces Round #395 (Div. 1) VP A 瞎数据结构暴力,后来发现用 \(dfs\) 序会好写很多。B 因为四色定理,肯定可行的,现在只需一种填法使相邻一定异色即可,由于有个奇数的性质,所以只要考虑坐标奇偶就行了。C 有点瞎搞,考虑枚举 \(d\) , 根据\(\sum a_i\) 可以算出 \(d\) ,然后需要快速判断是否可行,每次 \(O(n)\)\(T\) ,考虑加剪枝,\(\sum a_i\) 中对每个 \(a_i\) 单独的体现较少,我们发现 \(\sum a_i^2\) 也能求,所以判了这个就跑飞快了。\(D\) 不算难想,树同构一般考虑哈希,其实子树就只有 \(2n\) 个,即每条边有一个向下的子树,已经向上的剩余部分。这些都能处理出来,然后 \(dfs\) 一遍算最优就行了,注意细节。E 感觉这个做法好有启发性啊...考虑离线,枚举 \(R\) ,\(LCT\) 维护 \([1,R]\) 的最大生成树,边权的定义是较小的端点标号,这样就可以询问了,只需对 \([L,R]\) 看有几条生成树边即可。
09.28 BZOJ2200: [Usaco2011 Jan]道路和航线 拓扑一下,刷最短路就好啦。注意细节...
09.28 Topcoder SRM 518 Nim 即这个多项式异或卷积的幂,直接 \(FWT\)
09.28 BZOJ4036: [HAOI2015]按位或 \(FMT\) 那套理论。\(f[S]=\sum_{i=1}^{\infty} i(p^i[S]-p^{i-1}[S])\) 。两边做莫比乌斯变换。\(\hat{p^i}[S]=(\hat{p}[S])^i\) , 右边可以运用高中数列知识求和,得到 \(\hat f[S]=\frac{1}{\hat{p}[S]-1}\) ,然后 \(IFMT\) 回来就好了。
09.28 2015集训队论文《集合幂级数的性质与应用及快速算法》-VFK 戳这里
09.27 BZOJ1911: [Apio2010]特别行动队 我怎么盯着一道斜率优化裸题半天...
09.27 BZOJ4551: [Tjoi2016&Heoi2016]树 瞎搞吧,\(dfs\) 序,然后线段数区间更新。并查集做法比较巧妙,倒着搞。
09.27 Codeforces Round #511 (Div. 1) \(A\) 很正常,考虑都除以\(gcd\) ,然后就是找个最大的 \(gcd\) 大于 \(1\) 的集合,枚质数就好了,复杂度即埃式筛 。\(B\) 真鬼畜,我 \(wa\) 了无数发才过。小数据特判,大的一定能匹配完。\(C\) 感觉挺神的,想清楚了也不难,考虑最后一层块数 \(k\) , 若 \(k\) 可行,划分方案是唯一的。现在只需找到哪些 \(k\) 合法即可。合法即满足所有子树 \(\frac{S}{k}|sz_i\) , 就能统计了。\(D\) 好题,我没想到二分... 这种前 \(k\) 大的题可能需要二分,然后由于单调性,做一个类似滑动窗口的东西就可以验证个数了。现在的问题是怎么求区间并的长度。可以维护一个 \(set\) ,维护线段的颜色记为最后被谁覆盖的。可以发现总长度的变换是 \(O(n)\) 级别的,可以在验证时维护当前答案。\(E\) 神奇做法,这就是个子集卷积,只需求模 \(4\) 意义下的答案。正常做是 \(O(n^2 2^n)\) 。 题解做法是把 \(ai\) 写成 \(a_i 4^{cb(i)}\) , 然后做集合并的卷积得到 \(ans_i\)。答案是 \(\frac{ans_i}{4^{cb(i)}}\pmod 4\) 这样如果集合大小超了,就是 \(4\) 的倍数,就模没了。刚刚看了相关理论,写了一点。
09.25 BZOJ2161: 布娃娃 十分裸,直接扫描线 \(+\) 线段树。
09.25 BZOJ1989: Bonus 奖励计划 简单期望,直接考虑每条边的贡献就好了。
09.25 BZOJ1345: [Baltic2007]序列问题Sequence 挺好的小题,我们把贡献记在小的值第一次合并到比他大的值中的时候。这样就很好做了,求每个往两边第一比它的数,累计答案。
09.24 Codeforces Round #512 (Div. 1) \(A\) 题容易翻车,可以发现直角一定可以,仔细想一下是没问题的,可以想到分解 \(K\) 来找一组解。 \(B\) 挺轻易的吧,就是 \(sum\) 为偶,且最大值不能超过剩下所有加和,长区间不会出现后一种情况,暴力就好了。\(C\) 也不难,显然代价关于目标位置是下凸的,每次都二分一下找到最优位置就好了。\(D\) 题需要一些分析,先要推推式子发现有用的循环情况就几种,答案为 \(max\{pre_i\}+lcm(cir_i)\) 然后贪心搞。\(E\) 我写萎了,还没写出来,留坑。
09.24 BZOJ1701: [Usaco2007 Jan]Cow School牛学校 枚举剩下的分数个数,然后有个决策单调性。
09.22 BZOJ1316: 树上的询问 \(Q\) 比较小。点分治,暴力枚询问。
09.21 Codeforces 720D. Slalom 不错的题。考虑避免重复,尽量贴着下面的障碍走。扫描线,维护\(f_i\) 表示当前走到第 \(i\) 行的方案数,当加入一个障碍时,一段的 \(f_i\) 就要累加到障碍上边界那层去。线段树维护。
09.20 BZOJ3884: 上帝与集合的正确用法 扩展欧拉定理裸题。
09.20 Codeforces Round #510 (Div. 2) VP 打了场 \(div 2\)\(C\) 题看错两次..... \(D\)\(sb\) 数据结构题。\(E\) 直接考虑期望 \(DP\) ,转移需要求和 \((x_p-x_i)^2\) 这样的东西,打开后直接维护一堆和就好了。\(F\) 是个贪心,我开始考虑 \(dfs\) 序,发现两个集合最大最小\(dfs\) 序一定包含。所以只需要往上合并,若不能合,就把一个子树的剩余叶子扔掉作为一个集合。
09.20 BZOJ2658: [Zjoi2012]小蓝的好友(mrx) 经典题,扫描线,笛卡尔树维护轮廓,就可以很快维护贡献了。
09.20 BZOJ4826: [Hnoi2017]影魔 不错的题。发现其实有贡献的区间很有规律。考虑一个数 \(i\) ,设其左边第一个比他大的是 \(L_i\) ,\(R_i\) 同理,则 \([L_i,R_i]\) 贡献 \(p1\) ,\([Li+1..i-1,i],[i,i+1..Ri-1]\) 贡献 \(p2\) ,然后扫描线瞎搞就好了。
09.19 BZOJ5313: 新Fib数列 \(sb\) 题,显然循环节很小
09.19 BZOJ1069: [SCOI2007]最大土地面积 复习旋转卡壳...
09.19 Codeforces 793G. Oleg and chess 好题。注意看题,这个空的部分是不影响棋子互相攻击的。所以只需优化二分图边数。可以用扫描线,\(Set\) 搞一搞,就能把剩余部分分成 \(O(q)\) 个矩形,对一个矩形,可以线段树优化建图。
09.19 BZOJ4903: [Ctsc2017]吉夫特 枚举子集的分块套路。
09.18 Codeforces 793F. Julia the snail 我太菜了,一开始想了个显然错的东西。先扫描线枚举 \(R\) ,这样的好处在于不需要考虑上界。考虑直接维护 \(f_i\) 表示从 \(i\) 开始往上最大高度。每加入一个 \([a,b]\)\(1\)\(L-1\)\(f\) 中比 \(a\) 大的都会 \(max\)\(b\)。这个可以用吉利线段树搞。题解是分块没看懂,毛子英文有点晦涩。
09.16 BZOJ4527: K-D-Sequence 按模分类,对于连续一段模相同的,先除以\(d\) 然后转化成 \(d=1\) 的情况,区间要满足 \(max-min+1-len \le K\) ,然后扫描线枚举端点,线段树维护就好了。
09.15 BZOJ2923: [Poi1998]The lightest language \(manchery\) 给我们的考试题... \(xjb\) 贪心
09.15 BZOJ3622: 已经没有什么好害怕的了 十分套路。先 \(O(n^2)\)\(DP\)\(f_i\) 表示选 \(i\)\(a>b\) 的方案。然后 \((n-i)!f_i=\sum_{i\le j}ans_j{j\choose i}\) , 容斥掉就好了。
09.15 Codeforces 573D. Bear and Cavalry 度神给我们的考试题。可以证明最优方案一定可以竖着划分成相邻的不超过 \(3\) 对点的块。想法很直接,线段树维护 \(f[0..2][0..2]\) 表示当前区间除去边界的几个的最优解,这样在中间就可以大力分类合并了。
09.13 BZOJ5105: [CodePlus2017]晨跑 这么后面也有水题....
09.13 BZOJ4003: [JLOI2015]城池攻占 有些题可并堆真的很方便,自底向上合并就好了。没开 \(LL\) \(WA\) 了几发。
09.13 BZOJ2333: [SCOI2011]棘手的操作 随便弄个数据结构维护一下就行了...... 可并堆可以一个 \(log\) 。因为有从点往根爬的操作。需要用随机堆,删点的时候注意各种细节。
09.12 BZOJ2565: 最长双回文串 比较显然,回文树正反做两次,求出前缀后缀最长回文子串。
09.12 BZOJ2982: combination 点开了道 \(lucas\) 模板题...
09.12 BZOJ1367: [Baltic2004]sequence 可并堆经典应用。可以证明最优解是分成若干段,每段是中位数。中位数只会边小,合并维护中位值数可以可并堆。具体看论文。
09.12 BZOJ1455: 罗马游戏 可并堆...
09.12 BZOJ3456: 城市规划 裸的多项式求 \(ln\) 。我 \(zz\) 了,求逆了之后乘还倍长...下次要注意。
09.11 BZOJ4820: [Sdoi2017]硬币游戏 这题是bzoj1444加强版。上面的做法复杂度不对,考虑把非终止节点缩成一个点,但是这样转移就比较难写,看 这位大佬 的吧。
09.11 BZOJ4025: 二分图 这里有个 \(LCT\) 的技巧,维护删边时间的最小生成树,这样保证删边时优先删非树边,删树边时一定没有非树边覆盖,这样就能很方便的删除了。
09.11 BZOJ3681: Arietta dsu on tree + 主席树 优化网络流建图,具体见 这里。打了好久+调了好久......
09.10 Codeforces 1040E. Network Safety 数数题,比较套路。显然一个点集的贡献为从点集连出的边的种类数。考虑每类边的贡献,这些边组成一些连通块。补集转化一下发现每个连通块没有贡献只有全选或全不选两种方案,然后就好了。
09.09 BZOJ1444: [Jsoi2009]有趣的游戏 先建出 \(AC\) 自动机。现在我们需要求停在每个终止节点的概率。然后发现不太好列式子,但如果求经过每个点的期望次数,就很容易高斯消元解。因为终止节点到了就停住了,所以经过他的期望次数即是停在这个点的概率。这样就好了。注意串长都相同,所以终止节点都在\(fail\) 树的叶子上。
09.09 BZOJ4804: 欧拉心算 先反演,然后要求 \(\phi*\mu\) 的前缀和,可以直接线性筛。貌似自己会了一种无脑筛积性函数的方法。
09.09 BZOJ3874: [Ahoi2014&Jsoi2014]宅男计划 以前就写过,实在调不出来就弃了。现在终于过了。就先三分,然后贪心。
09.09 BZOJ1110: [POI2007]砝码Odw 我这题都没做过,就是类似进制下借位一样搞搞......
09.08 51nod1673 树有几多愁 一开始写了错的东西......首先要手玩一下,发现一个点一定比他子树内的都小,且小的尽量放下面。然后对叶子建虚树,然后 \(DP\) 。状态是哪些叶子已经填了,发现通过状态可以算出下次最多放什么数。
09.07 BZOJ3214: [Zjoi2013]丽洁体 以前做的时候不会,现在发现是 \(sb\) 题。两边先贪心搞,中间 \(DP\) ,因为保证了出现次数,所以复杂度很对。
09.07 BZOJ1181: [CROATIAN2009]IZBROI选举 我太菜了写了半天。最大值直接把剩下票都给他然后模拟。最小值二分然后 \(DP\) 验证,其他人总席位数是否能达到 \(m-mid\)
09.06 BZOJ2138: stone 肯定考虑 \(Hall\) 定理,一开始用点找区间发现做不了,然后考虑选某个区间的集合然后判断,显然只需对于任意一段相邻的区间都满足就可以了。推一下式子,发现直接线段树就可以维护了。\(RE\) 了好久,看 \(discuss\) 度神提醒有 \(m=0\) ,神 \(tm\) 都给 \(K[1],K[2]\) 了还会有 \(0\) ......
09.06 BZOJ4424: Cf19E Fairy 我自环没没判好, 调了 \(1h\) ...... 就是在 \(dfs\) 树上用非树边覆盖,合法边一定被所有奇环覆盖,且不被偶环覆盖。
09.06 BZOJ2142: 礼物 组合数取模,模数非质数。这题保证 \(pi^{c_i}\) 不大,可以 \(CRT\) 合并,然后需要在算阶乘的时候提取出 \(pi\) 。我怎么写这么久...
09.05 BZOJ3709: [PA2014]Bohater \(xjb\) 贪心就好了
09.05 BZOJ2152: 聪聪可可 合并子树是 \(O(1)\) 的,树形 \(DP\) 直接搞。
09.05 BZOJ2337: [HNOI2011]XOR和路径 这个异或不好列式子,其实把每位独立算贡献,就能高斯消元了。
09.05 BZOJ2626: JZPFAR 这题不是 \(K\) 临近,而是第 \(K\) 远,但还是一样 \(kd tree\) ...
09.05 BZOJ3600: 没有人的算术 之前写的,现在终于调出来了...... 就是替罪羊树维护实数 \(rank\) 的用法,可以快速比较两个节点的 \(rk\) 大小。
09.05 BZOJ3309: DZY Loves Math 先是套路反演,然后需要求 \(f*\mu\) 的前缀和,然后发现这个值与质因数有关,可以找规律然后分析,发现可以直接线性筛
09.05 BZOJ2555: SubString 直接 \(SAM+LCT\) ,码码码......
09.04 BZOJ2962: 序列操作 线段树直接维护 \(\prod(1+ax)\) ,区间加,区间取反都能直接算出系数的变化,直接打标记
09.04 BZOJ3304: [Shoi2005]带限制的最长公共子序列 直接 \(n^3\) \(DP\) 滚动一下...
09.04 BZOJ2632: [neerc2011]Gcd guessing game 有点神奇,仔细分析之后,差不多就是每次猜一个质因数集合,然后瞎贪心。
09.04 BZOJ2212: [Poi2011]Tree Rotations 线段树合并 算这个逆序对很方便,可以一个 \(log\)
09.04 BZOJ3999: [TJOI2015]旅游 直接树剖 就是区间的合并有顺序,注意一下就好了。