- 博客(115)
- 资源 (3)
- 收藏
- 关注
RSS订阅
原创 HDU 1305 Immediate Decodability HDU 1671 Phone List(字典树)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1305http://acm.hdu.edu.cn/showproblem.php?pid=1671这两题几乎都是一样，所以就一起贴上来了...........题意：每个测试实例先输入一个数N（1），接着输入N个数字串。这些数字串作为电话号码，判断在拨号过程中是否出现干扰的号码
2012-03-28 08:08:54
2465
2
原创 HDU 1251统计难题（字典树）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1251经典的字典树题目。。字典树：又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希
2012-03-22 08:11:37
1900
原创 C++ *max_element函数找最大元素 *min_element函数找最小元素 STL算法
#include#includeusing namespace std;int main(){ int n[]={1,4,22,3,8,5}; int len=sizeof(n)/sizeof(int); cout<<*max_element(n,n+len)<<endl; cout<<*min_element(n,n+len)<<endl; return 0;}C++ S
2012-03-20 14:16:13
37824
原创 NYOJ 42 一笔画问题
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=42快有一个礼拜没写过博客了，数据结构里面的算法太多，经典题目就那么点，做一道少一道，因为自己学，所以花了很多时间来理解。。。。。。不扯了。。。。。。思路：简单的欧拉回路，判断是否能够一笔画就在于各个点是否连通，判断是否连通可以用并查集来做。而且节点为奇点个数为0或者为2才能一笔画。
2012-03-02 16:32:22
4997
原创 NYOJ 35 表达式求值
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=35又是赤裸裸的栈的问题，弄了三天，最终还是卡在浮点数的读取。最后还是看别人博客上面才想到去标记浮点数。。。。又是浪费一天。。。。不过这题还是很经典的，数据结构上的就是拿这题当作例题讲解的，就直接贴上代码了。代码：#include#include#include#inc
2012-02-25 16:39:26
1138
原创 NYOJ 92 图像有用区域
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=92广搜问题。。。从上午一直弄到下午，最后发现自己画蛇添足，泪流满面。。。。。题目很简单，但深搜RumtimeError.跟迷宫那题差不多，只是不需要处理递归的边界（这就是悲剧所在，浪费了一个上午。。。。），还有个坑就在题目上面的输入，是先宽后高，跟一般的思维方式有点不一样。切到200道
2012-02-23 16:33:19
1795
1
原创 NYOJ 12 喷水装置（二）
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=12这题是算法艺术与信息学竞赛的经典题目，其实是跟以前写过的Radar是差不多的，都属于贪心思想。Radar还需要一点数学思想，这题就直接给出了点的坐标，貌似看起来要简单，可是在这题花的时间比Radar要长，小细节花了很多时间（太大意了）。主要思路就是在既能够保证两点有公共区域的情况下又
2012-02-18 09:36:58
3170
1
原创 NYOJ 17 单调递增最长子序列(O(n2))+HDU 1025 Constructing Roads In JGShining +NYOJ 214 单调递增子序列(二)(O(nlogn))（整理）
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=17这题其实是跟导弹拦截一样的，因为还有个加强版，所以把这个跟加强版一起贴上来。经典动态规划题,以后的动态规划很多都是从这个衍生出来的，所以就找了段自己认为比较详细的解释来了，保存下来，备用，语言组织能力太差。。。。。。一， 最长递增子序列问题的描述
2012-02-08 07:21:38
3818
9
原创 字符串处理笔记
类似于strlen,strcmp,strpcy就不写了。。。。。。以下都是在VC6.0下编译，可能在VS上编译错误。append()函数：功能：C++一个字符串连接在另一个字符串后面。代码：#include#includeusing namespace std;void main(){ string a="hello "; string b="world"; a.
2012-01-07 09:56:43
1295
原创 NYOJ 54 最少步数
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=58广搜问题，每个步骤的含义都写在代码里面了。欢迎大家相互交流，代码：#include#include#include#includeusing namespace std;int a[9][9]=//**迷宫地图**//{ 1,1,1,1,1,1,1,1,1,
2012-01-06 10:34:21
2404
1
原创 WHU 1462 - B – Books changing
题目链接：http://acm.whu.edu.cn/land/problem/detail?problem_id=1462#include#include#include#include#includeusing namespace std;int main(){ stacka,b,c; queuep,q; int ncases,n,x,y,i,count=1; s
2013-04-14 20:01:32
1028
转载 51单片机驱动无源蜂鸣器
在学习过程中遇到如下例题：8个发光管由上至下间隔1s流动，其中每个管亮500ms,灭500ms,亮时蜂鸣器响，灭时关闭蜂鸣器，一直重复下去。流水灯的程序相对我个人来说比较简单，但是蜂鸣器有些难度，正常给I/0口一个信号，蜂鸣器既然不响，后经查证是无源蜂鸣器；无源的蜂鸣器，就要通过IO口输出振荡信号来驱动蜂鸣器蜂鸣器简介：蜂鸣器根据结构不同分为压电式蜂
2012-12-06 17:13:37
13305
原创 流水灯
#include#include#define uint unsigned int#define uchar unsigned charvoid delay(uint z);uchar temp;void main(){ temp=0XFE; P0=temp; while(1) { delay(10); temp=_crol_(temp,1); P0=temp;
2012-12-05 13:05:50
1176
原创 控制LED灯闪烁时间（500ms）
#include#define uint unsigned int void delay(uint z)//1ms延时程序{ uint i,j; for(i=0;i<z;i++) for(j=0;j<110;j++);}void main(){ while(1) { P0=0XFF; delay(200); P0=0XFE; delay(200); }
2012-12-05 10:38:33
7023
原创 秦九韶算法
一般地，一元n次多项式的求值需要经过[n（n+1）]/2次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法。在人工计算时，一次大大简化了运算过程。特别是在现代，在使用计算机解决数学问题时，对于计算机程序算法而言秦九韶算法可以以更快的速度得到结果，减少了CPU运算时间。 把一个n次多项式f(x)=a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0]改写成如
2012-11-05 19:32:13
2166
原创 NYOJ 540 奇怪的排序(字符串)
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=540很简单的字符串处理题，因为不懂itoa是非标准C语言库函数，CompileError了一次。后来改成sprintf，就过了。水题，直接上代码。#include#include#include#include#includeusing namespace std
2012-05-17 10:30:00
1295
原创 NYOJ 55 懒省事的小明（优先队列）
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=55这里有先优先队列的简单介绍：http://blog.csdn.net/a_eagle/article/details/7371974http://blog.csdn.net/a_eagle/article/details/7400143没事切切水题，思路：只要
2012-05-09 12:49:46
2557
1
转载 STL 整理（map、set、vector、list、stack、queue、deque、priority_queue）
向量(vector) 连续存储的元素Vectorc;c.back() 传回最后一个数据，不检查这个数据是否存在。c.clear() 移除容器中所有数据。c.empty() 判断容器是否为空。c.front() 传回地一个数据。c.pop_back() 删除最后一个数据。c.push_back(elem) 在
2012-03-27 19:18:01
1335
原创 HDU 1075 What Are You Talking About（字典树）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1075还是赤裸裸的字典树问题。还是几乎套模版来做。。。。。。除了复制标记以外的跟上一篇博客统计难题没什么区别。不过一个小细节还是坑了一个小时。。。。。直接上代码。。。。。#include#include#includestruct node { bool flag;/*标记是
2012-03-27 11:24:04
1949
1
原创 HDU 1873 看病要排队(优先队列)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1873第一次写的优先队列题，准确来说不是写，是从网上找资料再从那里copy过来的。。。。。。。不过还是要保存下来学习。。。。。#include#include#include#includeusing namespace std;struct patient{ int
2012-03-23 12:36:56
1682
原创 字典树建立的一般方法
字典树的一般方法：写着留着看...........不喜勿喷............（1）建立起一个链表。 struct node { int count;/*数据域*/ struct node *next[26];/*指针域，26个只是表示小写英文字母，如果还要其他的字符则需要继续开大数组*/ };（2）建立起头节点
2012-03-22 09:55:53
1804
原创 NYOJ 290 动物统计加强版(字典树)
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=290经典的字典树的问题，代码几乎可以来当模版来用了，就留下来了~~~，不过貌似用运算符重载排序（不知道是不是）也能过。。。。。。。。需要注意的是开辟一个新的内存时下一个指针一定要指向NULL;字典树代码：#include#include#includeint max;
2012-03-21 09:10:28
1934
转载 STL 优先队列的优先级
struct cmp1{ bool operator ()(int &a,int &b) { return a>b;//最小值优先 } }; struct cmp2{ bool operator ()(int &a,int &b) { return a<b;//最大值优先 } };
2012-03-20 09:58:37
6558
原创 vector类中为什么没有push_front方法和pop_front方法
vector是开辟一块空间来作为数组来存放元素(随机迭代器),如果有了pop_front,pop_back这个功能则很容易造成内存碎片,pop_front会造成头部内存产生碎片,pop_back造成尾部内存产生碎片,所以不能像deque(双向迭代器)那样有pop_front, pop_back这样的完全相同的实现.其次才是性能上的问题,vector实现pop_front的功能可以这样:vec
2012-03-19 20:49:11
20072
4
转载 树状数组应用
一维树状数组常用的3个函数int lowbit(int x) //取x的最低位1，比如4，则返回4，如5，则返回1{ return x&(-x);}void update(int i, int val) //将第i个元素增加val{ //i的祖先都要增加val while(i <= n) { sum[i] += val; i += lowbit(i); //将i
2012-03-15 17:07:08
890
转载 一位ACMer过来人的心得
刻苦的训练我打算最后稍微提一下。主要说后者：什么是有效地训练？ 我想说下我的理解。 很多ACMer入门的时候，都被告知：要多做题，做个500多道就变牛了。其实，这既不是充分条件、也不会是必要条件。 我觉得一般情况下，对于我们普通学校的大学生，各方面能力的差距不会太大，在这种情况下，训练和学习的方法尤为重要。 其实，500题
2012-03-15 08:15:28
1175
4
原创 大数乘法（模版）
直接上代码：#include#includeint main(){ int ncases,i,j,alen,blen,sum[1001]; char a[1001],b[1001],ans[1001]; scanf("%d",&ncases); while(ncases--) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
2012-03-14 19:23:17
780
原创 NYOJ 322 Sort(归并排序求逆序数)
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=322如果按冒泡排序这些O(n^2)肯定会超时，所以需要找一种更快的方法 --------归并排序。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序
2012-03-14 13:46:56
1710
转载 树状数组
问题提出：已知数组a[],元素个数为n,现在更改a中的元素,要求得新的a数组中i到j区间内的和(1思考：对于这个问题,我们可以暴力地来解决,从a[i]一直累加到a[j],最坏的情况下复杂度为O(n),对于m次change&querry,合起来的复杂度为O(m*n),在n或m很大的情况下,这样的复杂度是让人无法忍受的.另外,如果没有元素的变更,我们完全可以存储sum[1,k](k=1,2,…
2012-03-13 17:17:04
667
转载 图论基本知识点
1.图的定义由若干个不同顶点与连接其中某些顶点的边所组成的图形就称为图。（顶点的位置以及边的曲直都是无关紧要的，而且也是没有假定这些顶点和边都要在一个平面内，只关心顶点的多少和这些变是连接哪些顶点的），通常用大写字母G表示图，V表示所有顶点的集合，E表示边的集合，记作G = (V, E)。2.同构如果两个图G和G1，它们顶点之间可以建立起一对一的对应，并且当且仅当G的顶点Vi与
2012-03-10 11:13:49
1190
原创 NYOJ 257 郁闷的C小加（一）(中缀式变后缀式)
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=257经典的数据结构题，用栈跟队列模拟。中缀式变后缀式：stack optr;用来存放运算符栈。队列queue opnd用来存放后缀表达式。从左到右扫描中缀表达式，是操作数就放进队列 opnd的末尾。如果是运算符的话，分为下面3种情况：(1）如果是‘（’直接压入opt
2012-03-05 07:46:03
1401
原创 NYOJ 38 布线问题
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=38最小生成树的最基础问题，不过对于比较笨的我来说却花了一个下午想再加上一个晚上敲代码。按照最小生成树的直接来求（随机选一个点，然后找这个点连接到其他点的那条边的最小值（权值），找到后再标记这个点，再从起始点和找到的那个点一起出发，继续找这些点连接到其他点的那条边的最小值，继续标记点。。
2012-02-23 08:07:42
1501
2
原创 HDU 4153 Grey Area
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4153这题是昨天杭电热身赛的题目，当时切了两道水题就跑了，晚上继续搞这题，英文不好理解，要不是有最后一组测试数据估计现在还在纠结。题目可以算是猜出的结果，再代入到第一根第二组测试数据对比，结果正确，貌似就算推对了。也拿第三组测试数据来看。。。1x1+2/3+3/5+1/3x1/5+0x1
2012-02-19 09:42:55
2064
7
原创 NYOJ 248 BUYING FEED
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=248题目比较长，还是英文的，貌似一上去就被这阵势杀到了，后来发现其实题目还是很好理解的。。。。。。。大意：John 需要买饲料，有一条X轴，在X轴的某些点上面有店出售饲料。题目给出了有饲料的商店的编号跟每磅饲料需要付出的价钱。各个商店的饲料价钱可能不想同，还要最多能出售的饲料的数目
2012-02-16 12:34:55
1354
原创 NYOJ 49 开心的小明
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=49其实还是简单的0，1背包，趁热打铁，只当作练手了，没啥好说的了，不过以前开数组开小了一次，这次还是开小了，o(︶︿︶)o 唉，不长记性。。。。。水过。代码：#include#includestruct bb{ int prize;//**价格**// int imp
2012-02-15 09:35:01
2618
原创 NYOJ 325 zb的生日+NYOJ 456 邮票分你一半
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=325http://acm.nyist.net/JudgeOnline/problem.php?pid=456都可以用0，1背包问题来做，不过 zb的生日貌似用搜索更快（没试过。。。。。。），邮票分你一半貌似用搜索就会超时（也没试过）。因为看起来用0，1背包更简单，所以就用0
2012-02-15 09:26:57
2828
原创 NYOJ 37 回文字符串
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=37思想：在纸上测试几组数据，发现先逆转原来的字符串，再用原来的字符串跟逆转后的字符串进行比较，求得的最长公共子序列就是回文串，也就是不需要添加的，再用总长度减去最长公共子序列就可以得到最少需要添加的字符数。代码就简单了，以前写过的稍稍改下就直接贴上来了。代码：#include
2012-02-14 19:30:20
1675
原创 NYOJ 16 矩形嵌套
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=16简单的动态规划题，直接水过。。。。。#include#include#includeusing namespace std;struct qt{ int len;//**长**// int wid;//**宽**//}w[1001];bool comp(qt x
2012-02-13 20:59:56
1273
原创 NYOJ 10 skiing
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=10还是搜索题，加上了DP的思想，看过书上面说搜索不剪枝就会超时，貌似这题。。。。。。，没减也能过，测试数据 的问题。属于简单的搜索题。。。。。代码：#include#includeint a[101][101],visit[101][101];int dx[4]={0,0
2012-02-13 20:38:38
1348
原创 NYOJ 348 Magic
题目链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=348题意：给你n张牌，让你变一个魔术：第1次把上面的1张牌放到底部，然后最上面的牌就是1，然后拿走1。第2次把上面的2张牌依次放到底部，然后最上面的牌就是2，然后拿走2....重复这个过程，直到所有的牌都被拿走。问一开始的牌应该从上到下怎么放，才能完成这个魔术。（题目意思其实我都看不懂
2012-02-12 22:13:28
974
1
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人