讲题

摘要

Day2T1 无向图

对每种权值判断是否有边(没边就做完了),每次删边判连通

50 分直接计算,复杂度 .

从小到大枚举权值

动态图问题,要求支持加边,删边,问图是否连通

如果只有加边,可以用并查集判断是否连通

发现在时间上,每一条边的存活时间对应两个区间(删比它小的边,删比它大的边)

我们在时间轴上建线段树,区间表示时间,每个结点保存这个时刻删掉的边。叶结点保存这个时刻删除的边的集合(同边权的边一起存在一个叶结点。实际上把边按边权排序后,叶结点也对应一个区间),我们想知道每个时刻(叶结点)图的连通性

每个区间对应线段树上的 log 个区间

每条边在某个时刻存活

在线段树上 DFS 时用并查集加边(DFS 到的叶子结点是当前删掉的那些边,因此我们要把沿途的兄弟结点包含的边加入到并查集)

删除(回溯)的话,记录加边时并查集(启发式合并)的操作,删除的时候撤销操作(删除变为撤销)

可以发现,每个结点包含的边最多添加 / 删除一次,而线段树一共有 层,每一层是 条边,因此一共有 次增加 / 删除操作。每一次操作的复杂度是一个并查集的 . 总复杂度 .

Day2T3 玩游戏

直接 DP,复杂度 .

dp[i,j]=not(dp[i+1,j-i] ans dp[i+1,j+i])

可以用 bitset 维护 DP 值

dp[i]=not((dp[i+1]<>i))

观察发现,DP 值的段数很少(平均)

因此我们把不可行区间左移,右移,取并取反即可,归并排序

Day1T1 智慧树

标算暴力 fft 转移

考虑点分治 + 背包, 做背包,加点分治的 ,复杂度 .

标算

CTSC2010 性能优化

Day1T2 组合数

第一个点 lucas 定理

第二个点数位 DP,一位一位确定

考虑容斥

0-r1,0-r2,0-rn

这样就没有下界了

考虑数位 DP

从高位往低位做


  转载请注明: Sshwy's Blog 讲题

 上一篇
点分治入门 点分治入门
摘要 莫名其妙发现这几天遇到了很多点分治的题目,于是来系统整理一下点分治算法 点分治是一种树上分治算法。通常用于解决无根树上的统计问题。对于统计的问题,可以按照结点对其分类,分别统计后再组合成结果。而这类问题的求解复杂度往往和树的深度、大小
2019.03.07
下一篇 
杂题整理 杂题整理
摘要 水题泛做 ZROIZROI332 摆花 对于一个整数序列和 m 个区间,定义序列的某一区间 的价值为 (即 sg 函数的 mex). 而这个序列的价值定义为这
2019.03.05
  目录