Mr Panda and Survey[HDU6001]

题目链接https://acm.hdu.edu.cn/showproblem.php?pid=6001 题解设$f(S)$表示有多少种选问卷的情况使得$S$中所有元素都不是好问题 设$ans[S]$表示选择的问题集合是$S$时,有多少种选择问卷的方案使得它们全部是好问题 那么由容斥原理,$ans[S]=2^n+\sum\limits_{S_2\subseteq S}(-1)^{t(S)}f(...

矩阵游戏[NOI2013]

题目描述婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的$n$行$m$列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质:若用$F[i][j]$来表示矩阵中第$i$行第$j$列的元素,则$F[i][j]$满足下面的递推式: $$F[1][1]=1$$ $$F[i,j]=a\times F[i][j-1]+b (j\neq 1)$$ $$F[i,1]=c\times ...

方伯伯的商场之旅[SCOI2014]

题目描述方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个人面前有几堆石子。说来也巧,位置在$i$的人面前的第$j$堆的石子的数量,刚好是$i$写成$K$进制后的第$j$位。 现在方伯伯要玩一个游戏,商场会给方伯伯两个整数$L,R$。方伯伯要把位置在$[L,R]$中的每个人的石子都合并成一堆石子。每次操作,他可以选择一个人面前的两堆石子,将其中的一堆中的某些石子移动到另...

树的计数[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...