posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

          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 任意兩點間都有邊

          posted @ 2007-06-03 20:06 ZelluX 閱讀(723) | 評論 (0)編輯 收藏

          一開始什么優化都沒有,過不了了(記得以前是可以的啊)
          然后用了三個hash數組記錄各列、對角線棋子的放置情況,再加上左右對稱解的優化,總算在0.828秒里過了
          /*
          PROG: checker
          ID: 06301031
          LANG: C++
          */


          #include 
          <iostream>
          #include 
          <fstream>

          using namespace std;

          int g[13];
          bool column[13], diag1[25], diag2[25];
          int n;
          int countResult = 0;
          int mid = 0, firstHalf = 0;
          ifstream fin(
          "checker.in");
          ofstream fout(
          "checker.out");

          void DFS(int t) {
              
          int i;
              
          if (t == n) {
                  countResult
          ++;
                  
          if (countResult <= 3{
                      fout 
          << g[0+ 1;
                      
          for (i = 1; i < n; i++{
                          fout 
          << " " << g[i] + 1;
                      }

                      fout 
          << endl;
                  }

                  
          return;
              }


              
          for (g[t] = 0; g[t] < n; g[t]++{
                  
          if ((countResult > 3&& (t == 0)) {
                      
          if (g[t] == n / 2{
                          firstHalf 
          = countResult;
                          
          if (n % 2 == 0{
                              fout 
          << firstHalf * 2 << endl;
                              exit(
          0);
                          }

                      }

                      
          if ((g[t] == n / 2 + 1&& (n % 2 == 1)) {
                          mid 
          = countResult - firstHalf;
                          fout 
          << firstHalf * 2 + mid << endl;
                          exit(
          0);
                      }

                  }

                  
          if (column[g[t]]) {
                      
          continue;
                  }

                  
          if (diag1[g[t] + t]) {
                      
          continue;
                  }

                  
          if (diag2[g[t] - t + n]) {
                      
          continue;
                  }


                  diag1[g[t] 
          + t] = true;
                  diag2[g[t] 
          - t + n] = true;
                  column[g[t]] 
          = true;
                  DFS(t 
          + 1);
                  diag1[g[t] 
          + t] = false;
                  diag2[g[t] 
          - t + n] = false;
                  column[g[t]] 
          = false;

          nextPosition:
                  ;
              }

          }


          int main() {
              fin 
          >> n;
              
          int i;
              
          for (i = 0; i < n; i++{
                  column[i] 
          = false;
              }

              
          for (i = 0; i < n * 2 -1; i++{
                  diag1[i] 
          = false;
                  diag2[i] 
          = false;
              }

              DFS(
          0);
              fout 
          << countResult << endl;
              fout.close();
              
          return 0;
          }

          posted @ 2007-06-03 19:22 ZelluX 閱讀(603) | 評論 (0)編輯 收藏

          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關鍵字。

          posted @ 2007-06-03 18:58 ZelluX 閱讀(373) | 評論 (0)編輯 收藏

          算法:
          進入大學后,對算法這些基礎的看法改變了好幾次。
          高中里認為搞ACM沒什么意義,覺得和應試差不多。
          但是大學里有意無意的一些接觸后,發現它涉及了大量應用數學的知識,對基礎的提高十分有用。
          保送的時候志愿填了數學系,不就是為了打好數學基礎嗎?
          從功利的角度講,有ACM的經歷以后進IT公司自然可以方便不少。

          英語:
          從小學到高中,英語一直是強項,考試不需要突擊,課本單詞不需要刻意背誦,語言點很少復習,高中的英語考試讓我對自己的英語過于自信了。
          然后進了大學,處處受到強人的打擊,上學期拿了B+覺得已經不錯了。到現在這個英語班已經成為中等偏下的學生了,無論是詞匯量還是聽說能力。
          sigh,暑假要報個補習班了。

          至于其他的應用,asp.net ruby 之類的東西,權且當玩具學學吧,等需要應用的時候再好好看未必來不及,關鍵要有扎實的基礎。

          希望這個想法在放假前不會改變。

          posted @ 2007-06-03 18:28 ZelluX 閱讀(346) | 評論 (0)編輯 收藏

          開始的方法太慢了,Superprime要從一位數開始生成,逐漸增加位數。


          /*
          PROG: sprime
          ID: 06301031
          LANG: C++
          */


          #include 
          <iostream>
          #include 
          <fstream>
          #include 
          <cmath>
          #include 
          <vector>
          #include 
          <algorithm>

          using namespace std;

          bool isPrime(long n) {
              
          if (n == 1{
                  
          return false;
              }

              
          for (int i = 2; i <= sqrt(n); i++{
                  
          if (n % i == 0{
                      
          return false;
                  }

              }

              
          return true;
          }


          int main() {
              ifstream fin(
          "sprime.in");
              ofstream fout(
          "sprime.out");
              
          int n;
              fin 
          >> n;
              
          long i, j;
              
          long base = 1;
              vector
          <long> prev, now;
              vector
          <long>::iterator iter;
              prev.push_back(
          0);
              
          for (i = 1; i <= n; i++{
                  
          for (j = 1; j <= 9; j++{

                      
          for (iter = prev.begin(); iter != prev.end(); iter++{
                          
          long number = *iter * 10 + j;
                          
          if (isPrime(number)) {
                              now.push_back(number);
                          }

                      }

                  }

                  prev 
          = now;
                  now.clear();
                  
          base *= 10;
              }


              sort(prev.begin(), prev.end());
              
          for (iter = prev.begin(); iter != prev.end(); iter++{
                  fout 
          << *iter << endl;
              }

          }

          posted @ 2007-06-01 22:32 ZelluX 閱讀(257) | 評論 (0)編輯 收藏

          最簡單的DP,于是只用了一維數組稍微提高下難度,不過還是一次編譯一次提交成功了,恩

          /*
          PROG: numtri
          ID: 06301031
          LANG: C++
          */


          #include 
          <iostream>
          #include 
          <fstream>

          using namespace std;

          int main() {
              ifstream fin(
          "numtri.in");
              ofstream fout(
          "numtri.out");
              
          int n;
              fin 
          >> n;
              
          int i, j;
              
          int f[1001];
              
          for (i = 0; i <= n; i++{
                  f[i] 
          = 0;
              }

              
          for (i = 0; i < n; i++{
                  
          for (j = 0; j <= i; j++{
                      
          int x;
                      fin 
          >> x;
                      f[j] 
          += x;
                  }

                  
          int temp[1001];
                  
          for (j = 0; j <= i; j++{
                      temp[j] 
          = f[j];
                  }

                  temp[i 
          + 1= f[i];
                  
          for (j = 0; j <= i; j++{
                      
          if (f[j] > temp[j + 1]) {
                          temp[j 
          + 1= f[j];
                      }

                  }

                  
          for (j = 0; j <= i + 1; j++{
                      f[j] 
          = temp[j];
                  }

              }


              
          int max = 0;
              
          for (i = 0; i <= n; i++{
                  
          if (f[i] > max) {
                      max 
          = f[i];
                  }

              }

              fout 
          << max << endl;
              
          return 0;
          }

          posted @ 2007-06-01 21:51 ZelluX 閱讀(267) | 評論 (0)編輯 收藏

          Packing Rectangles先cheat了,下星期再回來做。

          先用篩法做了一張hash表,記錄是否為素數,然后找各個素數判斷是否為回文數,超內存了。。。
          于是改為生成回文數后判斷是否為素數,過了。
          貌似現在寫這種程序的速度比高中快不少了,到底是什么進步了呢?
          /*
          PROG: pprime
          ID: 060301031
          LANG: C++
          */


          #include 
          <iostream>
          #include 
          <fstream>
          #include 
          <bitset>
          #include 
          <cmath>

          using namespace std;

          bool isPrime(const long num) {
              
          int i;
              
          for (i = 2; i <= sqrt(num); i++{
                  
          if (num % i == 0{
                      
          return false;
                  }

              }

              
          return true;
          }


          int main() {
              ifstream fin(
          "pprime.in");
              ofstream fout(
          "pprime.out");
              
          long from, to;
              
          long i = 0, j;
              fin 
          >> from >> to;
              
              
          long beginNum = 1;
              
          while (true{
                  
          int number;
                  i
          ++;  // i indicates the digits of palindromes to be generated
                  for (j = beginNum; j < beginNum * 10; j++{
                      
          long num1 = j, num2 = 0, temp = j;
                      
          if (i % 2 == 1{
                          temp 
          /= 10;
                      }

                      
          while (temp > 0{
                          num1 
          *= 10;
                          num2 
          = num2 * 10 + (temp % 10);
                          temp 
          /= 10;
                      }

                      number 
          = num1 + num2;
                      
          if (number > to) {
                          
          break;
                      }

                      
          if (number < from) {
                          
          continue;
                      }

                      
          if (isPrime(number)) {
                          fout 
          << number << endl;
                      }

                  }

                  
          if (number > to) {
                      
          break;
                  }

                  
          if (i % 2 == 0{
                      beginNum 
          *= 10;
                  }

              }

              
          return 0;
          }

          posted @ 2007-06-01 21:28 ZelluX 閱讀(465) | 評論 (0)編輯 收藏

          使用SQL登錄驗證:

          1. 在SQL Server Management Studio Express中右擊數據庫,Properties -> Security,Server authentication選為SQL Server and Windows Authentication mode

          2. 返回主界面,在Security的Login中增加用戶,分配權限。

          posted @ 2007-05-31 21:49 ZelluX 閱讀(372) | 評論 (0)編輯 收藏

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

          posted @ 2007-05-31 17:17 ZelluX 閱讀(705) | 評論 (0)編輯 收藏

          第一次做是用一張hash表記錄的所有的數是否為所謂的bisquare,然后先枚舉公差,再枚舉首項,本來想這樣做就不用再對結果排序了,沒想到效率很低。
          改為先枚舉首項,再枚舉第二項,然后計算公差后,速度提高不少。
          另外第一次使用sort方法。
          /*
          PROG: ariprog
          ID: 06301031
          LANG: C++
          */


          #include 
          <iostream>
          #include 
          <fstream>
          #include 
          <vector>
          #include 
          <algorithm>

          using namespace std;

          struct Ans {
              
          int start;
              
          int step;
          }
          ;

          bool compareOp(const Ans& ans1, const Ans& ans2);

          int main() {
              ifstream fin(
          "ariprog.in");
              ofstream fout(
          "ariprog.out");
              
          int n, m, i, j, k;
              
          bool solved = false;
              fin 
          >> n >> m;

              
          // generate Arithmetic Progressions sequence
              bool seq[250*250*2 + 1];    
              
          for (i = 0; i <= m * m * 2; i++{
                  seq[i] 
          = false;
              }

              
          for (i = 0; i <= m; i++{
                  
          for (int j = 0; j <= i; j++{
                      seq[i
          *+ j*j] = true;
                  }

              }


              vector
          <Ans> result;
              
          int step;
              
          for (i = 0; i <= m * m * 2; i++{
                  
          if (!seq[i]) {
                      
          continue;
                  }

                  
          for (j = i + 1; j <= m * m * 2; j++{
                      
          if (!seq[j]) {
                          
          continue;
                      }

                      step 
          = j - i;
                      
          if (i + step * (n - 1> m * m * 2{
                          
          break;
                      }


                      
          bool flag = true;
                      
          for (k = 1; k < n; k++{
                          
          if (!seq[i + step * k]) {
                              flag 
          = false;
                              
          break;
                          }

                      }

                      
          if (flag) {
                          Ans ans;
                          ans.start 
          = i;
                          ans.step 
          = step;
                          result.push_back(ans);
                          solved 
          = true;
                      }

                  }

              }

              
          if (!solved) {
                  fout 
          << "NONE" << endl;
              }


              sort(result.begin(), result.end(), compareOp);
              vector
          <Ans>::iterator iter;
              
          for (iter = result.begin(); iter != result.end(); iter++{
                  fout 
          << iter->start << " " << iter->step << endl;
              }

              fout.close();
              
          return 0;
          }


          bool compareOp(const Ans& ans1, const Ans& ans2) {
              
          return ans1.step < ans2.step;
          }

          posted @ 2007-05-30 22:18 ZelluX 閱讀(633) | 評論 (0)編輯 收藏

          僅列出標題
          共39頁: First 上一頁 23 24 25 26 27 28 29 30 31 下一頁 Last 
          主站蜘蛛池模板: 定南县| 叙永县| 阿拉尔市| 隆子县| 乌审旗| 双流县| 隆化县| 全州县| 湘潭县| 罗江县| 松潘县| 达尔| 冀州市| 罗田县| 惠安县| 南安市| 潢川县| 南汇区| 广西| 望谟县| 郁南县| 石棉县| 福安市| 忻州市| 新和县| 望谟县| 霍邱县| 武邑县| 桂平市| 原平市| 鲁山县| 镇赉县| 五家渠市| 通山县| 鲁甸县| 曲沃县| 阳信县| 韩城市| 泽库县| 弋阳县| 平南县|