首页 > 其他分享 >很骚的一场考试の反思

很骚的一场考试の反思

时间:2023-02-23 18:33:12浏览次数:29  
标签:很骚 rmin 质数 5e3 反思 质因数 可以 考试

这次考试三校联考 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

相关文章

  • chatGPT帮助开发实战解答问题和反思
     问题来自.Net开发群友 问题我想做一个自动生成单据号的功能,但是在EFCORE里没有行级锁,请有什么等价方案吗? ChatGPT回答在EFCore中确实没有提供行级锁(row-le......
  • 华为认证数通HCIA+HCIP题库全套操作指南(全套题库解析+模拟考试)​
    华为认证考试分为三个等级,分别为工程师HCIA、高级工程师HCIP、专家HCIE,等级越高,考试难度越大。​本篇带大家详细了解华为数通题库刷题工具的详细操作步骤。​操作须知:本款刷......
  • 中南大学CSU2022-2023级C语言期中考试机试答案
    卡在出线概率了。40%,没想到遍历时反了,我去。 1.时钟加法1#include<stdio.h>23#include<string.h>45#include<stdlib.h>67#include<math.h>8#d......
  • ACM新生赛反思
    12月16日举办了ACM新生赛,上周的热身赛发挥还可以拿到了500分,但是到了正式赛,题虽然比热身赛简单了,但是发挥的确很差,开始后大致看了一下题没有难题,都有思路,心里挺高兴的,感觉应......
  • 开学第一课反思
     开学3节课,王老师讲的很多,但始终都围绕一个点,那就是多加实践,多加练习。王老师学习游泳的的故事给了我很大的启发,王老师学习游泳的处境也许跟我们学习代码的处境是相同的,......
  • HDOJ2093 考试排名
    考试排名TimeLimit:1000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):16041    AcceptedSubmission(s):5604......
  • 对现状的反思
    1、对现状有那谢谢不满意的地方?1)工作时间不自由,不能在完成工作后,自由的做自己的事情2)工作时间不自由,不能随时请假回家处理家里的事情3)工作离家庭太远,没法照顾家庭,没法工......
  • 2.13~2.17反思
    2.14Problem-C-Codeforces设x局有胜负,y局平局易得x+y=n(n-1)/2,3x+2y=kn解得x=(k-n+1)n,y=((3n-3)/2-k)n 要使得y越小越好当n为奇数时 显然k取(3n-3)/2时y=0 ......
  • 2.18 考试总结
    A. 基础逆序对练习题字符串哈希85~90。想到了统计贡献,O(q*Z^2)查询的方法,但是用哈希卡MLE(双哈希MLE,单哈希TLE),应该用字典树预处理。以后想用字符串哈希的时候应该......
  • 2023/2/17 考试总结
    时间安排7.30~7.47发现重题,于是换题。7.47~7.52T1很sb,写了。O0O0O0OO0O0O0O0O0O0O0O0O0O0O0O00O7.52~8.40T2不是很sb,想了个状态数巨大的dp套dp。dfs搜了一下只有36......