Day 2 高中部寒假集训
浏览 54 | 评论 0 | 字数 12735
Snowflake_Pink
2019年01月24日
  • 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:
      #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:
      #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:
      #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$为已在生成树中的点构成的集合。

        1. 初始时,选择一个点$x$作为起点,初始化$A$={$x$}
        2. 选择一条权值最小的边$(u,v)$,需满足$u$在$A$中、$v$不在$A$中
        3. 将$ (u, v)$边加入生成树,将$v$加入A
        4. 若$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:
      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;
      }
      • 优化:在寻找树根时,将下方的子孙节点全部直接连接到树根
      int find(int x) {                       //路径压缩
              if (fa[x] == x) return x;
              fa[x] = find(fa[x]);
              return fa[x];
      }
      • 最简Code:
      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$算法:
      #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;
      }
      1. $Kruskal$算法
      #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上的事实)

    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/8/
    最后修改时间:2020-04-13 11:09:03
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论