青竹qingzhu

分类

AC自动机(3) KMP(3) tarjan(2) 主席树(2) 二分(1) 优先队列(1) 倍增(2) 后缀数组(1) 后缀自动机(1) 图论(1) 技巧(3) 最短路(10) 树状数组(1) 线性基(3) 网络流(10) 题解(7)

/ 注册

TA的专栏 2篇文章 0人订阅

2篇文章 648人学习

全部文章（共51篇）

bzoj 2115 线性基

题目链接题意给一个n个顶点m条边的无向带权图，求从1到n的一条路径上的最大异或和。思路从1到n的一条路径上，没有要求点各异、边各异，所以根据贪心的思想，如果有环的话，从1到n上的路径上的一个顶点，走过这个环再回到这个顶点，可能使异或值变大，所以遍历这些环，如果能使异或值增加的就走，最后可以得...

2020-07-13

0 417

bzoj 2844-线性基

题目链接题意给定n个数以及一个数q，将这n个数的所有子集（可以为空）的异或值从小到大排序得到序列B（这样B内就有2^n 个元素），求出q在序列B中第一次出现的下标，答案对10086取模（默认q一定存在）。思路首先有一个定理：B数列中每个数字出现次数都是2^(n-cnt)，cnt为线性基的大...

2020-07-13

0 470

POJ - 1062 有限制的最短路

题目链接题意 n个人每人有一个物品，每个物品可以直接买，也可以通过其他物品抵押加上少量的钱买，每个人有一个等级，经过若干次交换购买的人中的最大等级差不能超过m。求要得到第一件物品的最少花费是多少？思路如果没有等级约束就是一个最短路的模板题，根据a物品加w个金币换到b物品，可以建立一条有向边a-...

2020-07-13

0 483

hdu2767——tarjan强连通分量

hdu2767 题意给n个点和m条有向边，求最少还需多少条边n个点构成强联通图。思路 tarjan先处理出每一个强连通分量。如果强连通分量的个数为1，则答案为0。如果强连通分量的个数大于1，将每个强连通分量看成一个点，每个强连通分量之间可能存在边，a为没有出度的强连通分量的个数，b为没有入度...

2020-07-13

0 498

hdu4738——tarjan割边

hdu4738 题意 n个岛m座桥的无向图，每座桥上有若干个士兵，派出最少的士兵只炸毁一座桥，使得n个岛不连通（派出的士兵不能少于驻守的士兵，特别的改桥的驻守人数为0的时候要派一个士兵）。思路用tarjan算法，满足dfn[u] < low[v]的(u,v)就是割边，直接处理出来取最小值，...

2020-07-13

0 787

#6005. 「网络流 24 题」最长递增子序列

#6005 题意给定正整数序列x1 , … , xn 。（1）计算其最长递增子序列的长度s。（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。（每个数只能取一次）（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的递增子序列。思路第一问：n...

2020-07-13

0 533

K小数查询求k小数的非主席树做法

题目链接题意给出一个长度为 n 的数列 A，接下来有m 次操作，操作有两种： 1 l r x，表示对i属于[l,r]，令Ai = min(Ai,x) 2 l r k，表示询问区间[l,r]中第k小的数。思路第k小的数，也就是说小于第k小的有k-1个，考虑二分加分块，分块询问的时候求的是小于m...

2020-07-13

0 440

P1231 教辅的组成——网络流为什么要拆点

洛谷P1231 参考博客大佬Siyuan 题意有n1本书，n2本练习册，n3本答案。给出m1个书和练习册的联系，m2个书和答案的联系，一本书一本练习册一本答案为一册，问最多可以组成多少册。思路如果只有两样东西就是典型的最大二分匹配问题，但这里有三种，所以匈牙利算法做不了，可以用最大流。建图方法...

2020-07-13

0 403

最大子矩形问题

大佬博客讲解算法一 O（S^2），S是障碍点的个数。算法思想：以每个障碍点作为极大子矩形的左边界和右边界，枚举所有的极大子矩形，再找出最大的子矩形，最后还要算一下遗漏的以范围内的左边界和右边界为极大子矩形的左右边框的矩形大小。 P1578 奶牛浴场题目描述由于John建造了牛场围栏，激起...

2020-07-13

0 619

#6010. 「网络流 24 题」数字梯形最大费用最大流建图

题目链接题意分别求三个规则满足条件的所有路径最大和。思路网络流问题最重要的是建图问题。 1.路径互不相交，也就是一个数字只能用一次，那就是拆点了，每个点拆分为入点和出点，入点和出点之间连一条容量为1费用为权值的边；建立一个源点和一个汇点，源点与第一行的入点相连，容量为1费用为0，最后一行的...

2020-07-13

0 584