|
USACO上的簡單介紹,都快忘了各個術語的中文名了 graph vertex 頂點 (pl. vertexes / vertices) edge edge-weighted 帶權圖(貌似中文是這么叫的吧) weight self-loop 自環 simple graph 簡單圖,不存在自環或兩條(及以上)連接相同兩點的邊。multigraph 與之相對 degree adjacent (to) sparse graph 稀疏圖,邊數少于最大值(n*(n-1)/2)的圖。與之相對的是dense graph。 (un)directed graph (有)無向圖 out-degree in-degree 有向圖頂點的出度/入度 path cycle 回路
圖的表示: edge list adjecency matrix adjacency list implict
連通性: connected component 連通分量 strongly connected component 強連通分量 subgraph 子圖. The subgraph of G induced by V' is the graph (V', E') bipartite 二分圖 complete 任意兩點間都有邊
1. 關于函數指針 The C++ Programming Language上的一段示例代碼: map<string, int> histogram;
void record(const string& s) { histogram[s]++; }
void print(const pair<const string, int>& r) { cout << r.first << ' ' << r.second << '\n\; }
int main() { istream_iterator<string> ii(cin); istream_iterator<string> eos;
for_each(ii, eos, record); for_each(histogram.begin(), histogram.end(), print); }
其中record和print是以函數指針的形式傳遞給for_each的。感覺這種方法最清晰、直接。 Java似乎更多的是用接口來達到類似的效果的,比如Collections.sort(Comparable),通常通過匿名內部類來進行自定義元素的比較,從而排序。但是這在語義上已經不是函數了,而是將被排序對象解釋為實現了Comparable接口的對象。 另外Java反射機制中也有Mehod方法,覺得也可以通過傳遞Method類,然后在sort方法中調用這個Method的invoke方法,這應該更接近函數指針的語義。但沒看到過這樣的實例。 C#則引入了委托的概念,通過delegate關鍵字聲明該方法。多一個關鍵字感覺就是啰唆了點。 -,- 現在開始對第一次在Thinking in Java中看到的Callback回調機制有了一點感覺。當時看的時候很難理解。 看來在學習某一門語言的時候有一定其他語言的背景進行比較,很容易加深理解。
2. 使用地址傳遞結構,減少開銷 學C++最不適應的就是指針的應用,因為沒有C的基礎,盡管高中競賽用的是Pascal,也用指針實現了trie、圖的鏈式表示等比較復雜的數據結構,但是也沒有像C++這樣指針穿插在整個程序中的,當然C更多。 C++傳遞結構時默認是先復制一份拷貝,然后函數操作的是該拷貝,而不是Java中的傳遞引用(當然Java沒有結構這一類型)。 C++ Primer Plus中指出要 1) 調用函數時傳遞地址&myStruct 2) 形參聲明為指針MyStruct * 3) 訪問成員使用操作符 ->
3. 將引用用于結構 同樣,為了節省時空開銷,在函數返回值時盡量使用引用。 const MyStruct & use(MyStruct & mystruct) 注意最好將返回的引用聲明為const,否則可以使用這樣的代碼: use(myStruct).used = 10; 容易產生語義混亂。 但在某些時候必須去掉const關鍵字。
算法: 進入大學后,對算法這些基礎的看法改變了好幾次。 高中里認為搞ACM沒什么意義,覺得和應試差不多。 但是大學里有意無意的一些接觸后,發現它涉及了大量應用數學的知識,對基礎的提高十分有用。 保送的時候志愿填了數學系,不就是為了打好數學基礎嗎? 從功利的角度講,有ACM的經歷以后進IT公司自然可以方便不少。
英語: 從小學到高中,英語一直是強項,考試不需要突擊,課本單詞不需要刻意背誦,語言點很少復習,高中的英語考試讓我對自己的英語過于自信了。 然后進了大學,處處受到強人的打擊,上學期拿了B+覺得已經不錯了。到現在這個英語班已經成為中等偏下的學生了,無論是詞匯量還是聽說能力。 sigh,暑假要報個補習班了。
至于其他的應用,asp.net ruby 之類的東西,權且當玩具學學吧,等需要應用的時候再好好看未必來不及,關鍵要有扎實的基礎。
希望這個想法在放假前不會改變。
使用SQL登錄驗證:
1. 在SQL Server Management Studio Express中右擊數據庫,Properties -> Security,Server authentication選為SQL Server and Windows Authentication mode
2. 返回主界面,在Security的Login中增加用戶,分配權限。
BFS,一次通過
 /**//*
PROG: milk3
ID: 06301031
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <deque>
#include <set>

using namespace std;

 struct Status {
int a;
int b;
int c;
};

 void pour(const int from, const int to, const int maxTo, int& newFrom, int& newTo) {
newTo = from + to;
newFrom = 0;
 if (newTo > maxTo) {
newFrom = newTo - maxTo;
newTo = maxTo;
}
}

 int main() {
int i, j, k;
ifstream fin("milk3.in");
ofstream fout("milk3.out");
Status begin;
int maxA, maxB, maxC;
fin >> maxA >> maxB >> maxC;
begin.a = 0;
begin.b = 0;
begin.c = maxC;
bool hash[21][21][21];
 for (i = 0; i <= maxA; i++) {
 for (j = 0; j <= maxB; j++) {
 for (k = 0; k <= maxC; k++) {
hash[i][j][k] = false;
}
}
}
hash[0][0][maxC] = true;
set<int> result;

deque<Status> queue;
queue.push_back(begin);
 while (!queue.empty()) {
deque<Status>::iterator now = queue.begin();
 if (now->a == 0) {
result.insert(now->c);
}
Status newStat;
newStat = *now;
pour(now->a, now->b, maxB, newStat.a, newStat.b);
 if (!hash[newStat.a][newStat.b][newStat.c]) {
hash[newStat.a][newStat.b][newStat.c] = true;
queue.push_back(newStat);
}
newStat = *now;
pour(now->b, now->a, maxA, newStat.b, newStat.a);
 if (!hash[newStat.a][newStat.b][newStat.c]) {
hash[newStat.a][newStat.b][newStat.c] = true;
queue.push_back(newStat);
}
newStat = *now;
pour(now->c, now->a, maxA, newStat.c, newStat.a);
 if (!hash[newStat.a][newStat.b][newStat.c]) {
hash[newStat.a][newStat.b][newStat.c] = true;
queue.push_back(newStat);
}
newStat = *now;
pour(now->a, now->c, maxC, newStat.a, newStat.c);
 if (!hash[newStat.a][newStat.b][newStat.c]) {
hash[newStat.a][newStat.b][newStat.c] = true;
queue.push_back(newStat);
}
newStat = *now;
pour(now->b, now->c, maxC, newStat.b, newStat.c);
 if (!hash[newStat.a][newStat.b][newStat.c]) {
hash[newStat.a][newStat.b][newStat.c] = true;
queue.push_back(newStat);
}
newStat = *now;
pour(now->c, now->b, maxB, newStat.c, newStat.b);
 if (!hash[newStat.a][newStat.b][newStat.c]) {
hash[newStat.a][newStat.b][newStat.c] = true;
queue.push_back(newStat);
}

queue.pop_front();
}

set<int>::iterator iter = result.begin();
fout << *iter;
iter++;
 for (; iter != result.end(); iter++) {
fout << " " << *iter;
}
fout << endl;
return 0;
}

|