2020-2021:teams:die_java:weeksummary12
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:weeksummary12 [2020/08/28 16:39] fyhssgss [傅云濠] |
2020-2021:teams:die_java:weeksummary12 [2020/08/28 21:18] (当前版本) mychael |
||
|---|---|---|---|
| 行 12: | 行 12: | ||
| ====== 每周推荐 ====== | ====== 每周推荐 ====== | ||
| **fyh:** | **fyh:** | ||
| - | \\ **题目大意：**定义一个无根树的权值为所有点的度数的平方的和，求有标号的$n$个点形成的所有森林的权值的和。 | + | \\ **题目大意：**一个序列，你可以每次把这个序列前五个重排，然后如果重排后前三个数相同得一分，无论得不得分都会把这三个数删掉，特殊的是如果最后剩下三个数还相同的话也得一分，求最大得分 |
| - | \\ **tag:**prufer序列，计数问题 | + | \\ **tag:**DP，DP优化 |
| - | \\ **做法:**设$f[i]$表示$i$个带标号的节点有多少种不同的森林，递推式为$f[i]=\sum_{j=1}^i C_i^j*f[i-j]*j^{j-2}$。 | + | \\ **做法:**首先如果当前位置三个都相同我们一定要得上这一分（根据荒谬的方法可以证明（误）） |
| - | 设$w[i]$表示$i$个点能形成的所有无根树的权值和,考虑每一个点以及不同的度数对答案的贡献，递推式子为：$w[i]=i*\sum_{d=1}^{i-1}d^2*C_{n-2}^{d-1}*(n-1)*(n-2-(d-1))$ | + | 设$dp[i][x][y]$表示当前在第i轮，这两个数是x,y的最大得分。 |
| - | 那么最终答案$ans[i]$就是$ans[i]=\sum_{j=1}^iC_i^j*(j^{j-2}*ans[i-j]+f[i-j]*w[i])$ | + | 分几种转移，一种是三个数都相同的，那么对于$dp[i-1][][]$的所有合法状态都应该+1 |
| - | \\ **comment:**prufer序列一定要单独讨论N=1,N=2的情况，另外多开longlong取模会导致常数巨大 | + | |
| - | **wxg: ** | + | 第二种是有两个数相同的，设相同的数为p，另外一个为q，那么$dp[i][q][k]$可以从$dp[i-1][k][p]$（或者反过来）转移过来。 |
| - | \\ **题目大意** 给了一个字符串，问你有多少子串，自身是回文串而且一半也是回文串 | + | |
| - | \\ **tag: ** 回文自动机 | + | |
| - | \\ **做法:** 由回文自动机的性质知道一个串的本质不同的回文串最多有 $n$ 个，我们可以用回文自动机统计不同回文串的个数并标记位置，之后枚举每个串并用哈希判断他的一半是不是回文串就行 | + | |
| - | \\ **comment: ** 需要发现本质不同的回文串个数最多为串的长度 | + | |
| - | **hxm:** | + | 第三种是很随意的，设那三个数分别为p,q,r 那么$dp[i][q][r]$可以从$dp[i-1][p][p]$转移过来。 |
| - | \\ **题目大意：** 给一棵树，每个点都有一种颜色，设$s(i,j)$为两点之间颜色种类数，求所有点对$s(i,j)$之和 | + | |
| - | \\ **tag:** 点分治，差分 | + | |
| - | \\ **做法:** | + | |
| - | 点分治即可 | + | |
| - | 对于每棵分治出来的树，考虑过根的所有路径对树内点的影响 | + | 以上三种都是会使得答案增加的，当然我们必须得把其余剩下的所有换数情况考虑进来，比如直接把这三个数扔掉；扔掉其中两个数与自己手中的一个数；还有把自己手中的数全扔了，选两个加进来。 |
| - | 首先单独考虑一种颜色的影响，从根节点出发到每棵子树的每个点u，u节点在该颜色下会产生贡献当且仅当u到根的路径上有该颜色的节点 | + | |
| - | 所以我们只要找出一个子树中所有颜色为该颜色，且其祖先中没有该颜色【也就是最高的该颜色点】，其子树所有点都会产生贡献，那么所有的对根的贡献就是所有这样点的子树大小之和 | + | |
| - | 考虑对子树内的点，就减去该子树的贡献，就转化为和根类似的了 | + | 这看似是$O(n^3)$的，但是实则每次从$dp[i-1][][]$转移到$dp[i][][]$的最多是$O(n)$的，所以时间上得到了保证，至于空间上的优化，我们可以直接把第一维压掉，直接覆盖即可（有些当然不能直接覆盖，分析会发现，需要进行转移的信息只有$O(n)$个，所以转移前也需要维护这些信息。）（当然写起来有亿点恶心） |
| - | 每当第一次经过一种颜色的点时，其子树内所有点经过该点必定产生该颜色的贡献，此时把该颜色的贡献改为剩余子树的大小即可 | + | \\ **comment:**当时想到了$O(n^3)$做法，觉得绝对没前途于是放弃，实际上把所有转移方程写出来是可以优化到$O(n^2)$的 |
| - | 还有，根节点的颜色特殊考虑 | + | **wxg: ** |
| + | \\ **题目大意** 给了一个长度为 $2^n$ 的数列，让你进行单点修改，翻转每一个 $2^k$ 的区间，交换每个相邻的 $2^k$ 的区间，和区间求和。 | ||
| + | \\ **tag: ** 线段树 | ||
| + | \\ **做法:** 我们发现，操作2就是将线段树中所有区间长度小于等于 $2^k$ 的节点的左右儿子交换一下。操作3就是将线段树中所有区间长度等于 $2^{k+1}$ 的节点的左右儿子交换一下。我们用线段树的懒标记维护即可 | ||
| + | \\ **comment: ** 本题巧妙的把区间翻转和区间交换用线段树来维护。 | ||
| - | 写起来细节真的多 | + | **hxm:** |
| + | \\ **题目大意：** 给了一个$n*m$的棋盘的初态和终态，每次可以交换相邻两个棋子，每对位置之间交换次数有一个上限，求最小交换次数使得初态变为终态 | ||
| + | \\ **tag:** 费用流 | ||
| + | \\ **做法:** 容易想到由$S$向初始的黑点连边，由终态的黑点向$T$连边，然后相邻的点间连边 | ||
| + | 但是这样满足不了交换次数的限制，也无法计算答案 | ||
| - | \\ **comment:** 点分治练习 | + | 考虑如何满足一个点的交换次数限制 |
| + | 当然是拆点 | ||
| + | 但是一个位置被经过时会被交换两次，而终点和起点都只交换了一次 | ||
| + | 那么我们就拆成三个点$left$，$mid$，$right$，分别管理入，中介，出 | ||
| + | 它们之间顺次两边，费用为$1$ | ||
| + | 流量将限制$lim$拆开，当$lim$为奇数时要考虑给哪一边： | ||
| + | 如果该点一开始是黑点，终态是白点，那么这个点出边一定比入边多 | ||
| + | 如果一开始是白点，终态是黑点，那么一定要入边多一点 | ||
| + | 否则一样多 | ||
| + | |||
| + | 有一些要注意的地方： | ||
| + | ①要判黑白起始是否相同 | ||
| + | ②相邻不止是四个方向 | ||
| + | |||
| + | \\ **comment:** 费用流模型的建立 | ||
| ---- | ---- | ||
| 行 57: | 行 68: | ||
| ====== 王兴罡 ====== | ====== 王兴罡 ====== | ||
| - | 复习了回文自动机，整理字符串模板 | + | 比赛：CF 665div2 |
| ---- | ---- | ||
| ====== 黄旭民 ====== | ====== 黄旭民 ====== | ||
| - | 复习了点分治，整理了点分治模板 | + | 小学期 |
| - | \\ | + | \\ 将所有模板整理到一个文档中 |
2020-2021/teams/die_java/weeksummary12.1598603988.txt.gz · 最后更改: 2020/08/28 16:39 由 fyhssgss
