高中部寒假集训Day2

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:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    #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:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    #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:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    #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:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    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;
    }
    • 优化:在寻找树根时,将下方的子孙节点全部直接连接到树根
    1
    2
    3
    4
    5
    int find(int x) {                       //路径压缩
    if (fa[x] == x) return x;
    fa[x] = find(fa[x]);
    return fa[x];
    }
    • 最简Code:
    1
    2
    3
    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​$算法:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    #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$算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #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上的事实)

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×