【JZOJ4727】挺进 题解题目 ETG 的地图是树形的,相邻房间有一定距离。一开始,系统会随机断掉一条边,然后把四个宝箱两两分布在每个联通块的最远点对上。 一开始,小 Z 会出生在一个有宝箱的房间,然后他走到有另外一个宝箱的所在地,接着系统把他送到另一个联通块的某个宝箱处,然后小 Z 走到最后一个宝箱处,就通关了。 小 Z 想知道他最多会走多少距离。 $n \leq 10^5$ Aug 22 OI/XCPC 算法_DP, 算法_线段树 Comments
【JZOJ4587】Snow的追寻 题解题目大意 有一棵有 $n$ 个节点的根节点为 1 的树,他只能走一条不经过重复节点的路径。 给出 $q$ 个形如“$x\ y$”的询问,表示他不能走到 $x$ 和 $y$ 的子树中。现在他想知道对于每组询问,他能走的最长路径是多少,如果没有,输出 0。 $n, q \le 10^5$ Aug 22 OI/XCPC 算法_线段树 Comments
【JZ雅礼联考】斐波那契 题解题目大意 定义Fibonacci数列为:$F[1]=1;~F[2]=1;~F[n]=F[n-1]+F[n-2]~(n>2)$ 现有一个n个元素的数列$a$,进行m个操作,操作类型如下: 1 L R$~$表示给$a_i$加上$F[i-L+1]$,其中 L<=i<=R 2 L R$~$表示询问$\sum_{i=L}^Ra_i~mod~(10^9+9)$ 1<=n, m<=10^5 Aug 21 OI/XCPC 算法_平衡规划(定期重构), 算法_数论, 算法_线段树 Comments
【JZ雅礼联考】跳楼机 题解题目 Srwudi的家是一幢h层的摩天大楼。经过改造,srwudi的跳楼机可以采用以下四种方式移动: 1、向上移动 $x$ 层; 2、向上移动 $y$ 层; 3、向上移动 $z$ 层; 4、回到第一层。 现在 DJL 在第一层,跳楼机也在第一层。求DJL可以乘坐跳楼机前往的楼层数。 $h \le 10^{18},\ \ x, y, z \le 10^5$题目大意 给出h、x、y、z,求 [1,h] 中有多少个数,可以表示成 ax+by+cz 的形式。 Aug 21 OI/XCPC 算法_最短路模型 Comments
【JZOJ4718】准备食物2 题解题目大意 现在觉有 m 种食物,第 i 种食物有 a[i] 份。觉要为 n 个宠物按编号顺序分配食物,每个宠物需要 1 份食物。 觉通过读心,得出了每个宠物吃了每种食物后的喜悦值。觉还发现,对于其中一些宠物,假设它的编号为 i,如果 1~i-1 的宠物中,超过 s[i] 个被分配了第 num[i] 种食物,那么它会反动。 在不反动的情况下,求所有宠物的喜悦值之和最大。 1<=n<=200, 1<=m<=100, 0<=喜悦值$v[i][j]$<=10^5 Aug 20 OI/XCPC 算法_网络流/匹配 Comments
【搬自Spoj-SOPARADE】第四次忍者大战 题解题目大意 现在要将n个忍者排成一行,每个忍者有一个标识a[i](1<=a[i]<=4),相邻两个忍者的标识的差的绝对值一定要大于等于2,同时,有m组形如”b[1],b[2],b[3]…b[k]”的约束条件,表示这些忍者的标识各不相同。 现在我们想知道,给出n和所有约束条件后,是否存在一种a序列,使得a满足这些条件。 n,m<=100000 Aug 18 OI/XCPC 算法_2-SAT Comments
【GDOI2016】疯狂动物城 题解题目大意 n个节点的一棵树,有三种操作。 1:将x到y的路径上的所有点的点权加上delta 2:询问x到y的答案。答案的计算为:对于路径上的点i,设它到y的距离为s,则i的贡献为1加到s。 3:将这棵树恢复到第x次1操作之后的版本。 操作数为m,强制在线。 Aug 18 OI/XCPC 算法_树链剖分 Comments
【JZ雅礼联考】Binary 题解题目大意 给定一个长度为 $n$ 的整数数列 $a$ 和 $q$ 次操作: 修改操作:形如 1 x y,表示将 $a_x$ 的值修改为 $y$; 询问操作:形如 2 x y,表示询问$\sum_1^n(a_i+x)~and~y$的值。 $n,q \le 10^5$ $0 \le a_i,x,y \le 2^{20}$ Aug 17 OI/XCPC 算法_位运算 Comments
【搬自usaco2015Dec】【JZOJ4684】卡牌游戏 题解usaco原题叫 High Card Low Card【题目大意】 有2n张牌,分别是1~2n。WWT有其中的n张牌,你有另n张。 游戏规则本来是这样的:每一回合,你和WWT同时打出一张牌,谁大谁赢。但是,你可以在任意一个时刻将游戏规则改为“谁小谁赢”,但你只能改一次。 现在给定WWT的牌和出牌顺序,求你最多赢多少局。 n<=50000 Aug 14 OI/XCPC 算法_线段树 Comments
【JZOJ4473】Incantation Solution题目大意 有 n 次操作,每次往序列 A 末尾插入一个元素,问每次插入后,新产生了多少个本质不同的连续子序列。 Apr 27 OI/XCPC 算法_字符串 Comments