7.5测试
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------
~
--------------------------------------------------------
T1:题意是说给你一个有向带权图,求点数最小的正环大小
给每个点建大小为0的自环然后矩乘倍增...
考试的时候我没想到倍增,就写了个分块
然后强行开O2卡过去了
--------------------------------------------------------
T2:题意是给你一棵树和平面上n个点,让你把树上的点和平面上的点一一对应,要求树边不相交,求一组合法解
据说是最简单的一道,全场最高30
窝random_shuffle一下有20...
做法是nlog的,但是出题人不想写辣么大的spj,就把n出成了1500...
做法就是选最左下角一个点当根,然后把剩下的点按极坐标排序,连续的一坨一坨的分给他的儿子们,然后递归的搞
然后发现选定了第一个点之后,极坐标序是不变的,就不用排序了
然后用数据结构随便维护一下区间最左下的点就好了...
--------------------------------------------------------
T3:题意是给你一个矩阵,每个点为1或0,现在k个操作,每一个是把(x,y)这个元素(一定是0)改成1,然后问每次改完之后最大的全0正方形大小
窝考场上写了个自以为正确的算法,拿了50分,后来发现是错的...
考虑用线段树维护一下列,然后考虑怎么合并两个节点,只需要记一下这个子矩形第i行靠左或右最远的连续的0,然后单调队列更新答案
时间复杂度是O(n^2log)的
--------------------------------------------------------
评论 (0)
