题目大意

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

阅读更多……

题目大意

输出$Fibonacci$数列第$k$项除以$10000$的余数

阅读更多……

题目大意

阅读更多……

题目大意

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

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

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

阅读更多……

题目大意

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

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

阅读更多……

题目大意

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

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

阅读更多……

【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 Ⅲ：建立权值线段树，那么边界范围不会过大导致自取灭亡吗？

离散化大法好！

阅读更多……

【$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$增加，就取区间最值就好啦

题目大意

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

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

阅读更多……

题目大意

红包把它的南瓜灯划分成了$n\times m$的网格，并用 $(x,y)$表示第$x$行，第$y$列的格子

两个格子是相邻的当且仅当它们有一条公共边，特殊地，$(x,1)$和$(x,m)$，红包也视为是相邻的，但是他不把$(1,x)$和$(n,x)$当做是相邻的

然后删除$k$个网格，询问当前矩阵中是否满足任意两个网格之间有唯一路径

阅读更多……