头像

yuanwen

ENWOM




离线:3天前



yuanwen
1个月前
#include <iostream>

using namespace std;

const int N = 20010;

int h[N], P, n, m;

bool check(int x) {
    if (x == 1) return false;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return false;
    return true;
}

int find(int x) {
    for (int i = 0; i < P; i++) {
        int id = (x + i * i) % P;
        if (!h[id] || h[id] == x) return i + 1;
    }
    return P + 1;
}

bool insert(int x) {
    for (int i = 0; i < P; i++) {
        int id = (x + i * i) % P;
        if (!h[id]) {
            h[id] = x;
            return true;
        }
    }
    return false;
}

int main() {
    cin >> P >> n >> m;
    for (int i = P; ; i++) {
        if (check(i)) {
            P = i;
            break;
        }
    }
    while (n--) {
        int x;
        cin >> x;
        if (!insert(x)) printf("%d cannot be inserted.\n", x);
    }
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        cnt += find(x);
    }
    double res = (double) cnt / m;
    printf("%.1lf\n", res);
    return 0;
}


活动打卡代码 AcWing 1630. 期终成绩

yuanwen
1个月前
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 10010;

int cnt;

unordered_map<string, int> fp;

struct Student {
    string id;
    int tot, mid, final, grade;

    bool operator<(const Student &o) const {
        if (grade == o.grade) return id < o.id;
        return grade > o.grade;
    }

    void update() {
        if (mid > final) grade = round((double) mid * 0.4 + (double) final * 0.6);
        else grade = final;
    }
    void print() {
        update();
        if (grade >= 60)
            cout << id << ' ' << tot << ' ' << mid << ' ' << final << ' ' << grade << endl;
    }
} stu[N];

int main() {
    int p, m, n;
    cin >> p >> m >> n;
    while (p--) {
        string id;
        int tot;
        cin >> id >> tot;
        if (tot >= 200) {
            if (!fp.count(id)) fp[id] = cnt++;
            stu[fp[id]] = {id, tot, -1, -1, -1};
        }
    }
    while (m--) {
        string id;
        int mid;
        cin >> id >> mid;
        if (fp.count(id)) {
            stu[fp[id]].mid = mid;
        }
    }
    while (n--) {
        string id;
        int final;
        cin >> id >> final;
        if (fp.count(id)) {
            stu[fp[id]].final = final;
        }
    }
    for (int i = 0; i < cnt; i++)
        stu[i].update();
    sort(stu, stu + cnt);
    for (int i = 0; i < cnt; i++)  
        stu[i].print();
    return 0;
}


活动打卡代码 AcWing 1564. 哈希

yuanwen
1个月前
#include <iostream>

using namespace std;

const int N = 20010;

int h[N], n, P;

bool check(int x) {
    if (x < 2) return true;
    for (int i = 2; i <= x / i; i++)
        if (x % i == 0) return true;
    return false;
}

string insert(int x) {
    for (int i = 0; i < P; i++) {
        int id = (x + i * i) % P;
        if (!h[id]) {
            h[id] = 1;
            return to_string(id);
        } 
    }
    return "-";
}

int main() {
    cin >> P >> n;
    if (check(P)) {
        for (int i = P + 1; ; i++)
            if (!check(i)) {
                P = i;
                break;
            }
    }
    bool first = false;
    for (int i = 0; i < n; i++) {
        if (!first) first = true;
        else cout << ' ';
        int x;
        cin >> x;
        cout << insert(x);
    }
    cout << endl;
    return 0;
}


活动打卡代码 AcWing 1642. 危险品装箱

yuanwen
1个月前
#include <iostream>
#include <unordered_set>
#include <unordered_map>

using namespace std;

unordered_map<string, unordered_set<string>> goods;
unordered_set<string> list;

int main() {
    int n, m;
    cin >> n >> m;
    while (n--) {
        string a, b;
        cin >> a >> b;
        goods[a].insert(b);
        goods[b].insert(a);
    }
    for (int i = 0; i < m; i++) {
        int k;
        cin >> k;
        list.clear();
        while (k--) {
            string s;
            cin >> s;
            list.insert(s);
        }
        bool success = true;
        for (auto i : list) {
            for (auto j : goods[i]) {
                if (list.count(j)) {
                    success = false;
                    break;
            }
        }
        if (success) puts("Yes");
        else puts("No");
    } 
    return 0;
}


活动打卡代码 AcWing 1637. 漏掉的数字

yuanwen
1个月前
#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

int main() {
    unordered_set<int> a;
    int n;
    cin >> n;
    for (int i = 0, x; i < n; i++) {
        scanf("%d", &x);
        a.insert(x);
    }
    for (int i = 1; ; i++) {
        if (!a.count(i)) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}


活动打卡代码 AcWing 1610. 朋友数

yuanwen
1个月前
#include <iostream>
#include <set>

using namespace std;

set<int> S;

int get(int x) {
    int sum = 0;
    while (x) {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0, x; i < n; i++) {
        cin >> x;
        S.insert(get(x));
    }
    cout << S.size() << endl;
    bool flag = true;
    for (int i : S) {
        if (flag) flag = false;
        else cout << ' ';
        cout << i;
    }
    cout << endl;
    return 0;
}


活动打卡代码 AcWing 1549. 集合相似度

yuanwen
1个月前
#include <iostream>
#include <unordered_set>

using namespace std;

const int N = 10010;

unordered_set<int> s[55];

void calc(int a, int b) {
    int sum = s[a].size() + s[b].size(), cnt = 0;
    for (int i : s[a])
        if (s[b].count(i)) cnt++;
    double res = (double) cnt / (sum - cnt) * 100;
    printf("%.1lf\%\n", res);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int m, x;
        cin >> m;
        while (m--) {
            scanf("%d", &x);
            s[i].insert(x);
        }
    }
    int k;
    cin >> k;
    while (k--) {
        int a, b;
        cin >> a >> b;
        calc(a, b);
    }
    return 0;
}


活动打卡代码 AcWing 1532. 找硬币

yuanwen
1个月前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N], n, m;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    sort(a, a + n);
    int l = 0, r = n - 1;
    while (l < r) {
        int t = a[l] + a[r];
        if (t < m) l++;
        else if (t > m) r--;
        else {
            cout << a[l] << ' '  << a[r] << endl;
            return 0;
        }
    }
    puts("No Solution");
    return 0;
}


活动打卡代码 AcWing 1591. 快速排序

yuanwen
1个月前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

int a[N], n;

bool st[N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    for (int i = 0, t = 0; i < n; i++) {
        if (a[i] < t) st[i] = true;
        t = max(t, a[i]);
    }
    for (int i = n - 1, t = 1e9 + 5; i >= 0; i--) {
        if (a[i] > t) st[i] = true;
        t = min(t, a[i]);
    }
    vector<int> res;
    for (int i = 0; i < n; i++) 
        if (!st[i]) res.push_back(a[i]);
    cout << res.size() << endl;
    if (res.size()) {
        sort(res.begin(), res.end());
        cout << res[0];
        for (int i = 1; i < res.size(); i++)
            cout << ' ' << res[i];
        cout << endl;
    } else cout << endl;
    return 0;
}


活动打卡代码 AcWing 1583. PAT 计数

yuanwen
1个月前
#include <iostream>
#include <cstring>

using namespace std;

const int P = 1000000007, N = 1000010;

char s[N], t[] = " PAT";

int f[N][5];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) 
        for (int j = 0; j <= 3; j++) {
            f[i][j] = f[i - 1][j];
            if (s[i] == t[j]) f[i][j] = (f[i][j] + f[i - 1][j - 1]) % P;
        }
    cout << f[n][3] << endl;
    return 0;
}