树的计数[NOI2013]

题目描述我们知道一棵有根树可以进行深度优先遍历(DFS)以及广度优先遍历(BFS)来生成这棵树的 DFS 序以及 BFS 序。两棵不同的树的 DFS 序有可能相同,并且它们的 BFS 序也有可能相同,例如下面两棵树的 DFS 序都是 1 2 4 5 3,BFS 序都是 1 2 3 4 5。 现给定一个 DFS 序和 BFS 序,我们想要知道,符合条件的有根树中,树的高度的平均值。即,假如共...

方伯伯的玉米田[SCOI2014]

题目描述方伯伯在自己的农田边散步,他突然发现田里的一排玉米非常的不美。这排玉米一共有$N$株,它们的高度参差不齐。方伯伯认为单调不下降序列很美,所以他决定先把一些玉米拔高,再把破坏美感的玉米拔除掉,使得剩下的玉米的高度构成一个单调不下降序列。方伯伯可以选择一个区间,把这个区间的玉米全部拔高$1$单位高度,他可以进行最多$K$次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。问能最多剩多少...

LCT的进阶应用

关于LCT的进阶应用 不光是写算法思路,因为已经有很多人写过了,更重要的是代码写法中的细节,不然LCT各种奇怪应用的细节够你一题调一个小时 本篇文章将助你考试一遍过样例! 当然,还有一些基础应用比如维护路径信息或者维护联通性,但是代码都相对比较模板,所以也没什么好写 一. LCT维护边双连通分量有些题目中会动态加边并有形如“x到y之间有多少必经边” “某个边双内有多少点”的询问,这时候需要用...

长跑[BZOJ2959]

题目描述某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。为了让同学们更好地监督自己,学校推行了刷卡机制。学校中有$n$个地点,用$1$到$n$的整数表示,每个地点设有若干个刷卡机。有以下三类事件: 修建了一条连接A地点和B地点的跑道。 A点的刷卡机台数变...

我们的CPU遭到攻击[LOJ558]

题目描述给你一个有$n$个点的森林,点有黑白两种颜色,初始时所有点都是白色,森林的每条边有边权,初始时这个森林有$m$条边。 对这个森林进行$k$次操作,操作有三种: L u v w:添加一条连接$u$和$v$,长度为$w$的边。 C u v:删除连接$u$和$v$的边(保证存在)。 F u:反转点$u$的颜色(黑变白,白变黑)。 Q u:询问所有与$u$相连的黑点到$u$的距离之和。...

历史[ZJOI2018]

题目描述&输入/输出格式[ZJOI2018]历史 题解首先,没有修改时的答案可以使用树形DP解决 上图中,红色数字表示$a_x$,蓝色数字表示$x$子树的点权和$sum_x$ 观察点$2$,显然只有$2,5,6$”崛起”时才有可能在$2$发动战争 显然,当操作顺序形如$5,2,5,6$时,会在$2$进行三次战争,为最大值。 再来看点$1$,其实我们可以把$2,5,6$三个点看作一个点...

字符串[LOJ6517]

题目描述有$N$个字符串,每个字符串有一个权值$v_i$。随后给出$M$次询问,每次对一个区间进行检测。令最长的字符串长度为$L$,那么会给出$g_1,\cdots,g_L$表示每个长度的字符串的「识别值」。 对若干个字符串构成的集合$P$进行测试的过程如下: 对字符串$S$定义$f(S)$表示$S$在$P$中以其为前缀出现的串的权值和。 那么如果$S$在$P$中作为前缀出现过,并且$B*f...

奥运公交[LOJ3255]

题目描述JOI 王国共有$N$个城市,这些城市从$1$到$N$编号。共有$M$条公交线路连接这些城市,这些线路从$1$到$M$编号。第$i$条公交线是从城市$U_i$到城市$V_i$的,票价为$C_i$日元。如果乘客乘坐第$i$条公交线,他只能在城市$U_i$上车,在城市$V_i$下车。从一个城市到另一个城市可能有多条公交线。 不久,JOI 王国将举办奥运会。K 理事长是 JOI 王国交通部...

BLO-Blockade[POI2008]

题目描述在Byteotia有$n$个城镇。 一些城镇之间由无向边连接。在城镇外没有十字路口,尽管可能有桥,隧道或者高架公路(反正不考虑这些)。每两个城镇之间至多只有一条直接连接的道路。人们可以从任意一个城镇直接或间接到达另一个城镇。每个城镇都有一个公民,他们被孤独所困扰。事实证明,每个公民都想拜访其他所有公民一次(在主人所在的城镇)。所以,一共会有$n*(n-1)$次拜访。 不幸的是,一个程...

压力[BJOI2013]

题目描述如今,路由器和交换机构建起了互联网的骨架。处在互联网的骨干位置的核心路由器典型的要处理100Gbit/s的网络流量。他们每天都生活在巨大的压力之下。小强建立了一个模型。这世界上有$N$个网络设备,他们之间有$M$个双向的链接。这个世界是连通的。在一段时间里,有$Q$个数据包要从一个网络设备发送到另一个网络设备。一个网络设备承受的压力有多大呢?很显然,这取决于$Q$个数据包各自走的路径...