7.2测试总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------------------------
感觉差一点就ak了...
------------------------------------------------------------------
T1:
问你一个矩阵中最大的出现了不止一次的子方阵的大小
二分答案大小,然后哈希验证
然后被卡哈希卡成30分TAT
要用正确的哈希姿势...(矩阵哈希有特殊的姿势)
------------------------------------------------------------------
T2:
说让你用k种颜色给一棵大小为n的树染色,要求两个同色节点间的点还同色,问染色方案数(n,k<=300)
n^3标准做法:
设f[i][j]表示i这个子树被分成j块有多少种方案
可以树形dp用n^3的时间做这个
然后最后给每一块染色,统计一下方案数就行了
后来czh发现了O(n)的做法:
考虑加入一个节点,这个节点要么和他父亲的颜色相同,要么和所有节点颜色都不同,然后他的答案只和当前树的大小有关,和树的形态无关,因此可以把树看成是一条链,然后枚举分成多少块去算就可以了...
后来lcr又发现了一种O(n)的做法(公式是一样的,推出来的过程不一样):
对于每一种染色方案,把其中最浅的节点打上标记,于是每种染色方案都对应了一种打标记方案,每种打标记方案也对应了一种染色方案,因此只需要枚举有多少个标记然后组合数算一下就好...
------------------------------------------------------------------
T3:
给你一个长度为n的序列,每次把这个序列所有数加1然后对m求模,然后这个不断把最后一个元素放到第一个可以生成一共n个序列,问字典序最小的那个的第k个字符是多少,一共加m次
我的哈希乱搞做法:
设r[i]表示第i次加完之后的最小字典序的位置
显然求出r之后答案就不难求了
首先第一次的随便搞一搞
后面每一次,如果有0的话,那么r[i]一定是某个为0的位置,如果没有0那么有r[i]=r[i-1]
然后因为对m取模,只加m次,所以每个数到达0最多1次,因此最多n个0
预处理出每次哪些位置是0,然后拿出来排序就行了
排序比较的时候用二分+哈希来O(log)比较
时间复杂度O(n*log*log)
后来shy跟我说我sb了,不用排序,比一下找到最小值就行了,因此复杂度可以做到O(nlog)
标算做法:
注意到一个位置从某一个时刻开始,本来是最小位置,变得不是最小位置了,就永远都不能是最小位置了
建一棵后缀树,找到答案的位置
每次一旦有人变0,找到这个变0的位置的后缀,把之前的那条路径除了和这个节点相交的部分删掉,然后这个节点暴力向下走找一条最小路经
然后每个点最多被找到一次,最多被删除一次,所以是O(n)的
------------------------------------------------------------------
评论 (0)
