Day2：

先放课程表：

2019.1.24

上午

• 讲解订正$Day1$晚上考试的题目。

下午

• 图论：最小生成树。

晚上

• 考试：贪心

考试

• 时空限制：1000ms/512MB

1. 统计单词数（word.cpp/word.in/word.out）：

   • 题目描述：输入一段文段，统计不同单词（不分大小写）的个数。

   • 输入格式：输入一段文段（中间没有回车，只出现字母大小写、空格、逗号','、句号'.'，文段最后回车'\n'。

   • 输出格式：若有M个不同的单词，则按照在段落中出现的先后顺序输出M行。各行格式为： 单词均用大写形式输出（最长的单词顶格输出，它前面没有多余的空格; 其余单词与其右对齐）+冒号+N个*号+出现次数N。

   • 输入样例：

     This is a test. This test is easy. This is a test. This test is easy.

   • 输出样例：

     THIS:4

     IS:4

     A:**2

     TEST:4

     EASY:**2

   • 数据范围：文段单词总数$\leq$100，最长单词长度$\leq$20。

   • 分析：这题的数据还不足以用的上$KMP$，所以就是一道普通的字符串模拟题。重点是cin不能读入空格、'\n'等，所以要输入这些字符要使用：cin.get()或getchar()。

   • Code：

   CPP

   #include <bits/stdc++.h>
   using namespace std;
   
   const int MAXN = 110;
   const int MAXL = 30;
   
   bool isAlpha(char c) {
       return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
   }
   
   char upper(char c) {
       return (c >= 'a' && c <= 'z')? c - 'a' + 'A': c;
   }
   
   string getWord() {
       char c = '\0';
       string s = "";
       while (!isAlpha(c)) {
           if (c == '\n') return s;
           c = cin.get();
       }
       s += upper(c);
       while (c = cin.get(), isAlpha(c))
           s += upper(c);
       return s;
   }
   
   int cnt, freq[MAXN];
   string dict[MAXN];
   
   int main() {
       int r, maxl = 0;
       string t;
       freopen("word.in", "r", stdin);
       freopen("word.out", "w", stdout);
       while (t = getWord(), t != "") {
           r = 0;
           for (int i = 1; i <= cnt; i++)
               if (dict[i] == t) {
                   r = i; break;
               }
           if (r) { freq[r]++; continue; }
           dict[++cnt] = t;
           freq[cnt] = 1;
           maxl = max(maxl, (int)t.length());
       }
       for (int i = 1; i <= cnt; i++) {
           for (int j = 1; j <= maxl - dict[i].length(); j++)
               cout << ' ';
           cout << dict[i] << ":";
           for (int j = 1; j <= freq[i]; j++)
               cout << '*';
           cout << freq[i] << endl;
       }
     fclose(stdin);
   fclose(stdout);
       return 0;
   }

2. 数的读法（num.cpp/num.in/num.out）：

   • 题目描述：输入一个数字串，输出它的读法。注意必须严格按照规范，比如说“10010”读作“yi wan ling yi shi”而不是“yi wan ling shi”，“100000”读作“shi wan”而不是“yi shi wan”，“2000”读作“er qian”而不是“liang qian”。

   • 输入格式：一个数字串，长度不超过12。

   • 输出格式：一个由小写英文字母和空格组成的字符串，表示该数的拼音读法。

   • 输入样例：

     1234567009

   • 输出样例：

     shi er yi san qian si bai wu shi liu wan qi qian ling jiu

   • 分析： 这道题要注意的重点是：

     1、 数的开头不允许有零

     2、 不允许有相邻的零

     3、 不允许出现“零亿”、“零万”

     4、数的开头不允许出现“一十”，而要用“十”代替

   • Code：

   CPP

   #include <bits/stdc++.h>
   using namespace std;
   
   typedef long long ll;
   
   const string p[10] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
   
   ll n;
   string outp[10000];
   int cnt = 0;
   bool flag_yi[10000];
   
   void read(ll x) {
       if (x / 1000) {
           outp[++cnt] = p[x / 1000];
           outp[++cnt] = "qian";
       } else
           outp[++cnt] = "ling";
       x %= 1000;
       if (x / 100) {
           outp[++cnt] = p[x / 100];
           outp[++cnt] = "bai";
       } else
           outp[++cnt] = "ling";
       x %= 100;
       if (x / 10) {
           outp[++cnt] = p[x / 10];
           outp[++cnt] = "shi";
       } else
           outp[++cnt] = "ling";
       x %= 10;
       if (x != 0)
           outp[++cnt] = p[x];
   }
   
   
   int main() {
       freopen("num.in", "r", stdin);
       freopen("num.out", "w", stdout);
       cin >> n;
       
       if (n / 100000000) {
           read(n / 100000000); n %= 100000000;
           outp[++cnt] = "yi", flag_yi[cnt] = 1;
       }
       if (n / 10000) {
           read(n / 10000); n %= 10000;
           outp[++cnt] = "wan";
       }
       if (n) read(n);
       while (outp[cnt] == "ling") cnt--;
   
       bool start = 1;
       outp[0] = "ling";
       for (int i = 1; i <= cnt; i++)
           if (outp[i] == "ling") {
               if (outp[i - 1] != "ling" && (outp[i + 1] != "yi" || !flag_yi[i + 1]) && outp[i + 1] != "wan")
                   cout << outp[i] << " ", start = 0;
           } else if (outp[i] == "yi") {
               if (!(start && outp[i + 1] == "shi"))
                   cout << outp[i] << " ", start = 0;
           } else
               cout << outp[i] << " ", start = 0;
       cout << endl;
       fclose(stdin);
       fclose(stdout);
       return 0;
   }

3. 算术杀手（killer.cpp/killer.in/killer.out）：

   • 题目描述：输入一些形如a op b的简单算式（a,op,b以空格分隔，其中op可能为+,-,*，且a,b位数$\leq10^3$，要求计算式子。

   • 输入格式：每行一个算式，最多10行。

   • 输出格式：每行一个数表示结果。

   • 输入样例：

     32 + 99

     -3 * -6

     -2 + -3

     2 - 3

   • 输出样例：

     131

     18

     -5

     -1

   • 数据范围：

     对于第1,2,3组数据，输入不包含乘法算式

     对于第4,5组数据，a,b在int范围内

     对于第6,7组数据，输入不包含减法算式，且a,b为非负数

     对于第8,9,10组数据，无特殊限制

   • 分析：这道题主要考高精度算法，不过没有高精除（高精$\div$高精是不断使用高精减，高精$\div$低精是类似使用除式的算法）。需要注意的是，可能出现负数，所以读入数据时需要判断负号、分类讨论，输出时判断是否输出负号。

   • Code：

   CPP

   #include <bits/stdc++.h>
   using namespace std;
   
   const int MAXL = 2e3 + 10;
   
   struct bigNum {
       int d[MAXL], len;
   
       bigNum() {
           len = 0;
       }
   
       bigNum(const bigNum &t) {
           len = t.len;
           memcpy(d, t.d, sizeof(d));
       }
       
       bigNum(const string &s) {
           len = s.length();
           for (int i = 0; i < len; i++)
               d[i] = s[len - i - 1] - '0';
       }
   
       void operator +=(bigNum &t) {
           if (len < t.len) {
               for (int i = len; i < t.len; i++)
                   d[i] = 0;
               len = t.len;
           }
           for (int i = 0; i < len; i++) {
               if (i < t.len)
                   d[i] += t.d[i];
               if (d[i] >= 10) {
                   if (i == len - 1)
                       d[len] = 0, len++;
                   d[i + 1]++, d[i] -= 10;
               }
           }
       }
   
       void operator -=(bigNum &t) {
           for (int i = 0; i < len; i++) {
               if (i < t.len)
                   d[i] -= t.d[i];
               if (d[i] < 0)
                   d[i + 1]--, d[i] += 10;
           }
           while (len > 0 && d[len - 1] == 0)
               len--;
       }
   
       bigNum operator +(bigNum &t) {
           bigNum a(*this);
           a += t;
           return a;
       }
   
       bigNum operator -(bigNum &t) {
           bigNum a(*this);
           a -= t;
           return a;
       }
   
       bigNum operator *(bigNum &t) {
           bigNum res;
           memset(res.d, 0, sizeof(res.d));
           res.len = len + t.len - 1;
           for (int i = 0; i < len; i++)
               for (int j = 0; j < t.len; j++)
                   res.d[i + j] += d[i] * t.d[j];
           for (int i = 0; i < res.len; i++)
               if (res.d[i] / 10) {
                   res.d[i + 1] += res.d[i] / 10;
                   res.d[i] %= 10;
                   if (i == res.len - 1) res.len++;
               }
           return res;
       }
   
       bool operator <(bigNum &t) {
           if (len != t.len)
               return len < t.len;
           for (int i = len - 1; i >= 0; i--)
               if (d[i] != t.d[i])
                   return d[i] < t.d[i];
           return 0;
       }
   
       friend ostream &operator <<(ostream &out, const bigNum &t) {
           if (t.len == 0)
               out << 0;
           for (int i = t.len - 1; i >= 0; i--)
               out << t.d[i];
           return out;
       }
   };
   
   void work(bigNum &a, bigNum &b) {       // 输出 a - b 的结果
       if (a < b)
           cout << "-" << b - a;
       else
           cout << a - b;
   }
   
   int main() {
       string s, t;
       char op;
       freopen("killer.in", "r", stdin);
       freopen("killer.out", "w", stdout);
       while (cin >> s >> op >> t) {
           int sgna = 1, sgnb = 1;
           if (s[0] == '-')
               sgna = -1, s = s.substr(1, s.length() - 1);
           if (t[0] == '-')
               sgnb = -1, t = t.substr(1, t.length() - 1);
           bigNum a(s), b(t);
           if (op == '*') {
               
               if (sgna != sgnb)
                   cout << "-";
               cout << a * b;
               
           } else if (op == '+') {
               
               if (sgna == sgnb) {
                   if (sgna == -1)
                       cout << "-";
                   cout << a + b;
               } else {
                   if (sgna == 1)
                       work(a, b);
                   else
                       work(b, a);
               }
               
           } else {   // op = '-'
               
               if (sgna != sgnb) {
                   if (sgna == -1)
                       cout << "-";
                   cout << a + b;
               } else {
                   if (sgna == 1)  // a - b
                       work(a, b);
                   else            // (-a) - (-b) = b - a
                       work(b, a);
               }
               
           }
           cout << endl;
       }
       fclose(stdin);
       fclose(stdout);
       return 0;
   }

• 总结：这次考试主要靠字符串内容，普通的字符串输入输出、高精度等都要比较熟练，我前两道题就打了2$h$，导致我第三题没有足够的时间检查（我竟然因为每行答案之间没换行和忘记判断负数错了QAQ）。今天晚上是贪心，应该不会特别难吧！找到贪心策略就可以了，晚上打Code要打快一点。

笔记

最小生成树

• 基本概念：

  1. 生成树对于一个连通的无向图，从原来的边中选出一些边来，使得它们构成一棵树，且连通了原图中所有的点。
  2. 数的权值：对于带权图，一个生成树的权值为它包含所有边的权值和。
  3. 最小生成树：原图所有生成树中，边权和最小的生成树。
• $Prim$算法：
  • 算法：设原图点集为$V$，$A$为已在生成树中的点构成的集合。
    0. 初始时，选择一个点$x$作为起点，初始化$A$={$x$}
    1. 选择一条权值最小的边$(u,v)$，需满足$u$在$A$中、$v$不在$A$中
    2. 将$(u, v)$边加入生成树，将$v$加入A
    3. 若$V=A$，则算法结束，否则回到第1步
  • 算法复杂度：$O(n^2)$

• 并查集：

  • 初始状态：有 $n$ 个元素1，2， ......，$n$，初始时每个元素分属不同的集合。
  • 算法：用一个树形结构维护一个集合，初始时每个节点单独成一棵树，只需记录每个点的父节点，初始化 $fa[i] = i (1\leq i\leq n)$。
    1. 合并$u$，$v$所在集合：找到$u$，$v$所在树根$u’$，$v’$，将$v’$的父节点置为$u’$。
    2. 查询$u$，$v$是否在同一集合：找到$u$，$v$所在树根$u’$，$v’$，若$u’ =v’$，则在同一集合，否则不在同一集合。
  • 核心Code：
  CPP

  int find(int x) {                        // 查找 x 所在树的根节点
         if (fa[x] == x) 
              return x;
         else 
              return find(fa[x]);
  }
  bool query(int u, int v) {         // 查询 u 和 v 是否在同一集合
         return (find(u) == find(v));
  }
  void merge(int u, int v) {              // 合并 u 和 v 所在集合
        u = find(u), v = find(v);
        fa[u] = v;
  }

  • 优化：在寻找树根时，将下方的子孙节点全部直接连接到树根
  CPP

  int find(int x) {                       //路径压缩
          if (fa[x] == x) return x;
          fa[x] = find(fa[x]);
          return fa[x];
  }

  • 最简Code：
  CPP

  int find(int x) {
          return (fa[x] == x)? x: (fa[x] = find(fa[x]));
  }

  • 时间复杂度：
    • 未优化并查集：$O(n^2)$
    • 路径压缩优化：$O(1)$
• $Kruskal$算法：

  • 算法：

    1. 将所有边从小到大排序
    2. 依次遍历所有边，决定每条边是否选入最小生成树
    3. 如果选择当前边，不会使得图中产生环，则选中，否则不选
    4. 选完n–1条边时，算法结束

    用并查集维护点之间的连通性，对于一条边，查询两端点是否属于同一集合，若是，则会产生环，不能选；若不是，则可以选择。

  • 时间复杂度：$O(m)$，不包含排序复杂度。

• 例题：【洛谷】3366 【模板】最小生成树

  1. $Prim$算法：
  CPP

  #include <bits/stdc++.h>
  using namespace std;
  
  const int MAXN = 5e3 + 10;
  const int MAXM = 4e5 + 10;
  
  struct edge {
      int v, w, next;
  };
  
  int n, m, head[MAXN], size;
  edge e[MAXM];
  int dis[MAXN], flag[MAXN];
  
  void addEdge(int u, int v, int w) {
      e[size].v = v;
      e[size].w = w;
      e[size].next = head[u];
      head[u] = size;
      size++;
  }
  
  int main() {
      memset(head, -1, sizeof(head));
      cin >> n >> m;
      for (int i = 1; i <= m; i++) {
          int u, v, w;
          cin >> u >> v >> w;
          addEdge(u, v, w);
          addEdge(v, u, w);
      }
  
      for (int i = 1; i <= n; i++)
          dis[i] = 1 << 30;
      flag[1] = 1;
      for (int i = head[1]; i != -1; i = e[i].next)
          dis[e[i].v] = min(dis[e[i].v], e[i].w);
  
      int ans = 0;
      for (int i = 1; i <= n - 1; i++) {
          int md = 1 << 30, v = -1;
          for (int j = 1; j <= n; j++)
              if (!flag[j] && dis[j] < md)
                  md = dis[j], v = j;
          if (v == -1) {
              cout << "orz" << endl;
              exit(0);
          }
          flag[v] = 1;
          ans += md;
          for (int j = head[v]; j != -1; j = e[j].next)
              dis[e[j].v] = min(dis[e[j].v], e[j].w);
      }
      cout << ans << endl;
      return 0;
  }

  2. $Kruskal$算法
  CPP

  #include <bits/stdc++.h>
  using namespace std;
  
  const int MAXN = 5e3 + 10;
  const int MAXM = 2e5 + 10;
  
  struct edge {
      int u, v, w;
  };
  
  bool cmp(const edge &a, const edge &b) {
      return a.w < b.w;
  }
  
  int n, m, fa[MAXN];
  edge e[MAXM];
  
  int find(int x) {
      return fa[x] == x? x: fa[x] = find(fa[x]);
  }
  
  int main() {
      cin >> n >> m;
      for (int i = 1; i <= m; i++)
          cin >> e[i].u >> e[i].v >> e[i].w;
      sort(e + 1, e + m + 1, cmp);
  
      int cnt = 0, ans = 0;
      for (int i = 1; i <= n; i++)
          fa[i] = i;
      for (int i = 1; i <= m && cnt < n - 1; i++)
          if (find(e[i].u) != find(e[i].v)) {
              cnt++;
              ans += e[i].w;
              fa[find(e[i].u)] = find(e[i].v);
          }
  
      if (cnt == n - 1)
          cout << ans << endl;
      else
          cout << "orz" << endl;
      return 0;
  }

总结

今天讲了最小生成树和并查集，图论中的基本算法应该差不多就是（最短路+最小生成树+强连通分量+........）。还有3天，就可以过年了。我好认真啊，竟然写了3k字（试图掩盖很多都是PPT上的事实）。