10 月 5 日模拟赛总结

· · 个人记录

Before

本文章在博客园同步发布

Contest-Link

预期 100 + 100 + 5 + 0 = 205。

实际 0+100(0)+5+0=105(5)。（括号是重测前）

挂分 200。

rk21，直接垫底。菜死了

为什么会挂 200 呢？且听下文分解。

T1

Description

求 [l, r] 中 2 的幂。

输入一行两个整数 l 和 r。

输出第一行一个整数 \mathbf{cnt} 表示区间里 \mathbf{2} 的幂的个数，第二行输出这些数。

## Solution 直接开个标记数组标记不超过范围的 $2$ 次幂，这里可以直接用 `pow`，然后 $O(n)$ 扫一遍即可。 当然也可以 $O(\log n)$ 判是否在范围内就输出。 `Q:` 那你为什么保龄了？ `A:` 没有输出上文 `Description` 中加粗的输入中的 $\text{cnt}$。因为读题不仔细痛失 $\text{100pts}$。 考场想法：模拟。 考场寄因：如上。 时间复杂度 $O(n)$，空间复杂度 $O(n)$。 ## Code $\text{100pts:} 
// 2023/10/5 PikachuQAQ

#include <iostream>
#include <cmath>

using namespace std;

int l, r, b[3000000], cnt;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> l >> r;
    for (int i = 0; i <= 20; i++) {
        int x = pow(2, i);
        b[x] = 1;
    }
    for (int i = l; i <= r; i++) {
        cnt += b[i];
    }
    cout << cnt << '\n';
    for (int i = l; i <= r; i++) {
        if (b[i]) {
            cout << i << ' ';
        }
    }

    return 0;
}
\text{0pts:} 
// 2023/10/5 PikachuQAQ

#include <iostream>
#include <cmath>

using namespace std;

int l, r, b[3000000];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> l >> r;
    for (int i = 0; i <= 20; i++) {
        int x = pow(2, i);
        b[x] = 1;
    }
    for (int i = l; i <= r; i++) {
        if (b[i]) {
            cout << i << ' ';
        }
    }

    return 0;
}

T2

Description

给定 n 个字符串组成字典，然后进行 q 次查询，每次给出一个字符串问字典中是否存在与其编辑距离为 1 的串。

输入一行两个整数 n 和 q，接下来 n 行，n 个字符串表示字典，接下来 q 行，q 个字符串，每给出一个字符串表示一次询问。

输出 q 行，每行一个字符串，如果字典中有符合条件的字符串，输出这个字符串，如果有多个输出在字典中下标最小的那个。如果没有条件的字符串输出 No。

## Solution 开题 `20min` 首先写了个字典树，但发现~~字典树不会写了~~数据范围很小，所以可以直接暴力增删改，然后直接匹配即可。亦可以直接字典树，但比较麻烦。 `Q:` 那你为什么保龄了？ `A:` 没有输出上文 `Description` 中加粗的输出 `No`，我输出了 `NO`。因为读题不仔细又痛失 $\text{100pts}$。哈哈。 考场想法：暴力匹配。 考场寄因：如上。 时间复杂度 $O(qn^2\times len)$，带 $26$ 的常数，空间复杂度 $O(n)$。 ## Code $\text{100pts:} 
// 2023/10/5 PikachuQAQ

#include <iostream>

using namespace std;

const int kMaxN = 57, INF = 100;

int n, q;
string a[kMaxN], b;

string substr(string s, int l) {
    string res = "";
    for (int i = 0; i < s.length(); i++) {
        if (i ^ l) {
            res += s[i];
        } 
    }
    return res;
}

string insert(string s, int x, char c) {
    string res = "";
    int r = s.length() + (x == s.length());
    for (int i = 0; i < r; i++) {
        if (i ^ x) {
            res += s[i];
        } else {
            res += c;
            if (i < s.length()) {
                res += s[i];
            }
        }
    }
    return res;
}

int match(string a, string b) {
    if (a == b) {
        return 0;
    }
    string f = b;
    int ln = b.length();
    for (int i = 0; i <= ln; i++) {
        for (int j = 'a'; j <= 'z'; j++) {
            f = insert(f, i, j);
            if (f == a) {
                return 1;
            }
            f = b;
        }
    }
    for (int i = 0; i < ln; i++) {
        if (substr(f, i) == a) {
            return 1;
        }
    }
    for (int i = 0; i < ln; i++) {
        for (int j = 'a'; j <= 'z'; j++) {
            f[i] = j;
            if (f == a) {
                return 1;
            }
        }
        f = b;
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1, sol; i <= q; i++) {
        cin >> b;
        for (int j = 1; j <= n; j++) {
            if (match(a[j], b) != -1) {
                sol = 1;
                cout << a[j] << '\n';
                break;
            }
        }
        if (sol == 0) {
            cout << "No\n";
        }
        sol = 0;
    }

    return 0;
}
\text{0pts:} 
// 2023/10/5 PikachuQAQ

#include <iostream>

using namespace std;

const int kMaxN = 57, INF = 100;

int n, q;
string a[kMaxN], b;

string substr(string s, int l) {
    string res = "";
    for (int i = 0; i < s.length(); i++) {
        if (i ^ l) {
            res += s[i];
        } 
    }
    return res;
}

string insert(string s, int x, char c) {
    string res = "";
    int r = s.length() + (x == s.length());
    for (int i = 0; i < r; i++) {
        if (i ^ x) {
            res += s[i];
        } else {
            res += c;
            if (i < s.length()) {
                res += s[i];
            }
        }
    }
    return res;
}

int match(string a, string b) {
    if (a == b) {
        return 0;
    }
    string f = b;
    int ln = b.length();
    for (int i = 0; i <= ln; i++) {
        for (int j = 'a'; j <= 'z'; j++) {
            f = insert(f, i, j);
            if (f == a) {
                return 1;
            }
            f = b;
        }
    }
    for (int i = 0; i < ln; i++) {
        if (substr(f, i) == a) {
            return 1;
        }
    }
    for (int i = 0; i < ln; i++) {
        for (int j = 'a'; j <= 'z'; j++) {
            f[i] = j;
            if (f == a) {
                return 1;
            }
        }
        f = b;
    }
    return -1;
}

int main() {
    freopen("dict.in", "r", stdin);
    freopen("dict.out", "w", stdout);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1, sol; i <= q; i++) {
        cin >> b;
        for (int j = 1; j <= n; j++) {
            if (match(a[j], b) != -1) {
                sol = 1;
                cout << a[j] << '\n';
                break;
            }
        }
        if (sol == 0) {
            cout << "No\n";
        }
        sol = 0;
    }

    return 0;
}

T3

Description

Solution

Code

T4

Description

Solution

Code

Summary

需要掌握的：仔细读题。