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