关闭此博客

这个博客将于72小时内关闭。短期并未有重开博客的计划。

这个博客在我初上大学的时候建立,如今毕业关闭这个充满幼稚幻想与思考的博客,也象征着我的一段生活的终结。

感谢一切读者。

Posted in Life | Leave a comment

关于我的生产力与创造力以及兴趣

最近陷入了一种可怕地循环。我认为我必须将这些写出来(在我有任何精神疾病征兆前,也在我错的太远前)。平时进入我博客的人大部分是通过英文搜索搜索到我的人,因此我想,这篇文章不会有太多人注意到,权当我的自娱自乐吧。

想掌握某种技能A,A要求前置条件B与C,但是对C不感兴趣,B没耐心。真是一个讽刺的过程,于是碌碌无为地过了几周。写代码也是一种很没意思的状态,怀疑手头的代码的意义,丧失了为此努力的热情。没毅力么?还是别的什么原因?让自己永远处于一种如此无能的状态。

考虑到今年年初乃至去年到现在非常有限的收获。我必须开始思考,到底是什么在制约我在技术上的创造力和生产力。惰性,还是别的什么?

我毫不怀疑我的智力在解决工程类的问题上还是足够的,因此我不认为我的决定性制约因素是智商。于是思路转向性格,也许是懒惰不安分的性格导致我无法长时间坐在椅子上思考与前进。但是谁来告诉我,兴趣和梦想是可以扭转人的个性的?谁来告诉我?最后不可避免的,我开始认真的审视我的兴趣所向。

我开始思考我在本科期间对社会学产生出明显兴趣的原因,或许我并不热爱代码与技术,我更希望去理解人心,和联系着人的社会。这个问题纠缠我已久,在生活中,相比技术的问题,我似乎对人有更好的洞察力。可是,有时又会想起那些寄托于技术上的念想,曾经是如此渴望拥有可以创造事物的技术。相比于人,技术是如此的简单而自然而带有激励性。人是多么讽刺的东西啊。宇宙和自己,都是一个迷。

马上就要到University of Minnesota学习了,这个以心理学和化学闻名的高等学府。也许,我需要的只是一根稻草,一个巴掌,或者一段不一样的时光。愿一切安好,智商++,困惑–。

不过,不管怎么样,还是要先靠自己。努力思考和探索吧!

(PS。我为什么又开始在这个博客上写东西了?因为我发现我空间的流量可观,每天都有人搜索到我。新的blog系统现在发现写的太渣。通过一个项目发现了更好的practice。不过改进旧项目的时间不多了,干脆就放弃了。)

Posted in Life | Leave a comment

准备转移使用新的博客

很长时间来,我一直在思考要不要自己写一个博客,也可以说是自己的网站。

最近终于找到机会,很闲并且学了新的技术和语言,于是就开始写了。

基本目的有几个

1. 尝试新技术,语言。

2. 摆脱Wordpress。

3.增加一个让我学习的动机。

于是,新博客就诞生了,后台使用的是MongoDB + Clojure,前端使用的是backbone+requirejs+jquery。

地址在此:

http://184.82.206.69:8080/blog

现在还属于测试阶段,有很多问题,有很多东西值得改进。

git的repo:

https://github.com/mjzshd/motb

Posted in Life, Projects | Tagged , , , | Leave a comment

Calmness

May the calmness bring me peace, just as in poems.

Posted in Life | Leave a comment

人性的递归

我一直在思考,主观能动性和社会性比起来,有多脆弱?

这是一个鼓励撒谎的地方,这是一个抑制创造的地方,这是一个丛林,这是一个工厂,这是一切摧毁的开始,也是终结。

我一直在思考,为什么要思考?

Posted in Life | Leave a comment

失望只要一瞬间。

RT

Posted in Life | Leave a comment

一趟旅行带来的思考

人生太多徒劳的往事,却有数不尽令人向往的未来。

多么希望能战胜自己,看到那为我等待的雪白的景色。

拔地而起的树,仿佛伸向苍穹的巨手。

年复一年日复一日,能否不再彷徨,以最坚定的信仰,获取属于自己的光环。

若以钱权为交换,可否换我一世安宁与清醒。

是时候,以清醒浇醒自己了!

Posted in Life | Leave a comment

静下心不容易

RT

Posted in Life | Leave a comment

POJ1141 and POJ2955 Dynamic Programming

These 2 problems are exactly the same.
There are so many solution in Internet. I publish this post because few solutions in Internet has good style.

POJ2955: http://poj.org/problem?id=2955

In this problem: ‘dp[i][j]‘ represents the maximum number of matching bracket from Si to Sj;

Code:

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char s[110];
int dp[110][110];
bool match(int i, int j)
{
	if (s[i] == '(' && s[j] == ')') return true;
	if (s[i] == '[' && s[j] == ']')	 return true;
	return false;
}
int main(int argc, char *argv[]) {
	while (~scanf("%s", s) && s[0] != 'e')
	{
		int l = strlen(s);
		memset(dp, 0, sizeof(dp));
		for (int i = l - 2; i >= 0; i--)
			for (int j = i + 1; j < l; j++) {
				if (match(i, j))
					dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
				for (int k = i; k < j; k++)
					dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
			}
		printf("%d\n", dp[0][l - 1]);
	}
	return 0;
}

 

POJ1141: http://poj.org/problem?id=1141

In this problem: ‘dp[i][j]‘ represents the minimum number of character to be added to Sij(from i to j)

Code:

 

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char s[110];
int dp[110][110], pos[110][110];
bool match(int i, int j)
{
	if (s[i] == '(' && s[j] == ')') return true;
	if (s[i] == '[' && s[j] == ']')	 return true;
	return false;
}
void printAns(int l, int r ) {
	if (l > r) return;
	if (l == r){
		if (s[l] == '(' || s[l] == ')')
			printf("()");
		else
			printf("[]");
		return;
	}
	if (pos[l][r] == -1) {
		printf("%c", s[l]);
		printAns(l + 1, r - 1);
		printf("%c", s[r]);
	} else {
		printAns(l, pos[l][r]);
		printAns(pos[l][r] + 1, r);
	}
}
int main(int argc, char *argv[]) {
	scanf("%s", s);
	int l = strlen(s);
	memset(dp, 0, sizeof(dp));
	memset(pos, -1, sizeof(pos));
	for (int i = 0; i < l; i++) dp[i][i] = 1;
	for (int i = l - 2; i >= 0; i--)
		for (int j = i + 1; j < l; j++) {
			dp[i][j] = 0x7fffffff;
			if (match(i, j)) 
				dp[i][j] = dp[i + 1][j - 1];
			for (int k = i; k < j; k++)
				if (dp[i][j] > dp[i][k] + dp[k + 1][j]) {
					pos[i][j] = k;
					dp[i][j] = dp[i][k] + dp[k + 1][j];
				}
		}
	//printf("%d\n", dp[0][l - 1]);
	printAns(0, l - 1); printf("\n");
	return 0;
}
Posted in ACM/ICPC | Tagged , , , | Leave a comment

POJ3762 and POJ3680

These two problems are actually the same.

The key point here is using the property of max flow algorithm to find maximum number of disjoint interval. Then I used SPFA algorithm to make sure I got maximum reward.

Chinese version:
这两水题题基本是一样的,基本思想是通过最大流的性质,保证每次都只能选不相交的区间,并且利用SPFA获得最大费用。PS: 大家可以从我这里直接抠走模板~

:)

My code for POJ 3762:

 

#include 
#include
#include
#include
#include
#include
const int SIZE = 4010;
const int T = 4002, S = 4001, INF = 0x7fffffff;
using namespace std;
struct Edge {
	int to, last, cap, cost;
}e[SIZE &lt;&lt; 2];
int cnt, head[SIZE];
int pre[SIZE], dist[SIZE];
void init()
{
	memset(head, -1, sizeof(head));
	cnt = 0;
}
void addEdge(int from, int to, int ca, int co)
{
	e[cnt].to = to;
	e[cnt].last = head[from];
	e[cnt].cost = co;
	e[cnt].cap = ca;
	head[from] = cnt++;

	e[cnt].to = from;
	e[cnt].last = head[to];
	e[cnt].cost = -co;
	e[cnt].cap = 0;
	head[to] = cnt++;
}
bool spfa()
{
	bool inque[SIZE];
	for (int i=0; i que;
	dist[S] = 0;
	pre[S] = -1;
	que.push(S);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		inque[cur] = false;
		for (int i = head[cur]; i != -1; i = e[i].last) {
			if (e[i].cap &amp;&amp; dist[e[i].to] &gt; dist[cur] + e[i].cost )
			{
				dist[e[i].to] = dist[cur] + e[i].cost;
				pre[e[i].to] = i^1;
				if (!inque[e[i].to]) {
					que.push(e[i].to);
					inque[e[i].to] = true;
				}
			}
		}
	}
	return dist[T] == INF ? false : true;
}
int maxflow()
{
	int ret = 0, delta = INF;
	while (spfa()) {
		for (int i = pre[T]; i &gt;= 0; i=pre[e[i].to]) 
			delta = min(delta, e[i ^ 1].cap);
		for (int i = pre[T]; i &gt;= 0; i=pre[e[i].to]) 
			e[i].cap += delta, e[i ^ 1].cap -= delta;
		ret += (delta * dist[T]);
	}
	return ret;
}
//~~~~~~~~~~~~~~~~~~~~~~~~
struct Task {
	int l, r, w;
}tk[2010];
int inputTime()
{
	int h, m, s;
	scanf("%d:%d:%d", &amp;h, &amp;m, &amp;s);
	return h * 3600 + m * 60 + s;
}
int idx(vector&amp; v, int val) {
	return upper_bound(v.begin(), v.end(), val) - v.begin() - 1;
}
int main(int argc, char *argv[]) {
	int n, m;
	while (~scanf("%d %d", &amp;n, &amp;m))
	{
		init();
		vector num;
		for (int i = 0; i &lt; n; i++)
		{
			tk[i].l = inputTime();
			tk[i].r = inputTime();
			num.push_back(tk[i].l);
			num.push_back(tk[i].r);
			scanf("%d", &amp;tk[i].w);
		}
		sort(num.begin(), num.end());
		vector::iterator it = unique(num.begin(), num.end());
		num.resize(it - num.begin());
		addEdge(S, 0, m, 0);
		for (int i = 1; i &lt; num.size(); i++)
			addEdge(i - 1, i, INF, 0);
		addEdge(num.size() - 1, T, INF, 0);
		for (int i = 0; i &lt; n; i++)
			addEdge(idx(num, tk[i].l), idx(num, tk[i].r), 1, -tk[i].w);
		printf("%d\n", -maxflow());
	}
	return 0;
}

 
Code for POJ 3680:
 

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
const int SIZE = 410;
const int T = 401, S = 402, INF = 0x7fffffff;
using namespace std;
struct Edge {
	int to, last, cap, cost;
}e[SIZE * SIZE];
int cnt, head[SIZE];
int pre[SIZE], dist[SIZE];
void init()
{
	memset(head, -1, sizeof(head));
	cnt = 0;
}
void addEdge(int from, int to, int ca, int co)
{
	e[cnt].to = to;
	e[cnt].last = head[from];
	e[cnt].cost = co;
	e[cnt].cap = ca;
	head[from] = cnt++;
	
	e[cnt].to = from;
	e[cnt].last = head[to];
	e[cnt].cost = -co;
	e[cnt].cap = 0;
	head[to] = cnt++;
}
bool spfa()
{
	bool inque[SIZE];
	for (int i=0; i<SIZE; i++) dist[i] = INF;
	memset(inque,false, sizeof(inque));
	queue<int> que;
	dist[S] = 0;
	pre[S] = -1;
	que.push(S);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		inque[cur] = false;
		for (int i = head[cur]; i != -1; i = e[i].last) {
			if (e[i].cap && dist[e[i].to] > dist[cur] + e[i].cost )
			{
				dist[e[i].to] = dist[cur] + e[i].cost;
				pre[e[i].to] = i^1;
				if (!inque[e[i].to]) {
					que.push(e[i].to);
					inque[e[i].to] = true;
				}
			}
		}
	}
	return dist[T] == INF ? false : true;
}
int maxflow()
{
	int ret = 0, delta = INF;
	while (spfa()) {
		for (int i = pre[T]; i >= 0; i=pre[e[i].to]) 
			delta = min(delta, e[i ^ 1].cap);
		for (int i = pre[T]; i >= 0; i=pre[e[i].to]) 
			e[i].cap += delta, e[i ^ 1].cap -= delta;
		ret += (delta * dist[T]);
	}
	return ret;
}
//Template are above
struct Interval {
	int l, r, w;
}in[210];
int main(int argc, char *argv[]) {
	int cases;
	scanf("%d", &cases);
	while (cases--)
	{
		init();
		vector<int> num;
		int n, m;
		scanf("%d %d", &n, &m);
		for (int i = 0; i < n; i++)
		{
			int u, v, w;
			scanf("%d %d %d", &in[i].l, &in[i].r, &in[i].w);
			num.push_back(in[i].l);
			num.push_back(in[i].r);
		}
		sort(num.begin(), num.end());
		vector<int>::iterator it = unique(num.begin(), num.end());
		num.resize(it - num.begin());
		addEdge(S, 0, m, 0);
		for (int i = 1; i < num.size(); i++)
			addEdge(i - 1, i, INF, 0);
		addEdge(num.size() - 1, T, INF, 0);
		for (int i = 0; i < n; i++)
		{
			int u = upper_bound(num.begin(), num.end(), in[i].l) - num.begin() - 1;
			int v = upper_bound(num.begin(), num.end(), in[i].r) - num.begin() - 1;			addEdge(u, v, 1, -in[i].w);			
		}
		printf("%d\n", -maxflow());
	}
	return 0;
}
Posted in ACM/ICPC | Tagged , , , , | Leave a comment