ITeye博客

请留言

bbsunchen · 共 134 篇文章

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 · 评论(0)

USACO Arithmetic Progressions (ariprog) 题解

这道题目学到的是,如果是bool类型的判断,亲你还是用数组,加上初始化来得容易一些啊,然后判断是否是Bisquare的时候脑子抽筋,没有直接根据index去判断,导致一开始总是超时。但是值得鼓励的是自己的思路还是正确的,昨天关于数组的想法并没有及时记录或者实现。 下面是最终代码: /* ID: bbsunch2 PROG: ariprog LANG: C++ */ #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<queue> #include<ma…

2014-12-05 01:31 · algorithm · 评论(0)

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 · 评论(0)

USACO Wormholes(wormhole) 题解

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

2014-11-25 05:13 · Programming · algorithm · 评论(0)

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 · 评论(0)

用标准库或者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 · 评论(0)

我的vim配置文件

colorscheme delek set background=dark syntax enable set number set backspace=indent,eol,start "set expandtab set tabstop=4 set shiftwidth=4 set incsearch set hlsearch set nobackup set listchars=tab:>-,trail:~,extends:>,precedes:< set list autocmd Filetype python set expandtab smarttab smartindent a…

2014-05-14 03:04 · 评论(0)

将博客搬至CSDN

最近要把博客搬到CSDN了 因为最近的研究方向变成了算法和理论计算,iteye的风格有点不太适合 当然,我还是会继续搞计算生物学和生物信息学的 谢谢大家的支持,并欢迎访问我的个人主页 CSDN 博客地址: http://blog.csdn.net/bbsunchen

2013-10-07 03:03 · 评论(1)

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 · 评论(0)

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 · 评论(0)

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 · 评论(0)

师兄说的做科研的小技巧

这两天项目拖延,又想起来之前师兄跟我说的做科研的道理。 他说,做一个课题,需要每天都投入一定的时间,比如每天都做两个小时,就比一天做八个小时,做两天,然后歇几天,然后在开始做要好。 回头想想我这三年的科研,确实是这个道理。

2013-05-02 13:21 · Brain Storm · 评论(0)

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 · 评论(0)

USACO Mixing Milk 题解

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

2013-04-26 11:05 · Programming · 评论(0)

稍微说说动态规划和贪心

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

2013-04-25 10:16 · Programming · 评论(0)