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})。 ......  查看更多

NOIP提高组模拟赛Day1

NOIP提高组模拟赛题解

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

Agent1

对于20\%的数据 N \leq 10

这样的话我们可以使用DFS搜索进行枚举,枚举每一个Agent是进A队还是进B队还是不参加大战,复杂度为O(3^{10})

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

然而我们也可以加入一些剪枝,例如中间判断一下有没有元素是不符合的就剪掉,例如B里加入了个比A里最大元素小的人,那么就剪掉,估计可以再卡过几个点。 ......  查看更多

2018-4-13模拟赛:解题报告

比赛题目

2018-4-13模拟赛:A 2018-4-13模拟赛:B 2018-4-13模拟赛:C 2018-4-13模拟赛:D

解题概况

今天是休假后的第一场比赛,所以呢,很多东西都很陌生,这样的话我觉得我还是好好复习文化课吧,不存在的,那么,还是认真的写一下题解吧,加油。

解题详情

2018-4-13模拟赛:A

这题的话其实正负数没什么区别的呢。
最优的策略一定是尽量少走回头路,尽量往终点的方向跳。我们先一直跳,跳到已经超过终点,且离终点的距离为偶数时的步数即为答案,因为此时可以通过调整前面一些跳跃的方向,使得我们刚刚好到达终点,为什么呢?
当没有到达终点时,显然不行。
当超过终点且离终点的距离为奇数时,假设当前的位置在pos,若我们把之前往终点跳x距离的一步改为往终点的反方向跳x距离,那么我们的位置就到了pos-2x,只能到离当前位置为偶数距离的地方,并不能到达终点。
同理,当超过终点且离终点的距离为偶数时,我们就可以通过调整之前某些跳跃的方向,到达终点。
AcceptCode ......  查看更多

2018-4-13模拟赛:D

2018-4-13模拟赛:D
假如可以快速预处理出所有点的最远点那么就可以O(1)回答了。
有一个经典的树形dp套路就是dfs两遍,第一次维护子树内的信息,第二次求出答案(包括子树外)。
具体的实现/理解方法很多。对这题而言,在第一次dfs的时候求出子树内的最长链和次长链(这两条链需要从不同的儿子转移过来)。
然后再做一次dfs,这次要用fa更新儿子,假如最长链就是由这个点转移过来的话就用次长链更新,否则就用最长链。
因为上一问太水,所以强行套了个单调队列……
求极值不超过m的最长子串应该是单调队列的经典操作。
考虑双指针,因为r右移时l也是单调右移的,所以用两个单调队列得到l即可,一个单调上升,一个下降。
假如您nlogn过了那我也没办法…… ......  查看更多

2018-4-13模拟赛:C

2018-4-13模拟赛:C
这题暴力分70,呵呵,为什么还有人拿40的呢
Std可以转换成对于第i双鞋,所有满足a_j \le s_i的格子j可以走,一次最多可以从x走到x + d_i。不能走过去的情况只有一种:连续的不能走的格子的长度\ge d_i。所以我们可以把鞋子按s从大到小排个序,格子也排个序,用一个链表维护当前可以走的格子。对于当前处理的鞋子i,把链表中a_j \gt s_i的格子删掉,更新一下连续不能走的格子的长度的最大值,那就可以知道鞋子i的答案。复杂度是O(nlogn + blogb + n + b)。 ......  查看更多

2018-4-13模拟赛:B

2018-4-13模拟赛:B
这题就是字典树的基础用法啦,但是呢,作为休假选手,我好久没打过比赛了,打都不会打。
这题就是一个贪心。。你先建立把全部串在字典树上面建出来。然后对于每一个点,如果他是一个原名的结束节点,那么c++,如果是专属名字,那么。c1++显然,如果有一个点,c1c2同时不为0,那么他,那么他们在这里匹配肯定是最优的。然后多出来的一些,就给父亲去处理。容易发现这个做法肯定是对的。 ......  查看更多

2018-4-13模拟赛:A

2018-4-13模拟赛:A
这题的话其实正负数没什么区别的呢。
最优的策略一定是尽量少走回头路,尽量往终点的方向跳。我们先一直跳,跳到已经超过终点,且离终点的距离为偶数时的步数即为答案,因为此时可以通过调整前面一些跳跃的方向,使得我们刚刚好到达终点,为什么呢?
当没有到达终点时,显然不行。
当超过终点且离终点的距离为奇数时,假设当前的位置在pos,若我们把之前往终点跳x距离的一步改为往终点的反方向跳x距离,那么我们的位置就到了pos-2x,只能到离当前位置为偶数距离的地方,并不能到达终点。
同理,当超过终点且离终点的距离为偶数时,我们就可以通过调整之前某些跳跃的方向,到达终点。 ......  查看更多