- 博客(48)
- 收藏
- 关注
RSS订阅原创 最小费用最大流
SPFA版：题目描述同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。输入格式第一行有两个数M,N，表示技术人员数与顾客数。接下来n行，每行m个整数。第i+1行第j个数表...
2020-03-05 20:07:38
154
原创 牛牛的宝可梦Go
先floyd求一遍最短路。把每只宝可梦按出现时间的先后顺序排序。dp[i]表示前i只宝可梦能够捕获的最大战斗力之和。考虑如何转移，最先想到的一定是k方转移，但是铁定超时。然后发现地图最多只有200个点，也就是说最多200步，就能从一个点走到任意一个点（只要连通的话）。所以每次只用暴力往前for200个点，200以上的记录一下前缀max，每次直接从这里转移。#include <cs...
2020-02-10 23:18:24
265
原创 牛牛的Link Power II
设pre = 前缀1的数量，suf = 后缀1的数量，ppre = 前缀1的位置和，psuf = 后缀1的位置和。假设现在第i个1的位置是pos每个1对答案的贡献 = prepos - ppre + suf(n-pos+1) - psuf建四个树状数组，分别维护pre、suf、ppre、psuf#include <cstdio>#include <cstring>...
2020-02-10 23:06:36
113
原创 maki和tree
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <iostream>#include <map>#include <vector>#include <stack>#incl...
2020-02-10 21:18:53
100
原创 施魔法
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <iostream>#include <map>#include <vector>#include <stack>#incl...
2020-02-10 21:14:15
204
原创 求函数
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <iostream>#include <map>#include <vector>#include <stack>#inc...
2020-02-10 21:12:46
110
原创 最小割
（一）最小点割集最小点割集：给你一个图，有n个点，m条边，有源点S和汇点T，问你最少删去多少个点，使得S无法到达T。求法：对于每个点u，我们拆成入点u1，出点u2，u1和u2之间连一条边权为1的边。所有和u相连的点v，连一条（v2，u1）的边和（u2，v1）的边，边权都为INF。（别忘了上述所有边都要建边权为0的反边）。答案就是对新建的图跑最小割。题目描述农夫约翰的奶牛们喜欢通过电邮保持联...
2020-01-09 19:37:48
336
原创 Dinic求最大流模板
题目描述汶川地震发生时，四川**中学正在上课，一看地震发生，老师们立刻带领x名学生逃跑，整个学校可以抽象地看成一个有向图，图中有n个点，m条边。1号点为教室，n号点为安全地带，每条边都只能容纳一定量的学生，超过楼就要倒塌，由于人数太多，校长决定让同学们分成几批逃生，只有第一批学生全部逃生完毕后，第二批学生才能从1号点出发逃生，现在请你帮校长算算，每批最多能运出多少个学生，x名学生分几批才能运完。...
2020-01-08 14:56:40
90
原创 小B的询问
输入格式第一行三个整数 n,m,k。第二行 n 个整数，表示 小B 的序列。接下来的 m 行，每行两个整数 l,r。输出格式输出 m 行，每行一个整数，对应一个询问的答案。输入输出样例输入 #16 4 31 3 2 1 1 31 42 63 55 6输出 #16952说明/提示【数据范围】对于 100% 的数据，1≤n,m,k≤5*10^4#inclu...
2020-01-07 13:58:44
99
原创 维护区间加法和区间乘法
题目描述老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式：(1)把数列中的一段数全部乘一个值;(2)把数列中的一段数全部加一个值;(3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。输入格式第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为...
2020-01-07 13:52:21
192
原创 最短路+二分
题目描述在艾泽拉斯，有n个城市。编号为1,2,3,…,n。城市之间有m条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。假设1为暴风城，n为奥格瑞玛，而他的血量最多为b，出发时他的血量是满的。歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市...
2020-01-07 13:46:57
147
原创 Garland
Vadim loves decorating the Christmas tree, so he got a beautiful garland as a present. It consists of n light bulbs in a single row. Each bulb has a number from 1 to n (in arbitrary order), such that ...
2020-01-06 22:34:05
208
原创 期望dp
题意：一开始获得奖品的概率q=2%，给你每场游戏获胜的概率，如果赢了，没有获得奖品，q = min(100%,q+2%)，如果输了，q = min(100%,q+1.5%)。问你获得奖品的期望步数。题解：dp[i]表示获得奖品为q时的步数，因为有1.5%，所以所有数都扩大两倍。对于dp[i] = 1.0 + 本场获得胜利但没有赢奖品的后续步数 + 本场输了的后续步数。用记忆化搜索，当q>=...
2020-01-06 22:24:03
97
原创 给有向图加边
题意：给一个n×n矩阵，mp[i][j]=1代表i到j之间有一条i指向j的有向边，同一个强联通分量之间可以随便加边，不同强连通分量之间只能有单向连边，问在现有的图的基础上，最多能加多少条边。题解：tarjan缩点时记录每个连通分量包含的点的数量。ans一开始等于-tot，因为一定会减去现有的边。然后从第一个连通分量开始遍历，用pre记录连通分量点数量的前缀和，每一次，ans+=(num[i]-1...
2020-01-06 22:19:38
525
原创 找至少m个黑点使得它们之间最远距离最小
题意：有n个点，其中有些点是白点，有些点是黑点，问你能不能找至少m个黑点，使得它们之间最远距离最小。题解：由于数据范围很小，100，所以我们可以暴力。先用floyd预处理出每两个点之间的距离，然后枚举每两个黑点的距离dis[i][j]，把那个距离看成最远距离，看是否能有至少m个黑点它们之间的距离小于dis[i][j]，如果有，就更新ans。#include <cstdio>#in...
2020-01-06 22:17:15
232
原创 火车公司安排座位
题意：火车公司有两种方案给火车安排座位数量，方案一是让乘客尽可能自由选择，方案二的由火车公司给乘客安排座位。题解：方案二就是要你求单点最大区间覆盖数，差分一下就ok。方案一是最多区间相交数，要求某区间一共有多少区间和他相交，用n-右端点比他左端点小的区间数-左端点比他右端点大的区间数。右端点比他左端点小的区间数就是求个右端点的前缀和，左端点比他右端点大的区间数就是求个左端点的后缀和。#incl...
2020-01-06 22:15:29
271
原创 选两条平行于x轴的线使得穿过最多不同的矩形
题意：给你n个矩形的左上角和右下角的x、y坐标，让你选两条平行于x轴的线，这两条线穿过最多不同的矩形多少个。题解：因为线无限长，所以可以把二维的矩形看成一维的线段。线段的左端点就是右下角的y值，线段的右端点就是左上角的y值。n范围为1e5，x、y坐标范围为[-1e7,1e7]，先把点离散化，然后枚举第一条直线的值，把覆盖该值的线段剔除掉，ans就是覆盖该值的线段数+剩余的覆盖某个值最多的线段数，...
2020-01-06 22:13:19
147
原创 变成单峰序列
题意：给你一个序列，问你把它变成单峰序列最小要交换多少次，每次交换只能发生在相邻的两个数之间。题解：贪心。对于单峰序列，肯定是小的数放外面，大的数放中间，无论先移哪个数，最后肯定都是要移到他应该在的位置，所以应该先移哪个数字不重要。那我们从小到大移动好了，我们先预处理出每个a[i]的位置，然后从小到大遍历每个数字，如果这个数字存在在序列中，l是这个数字在序列中的第一个位置，r是这个数字在序列中的...
2020-01-06 22:11:19
604
原创 多少个子序列大于给定序列
题意：给你一个串s，一个串t，要你从s中找有多少个子序列大于t的。（两个串的长度都不超过3000）题解：对于位数比t大的子序列，统计时直接用组合数。组合数C（n,m） = n！/(n-m)!*m!。预处理出1到3000的阶乘和阶乘的逆元。对于位数和t一样的，用dp。dp[i][j]表示从第i位开始往后取j位，有多少子序列比t大。那么答案就会加上dp[1][m],dp[2][m]……dp[n-m+...
2020-01-06 22:07:45
134
原创 ABBA序列
题意：一个2*（n+m）长度的只包含“A”“B”的序列，可以分解成n+m个子序列，其中有n个“AB”，m个“BA”，给你n和m，问你符合条件的序列有多少个。题解：对于一个序列从前往后遍历过去，遇到一个“A”，肯定会优先把它当成“AB”的“A”，再考虑它是“BA”的“A”，遇到一个“B”同理。那么我们可以有dp[x][y]表示一共有x个“A”，y个“B”，当x或y至少有一个为0，此时方案数只有1。...
2020-01-06 22:06:21
378
原创 字典序最小的ABAB
题意：要你找两个数A，B，使得它们在序列中排列是ABAB，如果有多对，找字典序最小的。题解：我们假设这四个数在序列中的位置是x1,x2,y1,y2，那么我们可以枚举每一对x2,y2（在枚举前先从后往前扫，预处理每一个a[i]对应的位置），因为要字典序最小，我们要找符合条件的最小的y1，y1对应的数就是A，x2对应的数就是B。涉及区间最值，我们用线段树，一开始树的每个结点都是INF，然后每枚举完一...
2020-01-06 21:38:49
264
原创 病毒传染
题意：n个点，m条边，如果有（u，v），（v，w），那么u点可以传染w点，问你至少要添加多少条边，才能使无论从哪条边出发，都能感染所有点。题解：当有一个奇环的时候，就能符合题意。所以我们先找出有多少个联通块，ans = 联通块数量-1，如果图中本来不存在奇环，就ans再++。判是否存在奇环用二分图染色。#include <cstdio>#include <cstring&g...
2020-01-05 23:23:34
151
原创 打气球
题意：水平、竖直方向各打三枪，每打一枪，该坐标该方向上的所有气球都会爆，但同一个方向不同枪要相隔r个单位，问最多可以射爆多少个气球。题解：枚举打哪三行，然后用线段树求出打这三行的时候，竖直方向上最多射爆多少个气球。相加就能更新答案。线段树维护[l,r]区间内选三列气球来打，最多打多少个。#include <cstdio>#include <cstring>#incl...
2020-01-05 23:22:17
95
原创 状压+meet in the middle
题意：给n个数，和sum，要你选其中一些数，使得它们的和等于sum。（n最大为36）题解：状压+meet in the middle。#include <cstdio>#include <cstring>#include <algorithm>#include <map>using namespace std;typedef long ...
2020-01-05 23:21:23
190
原创 求极大全1矩形个数
题意：求极大全1矩形个数题解：用up[i][j]表示其向上连续1的个数。i枚举矩形的下边界，从前往后枚举每一列，用一个单调递增的栈维护up值，对于栈中的每个up值，都记录以它为最小值，最远的扩展到的左右边界。左边界是遍历到它时，如果有栈元素出栈，就是栈元素的左边界，否则就是它自己。右边界就是当遍历到某个元素j,栈顶元素要出栈时，右边界就是j-1。这样上下左都是不可扩展的，再看看它能否往下扩展，即...
2020-01-05 23:20:29
169
原创 砍树最小花费
题意：有n种树，每种树给出高度h，砍掉每颗树的花费c，每种树的数量p，现在要砍掉一些树，使得最高的树的数量超过所有树的一半，问最小花费。（不同种类的树高度可能相同）题解：枚举不同的高度，把高于它的树都砍掉，然后比它矮的树挑便宜的砍，使得该高度的树占所有树的1/2+1。给树按高度排序，首先可以用后缀和预处理出砍掉高于每种高度的树的花费，然后用线段树维护某一价格区间的树一共有多少颗，tr[1].nu...
2020-01-05 23:19:19
128
原创 分层图最短路
题意：n个点，m条边，起点s，终点t，可以最多选k条边免费，问你s到t的一共最小花费多少。题解：多层图最短路板子题。dis[i][j]表示起点s到点i最多选j条边的最小花费。优先队列q（u，dist，d）分别表示点i，s到i的最小花费，目前已用d条免费边。松弛的时候考虑这条边要不要变成免费边（当然，变成免费边的前提是d+1<=k），如果不变成免费边，dis[v][d] = dis[u][d...
2020-01-05 23:16:07
71
原创 找最大的矩形使得矩形内max-min不超过M
题意：给你n×n的矩形，要你找一个最大的矩形，使得矩形内最大值与最小值之差不超过M。题解：枚举矩形的上下边界，同时维护对于当前枚举的上下边界的每列最大最小值（用mi[j],mx[j]数组表示）。枚举矩形右边界，用一个单调递减队列维护mx[j]的最大值，用一个单调递增队列维护mi[j]的最小值，就可以知道可行的最左边界。（非常鬼畜，要手模拟队列+快读才不会t）#include <cstdi...
2020-01-05 23:14:20
170
原创 全1第二大矩形
题意：给你一个只包含0和1的n×m大小的矩阵，问你第二大的全为1的矩形有多大。（不严格第二大）题解：每个矩阵的大小由长和宽决定，矩形的长对应原矩阵中每一行最多有多少个元素，他们向上扩展的连续“1”的数量一样，矩形的宽对应向上扩展的连续“1”的数量。我们从第一行开始枚举，一开始先更新该行所有元素向上扩展最多有多少个连续“1”，设为c[j]数组，然后用一个单调递增的栈维护该行的c[j]数组，找出该行...
2020-01-05 23:11:35
104
原创 19牛客（1）
题意：两个数组定义为相等的，当且仅当从两个数组中任选一个区间[l,r]，他们的最小值的下标是一样的，给你两个数组u和v，问你最大的下标p，使得1到p中任选一个区间，他们的最小值下标是一样的。证明：假设遍历到第i个元素，也就是前i-1个元素都是符合条件的，那么我们需要考虑的新区间就是以第i个元素为右端点的所有区间，现在我们考虑以第i个元素为最小值的区间最左能延伸到哪里，如果两个数组最左能延伸到的位...
2020-01-05 23:09:56
68
原创 tarjan缩点+最长路
Suppose there are N people in ZJU, whose ages are unknown. We have some messages about them. The i-th message shows that the age of person si is not smaller than the age of person ti. Now we need to d...
2020-01-05 23:07:39
140
原创 两次生成树
Sample Input5 7 21 3 04 5 13 2 05 3 14 3 01 2 14 2 1Sample Output3 2 04 3 05 3 11 2 1第一次构建生成树确定哪些鹅卵石路是必须免费的第二次构建生成树是把生成树中除去必须免费的鹅卵石路的其他的路标记出来#include <cstdio>#include <cs...
2020-01-05 21:29:48
110
原创 tarjan缩点+dag上dp
题目描述给定一个 n个点 mm条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。输入格式第一行两个正整数 n,m第二行 n个整数，依次代表点权第三至 m+2 行，每行两个整数 u,v，表示一条 u→v 的有向边。输出格式共一行，最大的点权之和。输入输出样例输入 #12...
2020-01-05 20:50:32
106
原创 求割点+计数
题目描述在Byteotia有n个城镇。 一些城镇之间由无向边连接。 在城镇外没有十字路口，尽管可能有桥，隧道或者高架公路（反正不考虑这些）。每两个城镇之间至多只有一条直接连接的道路。人们可以从任意一个城镇直接或间接到达另一个城镇。 每个城镇都有一个公民，他们被孤独所困扰。事实证明，每个公民都想拜访其他所有公民一次（在主人所在的城镇）。所以，一共会有n*（n-1）次拜访。不幸的是，一个程序员总罢...
2020-01-05 20:50:18
106
原创 求强连通分量数量
Every cow’s dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell...
2020-01-05 20:50:07
215
原创 求点大于1的强连通分量数量
约翰的N (2 <= N <= 10,000)只奶牛非常兴奋，因为这是舞会之夜！她们穿上礼服和新鞋子，别 上鲜花，她们要表演圆舞.只有奶牛才能表演这种圆舞.圆舞需要一些绳索和一个圆形的水池.奶牛们围在池边站好， 顺时针顺序由1到N编号.每只奶牛都面对水池，这样她就能看到其他的每一只奶牛.为了跳这种圆舞，她们找了 M(2<M< 50000)条绳索.若干只奶牛的蹄上握着绳索...
2020-01-05 20:49:47
470
原创 入门
单调队列的性质：（1）：队列中的元素是单调的（2）：队尾插入元素，队首队尾删除元素应用：求静态区间最值裸单调队列DescriptionAn array of size n ≤ 10 6 is given to you. There is a sliding window of size k which is moving from the very left of the array ...
2020-01-03 19:01:35
97
原创 线段树染色
题目描述PP大厦有一间空的礼堂，可以为企业或者单位提供会议场地。这些会议中的大多数都需要连续几天的时间（个别的可能只需要一天），不过场地只有一个，所以不同的会议的时间申请不能够冲突。也就是说，前一个会议的结束日期必须在后一个会议的开始日期之前。所以，如果要接受一个新的场地预约申请，就必须拒绝掉与这个申请相冲突的预约。 一般来说，如果PP大厦方面事先已经接受了一个会场预约，例如从10日到15日，就...
2019-10-06 18:10:55
125
原创 二分答案
求最小值int l=0,r=n+1,ans=0; while(l<r) { int mid=(l+r)>>1; if(check(mid)) { r=mid; ans=mid; } else l=mid+1;}求最大值int l=0,r=n+1,ans=0; while(l<r) { i...
2019-07-09 11:21:52
102
原创 入门
单调栈的性质：（1）：栈中元素是单调递增或单调递减的（2）：后进先出应用：求某一元素左（右）边第一个比它大（小）的值。DescriptionBill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good...
2019-05-25 14:00:54
173
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人