标签：连通 leftarrow 题解 times 枚举 哈希 text ABC287

\(\text{AtCoder Beginner Contest 287}\)

A Majority

无意义题，问同意的是不是占半数以上。

B Postal Card

无意义题，对一个字符串集合开桶，对应匹配另一个字符串集合。

C Path Graph?

无意义题，判断是不是一条链。

D Match or Not

实际上是 \(T\) 分成两部分匹配 \(S\) 的前缀以及后缀，找到 \(T\) 所能匹配到的最长前缀和最长后缀，在这个范围内的所有划分都是可以匹配的。

E Karuta

可以 \(\text{Trie}\) 树，可以哈希，但是请不要但哈希或者双 \(\text{base}\) 哈希。

F Components

树上背包，设 \(f(u,k,0/1)\) 表示节点 \(u\) 在选或不选的前提下，子树内 \(k\) 个连通块的方案数。

\(f(u,k,0)\) 比较好转移，设 \(g(i,j)\) 为 \(u\) 不选的前提下，前 \(i\) 个子树内 \(j\) 个连通块的方案数。

枚举 \(k\in [0,siz_v]\) 来转移：

\[g(i,j+k)\leftarrow (f(v,k,0)+f(v,k,1))\times g(i-1,j) \]

转移 \(f(u,k,1)\) 则是设 \(h(i,j)\) 为 \(u\) 选的前提下，前 \(i\) 个子树除去 \(u\) 所在连通块后，连通块个数为 \(k\) 的方案数。

\[h(i,j+k)\leftarrow f(v,k,0)\times h(i-1,j) \]

\[h(i,j+k-1)\leftarrow f(v,k,1)\times h(i-1,j) \]

\(g\) 与 \(h\) 第一维可以滚掉。

树上背包三层循环应当是：枚举子树——枚举 \(j\)——枚举 \(k\)，这里要严格将第二维上界卡成前 \(i-1\) 棵子树的大小，第三维上界卡成第 \(i\) 棵子树大小。

这个过程相当于是 \(u\) 子树内任意两个子树进行贡献，也就是树中任意两个点进行贡献，于是时间复杂度是 \(O(n^2)\)。

G Balance Update Query

对于每次询问，同样得分的卡片即使种类不同也对答案无影响，于是问题实际上是支持对某种得分的个数
进行修改，并查询前 \(k\) 大得分之和，权值线段树上二分。

Ex Directed Graph and Query

我也许会。

标签：连通,leftarrow,题解,times,枚举,哈希,text,ABC287
From： https://www.cnblogs.com/SoyTony/p/Solution_about_ABC287.html