yangliuy
- 浏览: 65939 次
- 性别:
- 来自: 北京
-
最新评论
文章列表
从2010年10月份开始，经过2010冬季（期间参加了一次校ACM竞赛，初出茅庐拿了个二等奖），2011年夏季及冬季，到2012年春，总算POJ AC过100题，AC300大业完成了三分之一，耗时跨越了3年，当然中间穿插了2011春的实习和2011秋的考G，能坚持到今天，还是不容易的。要再接再厉，将ACM POJ AC300大业继续下去，坚持到底。
当A题成为一种习惯，发现了写程序是如此美妙，输入与输出之间，洋溢着无穷思考的乐趣
当A题成为一种习惯，理解了一名优秀程序员对技术专研和探求未知的执着
当A题成为一种习惯，明白了IT业软件工程师的真正内功是数据结构与算法艺术，用精巧高 ...
- 2012-02-10 22:16
- 浏览 417
- 评论(0)
这个题目直接用的暴力枚举，但是还是WA了几次
原因是这句话You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
注意i可能大于j，此时需要交换顺序，但是输出的时候还会是原始顺序
比如 输入1 10 输出 1 10 20 ；输入10 1 输出 10 1 20
因此交换i和j需要用标志位记录一下
Source Code
Problem: 1207
...
- 2012-02-10 21:57
- 浏览 471
- 评论(0)
水题一道，以后还是不做水题，没什么收获
Source Code
Problem: 2017
User:
yangliuACMer
Memory: 244K
Time: 0MS
Language: C++
Result: Accepted
#include <iostream>
using namespace std;
int main(){
int n,s[11],t[11];
int i,ret;
while(cin>>n, n != -1){
ret = 0;
me ...
- 2012-02-10 16:54
- 浏览 634
- 评论(0)
此题关键要理解输出的定义
For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.
输出是最小生成树中最长边的长度
对prim算法稍作变化即可AC
Source Code
Problem: 2485
User:
yangliuACMer
...
- 2012-02-09 23:27
- 浏览 558
- 评论(0)
题目：有两个长为n的非递减数组A和B，把B接在A的后面变成长为2n的数组C。设计算法求C的中位数（第n小数）。
思路：O(n)的算法很容易找到，关键是用二分的思想设计logn算法。这题关键是用好a和b数组中脚标和为定值的元素的大小关系。
直观想法是：如果中位数在数组a中，那么若a[m]<b[n-m-2]，此时比a[m]小的数最多只有n-2个，即a[m]不可能为第n小数，偏小更新左界;若a[m]> b [n-m-1],此时比a[m]小的数至少有n个，a[m]不可能为第n小数，偏大更新右界;若a[m]介于b[n-m-2]与b [n-m-1]则a[m]恰好为第n小数。中位数 ...
- 2012-01-11 16:46
- 浏览 643
- 评论(0)
本文探讨基于tesseract的多线程OCR服务器的JAVA实现，可同时对多个android手机客户端提供图片OCR服务
project源码下载http://download.csdn.net/user/yangliuy
最近接手一个项目，项目的背景是要开发一个CS架构的发票真伪识别系统，客户端为android手机，采集发票图像传到服务器做OCR识别，识别出来的发票号码和发票密码发送到国税局官网发票真伪查询页面，然后将真伪信息返回给手机用户。为了开发一个多线程OCR服务器，我研究了JAVA图像处理及OCR技术。JAVA的强大的图形处理相关库如java.awt.image等为采集图像的裁剪、 ...
- 2012-01-09 18:41
- 浏览 1437
- 评论(0)
思路：以物品为结点，物品之间的优惠价格为边权值建图，酋长10000金币当做0号结点，题意就是求图中各结点到0号结点的最短路长度，再加上终点处物品的价值，恰好就是探险家经过这个物品买卖途径所需要付出的金钱。用dijkstra算法求出单源最短路径，从各个结点的最短路径中选出最短的那条就是答案。基本还是经典最短路问题，但做了一点小小变形主要是：
1 有结点等级限制，需要枚举等级
2 把终点的物品价值计入最短路径中去，并且找最小的最短路径输出
3 要注意是单向图，即物品替换关系是单向的
Source Code
Problem: 1062
User:
yangliuACM ...
- 2012-01-03 19:23
- 浏览 510
- 评论(0)
C++虚函数与JAVA中抽象函数比较
1：java中没有虚函数的概念，但是有抽象函数的概念，用abstract关键字表示，java中抽象函数必须在抽象类中，而且抽象 函数不能有函数体，抽象类不能被实例化，只能由其子类实现抽象函数，如 ...
- 2012-01-03 01:54
- 浏览 543
- 评论(0)
今天看了看背包九讲，自己写了下0-1背包和完全背包
王晓东《计算机算法分析与设计》上面给出的C++实现比较繁琐，相比而言这个版本更加简明
给出了测试数据
0-1背包问题C++实现
/*任务：计算0-1背包问题的最大价值
Sample In ...
- 2012-01-03 00:52
- 浏览 1504
- 评论(0)
题意：给定字符串，求哈夫曼编码长和它与等长编码的比值，比较基础
思路：这题考查哈弗曼编码，但其实没必要建树得出编码，只需要统计哈弗曼编码后的总码长即可
参考了网友的题解，用到了优先权队列维持一个从小到大的序列
第38行其实就是把越小的频数反复多加几次，越大的频率少加几次，体现了前缀码的设计思想
Source Code
Problem: 1521
User:
yangliuACMer
Memory: 232K
Time: 0MS
Language: C++
Result: Accepted
//这题考查哈弗曼编码，但其实没 ...
- 2011-12-29 02:28
- 浏览 642
- 评论(0)
const类型定义：指明变量或对象的值是不能被更新,引入目的是为了取代预编译指令
**************常量必须被初始化*************************
cons的作用
（1）可以定义const常量例如：
constintMax=100;
intArray[Max];
（2）便于进行类型检查 ...
- 2011-12-26 10:54
- 浏览 466
- 评论(0)
背包问题
它是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人拥有大量物品，重量各不同。此人通过秘密地选择一部分物品并将它们放 到背包中来加密消息。背包中的物品中重量是公开的，所有可能的物品也是公开 ...
- 2011-12-26 10:35
- 浏览 244
- 评论(0)
题意：车的类型用字符串来描述，两个汽车类型的距离定义为其字符串中不同字符的个数，给定所有的车的类型，求车之间的派生关系，使得总的距离最短，派生关系质量分最大
算法：转化为图论问题，结点对应不同的汽车类型，边的权值就是不同结点字符串距离值，求最小生成树即可（因为题目说明了每个汽车只有一种汽车派生出）
Source Code
Problem: 1789
User:
yangliuACMer
Memory: 15688K
Time: 422MS
Language: C++
Result: Accepted
//00:31-0:53 ...
- 2011-12-26 01:35
- 浏览 378
- 评论(0)
这么多天第一次1AC，虽然题目不难，但是心里还是挺高兴
算法思路：先根据纯色颜料中的最大者求出至少需要的颜料盒数，然后用剩余的颜料来配gray，配的时候要1ml 1ml的配gray颜料，通过不断重新从大到小排序，每次从前三种颜料去1ml配出1mlgray颜料，配之前判断下第3种颜料是否还有剩余，没有就加1个颜料盒，以此类推，到gray颜料配足够为止。要注意判断一定要紧跟排序之后，防止减完第三种颜料为0误判，因为此时第4种颜料可能还剩余1ml。测试用例3就是这种情况
Source Code
Problem: 2709
User:
yangliuACMer
M ...
- 2011-12-26 00:02
- 浏览 441
- 评论(0)
看到关于字符串的面试题总结，第一题我就曾经遇到过- -
摘录于下， 来源：http://rjwyr.blog.163.com/blog/static/112986400201153061911864/
字符串操作
#include <iostream>
#include <sstream>
#include <limits>
#include <vector>
#include <string>
using namespace std;
/*\
1.翻转句子中的单词
题目： ...
- 2011-12-25 22:50
- 浏览 289
- 评论(0)