联赛前的坑 STICK

马上就要noip了 我觉得还有一点算法呀、数据结构的坑要填。 或者说还要复习一点吧。 字符串 Trie KMP 图论 各种奇怪的tarjan 最小割 树链剖分 k短路 次小生成树 最短路计数 数据结构 平衡树 可并堆 数论 剩余定理 矩阵 概率、期望 组合游戏 其他算法  ...

【算法】高斯消元

【算法】高斯消元

传送门 我们可能会遇到一些解线性方程组的问题。 这个时候,我们就需要用到高斯消元。 举个例子: 我们可以先把它转化成一个3\times 4的矩阵。 其中前面3\times 3表示系数,后面3\times 1表示等号右边的常数。 我们发现,类似方程组的加减消元,两行之间加减不会影响最终方程组的解,交换两行也不会。 那么我们发现,如果我们每次都通过加...

【题解】uvalive4730 王国

传送门 非常有趣的一道题目。 题目大意 坐标系上有n个点,编号为0到n-1每个点的坐标是(x, y) 初始时点与点互相独立。 然后会有m次操作。 给定两个点A,B,把A和B连线,使他们成为一个联通块。 询问一条y=C的水平线与几个联通块内部的连线有相交(切),且这些联通块...

【算法】Tarjan求割点

填坑美滋滋。 割点是什么 如果一个点A是割点,那么在原图删去A点后原图联通块数会增加。 Tarjan 先只考虑联通图。 算法主体是dfs,依赖于一个叫“时间戳”的定义。 时间戳就是说执行这一次dfs是第几次。 emmm可以用这个东西卡时间骗分 对于每个点u,定义两个数组pre[u...

密码保护:【坑】dalao

C++ #define DREP(i, s, e) for(register int i = s; i >= e ;i--) #define REP(i, s, e) for(register int i = s; i <= e ;i++) #define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__) #...

【题解】SCOI2008 奖励关

传送门 题目大意 系统会随机给出k个食物,食物的种类共有n种。 吃每种食物之前必须先吃某些食物,一种食物吃完后会有一个收益val[i]。 求期望最大收益。 思路 题面中n\le 15这个条件似曾相识,考虑状压dp。 设dp[i][j]表示当前吃到了第i个食物,状压后已经吃了的食...

【题解】NOIP2007 矩阵取数游戏

自己开的坑,跪着也要填完。 题目大意 有一个n\times m的矩阵,每次可以取出每行的首项或末项。 一个数k的收益是k\times 2 ^ i,其中i表示k这个数在第i次被选出。 求最大总收益。 思路 简单的dp。 发现每一行互不影响,分开做。 设dp[i][j]表示选择区间[i,j]所获得...

密码保护:【题解】ZJOI2007 最大半连通子图

传送门 讲课听来的,exciting! 题目大意 一个有向图G=(V,E)称为半连通的满足:图中任意两点u v存在一条u到v的有向路径或者从v到u的有向路径。 给定一个有向图G,请求出G的最大半连通子图拥有的节点数K,以及不同的最大半连通子图的数目C。由于C可能比较大,仅要求输...

【题解】HNOI2010 弹飞绵羊

传送门 题目大意 有n个装置,编号从0到n-1,每个装置有一个弹力系数k[i],表示在这个位置的绵羊会被弹到第i+k[i]个装置,若不存在第i + k[i]个装置,则绵羊被弹飞。 给出m次操作,每次可能修改一个装置的弹力系数或询问绵羊从某个装置开始被弹几次会被弹飞。 分块 ...

【算法】分块

分块复杂度正确,怎么能叫骗分? ——Dr.Brave Stone Fake定义 分块就是把一个序列分成几个小块,同时对小块和单个元素进行操作。 这对于一些区间操作来说,常常有意想不到的好效果。 例子 打个比方,我们要区间加、区间查询和。 我们当然可以树状数组、线段树。 但...

【数据结构】左偏树

模板传送门 STL是个好东西,因为它集成了许多数据结构,比如priority_queue。 但是要合并时,priority_queue就GG了。 那么有两种解决方案。 使用pb_ds,但是由于其__gnu_pbds的下划线开头命名空间可能会出事。 手写。 左偏树 左偏树是一个堆,它有如下性质。 堆...