这次考试三校联考 LJ NY RQ ,由张老师出题。我考的还不错,但是对比其他校区的同学还有差距,需要继续努力。依旧是浅浅分析一下:
T1:扫雷带师(P8427)
很骚的一道构造题,需要输出一种数字和为n的构造方法。首先就会想到 可以让每一个雷的贡献数为8,也就是每一颗雷单独放,周围8格都没有其他雷,并且数据范围也允许。如果数字和不为8的倍数时,就处理n/8剩下的余数。还要注意 有些时候需要特殊处理 ,比如n=2.5.7.13等;当时写的时候有些细节弄错了 WA90,有点可惜(这道题如果A了,我就是三校第一了)。
T2:质数幂(P8691)
这道题的正解做法太骚了。首先看n最大1e18,很大,说明求每个n不可能都线性,只有一部分的n可以线性,那剩下的应该怎么办呢?我们可以尽力将n分解后,看看剩下的n有没有什么特点。比如如果我们只筛到5e3,那么对于一个大于5e3的n,我们可以先看5e3以内有没有n的因数,如果有就n/=p,并记录下最少的p的个数rmin。到最后无法分解的时候,可以讨论一下:
1.n=1时 ,直接输出rmin
2.n!=1时,先看看n是不是完全平方数
如果是 看看根号n是不是完全平方数
如果是 输出min 4,rmin
如果不是 输出 min 2,rmin(这时候的根号n 要么是质数,要么是两个不同质数的积)
如果不是 看看n是不是三次方数
如果是 输出min 3,rmin
如果还不是 n肯定是质数(或者一个完全平方数乘一个质数),直接输出1;
(为什么可以这样做?因为当尽力将n分解后,n剩下的质因数只会是大于5e3的,并且最多应该只有5个质因数)
(再枚举这几个质因数的情况)
(不要问我为什么最多5个质因数,但为什么只算了4个质因数的情况,要问就是NY的人卡出来的)
考试的时候我没想出来正解,就打了个WA60的暴力,还不错哦
T3:积木(P10216)
很骚的一道DP,一眼DP,时间卡的特别极限。状态f[i][j][k]表示第i层j行k列的点到B点一共有多少条路;状态转移:分类讨论,有时候当前点可以从上面一个点爬过来,有时候是从向前的一个点或者向右的一个点爬过来。而且因为只能在表面爬行,所以只有最外面一圈的点是可以被爬的(也就是只转移外面一圈),时间复杂度差不多O(4*n*n);
但是这样是过不了的,空间会爆炸,所以可以采用滚动数组或者直接把第一维kill了(直接kill可能会快一些)。
但是这个算法的常数很大,所以要想办法搞一下优化,最后可以卡得很极限得A了!(但是听LSTG说真正的正解是排列组合)
考试的时候没有优化常数,导致我TLE80,也还可以;
T4:寻路游戏(P8702)
张老师说,其实看那些路径会被障碍影响,会被影响几次,一次或是两次,最后把路径长度全部加起来就可以了。但是我很菜,不会写代码,所以具体怎么实现我也不知道。
这道题考试的时候没写,我觉得很不应该,随便打个暴力就有30分的,应该骗点分的。
总成绩230,第三,我觉得还可以,第一只有240分。感觉我们和另外两个校区的差距也没有太大,努力一下是可以追上的。
标签:很骚,rmin,质数,5e3,反思,质因数,可以,考试 From: https://www.cnblogs.com/zhuzc/p/17145737.html