Day 2 高中部寒假集训

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

    • 数据范围:文段单词总数\leq100,最长单词长度\leq20。

    • 分析:这题的数据还不足以用的上 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算法:

    • 算法:设原图点集为 VA 为已在生成树中的点构成的集合。
      1. 初始时,选择一个点 x 作为起点,初始化A={x}
      2. 选择一条权值最小的边 (u,v),需满足uA中、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. 合并 uv 所在集合:找到 uv 所在树根 u’v’,将v’ 的父节点置为u’
      2. 查询 uv 是否在同一集合:找到 uv 所在树根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 上的事实)

本文链接:https://snowflake.pink/archives/8/
This blog is under a CC BY-NC-ND 4.0 Unported License