集训总结（经常鸽）

• 7.13

今天上午主要是把cdq和treap复习了一下，顺便写了两个博客来记录。
下午一直在学斜率优化，先是学了单调队列优化，写了
【P4954 [USACO09OPEN] Tower of Hay G】
【P2254 [NOI2005] 瑰丽华尔兹】
然后就开始学斜率优化，学完之后写了【P3628 [APIO2010] 特别行动队】这道题
真正搞懂斜率优化之后也会写博客记录一下。

晚上在学博弈论，看懂了但是还没写题。

• 7.16

把这天的补一下。

其实今天也没学啥，就是胡乱练了点题。
【P2205 [USACO13JAN] Painting the Fence S】，这题一看有线段树，本来想练练手的，结果发现根本没那个必要，完全可以用查分数组记录当时的层数然后用类似扫描线那样的东西扫一遍就能出答案了
【P5815 [CQOI2010] 扑克牌】，这道题不用想太复杂，也没那么复杂，直接二分判断合法不合法就行啦，一本想到之后就马上能切掉

• 7.17

不愧是lsr学长，不愧是组合数学，确实强，这是听组合数学的第三遍了才听懂不愧是我

今天上午在听卡特兰数的时候学长讲到一道题

【P3978 [TJOI2015] 概率论】 确实代码简单，但是确实难想，首先我们可以先手摸几个小的数：我们令 \(f_n\) 表示 \(n\) 个点的二叉树个数, \(g_n\) 表示 \(n\) 个点的所有 \(f_n\) 棵二叉树的叶节点总数,然后通过手摸出来的数推断出 \(g\) 和 \(f\) 的关系为 \(g_n = nf_{n-1}\) ，后面我其实觉得就简单了不少，我们只需要把 \(f\) 给求出来就行了，再带入卡特兰通项公式就可以A掉此题。
然后就在写组合数的题

【AT_agc025_b [AGC025B] RGB Coloring】 这题其实非常简单，是到绿题，应该很好切，一看 \(a,b,a+b\) 就知道可以把 \(a+b\) 转换为先 \(a\) 再 \(b\)，然后就可以通过枚举红色 \(i\) ，通过 \(i\) 来求 蓝色 \(j=\) \(k-A*i\over B\) 就行了，然后就可以用排列组合公式求了

【P1350 车的放置】 这题看着有排列组合就做了，结果发现就根本就不用，一个 \(dp\) 就行了啊，因为和数学无关，不细说了

此后在写分数规划一类的题，这类的题一般配合 \(dp\) ，其实这玩意还是挺好理解的，二分直接过了。

【P4377 [USACO18OPEN] Talent Show G】 很基础啊，基础分数规划题，用 \(dp\) 结果是否大于0来二分，看起来复杂度还挺高的，但是 \(n=250\) 更是重量级，直接水过了。

【P4322 [JSOI2016] 最佳团体】 这题不好评价，也可能是晚上浮躁的很，写了好久。这题跟上一道
没有本质区别，但是不知道为什么能想半天。。最后卡在 \(l\) 和 \(r\) 需要订成浮点类型的了输出就是让输出小数啊我定个int我不错谁错，然后就切了。

今天唯一不太满意的就是没写概率论，辜负佳和嘱咐力(悲

• 7.18

毫不夸张奥，今天讲的课85%没听懂。所以上午很气愤，就乱写了几道题。

【P3200 [HNOI2009] 有趣的数列】，这题裸卡特兰数啊，很简单啊不知道为什么是紫
【P5675 [GZOI2017] 取石子游戏】，博弈论，就Nim强化了一小下，虽然这题看题解了我的博弈还是太垃圾了，但是看完之后就会发现我们只要从普通的Nim往这道题慢慢推就能知道他只有在异或和是0或者异或和是1但是他取的那堆不足以改变异或和那就是可取的，然后就可以直接做了（亦或之后值会变大，所以数组要开大点）
【P2659 美丽的序列】，那个时候本来觉得自己码力不太高，就想写个模拟练练，就找到这道题了，谁知道这玩意不难，一个栈就能搞出来，就直接切了果然蓝色的模拟题都很水啊
上午成分挺复杂的写的题驴唇不对马嘴的

下午在写数论，写了几道 \(Lucas\).

【P3058 [USACO12NOV] Balanced Cow Breeds G/S】，是道dp，判断左右括号然后直接dp就行了没什么好说的
【P2606 [ZJOI2010] 排列计数】，这个是 \(Lucas\) ，求1到n的所有排列中，满足小根堆性质的排列的个数，简单推导一下就能想到是 \(Lucas\) 绝对不是我懒得打Markdown了，很好切，注意 \(long long\)，不开直接0分，害人不浅
【P2675 《瞿葩的数字游戏》T3-三角圣地】，这个和上面那个基本一样，不知道为什么就成紫题了，也是直接秒了

今天唯一不太满意的就是上午没听懂好多东西，血亏