July 21st 近期练习题总结

坦白来讲,这个礼拜自己的练习效率着实不高,在遇到一些难题的时候就失去了钻研的动力。正如STay所说,自己确实失去了一个月之前的干劲与活力,跑步的计划搁浅许久,希望在接下来的几天里把自己所欠缺的,非知识性的问题弥补一下。

过去的一个礼拜仍然进行了不少的比赛,老规矩,按时间顺序整理如下。

ICPC2015沈阳站

这场是心态爆炸的那一场,很尴尬,总结还被三星删掉了。D题是一道想法题,两个和尚建高塔,开始有两个高塔建在a和b的位置,他们只能把塔建在现有的任意两个位置之和或两个位置之差。两个人轮流建,最后没地方建塔的人就输了。一开始认为这是一道博弈,之后发现只需要求出所有能到达的位置,求了个gcd就过了,其实我一开始很不理解为什么是gcd,郝进告诉我ax+by=k*gcd(a,b),所有能到达的位置一定是gcd的倍数,恍然大悟。

B题就尴尬了,由于打这场比赛之前刚学了shift_and算法,被网上称为比KMP更高效的字符串匹配算法。结果在这道题上,由于每次shift_and都要进行预处理,这使得它变的很慢。想来也是,如果它是一个比KMP适用更广的算法,那网上的资料也不会这么少了。以后除了特别思路的题,一定要慎用。赛后用KMP写了个暴力就过了。

这一场补的题还有M题。题意是求两个点的最短路,只不过边的给出方式比较特别,采用分块,然后一个块里的所有点的距离都相等。如果直接建图,那边的数量实在是太大了,达到了n^2,一种特别的建图方法是每个块引入一个新的点,每个在这个块中的点向这个点连接一条权值为当前块价值的边和一条权值为零的边。这样就把n^2的复杂度变成了2*n。随便套个最短路的板子就过了。

F题待补,希望今天能好好看一看,题意都懂。

BC第四场

A题签到题,排个序比较下大小就好了,结果我忘加了一个叹号,wa了一发。

B题是是一道想法题,我们需要用线段的两端覆盖住所有的点,且线段之间不能有重叠现象。其实只需要遍历所有的可能就可以,所有的可能就是所有点的距离和所有点距离的一半,不过还是挺难把所有的情况都想全面的,一开始想二分求,但是发现会出现一些根本不满足条件的情况,就此作罢。

C、D题待补。

BC第五场

这场相当惨烈,大家只做了一题,A题在我觉得是一道打表找规律的题。不知道其他人怎么想,我想到一个半小时左右才做出来。三星很快就过了,其实很想知道他怎么想得,最后的方法大致都一样。其实只需要判断所有mod11等于三的数就可以了。

B、C、D需要补。

计算几何

这周计算几何做了一道题,但是还是一道相对简单的奥赛题,自己凑是很难凑出来的,看了题解之后感觉真是厉害,把题解放在这里,题目求阴影部分面积。

BC第六场

A题水题,比较中位数和平均数的大小,这都能wa,太粗心,下次交之前和写的时候都要多加注意,有些东西不是自己没注意到,而是自己写的时候根本没往那个方向去想。以后写代码的时候尽量在写的时候就把所有东西都考虑到。

B题和之前做的一道多校很像。他只要求存在性,所以直接贪心,判断各个部分的关系,注意会有很多特殊情况,要想出尽可能多的数据去验证自己的答案,(一种不错的方式是打表)。

C题贾大佬和黄大佬鼎力相助,在之后也遇到了这种类型的题,在此表示感谢。题意就是求出有多少个数对(a,b)满足gcd(a,n)*gcd(b,n)=nk并且a和b均小于n。

我们知道当k>2的时候这个式子是没有解的,当k==2或者n==1时,整个式子只有一个解,所以我们重点要解决的是k==1时的情况。首先我们枚举所有小于n的因子,这些因子等于gcd(a,n)和gcd(b,n),接下来我们需要找出所有小于n且符合条件的a和b,这个时候我们需要用欧拉函数找到小于b的数(使结果小于n)并且与b互质的数(使得gcd(a,n)的值不会改变),让这些数与a相乘所得到的结果都能满足条件。同理,b也是如此,将得到的结果相乘乘二即可得到当前这一组结果,值得注意的当gcd(a,n)==gcd(b,n)时不需要乘二。

ICPC2016沈阳站

这场的AB题都比较水,C题是一道矩阵快速幂,难点在于i4如何递推,其实需要将i的四次方和(i+1)的四次方联系在一起,想通这一点后,矩阵的构造就很简单了。

E题和G题需要自己好好补一补。

BC第七场

A题竟然一发A了,受宠若惊,分组输出了一遍就过了。

B题求数学期望,求完之后发现是调和级数的和,当数字很大的时候时间复杂度是不够的,改用估算公式ln(n)+0.57721566490153286060651209(欧拉常数)。

C题概率dp,每次状态是之前状态的和,经过化简可以得到下一个,需要注意的点是在循环末尾变化会变的很小很小,可以通过提前跳出循环节省时间复杂度。

D题待补

 

ICPC2016香港站

这场是真的坑。可做的题感觉很少。

B题是一道计算几何,自己想难了,只需要计算几个关键点的距离,然后找出最短的距离即可。

C题不是我做的0.0,就不总结了。

J题很皮, 想了半天想了一个字典树的解法,但有漏洞,思维还是不够灵敏。隔壁队也同样想到了字典树,但与此同时马上就发现想不通的部分和ac自动机的Fail指针相同。直接进行dfs就过了。我虽然赛后也过了,但弄了将近半天多,而且写的代码还很丑,需要继续学习。

简单说一下思路,找一个不包含给出所有字符串的最长串,且要求字典序最小,如果有无数个,就输出-1,对所有给出的字符建一棵字典树,给所有的单词节点添加一个信息(比如+1),然后对于每一个节点,都继承它指向的fail指针的节点信息。最后做一个dfs就可以得到结果了。

BC第八场

A题水题,太心急了导致没看清输入输入wa了三发。

B题矩阵快速幂,还是要看清楚转化的过程,方程还是比较好建的,往矩阵中输入还是需要更加仔细一些,总是浪费一些不必要的时间。

C、D题待补。

 

博哥开了一场CF,做了两道题,感觉没必要总结,因为难题都没做,简单题又太简单,等自己补完题之后再做吧。

 

这周还是比较尴尬的,效率确实比较低,从待补题数便可见一斑,这两天把黄大佬的数论做一做,赶紧为多校训练做准备了!

发表评论

电子邮件地址不会被公开。 必填项已用*标注