[TJOI2018]数学计算

[TJOI2018]数学计算
这题一看上去哇,没有思路哎。
但是扎眼看了下路牌,卧槽,煞笔题。
一开始就先维护好一个1q的值为1的线段树,线段树维护的值就是他们乘积,1操作就是把i改到x2操作就是把x改到1,每次操作后输出tr[1].c就是乘积和就好。 ......  查看更多

[HAOI2014]贴海报

[HAOI2014]贴海报
就是简单的线段树加上离散化解决就好,但是也可以用分块做,留个坑
就是先离散化一下,然后用线段树维护区间值,然后线段树维护相同值就好。

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模拟赛: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)。 ......  查看更多