NOIP提高组模拟赛Day2

NOIP提高组模拟赛题解

比赛地址
Markdown&PDF&大样例
[数据以及全部压缩包]明天发


Agent2

对于40\%的数据 N,M \leq 10^3

对于N,M \leq 10^3的数据,我们可以O(n^2)判断一下前面有多少Agent的区间是包括当前要查询的天数的。

对于100\%的数据 1 \leq a,b \leq N \leq 10^7,M \leq 4*10^5

我们可以通过树状数组维护一个差分数列,在每次询问中只要O(logn)进行修改或者进行查询,总复杂度为O(mlog_{n})

也有其他优秀的做法
来自小粉兔的提交


Portal2

对于20\%的数据 数据保证不会出现MOVE/SWAP操作,命令总数 \leq 100

既然不会出现MOVE/SWAP操作,就是简单得维护两个栈得问题而已。

对于40\%的数据 命令总数 \leq 1000

这个有可能会出现MOVE/SWAP操作,但是指令数太少了,可以O(n^2)过去,只要暴力取出再加入即可。

对于60\%的数据 数据保证MOVE的操作次数不会超过10000次,命令总数 \leq 10^5

这个点保证MOVE的出现次数不超过1000次,那么MOVE的总时间复杂度为O(10^9),显然是不可能的。但是我们考虑一下MOVE操作其实是把栈头接栈头,然后拼起来。所以我们可以考虑用双头链表维护一下这个栈(也许就是怎么神奇),就可以快速进行MOVE操作。

对于100\%的数据 0 \leq X,Y \leq 1,命令总数 \leq 10^6

在处理链表时,SWAP操作其实不一定要真的对换两个数组,只是SWAP的时候对换一下对应更改的数组的下标即可。因为中元素的数据可能达到2^{63}-1所以要开long long

数据保证无论任何情况,栈中元素的值X满足0 \leq x \leq 2^{63}-1

std代码在另一台电脑上,明天发

同样有其他优秀的做法
来自memset0的代码


War2

对于20\%的数据 1 \leq M \leq N \leq 4,0 \leq A[i],B[i] \leq 10^3

这样数据可以枚举一次全排列然后再计算一下当前的分数值,取最大值即可。

对于100\%的数据 1 \leq M,X[i],Y[i] \leq N \leq 18,0 \leq K \leq N^2−N,0 \leq A[i],B[i] \leq 10^9

总体数据而言N \leq 18,我们很容易想到着就是DP啊,我们DP数组f[i][j],i用状态压缩,代表有那些点已经被占领过了,j代表上一次我占的是那个。对于每一次状态转移,若当前我们要占领的Portal在占领j后有加分,那么就转移加分与基础值的和,否则只转移基础值。最后判断一下当i代表的状态已经有占领m个了,就记录下当前的最大值。

也有来自SCKer的优秀程序

另在本博客10月6日将有一份NOIP题目分析报告,有兴趣的记得关注一下。

“NOIP提高组模拟赛Day2”的6个回复

    1. 同,T1 我线段树只有70
      (不小心交上去的对拍暴力还有60 (ˉ▽ ̄~) )

发表评论

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