青竹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篇）

P2633 Count on a tree 树上主席树

树上主席树在树上根据dfs序建立主席树。题目给定一棵 n 个节点的树，每个点有一个权值。有 m 个询问，每次给你 u,v,k，你需要回答 u xor last 和 v 这两个节点间第 k 小的点权。其中 last是上一个询问的答案，定义其初始为 0，即第一个询问的 u 是明文。维护主席树...

2020-07-13

0 417

区间内不同数的个数

题目链接询问区间内不同数的个数做法一：树状数组做法：离线处理，将以r从小到大排序，一个标记数组记录数出现的位置，树状数组里只记录当前所有相同的数的最右位置，这样一个数就只会被加一次。 #include <bits/stdc++.h> using namespace std; ...

2020-07-13

0 446

hdu5919 Sequence Il 主席树

题目链接题意给出一个序列，问区间[l, r]中所有不同元素出现的第一个位置（取最左）组成的序列中的第k/2个，k是区间不同数的个数。第i个询问区间依赖于第i-1个询问的答案，所以是强制在线的。思路区间第k个，显然是主席树，和查询区间不同数的个数一样，都是相同的数只取一个，但这个是取相同数的...

2020-07-13

0 533

POJ2253---Frogger最小最大边

题目链接题意给n个石头的坐标，要求从一个石头到另一个石头路径上石头之间的长度的最小最大距离。思路最短路的变形，dijkstra算法是有一个核心条件，d[v] > d[u] + cost[u][v]则替换，因为到v的距离有更小的，这里可以用d[v] > max(d[u], cost...

2020-07-13

0 512

POJ - 1797最大最小边

题目链接题意 n个点，m条边，求从1到n的路径上最大的最小边，（如，有1 2 3，1 3 4， 2 3 5这几条边，从1到3最大的最小边就是4）思路松弛操作替换为d[v] = min(d[u], dis[u][v])，因为要找最大的边，所以每次进行松弛的的时候是找最大的边。 #include...

2020-07-13

0 364

POJ - 1860判断正环

题目链接题意有n种类型的货币，m个城市可以兑换两种货币，一个人手上有v块s类型的钱，要求判断是否可以经过若干次兑换后这个人手上的s类型的钱增加了。思路对于每种货币，建立一个点，两种货币可以交换，则这两个点之间有一条边，经过若干次兑换后要回到s类型的钱，则一定存在环，而钱要增加，则需要存在正...

2020-07-13

0 508

poj3360-floyd传递闭包

题目链接题意 n头牛，给出m个a打败b的结果，求有多少头牛的排名可以被确定。思路能确定排名的牛，也就是能确定击败它的牛的数量加上能确定被它击败的数量等于n-1,就可以确定排名。只需要判断能否到达，直接用floyd算法： mp[i][j]|=(mp[i][k]&mp[k][j]); ...

2020-07-13

0 626

POJ - 1511 Invitation Cards 往返最短路之和正向反向存边

题目链接题意给P个点Q条边的图，求所有点到1这个点的往返最短路之和。思路正向和反向分别存边，跑两遍dijkstra就可以了。 #include <iostream> #include <cstdio> #include <queue> #include ...

2020-07-13

0 432

POJ - 3159 Candies最大差异

题目链接题意 n个人分糖果，有m个约束条件，a认为b不能比他多c个糖果，求1和n的最大糖果数量差。思路约束条件等价为num[a] + c >= num[b]。相当于从a到b有一条等于c的有向边，这样就转换为了最短路问题，直接用dijkstra求1到n的最短路即可。参考大佬博客由p[...

2020-07-13

0 513

线性基基础问题

大佬的博客假设有n个数，这n个数能组成的异或和的集合为V，线性基就是能表示这个异或和集合V的最小集合。线性基的作用:求解异或和第k小、异或和最大值、某个数是否存在于异或和集合里等问题。洛谷P3812 求异或和的最大值 #include <bits/stdc++.h> using ...

2020-07-13

0 511