8.26集训

Posted on Edited on In

今天做题

第一道是钓鱼 昨晚是用贪心写的，今天用的dp

写出了点锅，还没d出来，wa了几个点

第二道叫：P4054 [JSOI2009]计数问题

一个二维树状数组的板子题目

以前从来没写过二维树状数组，第一次写

第三道的话，叫P2922 [USACO08DEC]Secret Message G

我愿意称之为Trie树最经典例题

初始没思路，

\(O(len)\)插入，\(O(1)\) 查询

sum表示以这个节点为终点的字符串个数

num表示到达这个节点而且没完成的字符串个数

这样就不重复也不遗漏了

第四道叫 P2887 [USACO07NOV]Sunscreen G

贪心的，感觉很简单，就切了

第五道叫 P1792 [国家集训队]种树

初始没思路，但是据说\(n^3\)的dp显然？？？？？

是一道贪心好题，用\(a[x - 1] + a[x + 1] - a[x]\)来做反悔，因为\(a[x] + a[x - 1] + a[x + 1] - a[x]\)终究还是要等于\(a[x - 1] + a[x + 1]\)

用大根堆来维护，注意每次都要维护好链表

第六道也叫做种树，P1484 种树

这个和上边的大致题意差不多，但就是有一个条件不太一样“ｋ可以不用完”

刚开始可以模仿上边的思路可以做到80分，但是距离正解还差一个边界条件

第五道题与第六道题的推广：再次遇到那种隔着选的题，考虑大根堆和链表维护反悔

第七道题　lca的模板题

这一次完完全全的搞透彻了，有以下几个需要注意的细节：

  • 1.for (i = 30; i >= 0; -- i) if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; 需要倒着搞

  • 2.必须从零开始！

第八道题　火车

初始的话，思路不太通畅，隐隐约约知道合并,但是不知道具体怎么合并

用UFS和LCA来做，每次找完之后，顺道把路过的节点都合并起来