UVa1395 - Slim Span

思路

首先有一点是可以确定的:对于任何一连通图,必有一生成树(简直废话)。
对于这一题,关键的问题是确定最大与最小。对于这种寻找两个相关变量的题,其实一般可以先试着确定一个,然后再去寻找另一个。
比如在这题中,可以迭代每一个边 L,同时把这条边 L 当做最小的边,用比它大的边去试着连同一幅图,知道找到边 R, 使得加上这条边 R 后刚好可以凑成一幅联通图。
因此,从上述思路可以看出,排序是必不可少了。所有排序是第一步。
排序好后进行遍历 L,建立 N (顶点数) 个并查集 S,每加入一条边就将该边的端点对应的并查集合并(前提是两个端点对应不同的并查集)。
直到刚好加入边 R 后,并查集只剩一个,且大小刚好与顶点数相等。此时对于 L 来说,R - L 极为其 “苗条度”。
因此对所有求得的“苗条度”求一个最小值即可。如果连一个“苗条度”都没有,那结果自然就是找不到合适的答案了。

这一年就这样过去了

Merry Xmas

Merry Xmas!

圣诞节悄然而至,再过几天就是2016了。已经不止一次这么感叹了:时间过得太快,总感觉这一年就这么没了。

对于2015年,总想写下一点内容,毕竟有些事情一直释怀不下,可能说出来会好一点。
Pixiv Id 54204715

UVa10285 - Longest Run on a Snowboard

思路

假设从( x, y )出发,并且从( x, y )出发所能走的最长路为 d[x][y],那么设想如果( x - 1, y )的值(即题目所给的高度)要小于(x,y),那么d[x-1][y] + 1 有可能就是我们所要求的d[x][y],因为这条路是单向的,只可能从较小的(x-1, y)走向(x,y)。如果考虑四个方向,用(x’, y’)表示(x , y)上下左右四个方向,那么d[x][y] = max(d[x’][y’]) + 1,且 (x’, y’)上的值要小于(x, y)。那么从这个方程可以看出这实际上可以采用 DFS 加上 dp 的做法,或者称之为记忆化搜索。而 搜索 的终点则是某点(x, y)的四周都比他大,则返回 1。

sort some list elements into an descreasing ones in js

Intro

Sort is a prevalent topic in programing. Although the sort operation mostly is handled by the back-end like PHP, Java and so on, occasionaly some are occured in front-end. Here are some simple instances I dealt with recently.

Bubble-like Sort

Suppose some list elements ordered as follows:

1
2
3
4
5
6
<ul id="demo">
<li>2</li>
<li>1</li>
<li>4</li>
<li>3</li>
</ul>

Every time I filter through the nodes to get the smallest-value one from 1st one to 4nd one, and then I put it to the tail of lists. Next, I still filter to get the smallest-value one but from 1st one to 3nd one, and still put it to the tail to the lists. Now, two elements are sorted, and still two ones stay idle. The operation continues until all the elements have been sorted.
The produceres can be illustrated as follows:

2 1 4 3 -> 2 4 3 1 -> 4 3 1 2 -> 4 1 2 3 -> 1 2 3 4

在JS中实现静态变量/函数

静态变量/方法

静态变量/方法,一般来说是独立於对象的存在,它不属於任何一个具体的对象,它属於每一特定类的所有对象。也可以认为是属於一个类的。静态变量一般用於常数,或者存储某一类的所有对象需要共有的变量。
学JS的时候发现,与JAVA,C++相比,JS并没有明确定义静态的声明或使用方法。虽然没有说,但仍然需要,比如一个很经典的需要就时用静态变量统计一个类被实例化了几次。

在初学JS时犯的一些错误

表示最近在学JS, 相对个人以前学的Python, JAVA之类的语言, JS的语言确实有一些”奇葩”. 把初学时的一些语法错误记录下来,方便自己以后查阅, 如果能帮助到读这篇文章的你自然就更好了.

number 与 string 相加/减/乘/除

Example 1:

1
2
var a  = "5" + 2;   // the result is "52"
var b = 2 + "5"; // the result is "25"