- 博客(212)
- 收藏
- 关注
RSS订阅原创 第二届全国大学生算法设计与编程挑战赛（春季赛）D - zeal（莫队算法）
DescriptionYassin 最近在量化投资方面很有兴趣。为了研究哪只股票是真正的牛股，他把历史 nn 天每一天成交量最大的股票代码写成了一排,并构建了一套属于自己的“理论体系”。成交量多说明人气好，人气好的肯定买的人多，赚钱就要靠人气！ – Yassin但是知道的人太多，这个大家都去接盘，那就都成为韭菜了 – Makik基于这个理论，Yassin 想知道 [L, R] 区间中人气“比较”好的股票有哪些，具体而言，他会给定你 L, R, k，你则需要告诉他 [L, R] 中出现 k 次的股票
2021-06-06 19:42:47
591
原创 Codeforces 1526C - Potions (Easy and Hard Version)（带悔贪心）
Potionstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is the hard version of the problem. The only difference is that in this version n≤200000. You can make hacks only if both versions of the
2021-06-03 20:28:56
801
原创 2018年ICPC南京区域赛I - Magic Potion（二分图的多重匹配）
Problem I. Magic PotionInput file: standard inputOutput file: standard outputThere are n heroes and m monsters living in an island. The monsters became very vicious these days,so the heroes decided to diminish the monsters in the island. However, the i-
2021-06-03 20:18:06
385
原创 Codeforces 1459D - Glass Half Spilled（背包DP）
time limit per test 2 secondsmemory limit per test 512 megabytesinput standard inputoutput standard outputThere are n glasses on the table numbered 1,…,n. The glass i can hold up to ai units of water, and currently contains bi units of water.You would
2020-12-21 21:00:43
436
原创 Codeforces 25D - Roads not only in Berland（并查集判环）
D. Roads not only in Berlandtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputBerland Government decided to improve relations with neighboring countries. First of all, it was decided to build new roa
2020-10-15 16:09:26
282
原创 POJ 1847 - Tram（链式前向星存图 + SPFA + 读题）
萨格勒布的电车网络包括许多交叉路口和连接其中一些的铁路。在每个交叉路口，都有一个开关指向离开交叉路口的一条导轨。有轨电车进入交叉路口时，只能沿开关指向的方向离开。如果驾驶员想走其他路线，则必须手动更改开关。当驾驶员确实从交叉路口A到交叉路口B行驶时，他/她试图选择一条路线，该路线将最大限度地减少他/她将不得不手动更改开关的次数。编写一个程序，计算从路口A到路口B所需的最少开关变化次数。Input输入的第一行包含整数N，A和B，以单个空白字符分隔，2 <= N <= 100，1 <=
2020-09-17 20:27:30
196
原创 LightOJ 1074 - Extended Traffic（spfa判负环 + dfs染色 + 最短路）
这一晚，TT 做了个美梦！在梦中，TT 的愿望成真了，他成为了喵星的统领！喵星上有 N 个商业城市，编号 1 ～ N，其中 1 号城市是 TT 所在的城市，即首都。喵星上共有 M 条有向道路供商业城市相互往来。但是随着喵星商业的日渐繁荣，有些道路变得非常拥挤。正在 TT 为之苦恼之时，他的魔法小猫咪提出了一个解决方案！TT 欣然接受并针对该方案颁布了一项新的政策。具体政策如下：对每一个商业城市标记一个正整数，表示其繁荣程度，当每一只喵沿道路从一个商业城市走到另一个商业城市时，TT 都会收取它们（目的地
2020-09-17 20:16:29
258
原创 POJ 3159 - Candies（链式前向星 + 堆优化dijksta）
在幼儿园的时候，Flymouse是班上的班长。有时班主任会给班上的孩子们带来一大袋糖果，让他们分发。所有的孩子都非常喜欢糖果，经常比较他们和别人买的糖果的数量。一个孩子A可以有这样的想法，尽管可能是另一个孩子B在某些方面比他好，因此他有理由比他应得更多的糖果，但无论他实际得到多少糖果，他都不应该得到比B少的一定数量的糖果，否则他会感到不满意。 Flymouse总是把他的糖果和snoopy的比较，他想在让每个孩子都满意的同时，尽可能使自己的糖比snoopy的多。现在他又从班主任那里得到了一袋糖果，他最多能比s
2020-09-17 19:52:03
94
原创 POJ 1511 - Invitation Cards（链式前向星 + 反向图最短路）
Descriptionn-1个人从1号点出发，到剩余n-1个宣传点，然后再回到1号点汇报结果，求所有人往返路径和的最小值Input输入由T个案例组成。输入的第一行只包含正整数T。接下来是N和M，1 <= N,M <= 1000000，表示N个点和连接N个点的M条边。然后有M行，每行包括三个值U,V,W，表示从点U到点V需要W的路程。你可以假设该图连通。注意是单向通道！！！Output对于每个案例，打印一行，表示路径总和的最小值。Sample Input22 21 2 13
2020-09-17 19:47:00
122
原创 POJ 1502 - MPI Maelstrom（链式前向星 + dijkstra模板题）
由于叛徒朱子明的出卖，导致独立团在赵家峪的团部驻军在团长李云龙大婚之日几乎全军覆没，突出重围之后，李云龙决定集合所有驻扎在外的部队，使用重型武器意大利炮攻打平安县城，消息从团部传出之后到达各部驻地之后，驻地长官会派出自己的通讯人员通知其他驻地部队，自团部派人传达命令开始，至少经过多长时间才能使得所有驻扎在外的部队受到命令。（假设通讯员在路上不会遭遇任何意外）Input第一行输入一个n，表示包括团部在内有多少不同的驻军（团部当然是编号为1了）。随后n-1行，以邻接矩阵的形式给出各驻军（1 ~ n）之间派
2020-09-17 19:40:39
199
原创 POJ 1860 - Currency Exchange（SPFA判正环）
我们的城市有几个货币兑换点。让我们假设每一个点都只能兑换专门的两种货币。可以有几个点，专门从事相同货币兑换。每个点都有自己的汇率，外汇汇率的A到B是B的数量你1A。同时各交换点有一些佣金，你要为你的交换操作的总和。在来源货币中总是收取佣金。 例如，如果你想换100美元到俄罗斯卢布兑换点，那里的汇率是29.75，而佣金是0.39，你会得到（100 - 0.39）×29.75＝2963.3975卢布。 你肯定知道在我们的城市里你可以处理不同的货币。让每一种货币都用唯一的一个小于N的整数表示。然后每个交换点，可以
2020-09-17 19:31:04
155
原创 POJ 2240 - Arbitrage（map + SPFA判正环）
Input套利是指利用货币汇率的差异，将一种货币的一个单位转换为同一货币的多个单位。例如，假设1美元买0.5英镑，1英镑买10.0法国法郎，1法国法郎买0.21美元。然后，通过兑换货币，聪明的交易者可以从1美元开始，购买0.5 x 10.0 x 0.21 = 1.05美元，获得5%的利润。您的工作是编写一个程序，以货币汇率列表作为输入，然后确定是否可能进行套利。Output输入将包含一个或多个测试用例。每个测试用例的第一行有一个整数n (1<=n<=30)，表示不同货币的数量。接
2020-09-17 17:56:51
113
原创 POJ 3259 - Wormholes（SPFA判负环）
题目描述教学楼里有很多教室，这些教室由双向走廊连接。另外，还存在一些单向的秘密通道，通过它们可以回到过去。现在有 N (1 ≤ N ≤ 500) 个教室，编号 1…N, M (1 ≤ M ≤ 2500) 条走廊，和 W (1 ≤ W ≤ 200) 条秘密通道。DY在养猫之余，还是一个时间旅行爱好者。她希望从一间教室出发，经过一些走廊和秘密通道，回到她出发之前的某个时间。共有F (1 ≤ F ≤ 5) 组数据。对每组数据，判断DY是否有回到过去的可能性。不存在耗时超过10,000秒的走廊，且不存在能带D
2020-09-15 20:37:00
127
原创 ACwing 282 - 石子合并（区间DP）
设有N堆石子排成一排，其编号为1，2，3，…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。例如有4堆石子分别为 1 3 5 2， 我们可以先合并1、2堆，代价为4，得到4 5 2， 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+11=24；如果第二步是先合并2，3堆，则代价为7，得到4 7，
2020-09-14 20:57:39
157
原创 ACwing 902 - 最短编辑距离（最长上升子序列模型）
给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：删除–将字符串A中的某个字符删除。插入–在字符串A的某个位置插入某个字符。替换–将字符串A中的某个字符替换为另一个字符。现在请你求出，将A变为B至少需要进行多少次操作。输入格式第一行包含整数n，表示字符串A的长度。第二行包含一个长度为n的字符串A。第三行包含整数m，表示字符串B的长度。第四行包含一个长度为m的字符串B。字符串中均只包含大写字母。输出格式输出一个整数，表示最少操作次数。数据范围1 ≤ n,m ≤
2020-09-13 21:24:24
126
原创 ACwing 897 - 最长公共子序列（线性dp 最长上升子序列模型）
给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。输入格式第一行包含两个整数N和M。第二行包含一个长度为N的字符串，表示字符串A。第三行包含一个长度为M的字符串，表示字符串B。字符串均由小写字母构成。输出格式输出一个整数，表示最大长度。数据范围1 ≤ N,M ≤ 1000输入样例：4 5acbdabedc输出样例：3题目大意：输入两个字符串的长度，然后输入两个字符串，输出两个字符串最长公共子序列。解题思路：状态表示： 用二维
2020-09-13 20:17:05
182
原创 ACwing 895 - 最长上升子序列（最长上升子序列模型）
给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数N。第二行包含N个整数，表示完整序列。输出格式输出一个整数，表示最大长度。数据范围1 ≤ N ≤ 1000，−109 ≤ 数列中的数 ≤ 109输入样例：73 1 2 1 8 5 6输出样例：4题目大意：输入一个 n ，第二行有 n 个数，输出最长上升子序列的长度。解题思路:动态规划之最长上升子序列模型，要求输出最长上升子序列的长度，从两方面入手：状态表示： 用一维表示状态 f[i
2020-09-13 18:31:30
153
原创 ACwing 898 - 数字三角形（数字三角形模型）
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 7 3 8 8 1 0 2 7 4 44 5 2 6 5输入格式第一行包含整数n，表示数字三角形的层数。接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。输出格式输出一个整数，表示最大的路径数字和。数据范围1 ≤ n ≤
2020-09-13 18:16:50
255
原创 POJ 3268 - Silver Cow Party（链式前向星正反建图 + 两次最短路spfa）
来自 N (1 ≤ N ≤ 1000)个农场的奶牛的编号分别为1,2, … ,N。现在在农场 X (1 ≤ X ≤ N) 举行聚会。总共有 M (1 ≤ M ≤ 100,000) 条单向通道。路 i 需要时间 Ti 才能通过。每头牛都需要参加聚会并返回，而且它们均选择花费时间最短的路线。问：在所有的奶牛中，所花费的最长时间为多少？Input第一行包含三个整数N，M，X。在接下来的M行中，每行都包括三个整数A，B和T，表示从农场A到B需要花费时间T。Output输出奶牛所花的最大时间。Sampl
2020-09-13 17:08:55
85
原创 组合数的四种情况及解法
组合数C（a, b）意为从 a 个物品中选 b 个物品的所有方案数。公式：a ! / b ! (a - b) !有时会涉及到 mod p，本文将介绍a b p在不同范围下的组合数求法，这里列举 4 种情况。情况一：给定 n 组询问，每组询问给定两个整数 a，b ，请你输出 C(a, b) mod (109+7) 的值。输入格式第一行包含整数 n 。接下来 n 行，每行包含一组 a 和 b 。输出格式共 n 行，每行输出一个询问的解。数据范围1≤n≤10000 ,1≤b≤a≤2000
2020-09-04 19:58:36
1105
2
原创 AcWing 883 - 高斯消元解线性方程组（高斯消元）
输入一个包含n个方程n个未知数的线性方程组。方程组中的系数为实数。求解这个方程组。下图为一个包含m个方程n个未知数的线性方程组示例：输入格式第一行包含整数n。接下来n行，每行包含n+1个实数，表示一个方程的n个系数以及等号右侧的常数。输出格式如果给定线性方程组存在唯一解，则输出共n行，其中第i行输出第i个未知数的解，结果保留两位小数。如果给定线性方程组存在无数解，则输出“Infinite group solutions”。如果给定线性方程组无解，则输出“No solution”。数据范
2020-09-02 18:46:17
305
原创 ACwing 257 - 关押罪犯（二分答案 + 二分图染色）
S 城现有两座监狱，一共关押着 N 名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表
2020-08-24 17:14:10
187
原创 ACwing 861 - 二分图的最大匹配（匈牙利算法）
给定一个二分图，其中左半部包含n1个点（编号1 - n1），右半部包含n2个点（编号1 - n2），二分图共包含m条边。数据保证任意一条边的两个端点都不可能在同一部分中。请你求出二分图的最大匹配数。二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。输入格式第一行包含三个整数 n1、 n2 和 m。接下来m行，每行包含两个整数u和v
2020-08-23 11:37:25
467
原创 ACwing 860 - 染色法判断二分图（染色法）
给定一个n个点m条边的无向图，图中可能存在重边和自环。请你判断这个图是否是二分图。输入格式第一行包含两个整数n和m。接下来m行，每行包含两个整数u和v，表示点u和点v之间存在一条边。输出格式如果给定图是二分图，则输出“Yes”，否则输出“No”。数据范围1≤ n,m≤ 105输入样例：4 41 31 42 32 4输出样例：Yes题目大意：输入n m 表示n 个顶点 m 条边，可能有重边和自环。判断该图是不是一个二分图。解题思路：判断一个图是否是二分图，判断是否存在奇
2020-08-23 11:21:17
541
原创 ACwing 853 - 有边数限制的最短路（Bellman - Ford）
给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。注意：图中可能 存在负权回路 。输入格式第一行包含三个整数n，m，k。接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。输出格式输出一个整数，表示从1号点到n号点的最多经过k条边的最短距离。如果不存在满足条件的路径，则输出“impossible”。数据范围1≤n,k≤500,1
2020-08-22 18:24:42
220
原创 ACwing 852 - spfa判断负环（spfa判负环）
给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你判断图中是否存在负权回路。输入格式第一行包含整数n和m。接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。输出格式如果图中存在负权回路，则输出“Yes”，否则输出“No”。数据范围1≤n≤2000 ,1≤m≤10000 ,图中涉及边长绝对值均不超过10000。输入样例：3 31 2 -12 3 43 1 -4输出样例：Yes题目大意:给出一个图，询问图中是否存在负
2020-08-22 17:54:37
489
原创 ACwing843 - n皇后问题（经典dfs）
n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数n，请你输出所有的满足条件的棋子摆法。输入格式共一行，包含整数n。输出格式每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。其中”.”表示某一个位置的方格状态为空，”Q”表示某一个位置的方格上摆着皇后。每个方案输出完成后，输出一个空行。输出方案的顺序任意，只要不重复且没有遗漏即可。数据范围1 ≤ n ≤ 9输入样
2020-08-20 22:57:54
410
原创 C++ 高精度除法及模板
本文介绍的是一个超过long long 范围的数除一个较小的数，用vector 模拟计算过程，同时输出商和余数Code：#include <iostream>#include <algorithm>#include <vector>using namespace std;vector<int > A;int b, r;vector<int > div(vector<int > &a, int b, int
2020-08-20 11:56:38
412
原创 ACwing 841 - 字符串哈希（字符串hash）
给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数 l1,r1,l2,r2 ，请你判断[ l1,r1 ]和[ l2,r2 ]这两个区间所包含的字符串子串是否完全相同。字符串中只包含大小写英文字母和数字。输入格式第一行包含整数n和m，表示字符串长度和询问次数。第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。接下来m行，每行包含四个整数 l1,r1,l2,r2 ，表示一次询问所涉及的两个区间。注意，字符串的位置从1开始编号。输出格式对于每个询问输出一个结果，如果两
2020-08-20 11:31:11
249
原创 ACwing 840 - 模拟散列表（Hash）
维护一个集合，支持如下几种操作：“I x”，插入一个数x；“Q x”，询问数x是否在集合中出现过；现在要进行N次操作，对于每个询问操作输出对应的结果。输入格式第一行包含整数N，表示操作数量。接下来N行，每行包含一个操作指令，操作指令为”I x”，”Q x”中的一种。输出格式对于每个询问指令“Q x”，输出一个询问结果，如果x在集合中出现过，则输出“Yes”，否则输出“No”。每个结果占一行。数据范围1≤N≤105−109≤x≤109输入样例：5I 1I 2I 3Q 2Q
2020-08-20 10:53:37
116
原创 C++ 高精度乘法及模板
高精度乘法解决了两数相乘得到的数大于long long 范围时的问题，这里提供的是一个大数乘一个小数（int 范围内）的模板，用vector 模拟乘法过程并存值，之后返回vector。先上模板：#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <iomanip>#include <sstream>#inclu
2020-08-19 11:47:00
517
原创 ACwing 839 - 模拟堆（数组模拟堆）
add(x){e[idx] = x;//先把x的值放入存值的数组ne[idx] = head;//这时 ne[dix] 代表 编号为idx 的节点的下一个点是head，而起初head = -1；head = idx;//做完上一个操作时，idx 已经成了头节点，所以head = idx,idx}...
2020-08-19 11:29:54
225
原创 C++ 高精度减法及模板
高精度减法在数据范围超过long long 的范围时，就要考虑到高精度，对于高精度减法而言，本文介绍的两个数均 >= 0, 高精度减法的实质是用代码去模拟我们的减法运算，包括借位…正负号种种问题，这里用vector 来模拟两个大数相减，先贴代码：#pragma GCC optimize(2)#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#i
2020-08-13 10:55:27
571
1
原创 C++ 高精度加法及模板
高精度加法适用于两个正整数相加，且int和long long 存不下的情况下，用代码模拟两个数相加过程，用vector 存值，实质上就是用vector模拟计算过程，达到数字范围远远高于long long 时的加法操作（本文为1e6）先上代码：#pragma GCC optimize(2)#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#inclu
2020-08-13 10:42:03
629
原创 洛谷P2580 - 于是他错误的点名开始了（字典树模板题）
题目大意：第一行输入一个 n 表示有 n 个人，接下来输入 n 个人的名字，再输入一个q 表示有
2020-08-07 11:42:32
306
原创 Codeforces 617E - XOR and Favorite Number（前缀异或 + 莫队）
E. XOR and Favorite Numbertime limit per test4 secondsmemory limit per test256 megabytesinput standard inputoutpu tstandard outputBob has a favorite number k and a i of length n. Now he asks you to answer m queries. Each query is given by a pair l i a
2020-08-07 11:01:34
216
原创 SPOJ 3267 - DQUERY - D-query（基础莫队）
题目大意：给出一个 n 表示有 n 个数，然后接下来输入n个数，紧接着输入一个 m 表示有 m 组询问，然后有 m 行，每行输入l r ，要求输出区间[l, r]不同数字的种数有多少。解题思路：莫队算法，离线扫描即可，将n个数分块，每块 根号n ，然后对询问的区间进行排序，左端点升序排序，相同时再对右端点基于奇偶排序（玄学优化），之后设左指针和右指针和计数数组cnt，根据左右指针的移动来判断种类的加减，注意运算符和优先级（这里是由add 和 del 函数压缩过来的，运算符错一点就会 WA）。Co.
2020-08-06 23:57:20
144
原创 Codeforces Round #661 (Div. 3) 解题报告（ABCD）
Codeforces 1399A - Remove Smalles（思维）Codeforces 1399B - Gifts Fixing（思维）Codeforces 1399C - Boats Competition（双指针）Codeforces 1399D - Binary String To Subsequences（思维）比赛秒出A，B因为没开LL调了几分钟，C题没写出来是最不应该的，暴力没跑过去，最开始想到了双指针，但是忘记判断指针是怎么移动的了…wa7次 没改出来… 赛后补题 CD..
2020-08-06 21:17:04
140
原创 Codeforces 1399D - Binary String To Subsequences（思维）
D. Binary String To Subsequencestime limit per test2 secondsmemory limit per test256 megabytesinput standard inputoutput standard outputYou are given a binary string s consisting of n zeros and ones.Your task is to divide the given string into the mi
2020-08-06 21:14:11
300
原创 Codeforces 1399C - Boats Competition（双指针）
C. Boats Competitiontime limit per test2 secondsmemory limit per test256 megabytesinput standard inputoutput standard outputThere are n people who want to participate in a boat competition. The weight of the i-th participant is wi. Only teams consisti
2020-08-06 21:01:22
554
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人