- 博客(40)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 POJ - 1182： 食物链 （并查集）
题目链接：http://poj.org/problem?id=1182题目大意： 中文题目，自己看就好解题思路：并查集经典中的经典题，在网上看了很多大牛的思路，大部分是增加一个结构体存动物间的关系，结合并查集判断，但是关系域的更新比较复杂，一下子不太容易理解，这里推荐一个大牛的解题思路，讲解得非常清楚：https://blog.csdn.net/niushuai666/article/de...
2018-04-21 15:14:27
6978
8
原创 L1-043. 阅览室(细节、思维)
天梯图书阅览室请你编写一个简单的图书借阅统计程序。当读者借书时，管理员输入书号并按下S键，程序开始计时；当读者还书时，管理员输入书号并按下E键，程序结束计时。书号为不超过1000的正整数。当管理员将0作为书号输入时，表示一天工作结束，你的程序应输出当天的读者借书次数和平均阅读时间。注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有S没有E，或者只有E没有S的纪录，系统应能自动忽略这种无效...
2018-03-11 15:00:42
1948
1
原创 C语言、C++中字符及字符串处理的写法总结
C语言：1、gets()和puts() 用法： gets(line)；puts(line)； 其中，line是字符数组（注：C语言中没有独立定义字符串的变量类型，而是采用字符数组的形式；字符串和字符数组很大的区别就是字符串以'\0'结尾） 函数特点： （1）在读入一行时，空格也会作为一个字符读入； （2）如果读入一行的字符串长度超过字符数组定义的长度，会出现警告； （3）用gets...
2018-03-04 16:43:44
2386
原创 L1-006. 连续因子（数学思维）
一个正整数N的因子中可能存在若干连续的数字。例如630可以分解为3*5*6*7，其中5、6、7就是3个连续的数字。给定任一正整数N，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。输入格式：输入在一行中给出一个正整数N（1< N< 231）。输出格式：首先在第1行输出最长连续因子的个数；然后在第2行中按“因子1*因子2*……*因子k”的格式输出最小的连续因...
2018-03-03 10:32:26
1376
原创 HDU - 1274： 展开字符串（递归，栈模拟）
传送门：HDU - 1274题目意思：给定一个简短的字符串，根据相关规则将其展开成完整的字符串思路：自己编写栈函数、或直接递归（调用系统的栈） 递归步骤：1、读入字符，只要不是)就读入，即进栈； 2、如果是数字，则记录，如果是字母，则默认缺省值为1；光标往后移读取数字后的字符； 3、如果是字母，则直接将字母按记录的次数循环输出；如果是(，则按记录的次数循环递归，即递归处理括号内的子串...
2018-03-02 09:32:22
265
原创 HDU - 2050: 折线分割平面（递归）
传送门：HDU - 2050: 折线分割平面题意： 1条折线分成2个平面，2条折线分成7个平面······问n条折线分成多少个平面分析：由直线分割平面可知，增加第n条直线最多与前面的直线有 n-1 个交点，此时分出的平面增加了 (n-1)+1 个； 同理，增加第n条折线最多与前面的折线有2∗2(n−1)" role="presentation" style="
2018-01-31 17:23:30
406
原创 POJ - 1579：Function Run Fun（递归，记忆化搜索）
传送门：POJ - 1579：Function Run Fun思路：递归的规则已经告诉你了，注意输出格式，照着去实现就好了； 有个需要注意的地方就是，要使用记忆化搜索，当遇到已经计算了的就直接返回，避免因重复计算而超时。AC代码：#include#includeusing namespace std;typedef long long LL;LL ans[21][21][21
2018-01-31 16:26:33
299
原创 HDU - 2045： 不容易系列之(3)—— LELE的RPG难题（递推）
传送门：HDU - 2045： 不容易系列之(3)—— LELE的RPG难题题意：排成一排的n个格子，用红、粉、绿三色去涂格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法。思路： n个格子的涂法分两种情况： 1、第n-1个格子和第1个格子同色，这时有f(n-2)种涂法，而第n个格子有两种涂法，所以共有2*f(n-2)种涂法； 2、第n-1个格子和
2018-01-31 16:06:20
215
原创 POJ: Aggressive cows（二分、最大化最小值）
题目链接：POJ: Aggressive cows题目大意：有N个桩和C头牛，将牛系在桩上，已知N个桩的位置坐标，因为牛和牛会相互攻击，所以要尽可能远离，问怎么系才能使离得最近的两头牛的距离最大化。题目分析：典型的二分，最大化最小距离；就是在能系下这C头牛的条件下尽可能让最小距离增大AC代码：#include#include#includeusing namespace
2018-01-30 20:36:31
433
原创 POJ: Monthly Expense（二分，最小化最大值）
题目链接：Monthly Expense 题目大意：FJ记录了接下来连续N天自己每天的开支，现在他想做一个数列清单，这个数列含有M个元素，每个元素代表FJ的一个月消费，每个元素是由连续一天及以上的开支组成，题目问怎样做这个清单才能减小月消费的上限。 题目分析：其实说白了，就是已知一个含有N个元素的序列，通过连续子序列求和得到一个含有M个元素的序列，但M个元素都不能大于某个值（很显然这个值是这个
2018-01-29 17:16:26
360
原创 点排序（比较函数、优先度排序）
点排序总时间限制: 1000ms 内存限制: 65536kB描述给定一个点的坐标(x, y)，在输入的n个点中，依次计算这些点到指定点的距离，并按照距离进行从小到大排序，并且输出点的坐标（如果距离相同，将x轴坐标比较小的点排到前面, 如果距离相等且x轴坐标也相同，则将y轴坐标较小的点排到前面）。坐标为int类型，范围为-1000到1000。n 为1到100之间正整数。输入3
2018-01-24 16:24:39
1914
原创 二分查找写法总结（找元素，定区间，求精度）
在有序表中查找元素常常使用二分查找，也可以叫折半查找，它是通过二分区间不断的缩小查找范围，已达到快速查找的目的，基本思路就像“猜数字游戏”：你心里想一个不超过1000的正整数，我可以保证在10次之内猜到它，只要你告诉我每次是大了还是小了或是相等。在ACM中，二分查找经常穿插在各类题型中，用途很广泛，是必须要掌握的一个算法。一、 整型二分查找采用逐步缩小范围的思维方法，它遵循分治三步法，
2017-08-27 00:18:33
1352
原创 HDU - 1083 : Courses（匈牙利算法，二分图最大匹配）
题目链接：HDU - 1083 : Courses 题目大意：有P门课程，N个学生，每门课程有若干个学生选，且每门课都要有一个课代表，但是每个学生至多只能担任一门课的课代表，问能否每门课都能找到课代表 解题分析：将课程和学生看成二分图的左右两部分，由是否选课确定中间的连边，接下来就是裸套匈牙利算法模板了，如果最大匹配数=课程数，则输出”YES”，否则输出”NO”
2017-08-24 16:12:26
362
原创 匈牙利算法，二分图最大匹配、多重匹配模板
初学二分图推荐： 关于最大匹配、完美匹配的介绍和匈牙利算法的两种实现方法：无权二分图的最大匹配和完美匹配 二分图最大匹配的匈牙利算法、最佳匹配的KM算法讲解：无权二分图最大匹配、有权二分图最佳匹配 关于最大匹配数（最小覆盖数）、最大独立数、最小路径覆盖、带权最优匹配的系统讲解
2017-08-24 15:51:56
1735
原创 HDU - 1150 : Machine Schedule（二分图、最小点覆盖）
题目链接：HDU - 1150 : Machine Schedule 题目大意：有A和B两台机器，A有n种工作模式，B有m种工作模式，现在有k个任务，每个任务可以被A的第x种模式执行，也可以被B的第y种模式执行，机器的初始工作状态在0模式，但是机器每换一种工作模式就需要重启一次，现在请你合理为机器安排任务，使得重启次数最少
2017-08-24 14:12:29
280
原创 HDU - 2044： 一只小蜜蜂...（递推）
传送门：HDU - 2044 题意： 蜜蜂只能从左向右走，不能返回 思路：递推公式dp[i] = dp[i-2]+dp[i-1]，i代表两蜂房之间的距离，即从序号为1的蜂房到序号为i+1的蜂房的线路数，只能由左边相邻的两个格子到达，把前面两个格子线路数相加就行了，这样一来，dp[b-a]就是答案了 AC代码：#include #include #define LL lon
2017-08-07 13:09:07
340
原创 HDU - 1312 ： Red and Black（dfs、bfs）
题目链接：HDU - 1312 ： Red and Black 题目大意：.代表黑棋，#代表红棋，@代表黑棋的起点，棋可以上下左右四个方向移动到同类型棋的位置，现在给你一个w*h的棋盘，问你黑棋可以到达位置的数量，简单的说其实就是求与起点连通的黑棋的数量 思路：可以用dfs，当然也可以用bfs,从起点的四个方向开始搜索，当没有符合条件的位置可以走了就结束搜索，统计数量（用bfs还可以统计走了多少步）
2017-08-01 23:00:54
436
1
原创 POJ - 2785 : 4 Values whose Sum is 0(二分、STL上下界函数）
题目链接：POJ - 2785 : 4 Values whose Sum is 0 题目大意：四组数中各选一个使满足a+b+c+d=0，问有多少种组合方式 思路：先a+b和c+d组合分别得到一个数组，排序后可以用二分，但这里需要注意一点，前面我们用二分是查找存不存在使满足条件的组合，很简单，而这里是要我们计算有多少种组合，所以二分的时候要先用二分查找有序数组中满足条件的第一个值，然后向后搜
2017-08-01 09:53:02
330
原创 HihoCoder - 1041: 国庆出游（dfs、邻接表）
题目链接：HihoCoder - 1041: 国庆出游 题目大意：已知n个城市之间有n-1条路，现在给定部分城市的旅游顺序，问能否刚好每条路都走两次，且按给定顺序参观完成旅行思路：经典dfs搜索，先用bitset计算每个节点的子节点（按位或运算加速），定义vector存邻接表，并用一个二维数组存各城市的连接情况，即邻接矩阵，然后将给定的旅游顺序存到一个一维数组，用这个顺序进行dfs搜索，
2017-08-01 08:47:30
314
1
原创 HDU - 2199：Can you solve this equation?(二分求根、零点逼近)
题目链接：Can you solve this equation? 题目大意：多项式求根，精确到10-4，数据范围是0到100 思路：很明显该多项式在0到100是递增的，故可以用零点逼近法，先求出多项式的最大值和最小值，然后在这个区间二分搜索，直到满足精度为止 AC代码：#include#include#includeusing namespace std;doubl
2017-07-30 09:56:20
267
原创 HDU - 2141：Can you find it?（二分搜索）
题目链接：HDU - 2141：Can you find it？ 题意：给你三组数，要你各从三组数中挑出一个，满足Ai+Bj+Ck=X" role="presentation" style="position: relative;">Ai+Bj+Ck=XAi+Bj+Ck=XA_i+B_j+C_k = X，若满足输出YES，否则NO 思路：典型的二分搜索，先A、B求和并排序，然后二分搜索ab
2017-07-30 09:40:57
613
原创 HDU - 4841： 圆桌问题（vector模拟、字符串模拟）
题目链接：HDU - 4841： 圆桌问题 题意：中文题目，意思应该很清楚，就不啰嗦了 思路：可以用vector模拟，当然也可以直接用字符串模拟，初始化全部为好人，按照规则模拟将指定未指定的好人变成坏人，当只剩下n个人时，模拟结束，输出序列
2017-07-28 08:29:42
562
原创 HDU - 1022 ： Train Problem I（栈模拟）
题目链接：HDU - 1022 ： Train Problem I 题意：告诉了火车进出战的顺序，问能可不可行，可行的话把输出进出站方案，否则输出No 思路：用栈模拟火车进出站，匹配输出序列，若栈顶与输出相同，就出栈，并vector标记进出战，若比较到了栈的末尾，说明可行，否则不可行
2017-07-28 08:15:05
206
原创 HDU - 1896 ： Stones（优先队列、有序对）
题目链接：HDU - 1896 ： Stones 题意：路上有一些石头，首先告诉你石头的坐标，接下来玩个丢石头的游戏，你往前走遇到的第奇数个的石头可以丢，投掷距离和坐标同时给出，遇到的第偶数个的石头原地不动。但注意！当一个坐标同时有几个石头时，你先遇到的是投掷距离最近的石头（这一条件在判断哪个石头是第奇数个遇到的以及该不该扔时很重要，说白了就是影响优先级排序）。问这样下去，最后距离起点最远的石...
2017-07-27 23:09:46
378
原创 CodeForces - 831C: Jury Marks（前缀和去重、STL）
题目链接：CodeForces - 831C 题意：有人去面试，他有一个原始成绩，然后k个评委依次打分，但是他并没有记住全部评委给他打分后的总分，只记得评委依次给他打的k个分数和其中的n个不同的总分，现在问你他的原始成绩有多少种可能取值 思路：先将评委依次给的k个评分前缀和排序后去重（很重要！！！），由于给出了n个中间的总分x，可以通过x−a[j]x-a[j]枚举所有可能的原始成绩，则这
2017-07-27 21:14:18
312
原创 POJ: Surprising Strings（map、字符串处理）
题目链接：POJ - 3096 题意：给你一个字符串，任意两个字符组成一个字符对，如果任意相同距离的字符对不存在相同的情况，则说明该字符串是奇异的，现在给出一些字符串让你判断并且以*结束 思路：遍历一遍所有的字符对，并将距离相同的字符对用map映射为1作为判断，用flag标记是否出现相同的字符对，一旦出现则NOT surprising
2017-07-27 08:42:31
318
原创 POJ: River Hopscotch（二分搜索）
题目链接：POJ - 3258 题意：有一群牛要过河，河中间有N个石墩，告诉了石墩与起点的距离（即坐标），和终点的坐标，现在要去掉M个石墩，但要使牛过河跳跃的最小距离最大化，要求输出该最小距离 思路：最大化最小值，二分搜索 被这道题目题目坑了好多次。。下面枚举一下可能的坑： 1、题目给的桩的坐标并不是按顺序的，所以要提前排一个序； 2、在判断能否去掉时，未考虑桩到终点的距离，因为桩
2017-07-26 23:39:11
209
原创 POJ: Drying（二分、值最小化）
题目链接：POJ - 3104 题意：有n件湿衣服，分别给出其含水量。若衣服放在空气中，每分钟含水量会减少1；若把衣服放进烘干器里面则含水量每分钟会减少k，当衣服含水量为0时说明衣服已经干了，现在问要至少经过多少分钟能使所有的衣服都干了 思路：设每件衣服要mid" role="presentation" style="position: relative;">midmidmid分钟干，其
2017-07-26 22:20:10
401
原创 COJ: Languages（字符串处理、map映射）
题目链接：CSU - 1826 题意：现在告诉你有n种语言，并给出每种语言对应的单词（不同语言间不会有相同的单词），然后给出几行文本，让你判断属于那种语言 思路：运用字符串流，先将每种语言对应的一行读进来，然后用字符串流将每个单词读进来，再用一个map将每个单词映射成每种语言的名称，然后也同样用字符串流输入每个单词，在输进来之前先遍历一遍其中可能出现的标点符号，将除“-”和“‘ ”以外的其他标点符
2017-07-26 20:40:19
269
原创 UVA： I Can Guess the Data Structure!（stl模拟）
题目链接：UVA - 11995 题意：给你一串序列并告诉进出顺序，要你判断这串序列是在什么数据结构中，有stack、queue、priority queue或者有多种可能或者都不可能 思路：直接把进去的序列用stack、queue、priority queue进行模拟，比较出来的序列和给定序列，记录符合条件的个数，再判断即可
2017-07-26 20:20:16
243
原创 CodeForces - 514D ：R2D2 and Droid Army（二分、暴力）
原题链接：CodeForces - 514D 题意：有n个机器排成一列，每个机器有m种类型的描述，每种类型的描述包括a个细节，现在你有m种类型的武器，可以射击k次，第i种武器一次可以摧毁该列所有机器的第i种类型的一个细节，当一个机器的所有细节都被摧毁即被消灭了，问各种类型分别射击多少次才能使连续消灭的机器的长度最大 思路：将每种类型的细节数记录到multiset中，对同一行的各列求和，判断是否满足
2017-07-26 19:45:53
366
原创 快速排序算法手工实现及qsort、sort运用
快速排序算法手工实现及qsort、sort运用 1. 快速排序算法(1) 设置两个变量i、j，排序开始的时候：i=0，j=N-1；(2) 以第一个数组元素作为关键数据，赋值给key，即key=A[0];(3) 从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；(4) 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于
2017-07-15 20:18:15
1102
原创 CodeForces 702B: Powers of Two（遍历、穷举）
Powers of Two time limit per test: 3 seconds memory limit per test: 256 megabytes inputstandard input outputstandard output You are given n integers a1, a2, ..., ana_1, a_2, ..., a_n. Find the n
2017-07-15 11:14:49
410
原创 CSU: B - Lawn mower
Lawn mower Time limit 1000 ms Memory limit 131072 kB description The International Collegiate Soccer1 Competition (ICSC) is famous for its well-kept rectangular stadiums. The grass playing fields
2017-07-14 18:39:57
282
原创 COJ: A-SUM（贪心）
sum you're asked whether there exists a consecutive subsequence whose sum is divisible by m. output YES, otherwise output NO
2017-07-14 12:07:44
229
原创 CSU 1957: Apache还想再活五百年
DescriptionApache总是觉得人生短暂，不能够尽欢。所以他还想再活五百年，于是Apache变跋山涉水来到传说中的蓬莱仙岛向各位长者询问长生的秘诀。长者毕竟是长者，怎么可能让一个年轻人如此容易的得到如此秘诀呢。长者给Apache设置了九九八十一道题目，通关后便可取得秘诀，再活五百年。长者给出的第一道题目如下： 蓬莱仙岛上曾经住着很多长者，我现在给出若干个长者的出生日期以及得道升天的日
2017-06-18 13:45:44
1017
原创 CSU 1958: 数字游戏
Description小明今年才上一年级，加减法只会算加一和减一。老师就是喜欢看小明写不出题目的样子，所以给小明出了个难题：给出两个数字x,y，每次可以让数字的某一位加一或者减一（0减1变成9，9加1变成0）。问从x变到y至少要几次操作？小明虽然数学不好但是编程很强呀，他很快就得出了正确答案，现在看你的了~注意：每次变换只能变动除前导零的数位。例如1109变成0109后不能变再成1109或
2017-06-18 10:04:25
394
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人