Codeforces Round #764 (Div. 3)

Codeforces Round #764 (Div. 3)

目录

A - Plus One on the SubsetB - Make APC - Division by Two and PermutationD - Palindromes ColoringE - Masha-forgetfulG - MinOr Tree

A - Plus One on the Subset

最大最小值之差

#include 
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N = 2e5 + 10;

int main() {
    ios::sync_with_stdio(0);
    int _; cin >> _; while (_--) {
        int n; cin >> n;
        vector a(n+1);
        int ma = 0, mi =1e9;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            ma = max(ma, a[i]);
            mi = min(mi, a[i]);
        }
        cout << ma - mi << endl;
    }
}

B - Make AP

要求a、b、c为等差数列，因为只改动一个数，因此固定两个数即可

#include 
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N = 2e5 + 10;

int main() {
    ios::sync_with_stdio(0);
    int _; cin >> _; while (_--) {
        ll a, b, c; cin >> a >> b >> c;
        ll d = b - a;
        if ((b + d) % c == 0 && (b+d > 0)) {
            cout << "YES" << endl;
            continue;
        }
        d = c - b;
        if ((b-d)%a==0 && (b-d > 0)) {
            cout << "YES" << endl;
            continue;
        }
        d = c - a;
        if (d % 2 != 0) {
            cout << "NO" << endl;
        } else {
            if ((c-d/2)%b==0 && (c-d/2 > 0)) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        }
    }
}

C - Division by Two and Permutation

数据范围很小，直接上二分图最大匹配

#include 
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N = 2e5 + 10;
vector g[55];
int vis[55];
int match[55];
bool dfs(int x) {
    for (auto v : g[x]) {
        if (!vis[v]) {
            vis[v] = 1;
            if (!match[v] || dfs(match[v])) {
                match[v] = x;
                return true;
            }
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(0);
    int _; cin >> _; while (_--) {
        int n; cin >> n;
        for (int i = 1; i <= n; i++) g[i].clear();
        vector a(n+1);
        memset(match, 0, sizeof match);
        memset(vis, 0, sizeof vis);
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) {
            int now = a[i];
            while (now) {
                if (now <= n) g[i].push_back(now);
                now /= 2;
            }
        }
        int num = 0;
        for (int i = 1; i <= n; i++) {
            memset(vis, 0, sizeof vis);
            if (dfs(i)) {
                num++;
            }
        }
//        cout << num << endl;
        if (num == n) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

D - Palindromes Coloring

主要思想就是先放两两相同的，因为求的是最小值，因此最后一层如果两两没铺满就先不放了，全部转化为1去放

#include 
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N = 2e5 + 10;

int main() {
    ios::sync_with_stdio(0);
    int _; cin >> _; while (_--) {
        int n, k; cin >> n >> k;
        string s; cin >> s;
        vector cnt(26);
        for (int i = 0; i < s.size(); i++) {
            cnt[s[i]-'a']++;
        }
        vector odd, even;
        int num = 0;
        int idx = 1;
        vector len(n+1);
        for (int i = 0; i < 26; i++) {
//            cout << cnt[i] << endl;
            while (cnt[i] > 1) {
                cnt[i] -= 2;
                len[idx] += 2;
                idx++;
                if (idx == k + 1) {
                    idx = 1;
                }
            }
        }
        int ans = 0, ma = 0;
        for (int i = 1; i <= k; i++) {
            ma = max(ma, len[i]);
        }
        for (int i = 1; i <= k; i++) {
            if (len[i] == ma) {
                ans++;
            }
        }
        if (ans != k) {
            for (int i = 1; i <= k; i++) {
                if (len[i] == ma) {
                    num += 2;
                    len[i] -= 2;
                }
            }
        }
        for (int i = 0; i < 26; i++) {
            if (cnt[i]) num++;
        }

        for (int i = 1; i <= k; i++) {
            if (num) {
                len[i]++;
                num--;
            }
        }
        int mi = 1e9;
        for (int i = 1; i <= k; i++) {
            mi = min(mi, len[i]);
        }
        cout << max(mi, 1) << endl;
    }
}

E - Masha-forgetful

很容易想到，将全部块分为长度2和3的，因为2和3可以组成大于1的所有自然数。接下来就用简单的dp存一下，最后路径返回记录一下答案就可以了。

#include 
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N = 1e5 + 10;

int main() {
    ios::sync_with_stdio(0);
    int _; cin >> _; while (_--) {
        int n, m; cin >> n >> m;
        map> mp;
        for (int i = 1; i <= n; i++) {
            string s; cin >> s;
            for (int j = 0; j < m; j++) {
                if (j + 2 <= m) mp.insert({s.substr(j, 2), {j + 1, j + 2, i}});
                if (j + 3 <= m) mp.insert({s.substr(j,3), {j+1, j+3, i}});
            }
        }
        vector dp(m+1);
        dp[0] = 1;
        string s; cin >> s; s = '#' + s;
        for (int i = 1; i <= m; i++) {
            if (i >= 2) {
                string tmp = s.substr(i - 1, 2);
                if (mp.count(tmp)) dp[i] |= dp[i-2];
            }
            if (i >= 3) {
                string tmp = s.substr(i-2, 3);
                if (mp.count(tmp)) dp[i] |= dp[i-3];
            }
        }
        if (!dp[m]) cout << -1 << endl;
        else {
            int now = m;
            vector> ve;
            while (now) {
                if (dp[now-2]) {
                    string tmp = s.substr(now-1, 2);
                    ve.push_back(mp[tmp]);
                    now -= 2;
                } else if (dp[now-3]) {
                    string tmp = s.substr(now-2, 3);
                    ve.push_back(mp[tmp]);
                    now -= 3;
                }
            }
            reverse(ve.begin(), ve.end());
            cout << ve.size() << endl;
            for (auto [l,r,i] : ve) {
                cout << l << ' ' << r << ' ' << i << endl;
            }
        }
    }

}

G - MinOr Tree

求或的最小生成树

最开始我们将30位全部置为1，代表全部的边都可取

不难想到通过位去计算，从高位到低位去置0，如果当前边权包含在当前状态里，这条边是可取的，我们只需要判断连通性就好了，复杂度是 O ( 30 ∗ m ∗ l o g n ) O(30*m*logn) O(30∗m∗logn)

#include 
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N = 2e5 + 10;
struct Edge {
    int u, v, w;
}e[N<<1];
int fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}

int main() {
    ios::sync_with_stdio(0);
    int _; cin >> _; while (_--) {
        int n, m; cin >> n >> m;
        for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
//        for (int i = 1; i <= n; i++) fa[i] = i;
        int now = (1 << 30) - 1;
        for (int i = 29; i >= 0; i--) {
            int tmp = now - (1 << i);
            for (int j = 1; j <= n; j++) fa[j] = j;
            for (int j = 1; j <= m; j++) {
                if ((e[j].w & tmp) == e[j].w) {
                    int u = find(e[j].u);
                    int v = find(e[j].v);
                    if (u != v) {
                        fa[u] = v;
                    }
                }
            }
            int flag = 0;
            for (int j = 2; j <= n; j++) {
                if (find(j) != find(1)) {
                    flag = 1;
                    break;
                }
            }
            if (!flag) now -= (1 << i);
        }
        cout << now << endl;
    }
}