|
|
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;
}
|