zcmimi's blog

categories/刷题记录/共659篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

首先,我们只用分析 NO 的情况,其他的都是 YES,NO 的情况有两种:

  1. x 既不在 A 中,也不在 B 中,即找不到 a-x 和 b-x,NO;
  2. x 既可以在 A 中,也可以在 B 中,也就是找到了 a-x 和 b-x,如果 x 在 A 中,那么 b-x 一定不在 B 中,因为数唯一,所以 b-x 只能在 A 中,也就是说必须存在 a-(b-x),如果不存在就行不通,同理得如果 x 在 B 中,则必须存在 b-(a-x),如果不存在就行不通,那么如果两个方案都行不通了,也就是说 NO 了。
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

一个矩形要想被保护的话,必须满足所有行 / 所有列上均有一个车的限制。这样我们解决问题就可以转化为判断一个矩形所有行上是否都有一个车了(对于列只需要把图转一下做就可以)。这样我们自然想到线段树 + 扫描线,我是用列上的扫描线从上到下,每一次扫到一个矩形的下边界就判断一下。线段树上维护每一列上距离最远的一个车的纵坐标,我们判断一个矩形是否被保护就只需要判断最远的车是否在当前矩形的范围内了。感觉OFN说的扫描线就是把问题转化到一个前缀的维护上面去其实是挺有道理的恩~

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们可以用分治愉快的解决这道题

答案统计的时候记得开long\ long

由于某种不可抗力,ai的值将会是1~10^9内随机的一个数。(除了样例)

看到这句话了没?

所以不用考虑分治是否会tle

不过我加了个rmq,就算没有这句话也可以过

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

自己写了个莫队,结果51nod跑的太慢,然后TLE(MLE)

题解妙极了:

离线之后,从左向右扫一遍,让每个值存储“当前已扫过的部分中,右边第一个与自己相等的点到自己的距离”,然后如果当前扫到的点是询问的右端点的话,就回答这个询问。

这里面有个很巧妙的地方就是在询问的时候按r的大小从左往右询问,每次更新的时候更新的是和这个点最近的左边的点。因为只有更新到第r个点时才能能查询 l - r 的区间例如:1 2 3 4 1 只有在 r 等于 5 时才能询问 L - 5的区间,此时更新第一个1的值为4,如果L > 1的话区间并未更新所以查询线段树中L- 5的最小值还是INF

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

检验每个数是不是在这个集合: 集合中所有是它的倍数的gcd是不是它

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

说实话,我觉得我是太傻吊了,一道动动脑筋就可以写的题我能写成麻烦的dp

dalao的代码:(直接扫描一遍就可以过了)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先按左端点排序,每次添加右端点的时候如果堆中个数等于k就统计答案,然后弹出最小的右端点

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

首先将数列按位分解成32个位数列.

枚举区间的左端点,,区间的and值要对答案有贡献必须为1,随着右端点右移,and值为不递增的,而区间的or值要对答案有贡献必须为1,随着右端点右移,or值为不递减的。

可以求出每一段一段的最大长度然后统计

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

\sum_{x=1}^n \sum_{y=1}^n [gcd(x,y)=1][a_{b_x}=b_{a_y}]

可以直接记录v[a_{b_x}]然后统计,用莫比乌斯容斥

34/66
Search
search