acwing

算法 > sjtu机试算法模拟

发布时间 : 2022-07-02 02:41

字数:792 阅读 :

评论:

AcWing 3581. 单词识别
n!后面的0
AcWing 3484. 整除问题
AcWing 3874. 三元组的最小距离

AcWing 3581. 单词识别
n!后面的0
AcWing 3484. 整除问题
AcWing 3874. 三元组的最小距离

AcWing 3581. 单词识别

统计每个单词的出现次数

把一个字母转换成小写字母：tolower(str[j ++ ])
判断某个字符是不是字母：isalpha(str[j])
遍历map：auto& [k, v]: hash

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
    string str;
    getline(cin, str);

    map<string, int> hash;
    for (int i = 0; i < str.size(); i ++ )
    {
        if (isalpha(str[i]))
        {
            int j = i;
            string word;
            while (j < str.size() && isalpha(str[j]))
                word += tolower(str[j ++ ]);
            hash[word] ++ ;
            i = j;
        }
    }

    for (auto& [k, v]: hash)
        cout << k << ':' << v << endl;

    return 0;
}

n!后面的0

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int res = 0;
    while (n / 5) res += n / 5, n /= 5;
    cout << res << endl;

    return 0;
}

AcWing 3484. 整除问题

给定 n，a 求最大的 k，使 n! 可以被 a^k 整除但不能被 a(k+1) 整除。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> get_ds(int n)//得到n的所有质因子及其次数
{
    vector<vector<int>> res;
    for (int i = 2; i * i <= n; i ++ )
        if (n % i == 0)
        {
            int s = 0;
            while (n % i == 0) n /= i, s ++ ;
            res.push_back({i, s});
        }

    if (n > 1) res.push_back({n, 1});
    return res;
}

int get_p(int n, int p)// n!里面有几个p相乘
{
    int res = 0;
    while (n / p) res += n / p, n /= p;
    return res;
}

int main()
{
    int n, m;
    cin >> n >> m;

    auto ds = get_ds(m);
    int res = 1e8;

    for (int i = 0; i < ds.size(); i ++ )
    {
        int p = ds[i][0], s = ds[i][1];
        res = min(res, (get_p(n, p) / s));
    }

    cout << res << endl;

    return 0;
}

重复者

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int n;
vector<string> p;

vector<string> g(int k)
{
    if (k == 1) return p;
    auto s = g(k - 1);
    int m = s.size();

    vector<string> res(n * m);
    for (int i = 0; i < n * m; i ++ )
        res[i] = string(n * m, ' ');

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (p[i][j] != ' ')
                for (int x = 0; x < m; x ++ )
                    for (int y = 0; y < m; y ++ )
                        res[i * m + x][j * m + y] = s[x][y];

    return res;
}

int main()
{
    while (cin >> n, n)
    {
        p.clear();
        getchar();  // 读掉n后的回车
        for (int i = 0; i < n; i ++ )
        {
            string line;
            getline(cin, line);
            p.push_back(line);
        }

        int k;
        cin >> k;
        auto res = g(k);
        for (auto& s: res) cout << s << endl;
    }

    return 0;
}

AcWing 3874. 三元组的最小距离

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int l, m, n;
int a[N], b[N], c[N];

int main()
{
    scanf("%d%d%d", &l, &m, &n);
    for (int i = 0; i < l; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
    for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]);

    LL res = 1e18;
    for (int i = 0, j = 0, k = 0; i < l && j < m && k < n;)
    {
        int x = a[i], y = b[j], z = c[k];
        res = min(res, (LL)max(max(x, y), z) - min(min(x, y), z));
        if (x <= y && x <= z) i ++ ;
        else if (y <= x && y <= z) j ++ ;
        else k ++ ;
    }

    printf("%lld\n", res * 2);
    return 0;
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com