- 博客(148)
- 收藏
- 关注
RSS订阅
原创 2019牛客多校训练赛第五场A题 （思维题）
题目描述（看不清图片可以右击图片-> 复制图片地址 ->浏览器新开一个标签页，粘贴此地址就可看大图（也可以右击图片-> 在新标签页打开图片题解题意：给你一个整型x（x <= 100）， 让你输出一个整型y， y要满足3个条件:y 能被 x 整除y和各个数位的数字之和能被 x 整除(就是个位， 十位， 百位，… 之和)y的位数不超过 10^4思维题， 真是太妙...
2020-11-25 19:43:18
387
原创 计蒜客 - 44280 UnDetected(并查集).md
题目大意题目链接给你n个圆，ans 为 最少 前多少个 圆 能把x轴(0, 200) 完全覆盖， 完全覆盖是相交的圆 的最左端 <=0 最右端 >= 200， 输出ans - 1分析并查集维护边界和输入的圆是否相交。代码12345678910111213141516171819202122232425262728293...
2020-04-21 00:50:22
369
原创 计蒜客 - 44284 Safe Passage(贪心、思维、dp).md
题目大意题目链接很经典的问题。n个人要过河， 过河需要保护罩， 一个保护罩最多只能容纳两个人， 每个人过去都有花费的时间， 如果两个人一起过，花费的总时间时间 就是两个人中 花费的时间最大的那个。问怎么安排能尽快过河。分析十分经典的问题， 从小到大排序， 充分利用好a[1], a[2]， 一共有两种情况。a[1], a[2] 过去， a[1]回来， a[i] 和 a[i - 1] 过...
2020-04-21 00:25:16
519
原创 计蒜客 - 44120 Circuit Counting(dp).md
题目大意题目链接给你n个点，求满足所有x坐标之和为0， 所有y坐标之和为0， 的真子集的数量。|x| <= 10, |y| <= 10, n <= 40分析唉， 愣是没想到用dp， 傻了吧唧的设 dp[i][x][y] 为前i个点， x坐标值和为x， y坐标和为y的集合的数量。dp[i][x][y] = dp[i - 1][x][y] + dp[i - 1][x...
2020-04-20 15:03:52
189
原创 ICPC Southeastern Europe Contest 2019 H - Absolute Game(贪心)
题目大意题目链接A和B分别有一个长度为n的序列， 一共进行n - 1轮， 每轮每人拿掉一个数字，A想要最后剩下的数字的绝对值差尽量小， B反之， 问俩人都采取最优策略，最后差值的绝对值是多少？分析不管怎么样， B肯定拿走与A剩下的差值最小的， 那么最后答案就是 max(min(b[j] - a[i]))代码1234567891011121314151617...
2020-04-18 07:02:11
210
原创 计蒜客 - 44529 The League of Sequence Designers(构造)
题目大意题目链接给你两个数k，n。n表示构造的序列的最小长度，k表示构造的序列满足下列两种算法得到的答案之差， 构造这个序列，若无，输出-1。这个序列最多有1999个， 元素的绝对值小于1e6.sum[i][j] 是指 a[i] 到 a[j]的和算法1：ans = max(ans, (r - l + 1) * sum[l][r])算法2：123456sum += a[...
2020-04-03 16:06:50
414
原创 POJ - 1733 Parity game(种类并查集).md
题目大意题目链接给你一个区间长度L (L <= 1e9) ， 和q(q <= 5000)组数据， 每组数据 x y odd/even ， 表示 区间[x, y]和为odd/even, 输出最先出现矛盾的组号(0 到 q - 1), 如果没有矛盾， 输出q 分析如果 [x, y] 是偶数， 那么 [1, x) 和 [1, y] 同奇偶性， 即[1, x - 1] [1, y] ...
2020-04-03 03:34:50
116
原创 POJ - 1417 True Liars(并查集、dp)
题目大意题目链接一个村庄有两类人，好人坏人， 好人总是说真话， 坏人总是说假话， 给你m(原题用n表示的， 我让n = p + q)个询问和好人、坏人的数量p q， 每个询问 x y yes/no, 表示 x 说 y 是 好/坏人。问是否能够唯一确定哪些是好人， 哪些是坏人， 如果可以输出好人的序号以”end”结尾， 否则输出”no”分析这让我想到食物链那道题， 所以我想用两个大集合来表...
2020-03-28 05:26:22
216
原创 POJ - 1456 Supermarket(并查集+贪心).md
题目大意题目链接超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.每天只能卖一个商品.现在你要让超市获得最大的利润.分析用并查集向前查找， 太妙了呀。首先贪心， 价值越大的物品， 越放在快过期的那天卖最好， 因为你肯定要卖的嘛， 如果快过期那天已经卖了别的了， 就说明有更大价值东西在那天卖了。然后寻找最靠近保质期切没有被用到的哪一天 ， 这...
2020-03-28 04:46:52
154
原创 HDU - 4081 Qin Shi Huang's National Road System(次小生成树)
题目大意题目链接给出n(<=1e3)个城市的x,y坐标以及每个城市的人数， 这些城市的主人想建造最小生成树，这时候有个会魔法的道士说， 我可以让一条路权值为0， 求A/B的最大值， 其中A是权值为0的道路连接的城市的人数之和， B是最小生成树的权值。分析这题实在是太妙了， 果然还是要多刷题。我们暴力遍历所有的边， 然后求 A/B的最大值就行了。MST为最小生成树的权值和，p[i]...
2020-03-28 00:44:09
96
原创 计蒜客 - 44154 Historical TV Remote Control (思维)
题目大意题目链接一个只有12个键的遥控器(0-9 上键， 下键)， 然后最多有9个键坏掉了（上下键不会坏）， 然后给你想要的序号(1-999), 问最少需要按几次上下键。保证只有(0-999), 且0不能到999且999不能到0。分析暴力， 居然是暴力0~999 。然后别忘了特判0 。代码1234567891011121314151617181920...
2020-03-26 13:46:08
124
原创 计蒜客 - 44141 First Last Sorting(dp)
题目大意题目链接给你一个1~n（n <= 1e5）随机排列的序列，你有两种操作， 把第i个移到对首或者队尾。为最少移动几次能让 ai = i(也就是1， 2， 3， … , n)分析正难则反， 我们只要求出严格上升的子序列的长度ans， 那么用 n - ans 就是答案代码123456789101112131415161718192021...
2020-03-26 12:13:54
114
原创 c++字符串转换为数字（stoi, stol, stoul, stoull, stof, stod, stold）
c++字符串转换为数字（stoi, stol, stoul, stoull, stof, stod, stold）头文件#include <string>1. stoi将字符串转换成int12int stoi (const string& str, size_t* idx = 0, int base = 10);int stoi (const wstring&...
2020-03-26 06:09:13
3033
原创 计蒜客 - 44158 World Cup Fever(最短路)
题目大意题目链接两支球队a, b，每支n人， 如果a球队两个队员之间没有其他人， 那么就可以传球， 问a队1号队员最少传多少次能传到a队n号队员， 输出次数， 传不到输出-1.分析思路很简单， 就是判断a球队的队员能不能直接传球，能的话就加一条边长为1的边， 注意如果两个球员之间有本队的球员也是不能直接传球的！！！代码123456789101112131415...
2020-03-26 03:37:27
207
原创 计蒜客 - 44345 I - Problem I. Journey(dp).md
题目大意题目链接一个无限大的二维图， 从(0, 0)出发，走n步，只能向右和向下走， 不能在同一方向连续走k步，问走n步，不同路径的方案数（对1e9+7取余）。分析dp[i] 表示第i步向下走的方案数。sum = dp[1] + dp[2] + … + dp[n]dp[i] 也可以表示第i步向右走的方案数。所以最后答案就是 sum * 2代码12345678910...
2020-03-19 01:22:05
132
原创 Preliminaries for Benelux Algorithm Programming Contest 2019E - Exits in Excess（思维题，有向图去环）...
题目大意题目链接n个点（n <= 1e5）, m条有向边（m <= 2e5）, 最多之能删掉(m / 2)条边， 让其不成环，输出删除的边数和其索引号i（1 <= i <= m）分析只保留一个方向的边就行了。我们可以认为边有两个方向， 一个是小索引号到大索引号， 另一个是大索引号到小索引号。我们删除这两个方向中边数较少的那个方向的边， 即可， 最多删除的边数是（...
2020-03-18 10:00:44
87
原创 POJ - 2502 L - Subway（最短路）
题目大意题目链接给你起始坐标s和终点坐标e， 然后给你地铁线（EOF结束）每条地铁线以EOF结束， 相邻的地铁线可以双向通， 问s到t的最短时间（min）。其中地铁的速度是 40 km/h ， 步行的速度是10 km/h， 然后单位是m，要转化，两点的距离是欧几里得距离， 不是曼哈顿距离。分析最关键的是建图。因为最多总共200个地铁站， 用邻接矩阵存就行， 因为求最短时间， 用邻接矩阵存时...
2020-03-15 01:47:57
135
原创 c和cpp的文件读入输出.md
C语言1234567891011121314151617181920 FILE *fp = fopen("input.txt", "r"); // 根据题目中要求的写 有的是text.txt FILE *fpw = fopen("output.txt", "w"); ...
2020-03-10 21:22:30
256
原创 矩阵求A的1到n的幂次之和
题目大意给你一个n*n(n <= 30)的矩阵A， 每个元素x（0 <=x<= 1e6 ）， 给你一个m（m <= 1e9）， 求S = A + A^2 + A ^3 + … + A^m,其中对每个元素对1e9+7取余。分析这里有另一种做法， 点此对于A矩阵， 我们可以构造一个这样的矩阵B12|A A||0 E|B^2为12|A^2 A + A^2...
2020-03-10 16:57:16
1013
原创 POJ - 1511 Invitation Cards（最短路， 有向图的逆图）
题目大意题目链接有n个点（n <= 1e6）， m条单向边（m <= 1e6）, n - 1个人从 点1 出发，去剩余n-1个点并回到1点， 求来回的和的最小值。其中注意权值和 小于 1e9 （这就是个坑， 一眼看去不用ll就能过， 其实不然。。。）分析用正的有向图跑一边， 逆的有向图跑一边， 最后求和就行了。代码12345678910111213...
2020-03-10 14:20:01
266
原创 POJ - 3660 Cow Contest(最短路).md
题目大意题目链接n（<= 100）头牛， m（m <= 4500 ）种关系， 每种关系 u, v代表 u能赢v。问最终能确定多少头牛的排名。分析用最短路的松弛操作， 确定出每两头牛的关系， 对于第i个牛， 如果和其他i - 1个牛都能确定胜负， 就能确定这头牛的排名。建图， 如果u能赢v， 那么ma[u][v] = 1, 否则就ma[u][v] = -1， 用floyd松弛的...
2020-03-10 09:31:21
86
原创 CodeForces - 1316B String Modification（思维）.md
题目大意题目链接给你一个长为n的字符串， 问k为多少时， 字符串的字典序最小k的定义， 翻转 s[i : i + k − 1] | 1 <= i <= n - k + 1 。分析写几个找规律。123456k = 2时abcd 结果是 bcd|aabcde 结果是 bcde|ak = 3是abcd 结果是 cd|ababcde 结果是 cde|ba...
2020-03-07 21:05:55
92
原创 POJ - 3268 Silver Cow Party(最短路).md
题目大意题目链接n个点， 给你m条有向边， 问 各个点到x的最短距离 + x到各个点的最短距离 的最大值是多少分析我跑了n次dijk（暴力过了滑稽）正解， 求一次其他点到x的最短路， 再求一次逆图 的 其他点到x的最短路 （这里我用了两倍空间， 但是时间复杂度是O(n logn)）代码1234567891011121314151617181920...
2020-03-07 17:57:12
98
原创 CodeForces - 1305E Kuroni and the Score Distribution（思维， 构造）.md
题目大意题目链接给你两个数n(<= 5000)， m(<= 1e9)， n为你要构造的序列长度， m下面会用到。该序列满足1231. 序列递增2. 1 <= ai <= 1e93. 有恰好m组 i, j, k (1 <= i < j < k <= n) 满足 ai + aj = ak如果存在这样的序列， 输出这个序列， 不存在输出...
2020-03-05 17:15:04
135
原创 CodeForces - 1305D Kuroni and the Celebration（交互题， 思维题）.md
题目大意题目链接给你一棵n个节点的树， 找出他的根结点。交互(不懂交互题的百度搜例题就明白了)最多可以交互 n / 2次输出 ? u v 返回 lca(u, v) .输出答案 ! root分析最多询问n / 2 次， 如果保证每次都能淘汰两个点的话， 肯定能找到根结点，如果n为奇数并且 在n / 2次内没找到根结点， 那么剩下的那个节点就是根结点。就是自己搞一搞。我选择的是每次选择叶子...
2020-03-04 13:20:18
105
原创 CodeForces - 1305C Kuroni and Impossible Calculation（数学）.md
题目大意题目链接calculate (∏1≤i<j≤n|ai−aj|) % m.其中 2 <= n <= 2e5 | 1 <= m <= 1000 | 0 <= ai <= 1e9分析由抽屉原理可知， 当n > m 时， 肯定会有 两个数和m同余。AC代码12345678910111213141516171...
2020-03-04 07:57:47
91
原创 CodeForces - 1321C Remove Adjacent（贪心）
题目大意题目链接给你一个字符串， 如果相邻的两个字母s[i], s[j] 满足 abs(s[i] - s[j]) == 1， 那么就能删除较大的那个字符， 问最多能删多少个。分析贪心， 先把字母z删掉， 然后在删y， 以此类推。代码12345678910111213141516171819202122232425262728293...
2020-03-02 23:41:10
121
原创 2020牛客寒假算法基础集训营6_A 配对（贪心）
题目大意题目链接现在有两个正整数集合， 每个集合n个数， 最大化第k大的 两两配对的和。分析具体怎么归纳不好说， 纯手工发现， 分别将前k大的数， 一个集合第i小的和另一个集合第i大的， 配对， 得出k个数最后最小的那个数就是答案。代码12345678910111213141516171819202122232425262728#i...
2020-02-16 10:14:56
164
原创 2020牛客寒假算法基础集训营6_C 汉诺塔（思维、dp）
题目大意题目链接跟你n个(x, y) 每一组， 都满足x_i < x_i + 1 && y_i < y_i + 1，问如何尽可能分更少的组， 输出每一个分到第几组（组号从1开始）分析按x从小到大排序。Dilworth定理： 最小组数等于y的最长下降子序列长度最长下降子序列 用二分优化的dp求法中， dp[i]表示长度为i的最长下降子序列的最后一个数， 显然，...
2020-02-16 05:55:15
103
原创 C++ STL 中unique详解
一. 概念unique的作用是去重。即“删除”序列中重复的相邻元素， 此处的删除不是真正的删除， 而是让不重复元素替换掉重复元素所在的位置。由于它是”删除”相邻的元素， 所以在使用unique之前， 一般要给序列排序。二. 函数原型只有两个参数且都是迭代器。1iterator unique(iterator it_1,iterator it_2);这种类型的unique函数是我...
2020-02-10 14:17:42
1090
1
原创 2020牛客寒假算法基础集训营3 I-牛牛的汉诺塔（记忆化搜索）
题目大意汉诺塔， 伪代码为123456789Function Hanoi(n,a,b,c) if n==1 then print(a+'->'+c) else Hanoi(n-1,a,c,b) print(a+'->'+c) Hanoi(n-1,b,a,c...
2020-02-10 09:49:40
165
原创 2020牛客寒假算法基础集训营1_F maki和tree（并查集）
题目大意题目链接给你一颗n个节点的树， 每个节点有黑白两种颜色， 问有多少条不同的简单路径， 恰好只经过一个黑点。注： 1. <u, v> 和 <v, u> 视为相同取法。2. 简单路径为两点的最短路。分析两种情况， 一种是以黑点为端点， 另一种黑点不为端点。可以先求出白点连通块以及每个连通块的点的数量sum[cnt]。然后，以黑点为端点的情况是 ans +=...
2020-02-08 14:30:05
115
原创 2020牛客寒假算法基础集训营2_H 施魔法（dp）
题目大意题目链接有n个元素（1-n）， 第i个元素能量值为ai， 可以选择至少k的元素施法， 消耗为选择的k个元素所组成的极值的差，每个元素当且仅当被用1次的最小消耗，分析首先排序。1f[i] 表示使用前i（包括第i）个元素的最小消耗然后维护min(f[j - 1] - a[j]) 即可。代码1234567891011121314151617...
2020-02-07 16:16:31
152
原创 2020牛客寒假算法基础集训营2_F 拿物品（贪心）
题目大意题目链接有n个物品， 每个物品有a，b两个属性， A， B两人一人一次拿一个（A获得a属性， B获得b属性）， A先拿， 求A如何拿能使 sumA - sumB越大， B如何拿能使 sumB - sumA越大， 求出最优策略下， A， B分别拿哪些物品。分析贪心， 比赛的时候试了两个策略不对（这两个策略是我猜的）， 没有找到理论依据。假设A拿B的物品1， B拿A的物品2123...
2020-02-07 03:57:47
109
原创 HYSBZ - 1098 bzoj - 1098 办公楼biu
题目大意题目链接求补图连通块的个数以及各个连通块的大小。分析参照了ww140142的做法。每次枚举一个未在连通块的点，然后从它开始宽搜出它所在的连通块；具体是枚举它的所有原图的边，标记起来，枚举边之后再枚举所有的点，将未标记的点加入该连通块，并加入队列继续宽搜；为了节约无用的枚举，我们还需要对所有点构建链表，将已经在某个块内的点删除；这个算法的复杂度是O(n+m)的；原因是每一个...
2020-02-06 12:13:08
84
原创 SDNU_ACM_ICPC_2020_Winter_Practice_3rd【解题报告】
欢迎评论提问， 纠错文章篇幅较长， 请参考右侧文章目录食用。专题链接： SDNU_ACM_ICPC_2020_Winter_Practice_3rdA HDU 1364 lzwの玩耍1. 题目大意题意超级超级超级恶心。！！！！大意就是， 给你一个01 图， 问机器人能从那些点开始， 进行一系列操作之后， 不撞墙也不跑出图， 问开始点的个数。2. 分析dfs暴力暴力！！3. AC代码...
2020-01-31 22:16:48
150
原创 SDNU_ACM_ICPC_2020_Winter_Practice_2nd【解题报告】
部分参照 SDNU_ACM_ICPC_2020_Winter_Practice_2nd【解题报告】– The__Flash。欢迎评论提问， 纠错文章篇幅较长， 请参考右侧文章目录食用。专题链接： SDNU_ACM_ICPC_2020_Winter_Practice_2ndA HDU 1559 【The__Flash】的矩阵1. 题目大意给你一个m×n的整数矩阵，在上面找一个x×y的子矩阵...
2020-01-29 03:38:29
396
原创 SDNU_ACM_ICPC_2020_Winter_Practice_1st【解题报告】
欢迎评论提问， 纠错文章篇幅较长， 请参考右侧文章目录食用。专题链接： SDNU_ACM_ICPC_2020_Winter_Practice_1stA CodeForces 854A1. 题目大意把一个数n分成两个互质的数(a, b, a < b)， 使 a / b 最大。2. 分析从 i = n / 2 –> 1遍历， 如果 gcd(i, n - i) == 1 ， 输出...
2020-01-29 03:35:44
262
原创 优先队列定义优先级的方法
默认优先级是从大到小.12345678910111213141516171819202122232425262728293031323334353637383940414243// 最大值优先struct cmp1{ bool operator () (int &a, int &...
2020-01-27 23:19:49
1257
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人