[数据结构与算法]Codeforces Round #790 (Div. 4)

A. Lucky?

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n, m, x, t;
int a[N];
int main()
{
    // freopen("1.in", "r", stdin);
    while (cin >> t) {
        while (t--) {
            string s;
            cin >> s;
            if (s[0] + s[1] + s[2] == s[3] + s[4] + s[5]) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    }
    return 0;
}

B. Equal Candies

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
typedef long long ll;
int n, m, x, t;
int a[N];
int main()
{
    // freopen("1.in", "r", stdin);
    while (cin >> t) {
        while (t--) {
            cin >> n;
            int minv = INT_MAX;
            ll s = 0;
            for (int i = 0; i < n; i++) {
                cin >> a[i];
                minv = min(minv, a[i]);
                s += a[i];
            }
            s -= n * minv;
            cout << s << endl;
        }
    }
    return 0;
}

C. Most Similar Words

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
typedef long long ll;
int n, m, x, t;
int a[N];
int deal(string& a, string& b) {
    int ans = 0;
    for (int j = 0; j < a.length(); j++) {
        ans += max(a[j], b[j]) - min(a[j], b[j]);
    }
    return ans;
}
int main()
{
    // freopen("1.in", "r", stdin);
    while (cin >> t) {
        while (t--) {
            cin >> n >> m;
            vector<string> strs(n);
            for (int i = 0; i < n; i++) {
                cin >> strs[i];
            }
            int ans = INT_MAX;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    ans = min(ans, deal(strs[i], strs[j])) ;
                }
            }
            cout << ans << endl;
            // cout << endl;
        }
    }
    return 0;
}

D. X-Sum

#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 5;
typedef long long ll;
int n, m, x, t;
int a[N][N];
int deal(int n, int m, int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) return 0;
    int v1 = deal(n, m, x + 1, y + 1);
    int v2 = deal(n, m, x - 1, y - 1);
    int v3 = deal(n, m, x + 1, y - 1);
    int v4 = deal(n, m, x - 1, y + 1);
    cout << v1 << " " << v2 << " " << v3 << " " << v4 << endl;
    return a[x][y] + v1 + v2 + v3 + v4;
}
int main()
{
    // freopen("1.in", "r", stdin);
    while (cin >> t) {
        while (t--) {
            cin >> n >> m;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    cin >> a[i][j];
                }
            }
            // cout << 1 << endl;
            int ans = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    int t = a[i][j];
                    for (int x = i + 1, y = j + 1; x < n && y < m; x++, y++) {
                        t += a[x][y];
                    }
                    for (int x = i - 1, y = j + 1; x >=0 && y < m; x--, y++) {
                        t += a[x][y];
                    }
                    for (int x = i + 1, y = j - 1; x < n && y >= 0; x++, y--) {
                        t += a[x][y];
                    }
                    for (int x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--) {
                        t += a[x][y];
                    }
                    ans = max(ans, t);
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}

E. Eating Queries

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
int n, m, x, t, q;
int main()
{
    // freopen("1.in", "r", stdin);
    while (cin >> t) {
        while (t--) {
            cin >> n >> q;
            vector<int> a(n);
            for (int i = 0; i < n; i++) {
                cin >> a[i];
            }
            sort(a.rbegin(), a.rend());
            for (int i = 1; i < n; i++) {
                a[i] += a[i - 1];
                // cout << a[i] << "\t";
            }
            // cout << endl
            for (int i = 0; i < q; i++) {
                cin >> x;
                auto idx = lower_bound(a.begin(), a.end(), x);
                if (idx == a.end()) {
                    cout << -1 << endl;
                } else {
                    cout << idx - a.begin() + 1<< endl;
                }
            }
        }
    }
    return 0;
}

F. Longest Strike

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
int n, m, x, t, q, k;
int main()
{
    // freopen("1.in", "r", stdin);
    while (cin >> t) {
        while (t--) {
            cin >> n >> k;
            map<int, int> mp;
            map<int, int> mp1;
            for (int i = 0; i < n; i++) {
                cin >> x;
                mp[x]++;
            }
            for (auto& kv: mp) {
                // cout << kv.first << " " << kv.second << endl;
                if (kv.second >= k) {
                    mp1[kv.first] = kv.second;
                }
            }
            // cout << endl;

            int l = -1, r = -1;
            int ans = -1, ansl = -1, ansr = -1;

            for (auto& kv: mp1) {
                // cout << kv.first << " " << kv.second << endl;
                if (l == -1 && r == -1) {
                    l = kv.first;
                    r = kv.first;
                } else {
                    if (kv.first != r + 1) {
                        if (r - l > ans) {
                            ans = r - l;
                            ansl = l;
                            ansr = r;
                        }
                        l = kv.first;
                        r = kv.first;
                    } else {
                        ++r;
                    }
                }
                // cout << "l:" << l << " r:" << r << endl;
            }
            if (r - l > ans) {
                ans = r - l;
                ansl = l;
                ansr = r;
            }
            // cout << endl;
            if (ansl == -1 && ansr == -1) {
                cout << -1 << endl;
            } else {
                cout << ansl << " " << ansr << endl;
            }
            // cout << endl;
        }
    }
    return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖