能补多少是多少吧（大哭
2
1002 梦中的地牢战斗 （hdu7446）
本来看到66/386的战况差点打算跳过，看一眼题解似乎是dp+最短路之类，或许可以再想想？
于是开始认真读题，数据范围很小，尤其是怪物数量 \(k\leq 10\)，加之题目时限 \(4s\)，考虑略显暴力的状态压缩。由于角色血量 \(\leq 0\) 时失去所有金币，为了优先保证角色存活，可直接将所受伤害总和当作贷款生命值处理，若最后还不起贷款，在开头选择离开地牢即可。经观察可得，角色受到的伤害值与其位置和周围怪物是否存活有关，而获得的金币数量仅与已死的怪物有关，因此用状压表示怪物死亡情况，可同时维护这两个变量。
设 \(dp[i][j][s]\) 表示角色在 \((i,j)\) 位置、已经杀死怪物状态为 \(s\) 时所受的最小伤害，由于角色可往上下左右四个方向运动，dp操作不便（或者是由于我dp没学好），考虑建图计算最短路，经计算 \(n*m*2^k*t\) 最大为 \(10^7\) 左右，复杂度符合要求。将每个dp状态换算为点的编号，角色的移动即在不同状态之间连边，为快速计算出移动过程中杀死的怪物，可用前缀和表示 \(x,y\) 方向上的怪物“前缀状态”；边的权值即到达状态下角色受到的伤害，预处理出每个格子受哪些怪物影响、每种怪物影响状态下的伤害值，连边时即可 \(O(1)\) 计算边权。最后统计答案，最大金币数量即获得金币数 \(-\) 损失生命值，获得的金币数即已死怪物的价值和，可以做类似于伤害值的预处理。为保证时间复杂度，需预处理的变量较多，代码实现时注意理清思路，避免混淆出错。我就莫名其妙写挂了好几次，我是猪
最后回去看题解，大体思路差不多，不过上述状态设计中边权非负，dijstra计算最短路即可。
1008 成长，生命，幸福 （hdu7452）
又错半天才过，真是太幸福了（闭眼）（心满意足地似了）
首先一个有趣的小结论：若最终树的直径经过了原树上某节点 \(x\) 生成的点，为了使直径最大，\(x\) 生成的所有点都应被包含在直径中。于是可以将 \(x\) 生成的点数视为其权值，问题转化为求一棵节点带权的树的直径。
对于生成点数，易知每个点在一次生长后，生成的所有节点度数不超过 \(3\)，具体来说，度数 \(ind\geq 2\) 时，生成 \(ind-2\) 个度数为 \(3\) 的点和 \(2\) 个度数为 \(2\) 的点。由此可尝试递推，设 \(a_i\) 为 \(i\) 次操作后生成的点总数，其中度数为 \(3\) 的点有 \(b_i\) 个，度数为 \(2\) 的点有 \(c_i\) 个，则有 \(b_{i+1} = b_i, c_{i + 1} = 2b_i + 2c_i;\space b_{i + 2} = b_i,c_{i + 2} = 2b_i+2*(2b_i + 2c_i); ......\) 观察规律，由高中学过的数列求和知识可得， $a_m = b_1*{\sum\limits_{i = 0}^{m - 1} 2^i} + c_1* 2^{m -1 } = b_1 * (2^m - 1) + c_1 * 2^{m - 1} $；代入最初度数值 \(ind,\space b_1 = ind - 2, c_1 = 2\)，得 $a_m = (ind - 2)* (2^m - 1) + 2^m = (ind - 1)* (2 ^ m - 1) + 1 $.
数据范围 \(m\leq 10^9\)，结果对 \(10^9 + 7\) 取模，当 \(m\) 过大时，取模后的权值无法准确比较大小。考虑分类讨论：\(m\leq 30\) 时，最终结果不会超过long long的数据范围，可直接求直径后对答案取模。\(m>30\) 时，由于最后一项 \(1\ll 2 ^ m - 1\)，可近似将 \((ind - 1)* (2 ^ m - 1)\) 作为权值计算，而整体 \(2 ^ m - 1\) 系数不变，比较路径上 \(\sum (ind - 1)\) 大小即可；当 \(\sum (ind - 1)\) 相同时，再考虑最后一项带来的误差，即比较路径上节点的数量。注意这几处特判，其他部分与树上求直径的代码实现基本相同。
1012 图计算 （hdu7456）
答案计算时只需考虑图的联通性，与其他性质无关，故用并查集维护。\((u,v)\) 联通意味着它们在每张图上都有相同的祖先，可记录每个点在 \(d+1\) 张图上的祖先集合，用随机哈希法可快速比较两个集合是否相同，给每张图赋一个随机哈希值 \(val\)，各点在每张图上的祖先集合即可用 \(val*fa\) 的异或值表示，保存在unordered_map中。
mt19937 ra(random_device{}()); //非常好随机数，我天天忘
for(int i = 1; i <= d; i++) {
val[i] = ra();
for(int j = 1; j <= n; j++) {
h[j] ^= val[i] * j;
}
}
对于每次加边操作，需修改其中一个并查集内所有点的祖先情况，复杂度较大，考虑使用启发式合并优化复杂度。每次合并操作时，以并查集大小为序、将较小者并入较大者，由于每次合并后并查集大小翻倍，可保证每个点被修改的次数不大于 \(dlogn\)，复杂度即稳定于 \(d*nlogn\). 合并改祖先的同时修改哈希值，赋值规律同上所述，此时可直接计算 \(ans\) 的变化量，省去每次重新统计答案的复杂度。点对无序的情况下，设 \(cnt=mp[hash]\)，其对答案的贡献即 \(cnt*(cnt - 1) / 2\)；每次改变一个点的祖先情况，\(cnt+1\) 时答案即变化 $cnt * (cnt + 1) / 2 - cnt * (cnt - 1) / 2 = cnt $， \(cnt - 1\) 时同理计算即可。
双倍经验（bushi）：洛谷P8026（事实上看了洛谷的题解才理解启发式合并··· 感谢洛谷题解区的大佬呜呜）
3
1001 深度自同构 （hdu7457）
快乐找规律题，赛时两人经过一番乱搞推理过的。
由于最后形成森林，可对一棵树与多棵树的情况分类讨论，为保证深度自同构，多棵树的形状必须完全相同，若 \(x\) 是 \(y\) 的倍数，则 $ ans[x]$ 与 $ans[y] $ 之间存在递推关系。设 \(dp[i]\) 为 \(i\) 个点形成一棵树的情况数， \(ans[i]\) 为 \(i\) 个点时形成的森林总数，则对于 \(x\) 的所有因数 \(y\)，$ans[x]=\sum\limits_{y = 1} dp[y] $；而 \(dp[x]\) 可视为将 \(ans[x - 1]\) 中所有树连接至新增的根节点上，有 \(dp[x] = ans[x - 1]\). 计算答案时在循环中将 \(dp[i]\) 累加至 \(ans[i * k]\) 上，貌似用调和级数可算出复杂度 \(nlogn\).
标签：杭电多校,cnt,复杂度,2024,怪物,ans,ind,dp From： https://www.cnblogs.com/meowqwq/p/18331359