ty每日刷题记录(咕咕咕中)

ty的刷题总结

标签 :知识总结

题号	算法	坑点	日期
hdu 1358 Period	KMP求循环节，每一位判断即可	敲对模板即可	2.16
hdu 2222 Keywords Search	AC自动机，裸题	注意根节点我用的0，还有优化清空方法	2.16
hdu 2896 病毒侵袭	AC自动机，裸题*2	输出格式麻烦，以及算对空间	2.16
CH 2101 可达性统计	拓扑排序，状态压缩	bitset变量可以直接或(\|)，写循环慢的一批	2.17
BZOJ 3306 树	线段树，树的dfs序	关于判断换根，可以直接在dfs序上进行	2.17
poj2774Long Long Message	后缀数组模板，求两个串最长公共子串	把两个串合一起，求height，求满足要求height最大值	2.23
hdu3065病毒侵袭持续中	AC自动机	没有	2.23
bzoj1306树的统计Count	树链剖分单点修改区间查询	把线段树写错了	2.24
[HAOI2006]受欢迎的牛	tarjan+缩点+dag统计（数学归纳	注意缩点后不用这个并查集的话可能重复加边	7.14
上白泽慧音	tarjan+存分量	7.13
P5461 赦免战俘	递归	反应慢了	7.14
P5462 X龙珠	双向链表	7.14
P5463 小鱼比可爱（加强版）	数学，求所有区间的逆序对总数	7.14
P3377 【模板】左偏树（可并堆）	是一种可并的数据结构	多理解	7.15
P3373 【模板】线段树 2	带两种标记的线段树	注意mul和add的下放方式	7.15
P1631 序列合并	杂题，用优先队列缩小状态空间	神奇的n个队列取队首的方式	7.15
P1880 [NOI1995]石子合并	区间dp例题	链转二倍环	7.16
AT2827 LIS	lis的O(nlogn)算法	用lower_bound	7.16
【模板】可持久化数组（可持久化线段树/平衡树）	很diao的数据结构	多理解	7.18
#6560. 小奇取石子	dfs 背包	原来要拿限制大小的k做容量，然后dp里是取这么多数时已经取了多少堆石子，然后在<=m时取最值	7.17
P1005 矩阵取数游戏	区间dp	从外面往内走，最后只剩一个值时特判(还有高精的40分没拿！！！！)	7.18
poj2955Brackets	区间dp括号匹配	如果两头匹配就从中间+2，然后用len ij k的循环更新即可	7.18
[IOI1998]Polygon	很***的区间dp	数据范围简直给不清楚，还有十分sb的输入；转移时注意有两种情况同时存下来，可能有两个最小值是负数乘起来得最大正数	7.18
P2746 [USACO5.3]校园网Network of Schools	tarjan缩点+dag的性质	在同步统计出入度时居然写个elseif错爆，最后有一个特判只有一个强连通分量的情况。学会了用set存缩点后的图，size就是出度	7.19
没有上司的舞会	树形dp水题	复习	7.19
P2015 二叉苹果树	树形dpdiao题	是自己设计的！！（所以写的很蠢)最好还是从小到大枚举两个儿子的边数，用加的方式填背包。这个题只要分清3种情况就可以a	7.19
P1757 通天之分组背包	分组背包	和01那些水背包不一样的，一定注意最外层的阶段是第几组，先枚举空间在枚举具体这一组的物品，还要考虑空间装不装得下	7.19
P1273 有线电视网	树上分组背包	统计叶子节点和边上负权值之和最优，用叶子数作为每个点dp的容积，决策是从v子树里选k个用户	7.19
P2607 [ZJOI2008]骑士	（基环树）树形dp神题	dp是舞会的模型，爆搜断环，tot=1开始就可以用i^1访问反边。然后用断边的两边的点dp。最后统计的是两边dp[m][0],相当于强制让u不选,在强制u/v中选一个或者都不选的情况下，进行一个树形dp。	7.19
挖地雷	dfs+细节	黄题都错了2次，特别尴尬	7.19
小凯的疑惑	神秘数论题，证明看不懂	打表找规律，还打错了日，然后为什么是黄题？	7.19
P1972 [SDOI2009]HH的项链	求区间数字种数，树状数组维护最新状态	对于询问舍弃旧状态，维护最新状态	7.20
SP3267 DQUERY - D-query	和hh的项链一样	数据太小可以用莫队+(奇偶优化)水过	7.20
wisdom	线段树+差分+构造	阶梯加，借用前缀和。以后记得想到用线段树query(1,i)来得前缀和	7.20
P2023 [AHOI2009]维护序列	线段树裸题，区间乘	又忘了最后pushup调半天，真的要细心	7.21
Can you answer these queries III	线段树求最大子段和（线段树八题）	这个题和hotel的合并一样，满足“区间加”，它的设计上讲，必须活用节点写法线段树，而query时的区间合并也要用这个节点式pushup	7.21
P2240 数的计数数据加强版	线性dp	你以为要递归？必须用O(n)的dp啦，思维定式	7.22
P2279 [HNOI2003]消防局的设立	贪心	每次从最深的点的爷爷那里放一个标记就可以覆盖	7.22
P1111 修复公路	并查集水题	没一边过是我太粗心，要认真读题	7.22
P2698 [USACO12MAR]花盆Flowerpot	神奇的单调队列题	有坑，好理解的正解是二分区间每次单调队列	7.22
P1182 数列分段 Section II	二分+贪心	二分时一直分不清边界，这里l不能从1，0开始，而是数列中最大值	7.22
P1134 阶乘问题	数学求阶乘最后一个非零位	去最小的7位可以避免误差，但是也可以用最后一位做，必须注意*5会产生错误，所以可以用2来抵消，数2 5的个数，2 5抵消了后把多的2×回去	7.22
P1316 丢瓶盖	二分+贪心	这里要写l<=r 并且用ans保存mid	7.22
P1939 【模板】矩阵加速（数列）	矩阵乘法构造	复习了	7.22
P1020 导弹拦截	lis lds的O(nlogn)算法	搞清楚了lower upper 的用法，但是那个维护方式正确性待证	7.23
[JSOI2004]平衡点 / 吊打XXX	模拟退火	rua,这个没有什么暖用	7.23
[SHOI2002]滑雪	记忆化搜索	如果往低处搜会没法max，所以从低往高搜	7.23
[USACO09MAR]沙堡Sand Castle	贪心	直接排序，用上变到下即可，易证如果不按升序排，则答案不最优	7.23
[AHOI2005]约数研究	数学+思维	不要思维定式，这个太有意思了，你以为你只是在算时间复杂度	7.23
P1282 多米诺骨牌	dp	死活还没懂，等以后再来
[HAOI2012]音量调节	可达性背包	写错了两次还行，没有注意符号，无解判断	7.24
bxt 光环	树上贪心	第一遍交的都有40分，怕被卡改成错解了，烦。以及忘了判上跳不能超过根，日	7.24
P1569 [USACO11FEB]属牛的抗议	线性dp	没考虑到合法状态wa了2次	7.24
P1865 A % B Problem	线性筛	线性筛漏了i*prime[j]<=n然后re了	7.24
P2663 越越的组队	二维费用的背包dp（装满类、可达类）	空间开小了还行，第一次写二维费用	7.24
P2504 [HAOI2006]聪明的猴子	最小生成树	空间算错了？？今天第二次	7.24
P1006 传纸条	两个过程同时进行的dp	写了lyd的版本，题解代码看不懂所以用书上的方程摸得，发现有2个限制条件没想到wa了，以后要考虑dp的合理性	7.25
P1196 [NOI2002]银河英雄传说	带边权并查集模板	记住新概念：每个点距父亲的距离d[]，每个点父亲的集合的size[]，经典的fa[]	7.25
[NOI2001]食物链	扩展域并查集模板	不要写xn,x2n完全未动脑子，记住是平移式的扩展域，写x+n,x+2n	7.25
能量项链	区间dp	终于可以说自己懂区间dp了，然后空间的观念该该改了，每次读完范围可以加个0，或者来个5倍	7.25
[JSOI2008]星球大战	并查集+思考	不要去想并查集里删点，正难则反，倒着加点倒着计算答案。写暴力有助增强理解	7.26
[ZJOI2008]树的统计	树链剖分模板再理解	fchar好像会在luogutle？这个树剖再理解了	7.26
[HAOI2015]树上染色	树形dp	考试时以为完全不可做，但是下来看题解看懂了，类似背包，主要重在xv边的价值的可加性	7.26
[NOI2015]程序自动分析	并查集+离散化	离散化写错了，lower加指针习惯了，这里是要得到新编号，所以要减arr，另外unique 是-(arr+1)	7.27
P1967 货车运输	最大生成树+倍增（lca路径）	改了一下午最后是最后一节倍增时没跟MIN比较，长代码很难写，多算法结合要测试部分，一定要对排	7.27