• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

20210429总结

开发技术 开发技术 2周前 (04-29) 9次浏览

考试总结&反思

一开始先看的T1,看出来了是个有向无环图求路径数,路径只会从小标号的点指向大标号的点,把询问的点按标号排一下序直接for一遍就行了。这个方法是可以稳过30分的,但是60分有一个性质每个点只有一条出边,这意味着枚举出边更新答案每个点就是 O(1) 的,但我把边反着存了,这意味着每次我是考虑 你会被谁更新 而不是 你会更新谁 前者的谁并不是 O(1) 的。在均摊情况下,(n) 个点,(2n) 条边,每个点只会是 O(2) 的,看起来也非常美好。但是数据可能并不均摊,随便弄一个点 (x) 让他向后指向很多条边,每次询问都带上 (x) 。这样我是会被卡成 (O(qn)) 的。对拍的时候由于造的是随机数据没有及时发现这个问题,就被卡成30了。

正解的做法是比一下度数,对于一条边让他从度数小的指向度数大的,具体的讲对于每个点。考虑他会被谁更新,这个谁要满足度数大于他;还要考虑他会更新谁,这个谁要满足度数小于他。实现起来只需先处理一下度数,存2个图即可。算是其他人的60分做法和我错误的60分做法的结合吧。

写完T2以后看了以后写了个 (O(m^ntimes n^3))算法,对小数据打了个表,没找到啥规律。然后考虑用 总方案数-不合法方案数,总方案数很好求即 (m^n) 但是这个不合法方案数好像要用一个容斥,对于一个三元组 ((k,2k,3k)) 它有重复的方案数可以 有重复数字的方案数-都不重复的方案数(又一个)。

  • 前者是 (m^{tot_k+tot_{2k}+tot_{3k}}),(tot_k) 表示数字 (k) 出现的次数。
  • 后者要考虑 (m) 种颜色中哪些没出现。
    • 考虑枚举这个颜色,发现容斥我好像只会子集容斥,复杂度 (O(2^n)) 根本过不去第二档分。

最后也没再管了。

然后就去看了看T3,好像要维护数的联通性(LCT?),好像只会前两档分,先写了第一档。第二档要用线段树二分,感觉好麻烦,但是为了抢 rk1 还是写了(zbl,考了个倒2,6个rk1)。和暴力拍出来2个错误,但是败给了时间复杂度。

为什么败给了复杂度?

感觉原因(借口)有2个。归根结底就是没分析复杂度

原因1:线段树二分好久没写了,露了个细节。

这是考场代码:

int askL(int p,int pos)
{
	if(!pos)return 1;
	if(st[p].l==st[p].r)
		return st[p].l+st[p].data;
	spread(p);
	int mid=(st[p].l+st[p].r)>>1;
	if(pos<=mid)return askL(p<<1,pos);
	int temp=askL(p<<1|1,pos);//缺个if
	if(temp!=mid+1)return temp;
	return askL(p<<1,pos);
}

这是30分代码

int sum(int p,int l,int r)
{
	if(l<=st[p].l&&st[p].r<=r)
		return st[p].data;
	spread(p);
	int mid=(st[p].l+st[p].r)>>1,temp=0;
	if(l<=mid)temp+=sum(p<<1,l,r);
	if(mid<r)temp+=sum(p<<1|1,l,r);
	return temp;
}
int askL(int p,int pos)
{
	if(!pos)return 1;
	if(st[p].l==st[p].r)
		return st[p].l+st[p].data;
	spread(p);
	int mid=(st[p].l+st[p].r)>>1;
	if(pos<=mid)return askL(p<<1,pos);
	if(sum(1,mid+1,pos)){//多了个if
		int temp=askL(p<<1|1,pos);
		if(temp!=mid+1)return temp;
	}
	return askL(p<<1,pos);
}

这个if语句表面上加了个 log ,实际上可以避免单次询问被卡成 O(n) 的。

原来二分思路,如果右边搜完了,发现全是0,那么搜左边(这二分了个寂寞)

这有一个致命的问题,这个搜索是 O(n) 的。原因,右边全零可以用一个区间查询解决,但是好久没写了,大E了。

原因2:

windows下对拍我会输出一个 程序运行时间,这会被输出在点开 对拍.exe 后弹出的黑框中。

linux 下则没有黑框,只有在终端运行时才会看到输出。

编译完以后不想再敲一行 ./check 了,就直接在文件夹里点了可执行文件,导致没出现黑框。

就没法对比暴力和这个线段树二分的复杂度,也算长了个教训。

反思

头一次在 Linux 下对拍还是出现了很多问题,太久没练的算法会忘记一些细节,最近也每咋抽空回顾一下。

T1的问题应该预判出数据可能是会 刻意构造卡依赖均摊的算法的 。对于计数一类的题一直不好,容斥也不好。


关于 线段树二分 的简单总结

线段树二分可以处理类似于 对于一个左端点,找到一个最右边的右端点,这个区间要满足一些性质。

常见的方法是 将右段点可以出现的位置 ([L,R]) 划分为 ([L,M]cup[M+1,R])

用一种快速的方法判断右段点是否可以出现在 ([L,M]) 里,选择一半递归即可,可以在 (O(判断时间timeslog n)) 得到最优秀的右端点。

这里只具体地讲那个快速的判断方法。

例题1:siano

考虑将每种草按生长速度从小到大排个序,容易发现:在每次收割之后,生长速度最快的草一定最高,那么排完序后,每次收割的草肯定是一个连续的区间,我们需要找到这个区间的左端点。线段树的每个节点里记录这个区间里最高的草的高度(一定是最右边的),如果他够高了,直接考虑左边的空间,否则搜右边的区间。

还要灵活地运用懒标记,记录一个上次割完的高度和距离上次割草过了多久可以加快修改、查询和判断操作。传标记的时候要先传前者,再传后者,因为前者是可以直接“抹杀”掉后者的,儿时间过得再就上次割的高度是不会变的,后者只能在前者后面打一些”补丁”。

例题2:脑洞治疗仪

题目中的这句话 ”这是因为如果新脑洞挖出来的脑组织不够多,脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。“ 给了我们提示。

我们要找到一个最靠前的 (r) 满足 (r-l+1==sum_r-sum_{l-1}+k) ,这显然是线段树二分该处理的问题。

找位置的时候记录一个 (k)

  • (sum_{mid}-sum_{l-1}<k) 直接把左边填满打个懒标记,令 (k-=sum_{mid}-sum_{l-1}),向右区间递归
  • 否则直接向左边递归。

例题3:IIIDX

先鸽着


程序员灯塔
转载请注明原文链接:20210429总结
喜欢 (0)