题目链接 题意 有n种类型的货币，m个城市可以兑换两种货币，一个人手上有v块s类型的钱，要求判断是否可以经过若干次兑换后这个人手上的s类型的钱增加了。 思路 对于每种货币，建立一个点，两种货币可以交换，则这两个点之间有一条边， 经过若干次兑换后要回到s类型的钱，则一定存在环，而钱要增加，则需要存在正权环，所以用通过上述方法建图，然后跑spfa，注意初始化d数组要初始化为-INF，并且松弛条件改为（d[y] < (d[x] - c[i]) * edge[i]）。也就是能使钱增加的判断条件。 #include <iostream> #include <cstdio> ...

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

题目链接 题意 给P个点Q条边的图，求所有点到1这个点的往返最短路之和。 思路 正向和反向分别存边，跑两遍dijkstra就可以了。 #include <iostream> #include <cstdio> #include <queue> #include <string.h> using namespace std; #define INF 0x3f3f3f3f typedef long long ll; #define pr pair<int, int> const int MAXN = 1e6 + 7; int head[2...

题目链接 题意 n个人分糖果，有m个约束条件，a认为b不能比他多c个糖果，求1和n的最大糖果数量差。 思路 约束条件等价为num[a] + c >= num[b]。相当于从a到b有一条等于c的有向边，这样就转换为了最短路问题，直接用dijkstra求1到n的最短路即可。 参考大佬博客 由p[j] - p[i] <= k可得p[j] <= p[i] + k 在单源最短路径的算法中有一步是“若mindis[j] > mindis[i] + dis[i][j]，则mindis[j] = mindis[i] + dis[i][j]，这样就满足mindis[j] <= mi...

大佬的博客 假设有n个数，这n个数能组成的异或和的集合为V，线性基就是能表示这个异或和集合V的最小集合。 线性基的作用:求解异或和第k小、异或和最大值、某个数是否存在于异或和集合里等问题。 洛谷P3812 求异或和的最大值 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 7; typedef long long ll; ll a[maxn], b[65], ans; int n, m; void prepare() { int cnt = 0; memset(b, 0, sizeof(b));...

题目链接 题意 给一个n个顶点m条边的无向带权图，求从1到n的一条路径上的最大异或和。 思路 从1到n的一条路径上，没有要求点各异、边各异，所以根据贪心的思想，如果有环的话，从1到n上的路径上的一个顶点，走过这个环再回到这个顶点，可能使异或值变大，所以遍历这些环，如果能使异或值增加的就走，最后可以得到最大异或值。这里用线性基求一个最小的 形成最大异或值 的集合。 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 7; typedef long long ll; int head[maxn], t...

题目链接 题意 给定n个数以及一个数q，将这n个数的所有子集（可以为空）的异或值从小到大排序得到序列B（这样B内就有2^n 个 元素），求出q在序列B中第一次出现的下标，答案对10086取模（默认q一定存在）。 思路 首先有一个定理：B数列中每个数字出现次数都是2^(n-cnt)，cnt为线性基的大小。知道了每个不同的数字都是2 ^(n-cnt)个后，只需要知道q在B里的排名就可以算出答案：2 ^(n - cnt) * (rank - 1) + 1。 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5...

题目链接 题意 n个人每人有一个物品，每个物品可以直接买，也可以通过其他物品抵押加上少量的钱买，每个人有一个等级，经过若干次交换购买的人中的最大等级差不能超过m。求要得到第一件物品的最少花费是多少？ 思路 如果没有等级约束就是一个最短路的模板题，根据a物品加w个金币换到b物品，可以建立一条有向边a->b，cost w。然后直接用最短路即可，但是因为有了约束，不能直接调用。考虑题目的要求是要换到编号为1的物品，所以能交换到1的人群中，等级差异不能超过m，并且这个等级范围要包括1的等级，因题目范围较小，直接枚举区间，多次调用dijkstra取最小值。 还有一个小技巧，题中没有规定起点，我们可...

hdu2767 题意 给n个点和m条有向边，求最少还需多少条边n个点构成强联通图。 思路 tarjan先处理出每一个强连通分量。 如果强连通分量的个数为1，则答案为0。 如果强连通分量的个数大于1，将每个强连通分量看成一个点，每个强连通分量之间可能存在边，a为没有出度的强连通分量的个数，b为没有入度的强连通分量的个数。则答案为max(a,b)(动手画下很容易得到)。 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 +7; typedef long long ll; int n, m, scc, l...

hdu4738 题意 n个岛m座桥的无向图，每座桥上有若干个士兵，派出最少的士兵只炸毁一座桥，使得n个岛不连通（派出的士兵不能少于驻守的士兵，特别的改桥的驻守人数为0的时候要派一个士兵）。 思路 用tarjan算法，满足dfn[u] < low[v]的(u,v)就是割边，直接处理出来取最小值，这里还有一个问题就是有重边，所以要判断一下。 #include <bits/stdc++.h> using namespace std; const int maxn = 1e3 +7; const int maxm = 1000000 + 7; typedef long long ll...

#6005 题意 给定正整数序列x1 , … , xn 。 （1）计算其最长递增子序列的长度s。 （2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。（每个数只能取一次） （3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的递增子序列。 思路 第一问：n^2的dp搞定，处理出dp数组，dp[i]表示下标为i的数为结尾的最长不下降子序列的长度是多少。 第二问：每个数只能取一次，考虑用dinic来写，流量即个数。主要在建图，建图有两个限制，一个是每个数只能取一次，还有就是要长度为s。只能取一次的条件可以用拆点解决，把一个点i拆成两个点i,i+n，然后将...

题目链接 题意 给出一个长度为 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个，考虑二分加分块，分块询问的时候求的是小于mid的数有多少个，二分逼近答案。 #include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int maxn = 1e5 + 7; typedef long long ll; int belong...

洛谷P1231 参考博客大佬Siyuan 题意 有n1本书，n2本练习册，n3本答案。给出m1个书和练习册的联系，m2个书和答案的联系，一本书一本练习册一本答案为一册，问最多可以组成多少册。 思路 如果只有两样东西就是典型的最大二分匹配问题，但这里有三种，所以匈牙利算法做不了，可以用最大流。建图方法是：源点->练习册->书（拆点）->答案->汇点。拆点很重要，下面是一个样例说明为什么要拆点，拆点也就是一个点拆成两个的意思。 如果没有拆点，下面的图用最大流跑出来就是2，显然答案并不是2，因为数只有一本。  将书的点拆成两个点，两点之间连一条容量为1的边，这样就可以限制书只...

大佬博客讲解 算法一 O（S^2），S是障碍点的个数。 算法思想：以每个障碍点作为极大子矩形的左边界和右边界，枚举所有的极大子矩形，再找出最大的子矩形，最后还要算一下遗漏的以范围内的左边界和右边界为极大子矩形的左右边框的矩形大小。 P1578 奶牛浴场 题目描述 由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。你还能帮助Clevow吗？...