Prime Gift

  • 可以先预处理出1-INF中所有的数,然后进行判断
  • 但是这样复杂度过高,不能承受
  • 考虑预处理出两个数集,最终的数集中的数是这两个数集中的数的乘积
  • 这样就可以使用双指针+二分来得到答案
  • 代码:

Continue reading “Prime Gift”

Tree

  • 显然取重心为根可以达到ans=2sum(deep)
  • 考虑构造字典序最小的答案。
  • 令size[x]为x的子树中未被钦点的点数
  • 若剩下能选的点数<=size[x],则当前点必然和一个在x子树中的点匹配
  • 使用线段树维护。
  • 代码:

Continue reading “Tree”

NN country

  • 贪心倍增预处理
  • 问题可以转化为给定若干个点对(x,y),是否有路径覆盖他们
  • 可以使用欧拉序列。对于每一条路径,当遍历到其中的一个端点时,将另一个端点dfs序所在位置+1。对于询问的点对,在遍历到某一个点时对另一个点进行子树求和。当遍历完当前子树后再次进行子树求和。若两次求和结果相同,则不存在覆盖两点的路径。
  • 代码:

Continue reading “NN country”

涂色

  • 考虑错误的DP
  • f[i][j]表示考虑到第i个颜色,分成j段的方案数
  • 由于无法处理颜色段连续的情况,所以考虑重新计算颜色段分解的贡献
  • 代码:

Continue reading “涂色”

Lovers Gift

  • 将答案离线后倒序处理。
  • 对于有银行的点,答案显然是n-1
  • 否则答案即为不包含在当前连同块内的点的次大值
  • 倒序处理后变成合并连同块,答案严格不递增
  • 合并连同块可以使用并察集,更新答案时向下探查
  • 由启发式合并复杂度类比得复杂度为O(mlogn)
  • 代码:

Continue reading “Lovers Gift”

Permutation Tree

  • 首先模拟一下连边的过程,你会发现这棵树的形态是一条长链+一堆挂在链上的点。
  • 对于无解情况只需要预判一下,解满足“挂点”编号小于其父亲且权值大于其父亲
  • 贪心地对于每一个链上的点,使得其非链儿子都在其前面出现即可。
  • 代码:

Continue reading “Permutation Tree”

Symmetric Grid

  • 由于行和列是独立的,所以先考虑行交换完情况。
  • 这个时候剩下的方阵中的每一列都和另一列“翻转后相同”。直接暴力判断即可。
  • 注意枚举行的时候,不要用阶乘暴力而是枚举交换,可以优化到11!!=10395次枚举
  • 代码:

Continue reading “Symmetric Grid”