脚本宝典收集整理的这篇文章主要介绍了2021.10.2 QBXT，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
0 + 50 + 10 + 30 = 90
二分 + 贪心
考虑 check 不断的找最左边的树 找到需要浇水的树之后将这棵树能覆盖的位置的树删除 然后继续迭代
代码
字符串哈希 用 @H_304_64@(map) 存一下 直接判断
复杂度 (O(10m)) 可过
代码
在一棵树上截取一棵子树 使得分最高
dp
(f_u) 表示以 (u) 为根的子树内 钦定 (u) 和 (par_u) 是一定选的最优得分
在每个点对 (f_v) 从大到小排序 贪心的找 (k) 个 设 (i) 表示所有的 (f_v) 中第 (i) 大的值
复杂度一只 (LOG) 来自排序
代码
kru 重构树 从大到小建树 向上找到走不动的最后一个点 这个点在重构树中能走到的所有点都是符合要求的点
在原树上限制只能向下走
通过两个 (DFs) 序完成上面两个限制
原树上维护 (dfs) 序 限制该点子树的区间
kru 重构树上维护 (dfs) 序限制该点所能到达的点
问题转化为二维数点问题 再加上时间一维 三维偏序问题 CDQ 分治可做
代码
P0
给定正整数序列 求有多少种不同的方法在其中选三个数 满足 (a_i + a_j = a_k) (n leq 5000, a_i leq 10^5)
倒着枚举 (j) 开桶统计 (k)
考虑 (n leq 5 times 10^4) 考虑对序列分块 如果一个三元组有两个在同一个块中 直接暴力做 否则...
弃疗++
当 (n) 更大的时候
分块 FFT???
弃疗++
P1
枚举个 (P) 再枚举 (Q) 在 (S - P) 中
子集枚举
P2 P1123
暴力
(O(2^{nm}nm))
搜索
剪枝
可行性剪枝: 如果当前状态中已经选取了相邻的元素 直接 (return)
P3 P1784
剪枝
维护三个数组 表示每个数在每行每列每个九宫格里面已经用过的 如果一个点没法填数了 直接 (return)
人类智慧: 如果某行某列某九宫格空格子比较少 先去搜
可行性剪枝
最优性剪枝
P4 P1559
可行性剪枝 匹配过的人不在匹配
最优性剪枝 假设之后没有匹配的人都匹配上最优的搭档 仍达不到当前最优答案 (return)
P5 CF-Gym 100503B
剪枝
如果一个 (run) 里面 所有未填的数都按照最小的数 比限定的和大 减掉
如果一个 (run) 里面 所有未填的数都按照最大的数 比限定的和大 减掉
P6 Cf292C
找出所有合法的回文串 对每个合法回文串搜索 (ip) 地址的划分
搜索的一些技巧
不一定按照从小到大的顺序来搜每个变量的值
将变量的确定顺序加入搜索 也可以随机打乱
P7 P3959
考虑用一个序列描述一棵树 (u_0, (p_1, v_1), (p_2, v_2)...) 表示以 (u_0) 为根 (u_i) 的 (par) 为 (p_i)
将这个序列的每个元素看做变量
...
P8 P5758
直接枚举爆炸
剪枝
先枚举加好 乘号 等号的对应 确定每个数的位数
预估左右两边的数位进行剪枝
在搜数位
预估左右两边的数字大小进行剪枝
...
以 (bfs) 写 (dfs)
P10 POJ3134
迭代加深
(dfs) 与 (bfs)
空间只需要维护走到当前状态的栈 和 (dfs) 一样
时间比 (bfs) 稍差 会重复搜索
可以剪枝
...
3-set
...
题目
绝地反击
传奇团子师傅
P1731
P1092
P1526
P4518
水题出题人
TASKSAUTHOR
以上是脚本宝典为你收集整理的2021.10.2 QBXT全部内容，希望文章能够帮你解决2021.10.2 QBXT所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。