Day 2 高中部寒假集训

浏览 1100 | 评论 0 | 字数 12735

Snowflake_Pink

2019年01月24日

Day2：

先放课程表：

2019.1.24

上午

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

下午

图论：最小生成树。

晚上

考试：贪心

考试

时空限制：1000ms/512MB

统计单词数（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;
}

数的读法（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;
}

算术杀手（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 【模板】最小生成树

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

$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 来审核鸭~

评论列表

暂无评论