ITeye博客

Programming

共 51 篇文章

USACO Mother's Milk(milk3)题解

每种状态下,只有六种移动的情况:A->B, A->C, B->A, B->C, C->A, C->B, 一一判断,BFS,直到没有新的状态出现。 /* ID: bbsunch2 PROG: milk3 LANG: C++ */ #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<queue> #include<map> #include<set> #include<cmath> #include<algorithm> #include<fstream>…

2014-12-05 11:31 · Programming · algorithm

USACO Ski Course Design(skidesign) 题解

这一题被我想复杂了,我自己加了一个约束条件,可是题目中并没有,这个约束条件是:从high hill上砍下来的东西必须安到其他low hill上去,可是原题并没有。那么问题来了,如果加上了这个约束条件,这一题应该怎么解? 如果去掉这个约束条件,题目就变得异常简单,只需要iterate max hill的值就可以了,代码如下: /* ID: bbsunch2 PROG: skidesign LANG: C++ */ #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #in…

2014-11-27 00:44 · Programming · algorithm

USACO Wormholes(wormhole) 题解

这里再次强烈推荐USACO,因为他们每一题的题解现在有视频了!! 在这一题上花了一天时间,想到用recursion来解决问题,想到检测loop的方法,不过还是出了错误,loop解决方案参考了http://blog.csdn.net/thestoryofsnow/article/details/39821333 通过之后,看了USACO自己的题解,他们有更简洁和高效的解决方案,发现大家看问题的方式真的是不一样,这个人应该是那种大牛的赶脚,同时突然很庆幸自己在USACO上花时间,因为这一次比以往的任何一次学到的东西都多,包括对问题抽象化的方式也跟以前大不相同。 下面是我的代码,我比较喜欢用容器,…

2014-11-25 05:13 · Programming · algorithm

USACO Combination Lock (combo)题解

有人说这一题暴力搜索,O(N^3),naive,哥只要O(N^2) 当然也差不了多少啦哈哈,因为N只有5。。。 思路: 总数,减去overlap的,就是结果 代码: /* ID: bbsunch2 PROG: combo LANG: C++ */ #include <iostream> #include <fstream> #include <stdlib.h> #include <vector> using namespace std; int main() { ofstream fout ("combo.out"); ifstream fin ("combo.in"); int N; f…

2014-11-05 23:41 · Programming · algorithm

用标准库或者boost分割C++字符串

使用标准库 #include <iostream> #include <vector> #include <string> #include <sstream> using namespace std; std::vector<std::string> &split(const std::string &s, char delim, std::vector<std::string> &elems) { std::stringstream ss(s); std::string item; while (std::getline(ss, item, delim)) { if (!item.emp…

2014-09-30 04:41 · Programming

Qt 使用Dom 操作XML的范例

//--------------------读----------------------------------------------- QString filename = "D:/zhao/qt/tryxml-build-desktop-Qt_4_8_0_for_Desktop_-_MinGW__Qt_SDK__Debug/history.xml"; qDebug() << filename; QFile file(filename); if(!file.open(QFile::ReadOnly | QFile::Text)) { qDebug() << "Error: Cannot…

2013-05-09 13:41 · Programming · QT

USACO Prime Cryptarithm 题解

此题很水,暴力搜索,然后根据条件判断,continue掉一些循环就可以了,简称,剪枝,一次过! 下面上代码: /* ID: bbsunch2 PROG: crypt1 LANG: C++ */ #include <iostream> #include <fstream> #include <stdlib.h> #include <vector> using namespace std; int main() { ofstream fout ("crypt1.out"); ifstream fin ("crypt1.in"); int digitNum; vector<int> digits;…

2013-05-08 15:53 · Programming

USACO Calf Flac题解

这一题有点烦 我一开始的思路是,回文序列么,就是正序字符串和逆序字符串中相同的那一串 于是乎,就转化成求最长公共子字符串,于是用动态规划,O(N^2)的时间复杂度和空间复杂度 首先是内存超了,于是换成O(n)空间复杂度的实现方式,即只记录上一状态就可以 接着到最后一个测试程序的时候,时间也超了 无奈,想不出其他思路的情况下,看了NOCOW的解题,O(n)的动态规划 思路是这样的: 写道 begin if cha[i]=cha[i-1] then f[i]:=i-1; if cha[i]=cha[f[i-1]-1] then f[i]:=f[i-1]-1; end; 以下是代码,注释部分是我一…

2013-05-06 17:21 · Programming

USACO Barn Repair 题解

题目翻译还是看USACO吧, 这题贪心,贪心都是很水的,还有解析说用动态规划做的,是因为题目太水让你脑子进水了吧? 下面是代码,忍不住用STL /* ID: bbsunch2 PROG: barn1 LANG: C++ */ #include <iostream> #include <fstream> #include <string> #include <vector> #include <stdlib.h> #include <algorithm> using namespace std; int main() { ofstream fout ("barn1.out"); ifstrea…

2013-04-26 19:22 · Programming

USACO Mixing Milk 题解

题目大意: 描述 由于乳制品产业利润很低,所以降低原材料(牛奶)价格就变得十分重要。帮助Marry乳业找到最优的牛奶采购方案。 Marry乳业从一些奶农手中采购牛奶,并且每一位奶农为乳制品加工企业提供的价格是不同的。此外,就像每头奶牛每天只能挤出固定数量的奶,每位奶农每天能提供的牛奶数量是一定的。每天Marry乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。 给出Marry乳业每天对牛奶的需求量,还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。 注:每天所有奶农的总产量大于Marry乳业的需求量。 格式 PROGRAM NAME : milk INP…

2013-04-26 11:05 · Programming

稍微说说动态规划和贪心

最近在做USACO的training,又碰到了greedy algorithm的训练章节。回想起来大学时光学习dynamic programming的时候,一直搞不清,后来看Introduction to Algorithm,突然顿悟,那种感觉真的是很爽,我觉得一直学不明白,有一天突然顿悟的感觉,大家都应该去体验一下,真的很爽。 greedy的思想太简单了,每次都找最优的,也就是每次的结果只有一个点咯。不过应用greedy algorithm的时候需要特别注意条件,局部最优即全局最优。这是多于dynamic programming的一点。 然后dynamic programming吧,它和g…

2013-04-25 10:16 · Programming

USACO Dual Palindromes 题解

一天水了两题,呵呵,题目确实挺水的 做完上一题,这一题已经毫无难度可言了,只改了点代码 诸位凑合看: /* ID: bbsunch2 PROG: dualpal LANG: C++ */ #include <iostream> #include <fstream> #include <string> #include <vector> #include <stdlib.h> using namespace std; string changeBase(int formerNum, int baseNum) { string latterNumString; while(formerNum) …

2013-04-23 14:41 · Programming

USACO Palindromic Squares 源码

这题很容易的,依然是暴力搜索,好吧,这一章都叫complete search 要点就两个,一个是进制转换,一个是ASCII码转换(当然你要想用数组来搞也是没什么问题的) 难道就是在告诉你,暴力搜索才是你最需要care的么?! 下面上我的代码: /* ID: bbsunch2 PROG: palsquare LANG: C++ */ #include <iostream> #include <fstream> #include <string> #include <vector> #include <stdlib.h> using namespace std; string changeBas…

2013-04-23 14:02 · Programming

USACO Name That Number源码

这次一直没过的是,C++的char转int, 要用这一句 int rightNum = (int)num[i] - 48; 一定要减去48才行。。调了一会儿才发现 下面是源码 /* ID: bbsunch2 PROG: namenum LANG: C++ */ #include <iostream> #include <fstream> #include <string> #include <vector> #include <stdlib.h> using namespace std; char number_letter[10][3] = { {},// 0 {},// 1 {'A','…

2013-04-08 15:26 · Programming

USACO Transformation源码

/* ID: bbsunch2 PROG: transform LANG: C++ */ #include <iostream> #include <fstream> #include <string> #include <vector> using namespace std; vector<vector<char> > rotate90(vector<vector<char> > formerMatrix, int num) { vector<vector<char> > latterMatrix; for(int i = 0; i < num; i++) { vector<char> …

2013-04-03 20:59 · Programming

USACO MilkingCow源码

/* ID: bbsunch2 PROG: milk2 LANG: C++ */ #include <iostream> #include <fstream> #include <string> #include <map> using namespace std; int main() { ofstream fout ("milk2.out"); ifstream fin ("milk2.in"); map<int, int> startPoint_endPoint; int pairNum = 0; fin >> pairNum; for(int i = 0; i < pairNum; …

2013-04-03 20:57 · Programming

PyDev,在Eclipse中运行python

最近学python做高精度运算。 虽然网上有很多高精度运算的算法,可是用了一个O(n^2)的算法,C++竟然运行了半个小时,坑爹。 今天发现,python是跟我一年生的,1989,属蛇。而python的翻译也是蟒蛇。 真是太巧了! 下面这篇文章是说怎么在eclipse中运行python: PyDev 简介 2003年7月16日,以 Fabio Zadrozny 为首的三人开发小组在全球最大的开放源代码软件开发平台和仓库 SourceForge 上注册了一款新的项目,该项目实现了一个功能强大的 Eclipse插件,用户可以完全利用 Eclipse 来进行 Python 应用程序的开发和调试。这…

2012-04-20 10:38 · Programming · bioinformatics

开源,选择Google Code还是Sourceforge?

从第一个项目canto(有兴趣的可以到google code上看看,这是bbsunchen的第一个大型项目)到现在在中科院的项目,只要是事关发布的,我一直使用google code和svn来做版本控制工作。而Sourceforge,则是在最近要发表论文时才发现,很多论文的editor审稿时,要求提供Sourceforge的源码下载地址。下面就google code 和Sourceforge来具体说说。 初接触Google Code的时候,我简单地认为,Google Code只是一个半成品,从各方面的功能来讲,似乎远不能够与Sourceforge的完备相比。但是,随着对Google Code了…

2012-01-04 11:35 · 项目管理 · Programming

QT中文字的绘制

为什么要做这次文字的介绍,因为在一般的教材中,还真没有文字的描述: 1.绘制最简单的文字。 我们更改重绘函数如下: void Dialog::paintEvent(QPaintEvent *) { QPainter painter(this); painter.drawText(100,100,”yafeilinux”); } 我们在(100,100)的位置显示了一行文字,效果如下。 2.为了更好的控制字体的位置。我们使用另一个构造函数。在帮助里查看drawText,如下。 这里我们看到了构造函数的原型和例子。其中的flags参数可以控制字体在矩形中的位置。我们更改函数内容如下。 void …

2011-12-06 16:11 · Programming · QT

QT 2D绘图的坐标系统与图形显示

这篇文章中,给出Qt坐标系统的详细介绍,在附件中,给出使用Qt制作的绘图程序,类似于windows中的画图程序。 整合了网络中可见的所有Qt绘图资源 一、坐标系简介。 Qt中每一个窗口都有一个坐标系,默认的,窗口左上角为坐标原点,然后水平向右依次增大,水平向左依次减小,垂直向下依次增大,垂直向上依次减小。原点即为(0,0)点,然后以像素为单位增减。 例如: void Dialog::paintEvent(QPaintEvent *) { QPainter painter(this); painter.setBrush(Qt::red); painter.drawRect(0,0,100,10…

2011-12-06 16:09 · Programming · QT