- 博客(106)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 学习ACM的系统大纲 【技能树】
今天听了知乎大佬SimonS的一个Live：如何快速攻克传统算法和数据结构？ Live链接 欢迎大家支持里面有很多受益匪浅的地方，在这里和大家分享一下。 学习算法是否有必要参加ACM算法编程竞赛？ 这里给出的答案是一定有必要，不论专科还是本科，无论你在算法方面是否真的有所建树，都建议参加。其中主讲人提到：ACM是未来就业的金牌敲门砖，可想这比赛的含金量是真的高。除此之外，ACM...
2018-04-09 08:52:09
3046
原创 并查集详解【ORZ式教学】
并查集的概念并查集（Union-find Sets）非常精巧而实用，本身不具备结构，借助一定的数据结构以得到支持和实现，他主要用于处理一些不相交集合的合并问题。 举个简单的例子：想必大家都听说过七大姑八大姨九大娘十大爷吧，那么问题来了，给你一个群体的人，他们之间存在有数对亲属关系，给定一对人判断他们之间是否存在亲属关系（近亲、远房亲戚、七大姑八大姨都可以啦~）。PS：关系只能是年幼的指向年长...
2018-03-24 21:07:42
425
原创 C++_STL基础易学教程_【ORZ式教学】
在讲STL之前，首先来引入C plus plus （c++）浅谈c++的优点：1.输入输出流：输入输出基本类型的数据时，可以不必考虑数据是什么类型，系统会判断数据的类型并根据其类型选择调用与之匹配的运算符重载函数。这个过程都是自动的，用户不必干预。如果在C语言中用prinf函数输出不同类型的数据，必须分别指定相应的输出格式符，十分麻烦，而且容易出错。 2.变量的定义可以在for循环里...
2018-03-19 17:41:12
774
原创 背包九讲【ORZ式教学】
背包问题P01: 01背包问题1．1 问题有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。1．2 基本思路在不超过背包容量的情况下，最多能获得多少价值 子问题状态:f[j]:表示前i件物品放入容量为j的背包得到的最大价值 状态转移方程:f[j] = max{f[j],f[j - weigh...
2017-12-06 11:22:09
918
原创 乘法逆元数论篇【ORZ式教学】
引入篇乘法逆元较多用于求解除法取模问题 例如：(a/b)%m时，可以将其转换为(a%(b×m))/b，但这样求解的过程依然涉及到除法，所以我们应当避免除法的直接计算。这时候就需要用到我们要讲的乘法逆元。 可以使用逆元将除法转换为乘法：假设b存在乘法逆元，即与m互质（充要条件）。 设c是b的逆元，即 b×c≡1(mod m) 那么有 a/b=(a/b)×1=(a/b)×b×c=a×c(m
2017-08-19 10:28:03
1220
原创 字典树详解和应用【ORZ式教学】
Trie的简介Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。 Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。Trie树的特性根节点不包含字符，除根节点外每一个节点都
2017-08-11 20:43:18
1233
原创 第十一届河南省ACM大学生程序设计竞赛&&第九届蓝桥杯C/C++ B组国赛
今年本来蓝桥杯国赛和省赛的时间是冲突的，一个蓝桥杯26号下午；一个省赛27号上午。起初决定只参加蓝桥杯国赛，去北京大学参加蓝桥杯蓝桥杯国赛就打算结束了大学的ACM之路，但是实验室的辅导老师说可以在北京比赛完之后赶回来参加省赛，又给了我们一次参加省赛的机会，也正是因为这次机会，让我们队拿到了梦寐以求的省赛金奖！同时完成了与千千一年的约定。前所未有的开心呢。 日期：5.24 定位 ：平...
2018-06-03 20:13:29
1627
1
原创 考研之路【基础阶段】
时间2018.04.23 距19考研仅有8个月！时间很短，任务繁重！基础阶段概述基础复习阶段，从今天起到暑假之前。（4.23 - 7.01） 主要复习的科目英语、数学和数据结构。 英语主要是单词与长难句。 数学主要是高数上下册，线性代数，概率论四本。 数据结构主要是数据结构课本知识。 该阶段主要是把基础打牢，为暑假强化阶段打下基础。 除了每天考研以外，每天晚上抽...
2018-04-23 21:21:53
462
3
原创 无题
蓝桥杯成绩出来了，符合人意的省一，获得参加国家赛的资格。可是事情就是这么巧，今年ACM省赛的比赛时间安排在蓝桥杯比赛的后一天，而我和实验室晋级国赛的伙伴必须要面对的一个问题就是该如何选择。我选啦果？[四川话] 作为一个半路杀来的考研党，本身来说进度就慢，基础还差，和别人已经有很大的差距了。起初的安排：之前的省赛时间定在5月5，6日，准备停课这段时间复习省赛，顺便复习考研的专业课《数据结构》，这样可
2018-04-11 10:09:01
258
原创 POJ_1936 All in All 【字符串】
题目链接题目描述给定两个字符串a,b，可以在a中任意位置插入字母，问最后是否可以得到b串。解题思路我首先想到对两个串进行LCS，发现字符串的长度为100000，果断爆炸。超时超内存。 回归正题，这道题就是一道很水的模拟，只需要从头到尾便利一下b串，判断a串在b串中是否顺序存在即可。代码部分#include <iostream>#inclu...
2018-04-10 11:35:57
244
原创 POJ_3080 Blue Jeans 【KMP】
题目链接题目描述题目叭叭说了一大堆，其实意思就是让你在n个字符串中找到一个最长的公共子串，如果长度小于3输出：no significant commonalities 否则输出最长的子串即可。解题思路首先将第一个串分解，把其所有的子串作为kmp的模式串，在剩余的字符串中查找，如果剩余的字符串中都存在该模式串，就更新答案（公共子串的长度 和 公共子串）。 最后根据题目...
2018-04-10 11:29:38
379
原创 POJ_1035 Spell checker 【字符串】
题目链接题目描述给定几个字符串，以“#”结束，作为字典里的元素。 接着输入几个字符串，以“#”结束，对于每个字符串，要求有以下的输出方式： 如果该字符串存在于字典里，则根据题目规定输出correct 如果不存在，要把它型近的字典里的元素输出来。 型近的3种情况： 1. 字典里面的字符串，长度相等改变一个字母如果与该字符串相同 2. 字典里面的字符串，如果在任意位置，增加...
2018-04-10 11:17:48
195
原创 第三届天梯赛/第九届蓝桥杯 【总结】
说起来今年的天梯赛和蓝桥杯还真是赶巧，两个比赛就差了一天时间，为了两场比赛，做了两天的大巴，终身难忘呀！已经过去了一天了，现在头还在疼着呢。这两场比赛打下来疲惫不堪，但不得不说收获还是挺多的，总体来说吧，比赛成绩并不算特别合人意。下面就来详细的聊聊这场比赛之旅。第三届天梯赛 坐标定位：郑州轻工业学院早上七点半集合信息采集，八点就踏上了这场为期两天的征程，拉了一车的比赛大军，坐...
2018-04-03 14:22:56
546
原创 蓝桥杯_PREV-21_回文数字 【字符串】
题目链接问题描述观察数字：12321，123321 都有一个共同的特征，无论从左到右读还是从右向左读，都是相同的。这样的数字叫做：回文数字。 本题要求你找到一些5位或6位的十进制数字。满足如下要求： 该数字的各个数位之和等于输入的整数。 数字按从小到大的顺序排列。解题思路暴力大法：从小到大遍历5位或6位十进制数，符合回文定义并且数位分离之和为n，输出即可。...
2018-03-27 11:13:06
405
原创 蓝桥杯_PREV-27_蚂蚁感冒 【模拟】
题目链接问题描述长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。 每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。 当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。 这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。 请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。解题思路首先来思考：如果带病的蚂蚁值为...
2018-03-27 11:07:46
212
原创 蓝桥杯_PREV-32_分糖果 【模拟】
题目链接问题描述有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏： 每个小朋友都把自己的糖果分一半给左手边的孩子。 一轮分糖后，拥有奇数颗糖的孩子由老师补给1个糖果，从而变成偶数。 反复进行这个游戏，直到所有小朋友的糖果数都相同为止。 你的任务是预测在已知的初始糖果情形下，老师一共需要补发多少个糖果。解题思路数据范围小，直接暴力模拟，...
2018-03-27 10:51:50
252
原创 蓝桥杯_PREV-33_兰顿蚂蚁 【模拟】
题目链接问题描述给定一个m*n的矩形，每个格子上有0，1，两种形态，0代表白，1代表黑。 蚂蚁要移动k次，移动规则： 若蚂蚁在黑格，右转90度，将该格改为白格，并向前移一格； 若蚂蚁在白格，左转90度，将该格改为黑格，并向前移一格。现在给你一个兰顿蚂蚁的位置，和他头的方向，要走的步数，问最后这个蚂蚁会在什么位置停下。解题思路除去题目中的移动规则，这道题就是...
2018-03-27 10:39:01
226
1
原创 蓝桥杯_PREV-3_带分数 【全排列】
题目链接问题描述100 可以表示为带分数的形式：100 = 3 + 69258 / 714。 还可以表示为：100 = 82 + 3546 / 197。 注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。 类似这样的带分数，100 有 11 种表示法。 输入n ，得出表示法有多少种。解题思路首先将1~9 存到a数组中，对a数组进行全排列，对每种排列...
2018-03-27 10:25:19
310
原创 蓝桥杯_PREV-1_核桃的数量 【GCD】
题目链接问题描述小张是软件项目经理，他带领3个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是： 1. 各组的核桃数量必须相同 2. 各组内必须能平分核桃（当然是不能打碎的） 3. 尽量提供满足1,2条件的最小数量（节约闹革命嘛）解题思路求两遍最小公倍数即可。代码部分#include <ios...
2018-03-27 10:14:30
208
原创 蓝桥杯_PREV-4_剪格子 【DFS】
题目链接问题描述给定一个n*m的格子，每个格子上都有相对应的数字，让你将其分割成两部分，两部分格子的数字之和相等。 如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。 如果无法分割，则输出 0。解题思路首先我们需要找到题目中的突破口，那就是左上角的格子，题目要求，其中一部分要求必须包含左上角的格子，那么我们就可以从左上角开始搜索。 问题来了...
2018-03-25 10:52:02
325
1
原创 蓝桥杯_PREV-19_九宫重排 【双广搜】
题目链接题目描述本题就类似于小游戏拼图，将九宫格中扣去一块，可以导致拼图可以移动，现在问你，给定一个图形，是否可以通过移动得到另一种形状。如果可以，输出最小步数，否则输出-1。 解题思路首先我们可以看出，移动的方向，只能是上下左右四个方向移动，并且只可以将有数字(‘1’ ~ ‘8’)的位置移向空格(‘.’)的位置。反过来可以看出，只有’.’可以上下左右四个方向移动。我...
2018-03-24 19:16:47
957
1
转载 STL_字符串_【string】
一、string对象的定义，初始化及读写string s1;//默认构造函数，s1为空串string s2(s1);//将s2初始化为s1的副本string s1('wuyang');//将s1初始化为一个字符串面值副本string s1(n,'w');//将s1初始化为'w'的n个副本cin>>s1;//读取有效字符，遇到空格结束getline(cin,s1);//...
2018-03-19 17:22:20
526
原创 STL_排序_【sort】
排序可以将容器中的值按照某种规则进行排序，同时可以进行结构体排序 对于普通的数组排序这里不再展开讲，我们根据一道题讲解：天梯赛练习题：L2-009. 抢红包下面就通过简单易懂的代码对其讲解#include<bits/stdc++.h>using namespace std;const int maxn = 1e4 +10;int a[maxn] = {0...
2018-03-19 17:15:40
253
原创 STL_队列_【queue、priority_queue】
队列，使用时需要加头文件queue。特点先进先出。 成员函数有： q.front();返回队首元素 注意：优先队列为q.top(); q.back();返回队尾元素 q.push ();压入队列元素 q.pop();弹出队列元素 q.size();返回队列的大小，即栈中有多少个元素 q.empty();判断队列是否为空 队列的应用：广搜等...
2018-03-19 17:10:37
293
原创 STL_栈_【stack】
栈，使用时需要加头文件statck。特点：栈中的数据是后进先出。 成员函数： s.top();返回栈顶元素 s.push();压栈 s.pop();出栈 s.size();返回栈的大小，即栈中有多少个元素 s.empty();判断栈是否为空下面就通过简单易懂的代码对其讲解///括号匹配问题#include <iostream>...
2018-03-19 17:07:13
223
原创 STL_集合_【set】
顾名思义，就是数学上的集合——每个元素最多只出现一次， 并且set中的元素已经从小到大排好序。使用时需要加头文件set。下面就通过简单易懂的代码对其讲解#include <iostream>#include <set>using namespace std;struct Info{ string name; double s...
2018-03-19 17:01:38
266
原创 STL_映射_【map】
map是STL的一个关联容器，它提供一对一的数据处理能力。（其中第一个可以称为关键字， 每个关键字只能在map中出现一次，第二个可以称为该关键字的值） 比方说 字典, 统计单词下面就通过简单易懂的代码对其讲解#include <iostream>#include <map>using namespace std;//构造方法 int c...
2018-03-19 16:58:23
286
原创 STL_动态数组_【vector】
动态数组，使用时需要加头文件vector。 它的特点可以实现动态增长的数组。也就是说我们不必关心该数组事先定义的容量是多少，它的大小会动态增长。 与数组类似的是，我们可以在末尾进行元素的添加和删除， 也可以进行元素值的随机访问和修改。下面就通过简单易懂的代码对其讲解#include <iostream>#include <vector>...
2018-03-19 16:55:07
319
原创 STL_二分_【binary_search、upper_bound、lower_bound】
关于STL中的二分查找 （1）STL中关于二分查找的函数有三个：lower_bound 、upper_bound 、binary_search —— 这三个函数都运用于有序区间(当然这也是运用二分查找的前提) （2）ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val) 算法返回一个...
2018-03-19 16:37:15
325
1
原创 RQNOJ_123 多人背包 【背包第K优解】
题目链接题目描述DD 和好朋友们要去爬山啦！他们一共有 K 个人，每个人都会背一个包。这些包的容量是相同的，都是 V。可以装进背包里的一共有 N 种物品，每种物品都有给定的体积和价值。 在 DD 看来，合理的背包安排方案是这样的： 每个人背包里装的物品的总体积恰等于包的容量。 每个包里的每种物品最多只有一件，但两个不同的包中可以存在相同的物品。 任意两个人，他们包里...
2018-03-04 10:42:56
285
原创 HDU_1541 Stars 【树状数组】
题目链接题目描述有N个星星，给出N个星星的坐标，但是坐标给出的顺序有一定的规律，按照y坐标从小到大给出，当y坐标相同的时候按照x坐标的大小顺序给出；之后输出处在各个等级的星星的个数，等级就是看y坐标和x坐标同时小于等于这个星星的个数之和。解题思路这道题的难点在于如何用树状数组来存各个坐标星星的等级。 题意已说明输入的的时候是按Y坐标从小到大排序的，然后可以用一个数组来...
2018-03-04 10:34:42
172
原创 HDU_2159 FATE 【二维dp】
题目链接题目描述中文题目，这里就不过多描述解题思路从题目可以看出，怪物可以无限刷，那么这就是完全背包问题。因为题目中涉及到两个条件（忍耐度，刷怪数量），可以看出这是一个二维费用完全背包题目。 我们应该用一个二维的dp数组存放在一定的（刷怪数量和和忍耐度）的状态，得到的经验是多少。 状态转移方程：dp[j][z] = max(dp[j - 1][z - b[i]]...
2018-03-04 10:19:58
128
原创 HDU_1421 搬寝室 【dp】
题目链接题目描述给定n个物品，每个物品有重量， 从中选出m对，使得这m对物品重量差的平方和最小。 疲劳度：m对物品重量差的平方和解题思路将物品按质量递增排序后，从前i件物品中拿走j对（j*2<=i）时，（1）不拿第i件，则dp[i][j]=dp[i-1][j],这个毫无疑问。（2）拿第i件物品，则第i件物品肯定和第i-1件物品一起拿，则dp[i][j]=(...
2018-03-04 10:11:29
157
原创 HDU_1078 FatMouse and Cheese 【记忆化搜索】
题目链接题目描述给出n*n的数字矩阵，从（0，0）出发，走的下一步格子上的数要大于当前格子上的数，并且每次可以沿直线前进最多k个位置，也就是每次有4*k个选择，问最后所有数之和的最大值。解题思路记忆化搜索，所谓记忆化搜索就是搜索加上动态规划代码部分#include <iostream>#include <stdio.h>#in...
2018-03-04 10:04:11
154
原创 HDU_1059 Dividing 【多重背包】
题目链接题目描述给定六件物品，问是否可以按照价值平分解题思路经典的多重背包问题代码部分#include <iostream>#include <string.h>#include <stdio.h>using namespace std;const int maxn = 10;int f[200000];...
2018-03-04 09:57:56
171
转载 HDU_3092 Least common multiple 【dp】
题目链接题目描述给你第一个数n，问你把n分解成另外几个数字，求这几个数字最大的LCM（最小公倍数），结果对m取模解题思路首先我们可以明确的是n分成的这几个数字必然是互质的，为什么？ 假设有两个数字a和b不互质，那么两者的gcd必然不为1，求LCM是必然会少乘以一个两者的gcd，最后的解也就肯定不是最优解了。而对于多个互质的数，最小公倍数是他们的乘积， 所以我们可以先...
2018-03-04 09:53:09
217
原创 HDU_1166 敌兵布阵 【线段树】
题目链接题目描述给定一个区间，在区间上有三个操作。 Add：第i个坐标加上j Sub：第i个坐标减去j Query：查询i到j区间的和解题思路数据范围过大，暴力肯定撞墙，线段树问题，单点更新求区间和，线段树的入门模板题。代码部分#include <iostream>#include <stdio.h>#include &...
2018-03-02 12:39:34
161
原创 HDU_1754 I Hate It 【线段树】
题目链接题目描述N个学生，M个操作，操作分两种，Q：询问A到B中值最大的是多少；S：将A更改为B。解题思路数据范围过大，暴力肯定撞墙，线段树问题，单点更新求区间最大值，线段树的入门模板题。代码部分#include <iostream>#include <stdio.h>#include <algorithm>#...
2018-03-02 12:08:48
144
原创 HDU_1300 Pearls 【DP】
题目链接题目描述一道特别长的英文题目，其实就是让你算一下怎么用最少的钱把这所有的珍珠给买下来。题目上给出n种珍珠，每种珍珠对应着数量和价格（价格从小到大排列）。你有两种购买方式：1.一次只买一种，但是需要你多买10个 2.可以连续着买多种，最后也需要多买10个，所有的珍珠都需按照价格最高的来计算（可以从任意位置开始连续，可以有多个连续）。解题思路首先我们用一个dp[i]数组，
2018-02-06 10:52:30
202
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人