2 Timsei

尚未进行身份认证

暂无相关简介

等级
TA的排名 3w+

WC2019数树

首先由于我们很难直接求解边集之交为S的树的个数,所以考虑容斥,转化成至少交S,这里需要推一波式子,然后利用组合意义,转化成一个连通块内给一个点染色,就可以O(n) DP了。这类题能够转化成包含的好算一定要尝试着去凑一下,很有可能可以出奇迹。然后再推一推就可以推出一个多项式exp的式子啦,感觉还是很妙妙的QAQ。prufer序列那一部分可以用生成函数的exp来推。...

2019-02-21 22:06:45

维护点分树

总的来说,维护点分树需要记录以下这些东西:该点在点分树上的每一级父亲。它在每一级父亲那里的深度。它和它父亲之间的cut点。如果要维护数据结构,需要该求解的答案可减,并且需要对于每一个点分中心记录一个该点分中心为中心的数据结构,以及以该割点为点分中心的数据结构,查询时相减即可。可以用来维护一系列求解路径长度的问题。口胡口胡。BZOJ 地震 裸题。BZOJ 幻想乡战略游戏就是求带...

2019-02-20 20:29:10

codeforces #327 #333 Div1 总结

两场相对比较简单的codeforces策略上都反应了一些问题。#327 总的来说在A、B两题上花的时间太多了。 A题我认为我花这么久的原因在于我代码写的不够简洁。B题少要考虑边界情况,像这个题,我没有考虑起点和终点重合的情况导致WA。 每次用到除法的地方要特别谨慎。C题这一类题要想清楚了再写。 思路不清晰随便fst。D 思博题。E 这个题很强。首先AC自动机匹配的方法很灵活,感觉可以拓展...

2018-12-13 22:34:00

BJOI染色

我还是自己脑补了很久才理解。首先二分图全部相同即可。然后可以不停地剔除那些du为1的点,这些点对答案没有任何影响。然后我们发现我们对于一个环我们可以用三个点来直接把剩下的部分染上相间的颜色。一个推广是如果两个偶环有公共部分,且这两个环的每个环自己独有的部分长度至少为2的话,我们一定可以构造出一个合法解来cha掉。单独考虑每一个边双。这个结论的推论就是一个点如果度数超过3 那么一定可以找...

2018-12-11 21:28:42

Topcoder TCO R2A Div1

A 题 范围要看清楚,不能够想当然。B题 第一次fst是因为没有考虑直接把一个环首尾相接。C题 构造题。不会捉。主要的难点在于三角形的三边关系需要满足。我们考虑如何满足这个限制。首先wxh 的做法是,既然我们很难处理,那么我们就递归左右两边。左边已经帮我处理好了这样的情况。我们尽量最终的序列分成均匀的6段。s1,s2,s3的构造方案已经被给出,将s2,s3平移至s3, s4然...

2018-12-01 11:13:50

九省联考总贴

秘密袭击单独写了。详情见另一个博客。#include <bits/stdc++.h>using namespace std;typedef unsigned int ui;const int N = 2e3 + 5;const int M = N * 2;const ui mod = 64123;const int MAX = 1e5 + 5;struct ...

2018-11-30 07:30:30

2018.11.30 多项式

题目大意: 求n个点的二分图,将其所有边都黑白染色后不同的图的数量,两个图不同当且仅当x-y 这条边只在一个图中出现或者两张图中颜色不同。n 1e5多项式模板题。首先我们考虑联通二分图的生成函数G容易知道答案F = e^G.联通二部图的数量的生成函数 H=e ^ (2G) 所以我们只需要计算出H然后多项式开根就是答案。H 的 n 次项显然是 sigma i = 1 - n C(n, i...

2018-11-29 08:01:13

LOJ#2473. 「九省联考 2018」秘密袭击(线段树合并+拉格朗日插值)

一个非常强的题。也许比较套路但是都比较生疏。主要使用两个思想。首先是把求第k大的权转化成枚举i 从1 - W 计算 最终的第k大 大于等于 i 的和。然后就可以 转化成一个DP。f[i][j][k] represents the subtree of the node i and we are considering the value of the kth node is not le...

2018-11-27 22:32:54

HAOI2018

背包看出gcd的小trick之后就可以直接跑莫比乌斯反演了。以后这一类要查找一个数的因子的位置的题,可以用杜教筛记忆化的方法分两个数组记录。 做莫比乌斯DP的时候可以直接暴枚哪些质因乘积这样可以减少复杂度。 不过想要简洁的话预处理mu...

2018-11-19 22:24:37

codeforces 1055

比赛的时候 C 题卡了有一段时间。 原因是边界情况,当b是a的倍数的时候不能够倍长。 以后当要做一个事情的时候要思考这个事情成立的条件。 避免心态崩了的情况。D题没有调出来, 主要原因是我只考虑了那些应该被更改的字符串被改正确了。 却没有保证剩下的字符串不被修改。 下次要忽略某些干扰条件的时候,要考虑这些干扰条件何时成立,何时会对 结果有影响。F题是Trie树卡空间,这个东西分层搞或者建出Tr...

2018-11-18 21:32:47

codeforces778

C 求一个Trie 树 缩掉每种深度的一层之后 的 大小。 n 3e5这个题我直接像线段树合并那样暴力的合并过掉了。不知道复杂度为什么是对的。D 一个 1 * 2 密铺的矩形 每次可以选择一个仅包含两个 12的 正方形,旋转90度,问是否能用 少于 4 * n * m 达到目标状态。n,m 50这个题又是构造题的典型套路,把所有的目标局面和初始局面都转化成一个好弄的特定局面,这题里这个局...

2018-10-20 21:12:25

codeforces 1054

D 题意不说了 转化成抑或前缀和然后相当于每一位能够取反求最少相同的对数、E 这个题自己想出来的。300*300 的矩阵 每个位置一个 01串,每次可以选择用一行或者同一列的两个格子把一个格子里的字符串的末尾元素删去插入到另一个格子里字符串的头部。问是否能从 初始局面变化到 目标局面。用不超过 4 * 字符串总长次操作。总字符串长度 1e5第三次遇见这一类构造题了,终于切出来了。 具体...

2018-10-20 20:56:52

死法大全

10.18 日 死于 (dp[x][1] * 2 + dp[x][0]) 爆 int死于 没有对拍。前一次 死于没有开子文件夹。

2018-10-18 13:57:54

codeforces 1063

D 这个题 有点胖胖。题意是 有一个环 n 1e11 个小朋友 k 1e11 颗糖分给他们,这n个小朋友排成一个圈, 每个人要求得到1个或 2个 糖果, 如果不足全拿完,已知现在从l开始发糖,顺时针一直发发到r号人结束,求 最多有多少人要2颗糖。考试的时候一直在想如何二分答案。后来发现枚举圈数非常的方便,以后这种左右摇摆有边界的题直接周围稍微for 一点 只要不TLE。这类题目先列出方...

2018-10-15 22:30:42

AGC 028

C 一道和以前做过的一道codeforces类似的题,但不大一样。题意: 每个点两个权值L ,R, 要求把这些数排成一个环,相邻两点ab间的(处于逆时针方向的数为a)的代价为 min(L[a], R[b]), 求能构造的最小的环。n 100000这个题自己做出来的。首先考虑 如果说能分解成多个环的话,我们一定可以构造一个方案使得权值和为所有L,R从小到大排序的前n个数的权值和。那么我们...

2018-10-15 22:23:47

codeforces做题 记录

1033 G 题意是 给 n堆 石子 Alice 和 Bob 游戏 Alice 每次可以在一堆中取出a枚石子,Bob可以在一堆中取出b枚石子,求对于a 属于 [1,m] b 属于[1,m] 有多少对 <a,b> 满足 1)Alice必胜 2)Bob必胜3)先手必胜 4) 后手必胜这一类 博弈题 考虑 每堆对于 (a+b)的余数即可, 像这种 双方在对手操作后总可以再进行一步操作达到...

2018-10-14 13:28:31

nowcoder提高组四 灭虫

题意:3000个在数轴上的点,对于每个点可以选择这个点向左延伸li长度的线段,或者这个点向右延伸ri长度的线段,问选择的方法使得最终覆盖的数轴长度最长,输入均在int以内。一个非常巧妙的DP题。首先这一类题目有重复的线段长度统计(或者是树上的可以相交的路径方案统计)或者其他内容有一个比较自然的做法:就是把每一段线段保留一段前缀或者后缀,将限制转化为最大值,然后要保证所有的线段不相交。这个题...

2018-10-07 21:55:36

Topcoder SRM 100 场计划

SRM 550 Div1 250 按题意模拟,注意判断边界是否被访问时,以后的路径不能算上 SRM 550 Div1 500 一道找规律题,打个表 SRM 550 Div1 1000 矩阵快速幂题,每个位置是该位置需要多少次才能转到目标态,先让他转到目标态的贡献减去之后,剩下就只剩下自己转圈的贡献了,我们发现这样的贡献在每个位置都相同,就可以算出最大旋转次数. 然后状态就是 有多少个需要两步到...

2018-10-04 19:39:24

codeforces VK CUP 2016 R3 VP

A,B 太水 C 题 具有单调性可以二分做,也可以推一波式子用凸包,能写第一种尽量写,不容易错。 D 题 大分类讨论题,要注意的有 删除在所有操作之前,注意用set去重,最后一起加回来。 中间部分对称的东西尽量对称写,能在首尾写的写在首尾。 重复以及对称变量用一个变量存起来。 E 题 这个题提供了一个好的思路:当我们一堆东西取max的时候利用min小于等于什么来DP,或min-max容斥有...

2018-07-11 22:24:51

LCT模板题2 最长链

树是任意两点间仅有一条路径的联通图,树上的一条链定义为两个点之间的路径。在本题中定义一条链的长度为链上所有点的权值和。现有一棵带点权树,要对它进行一些操作,请你在第一次操作前和每一次操作后输出这棵树的最长链。这题非常不错的虚边维护儿子信息的LCT,并且,利用LCT splay 维护的是链的性质,可以动态的利用最大子段和的方式进行合并,主要思想就是维护以x节点为根的子树所表示的链的从头开始的最大...

2018-03-07 22:04:15

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!