编程语言小筑
bcyy · 共 3088 篇文章
codeforces Epic Game 题解
Simon and Antisimon play a game. Initially each player receives one fixed positive integer that doesn't change throughout the game. Simon receives number a and Antisimon receives number b . They also have a heap of n stones. The players take turns to make a move and Simon starts. During a move a pl…
2014-04-30 07:16 · 评论(0)
Codeforces Helpful Maths
Xenia the beginner mathematician is a third year student at elementary school. She is now learning the addition operation. The teacher has written down the sum of multiple numbers. Pupils should calculate the sum. To make the calculation easier, the sum only contains numbers 1, 2 and 3. Still, that…
2014-04-30 07:11 · 评论(0)
Unique Binary Search Trees -- LeetCode
原题链接: http://oj.leetcode.com/problems/unique-binary-search-trees/ 这道题要求可行的二叉查找树的数量,其实二叉查找树可以任意取根,只要满足中序遍历有序的要求就可以。从处理子问题的角度来看,选取一个结点为根,就把结点切成左右子树,以这个结点为根的可行二叉树数量就是左右子树可行二叉树数量的乘积,所以总的数量是将以所有结点为根的可行结果累加起来。写成表达式如下: 熟悉 卡特兰数 的朋友可能已经发现了,这正是 卡特兰数 的一种定义方式,是一个典型的动态规划的定义方式(根据其实条件和递推式求解结果)。所以思路也很明确了,维护量res[i]…
2014-04-30 06:16 · 评论(0)
Unique Binary Search Trees II -- LeetCode
原题链接: http://oj.leetcode.com/problems/unique-binary-search-trees-ii/ 这道题是求解所有可行的二叉查找树,从 Unique Binary Search Trees 中我们已经知道,可行的二叉查找树的数量是相应的 卡特兰数 ,不是一个多项式时间的数量级,所以我们要求解所有的树,自然是不能多项式时间内完成的了。算法上还是用求解 NP问题 的方法来求解,也就是 N-Queens 中介绍的在循环中调用递归函数求解子问题。思路是每次一次选取一个结点为根,然后递归求解左右子树的所有结果,最后根据左右子树的返回的所有子树,依次选取然后接上(…
2014-04-30 06:15 · 评论(0)
【图像处理】Gabor滤波器
Gabor的核函数参考的 wiki 使用实数Real的公式计算核函数代码: Mat gaborFilter(Mat& img, Mat& filter){ int half_filter_size = (max(filter.rows,filter.cols)-1)/2; Mat filtered_img(img.rows,img.cols,CV_32F); for(int i=0;i<img.rows;i++){ uchar* img_p = img.ptr<uchar>(i); float* img_f = filtered_img.ptr<float>(i); for(int j=0;…
2014-04-30 00:36 · 评论(0)
Codeforces A. Double Cola 题解
题目很奇怪,就是5个人排队喝可乐,喝完之后编程两个人,然后拍在队后面,然后继续喝可乐。 给出个数值,代表第几罐可乐,问会是第几个人喝到? http://codeforces.com/problemset/problem/82/A 一个数学问题,仔细点就好了。 要熟练的知识点: 1 要熟悉解决这种递增数列,如何减去循环部分 2 要知道如何计算,求余取答案 #include <string> #include <iostream> using namespace std; void DoubleCola() { string strs[] = {"Sheldon", "Leonard", "Pe…
2014-04-29 18:16 · 评论(0)
Timus 1119. Metro 动态规划
Many of SKB Kontur programmers like to get to work by Metro because the main office is situated quite close the station Uralmash. So, since a sedentary life requires active exercises off-duty, many of the staff — Nikifor among them — walk from their homes to Metro stations on foot. Nikifor lives in…
2014-04-29 15:05 · 评论(0)
Timus 1104. Don’t Ask Woman about Her Age题解
Mrs Little likes digits most of all. Every year she tries to make the best number of the year. She tries to become more and more intelligent and every year studies a new digit. And the number she makes is written in numeric system which base equals to her age. To make her life more beautiful she wr…
2014-04-29 12:27 · 评论(0)
Timus 1446. Sorting Hat 分类问题
At the start of each school year, a very important event happens at Hogwarts. Each of the first-year wizards and witches is assigned to one of the four Hogwarts houses. The bravest children are put to Gryffindor, the cleverest are put to Ravenclaw, the most hard-working go to Hufflepuff, and Slythe…
2014-04-29 09:31 · 评论(0)
Timus 1777. Anindilyakwa 奇怪的数数问题
The language of Australian aborigines anindilyakwa has no numerals. No anindilyakwa can say: “I've hooked eight fishes”. Instead, he says: “I've hooked as many fishes as many stones are in this pile”. Professor Brian Butterworth found a meadow with three piles of stones. He decided to determine whe…
2014-04-29 08:43 · 评论(0)
Restore IP Addresses -- LeetCode
原题链接: http://oj.leetcode.com/problems/restore-ip-addresses/ 这道题的解法非常接近于 NP问题 ,也是采用递归的解法。基本思路就是取出一个合法的数字,作为IP地址的一项,然后递归处理剩下的项。可以想象出一颗树,每个结点有三个可能的分支(因为范围是0-255,所以可以由一位两位或者三位组成)。并且这里树的层数不会超过四层,因为IP地址由四段组成,到了之后我们就没必要再递归下去,可以结束了。这里除了上述的结束条件外,另一个就是字符串读完了。可以看出这棵树的规模是固定的,不会像平常的 NP问题 那样,时间复杂度取决于输入的规模,是指数量级的…
2014-04-29 05:01 · 评论(0)
Interleaving String -- LeetCode
原题链接: http://oj.leetcode.com/problems/interleaving-string/ 这是一道关于字符串操作的题目,要求是判断一个字符串能不能由两个字符串按照他们自己的顺序,每次挑取两个串中的一个字符来构造出来。 像这种判断能否按照某种规则来完成求是否或者某个量的题目,很容易会想到用动态规划来实现。 先说说维护量,res[i][j]表示用s1的前i个字符和s2的前j个字符能不能按照规则表示出s3的前i+j个字符,如此最后结果就是res[s1.length()][s2.length()],判断是否为真即可。接下来就是递推式了,假设知道res[i][j]之前的所有…
2014-04-29 04:28 · 评论(0)
Timus 1644. A Whole Lot of Walnuts 算法
Ten big walnuts is a whole lot of walnuts, that's for sure! Two walnuts is too little for anybody. How about six walnuts? Is it a small number of walnuts or a large one? The Parrot has already found an answer to this question: after eating a small amount of walnuts he wants to eat some more, while …
2014-04-28 19:26 · 评论(0)
Timus 1510. Order 找到出现次数过半的数
A New Russian Kolyan likes two things: money and order. Kolyan has lots of money, but there is no order in it. One beautiful morning Kolyan understood that he couldn't stand this any longer and decided to establish order in his money. He told his faithful mates to fetch the money from an undergroun…
2014-04-28 18:19 · 评论(0)
Timus 1161. Stripies
Our chemical biologists have invented a new very useful form of life called stripies (in fact, they were first called in Russian - polosatiki , but the scientists had to invent an English name to apply for an international patent). The stripies are transparent amorphous amebiform creatures that liv…
2014-04-28 16:08 · 评论(0)