8.5 NOIP 模拟测试 13

时间:2023-05-12 17:44:03

 今天的考试说实话T1很简单没A,我是傻X。T2T3难得一批,但是暴力的分还是拿了!

总结一下就是:骗分过样例,暴力出奇迹!只要瞎搞就行了

话说现在终于不像之前那么傻了,终于知道打暴力了,因为之前暴力不会打,所以总排行榜我底的一批,包括之前还有一场两个CE,直接奠定了我第二机房的基础,(下一轮再努力进第一机房吧!),我在这里也祝贺那些顺利升入第一机房的同学(我rp++)我也会努力的!

 

T1其实水的一批,但是我数学好并没有什么卵用,还是打的n*n的暴力,考试之后就想到了横行和数列的离线分治算法!

(然后就愉快的AC了!)

T1其实就是没有想到离线,其实考完试之后想一想就知道,这题肯定离线处理啊,woc,我当时就是脑残,然后我在改完题之后去看别人打的程序,发现我的思路和别人的不太一样,然后就在这里说一下!

我们可以吧行的操作和列的操作分开存到两个结构体中,我们已知可以$ O(1) $求出x行y列的数,以及任意x行或y列的权值和!(这是高考数学的事情!)然后我们就可以推出在进行完行的操作之后的第一列的权值和,然后我们就可以愉快的推出各列的权值和,然后再进行普通的列操作,最后统计答案就行了!时间复杂度$ O(max(n,m)) $但是常数稍大!

 

T2 跳房子;

首先一看时间限制3s然后n和m都不大,就想到了模拟,但是我的模拟死了,只有5分,是一个比较失败的模拟,然后其实当时乱搞一下都可以20+,然后找一下寻环节就可以80+,其实就是分快的思想,我们已知这是一个循环,然后他经过m步之后一定会回到第一列,所以我们就可以求出每一个格子到第一列会出现在哪一行,然后询问时通过取模,就可以减小复杂度,然后最后剩的那一段就直接暴力统计就行了!主要就是没想到分快,然后看见时间限制好像很宽裕就打的模拟,然后还死了!

 

T3 优美序列

这道题我一看就想到了之前的考试题,奇袭,然后我们就愉快的打了一个大暴力,然后因为人丑自带大常数,所以只有52分,别人都是60分,然后T3就炸了~

T3正解是线段树优化XXX,然后可以ST表优化暴力,本人卡到了92分,(据说remarkable卡A了%%%%%orz)然后,这道题的档次瞬间就掉了,但是这道题在luogu上是黑体,所以难度还是有的,鉴于大家都A了,提接我就先沽了,先去打别的了(逃)