UOJ Logo zgjkt的博客

博客

【bzoj2326】数学作业

2015-12-14 13:24:47 By zgjkt

题目大意

将$[1,n]$这$n$个数连在一起,然后求这个大数字除以$m$的余数

阅读更多……

【poj3070】Fibonacci

2015-12-12 15:52:08 By zgjkt

【bzoj2733】永无乡

2015-12-11 13:46:41 By zgjkt

题目大意

永无乡上有$n$个岛,原本有$m$座桥连接着永无乡,每座岛有它的重要程度$[1,n]$与编号一样

执行$q$次操作,操作分两种:

  1. 新建一座桥连接两个岛屿

  2. 询问与一个岛相连通的岛屿中重要程度第$k$小的岛屿编号

阅读更多……

【bzoj3158】千钧一发

2015-12-03 13:51:28 By zgjkt

【bzoj2657】旅游

2015-11-30 13:47:27 By zgjkt

题目大意

给出一个凸$n$边形,按顺时针给予顶点编号为$[1,n]$

如今把这个凸$n$边形划分成$n-2$个三角形,给出这些三角形的三个顶点编号

询问两个不相邻顶点间的路径最多可以经过多少个三角形(路径中包含一个三角形的一条边视作经过这个三角形)

阅读更多……

【bzoj1912】patrol 巡逻

2015-11-27 14:08:43 By zgjkt

题目大意

给出一棵有$n$个节点的有根树,然后新建$k$条边,边权全都是$1$

询问此时从根节点出发遍历回到根节点的最短路程

阅读更多……

【bzoj2654】tree

2015-11-21 16:59:31 By zgjkt

题目大意

给你一个有$n$个点$m$条边的无向带权连通图,每条边是黑色或白色

让你求一棵最小权的恰好有$need$条白色边的生成树

阅读更多……

各种区间第K小问题

2015-11-16 13:23:03 By zgjkt

【poj2104】$K-th\ Number$——无修改区间第K小问题

题目大意

给出一个有$n$个数的数列,执行$m$次询问

每次询问在区间$[l,r]$中第$k$小的数

数据范围

$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 5000$


题解

由于操作只有询问,不执行修改,那么可以直接套用可持久化线段树即可

Question Ⅰ:可持久化线段树是啥?

可持久化线段树也叫主席树,它的特点就是能够充分利用历史信息

对于这道题,具体做法就是,建$n$棵权值线段树,第$i$棵树记录在数列区间$[1,i]$中权值出现的个数

然后由于这$n$棵权值线段树的结构都是相似的,所以询问区间$[l,r]$时,可以用第$r$棵权值线段树对应减去第$l-1$棵权值线段树,得到$[l,r]$区间权值的信息,最后沿着新树直接向下查找得到第$k$小的数

超人熊

Question Ⅱ:建n棵权值线段树,不会空间溢出吗?

直接大力造$n$棵权值线段树肯定会空间溢出啦,但可持久化线段树利用历史信息可以节省大量空间

具体来说,第$i$棵权值线段树和第$i-1$棵权值线段树相比,只是多更新了一个权值

那么这个权值在权值线段树中只是影响了单条路径而已,因此可以在第$i$棵线段树中把不影响的子节点直接指向第$i-1$棵线段树的对应节点,就可以节省好多好多空间啦!

鼓掌熊

Question Ⅲ:建立权值线段树,那么边界范围不会过大导致自取灭亡吗?

离散化大法好!

阅读更多……

【NOIP'2015'】普及组扯淡++

2015-11-07 21:06:30 By zgjkt

【$T1$】金币

题目大意

国王给忠诚的$Saber$发工资,当连续的$n$天每天收到$n$枚金币时,$Saber$会在之后的$n+1$天每天收到$n+1$枚金币

询问在前$k$天一共怒领多少工资

超人熊

数据范围

$1\leqslant k\leqslant 10000$


题解

考你会不会编程咯



【$T2$】扫雷游戏

题目大意

给出一个$n\times m$的矩阵,矩阵中每个地雷格位置已知,求每个非地雷格八个邻格上的地雷总数(左上左下右上右下正上正下正左正右)

炸弹熊

数据范围

$1\leqslant n\leqslant 100,1\leqslant m\leqslant 100$


题解

考你会不会编程咯



【$T3$】求和

题目大意

给出$n$个格子,编号是$1~n$,每个格子染了一种颜色$Colour_i$,而且写了一个数字$Number_i$

若有两个不同的格子编号$x,z$满足奇偶性相同,且格子颜色相同,则这个二元组对答案的贡献是$(x+z)\times (Number_x+Number_z)$

求最终答案除以10007所得余数

数据范围

$1\leqslant n,m,Number_i\leqslant 100000,1\leqslant Colour_i\leqslant m$


题解

$(x+z)\times (Number_x+Number_z)=x\times Number_x+x\times Number_z+z\times Number_x+z\times Number_z$

则每个格子$x$在每个合法的二元组($x,z$)对答案的贡献是$x\times Number_x+x\times Number_z$,然而时间复杂度是$O(n^2)$,怎么办呢?

思考熊

可以记录集合$S$,使得在集合$S$中的格子两两可以组成一个合法的二元组,然后用$size$表示集合$S$的格子个数,$sum$表示集合$S$中的$\sum Number_i$,则集合$S$中的格子$x$对答案的独立贡献就可以表示为$$x\times Number_x\times (size-1)+x\times (sum-Number_x)$$

最后$O(n)$扫过去就好啦

鼓掌熊



【$T4$】推销员

题目大意

给出一个有$n$个数字的数列,数字的编号是$1-n$

选取k个数,假设其中编号的最大值为$m$,那么得到一个叫做疲劳值的东西,等价于$2\times m+k$个数的总和

询问当$1\leqslant k\leqslant n$时的$n$个当前最大的疲劳值

数据范围

$n\leqslant 10^5$


题解

用线段树维护数列最值,每当$k$增加,就取区间最值就好啦

【bzoj1407】荒岛野人Savage

2015-11-07 12:40:42 By zgjkt

题目大意

给出$n$只野人,第$i$只野人一开始会住在山洞$pos_i$里,每年会顺时针往前走$step_i$个山洞住下来,寿命是$age_i$

假设山洞是环形排布,且野人在有生之年都不会见到他的同类,询问山洞的最少个数

阅读更多……

共 63 篇博客