Codeforces Round #804 (Div. 2)

A. The Third Three Number Problem

Description

给出一个数 n 问你能否给出三个数 a,b,c 使得 $(a⊕b)+(b⊕c)+(a⊕c)=n (0≤a,b,c≤10^9)$

Solution

如果是奇数，那么没有答案，否则为 0,0,n/2

Code

不贴

B. Almost Ternary Matrix

Description

给出方格矩阵的长宽（限定为偶数），问能否给出一个黑白涂色，使得一个方格的上下左右正好有两个不同颜色的方格

Solution

构造题。可以第一行从左往右涂 黑白白黑黑…… 接下来两行为 白黑黑白白…… 以此类推

Code

不贴

C. The Third Problem

Description

给出一个从 $0\ -\ (n-1)$ 全排列 $a_1,a_2,…,a_n$ ，求满足下列条件的全排列的数量

$MEX([al,al+1,…,ar])=MEX([bl,bl+1,…,br])$

Solution

如果一个区间 $[L,R]$ 其 $MEX([al,al+1,…,ar])=x$ 则说明 $[0,x-1]$ 的数都在这个区间里出现过了。

所以我们需要从 0 到 n-1 枚举 i ，并且维护 $[0,i-1]$ 出现的数的最左和最右的端点 $(L,R)$

那么，如果枚举到的 $i$ 的位置 $pos[i]$ 落在了区间 $[L,R]$ 中，那么剩下的位置 $len-i , i$ 是可以随便放的 $(len=L-R+1)$

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
const ll N = 1e9 + 7;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    int t = read();
    while (t--) {
        ll n = read();
        ll ans = 1;
        vector<ll> a(n), pos(n);
        for (ll i = 0; i < n; i++) {
            a[i] = read();
            pos[a[i]] = i;
        }
        ll l = pos[0], r = pos[0];
        for (ll i = 1; i < n; i++) {
            if (pos[i] < l)
                l = pos[i];
            else if (pos[i] > r)
                r = pos[i];
            else
                ans = ans * (r - l + 1 - i) % N;
        }
        cout << ans << endl;
    }
    return 0;
}

Educational Codeforces Round 131 (Rated for Div. 2)

A. Grass Field

Description

给出 $2\times 2$ 的草地，上面某几个有草，每次选择一行或一列除草，最少除多少次。

Solution

分类讨论即可

Code

不贴

B. Permutation

Description

给出 $n$ 找出一个全排列和一个数 $d$ ，使得其中 $p_i⋅d=p_i+1$ 的个数最多

Solution

显然，$d=2$ 时最多，所以从小到大遍历，对于每个数往后推出所有满足条件的数。

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int t;
bool bo[200005];
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    t = read();
    while (t--) {
        int n = read();
        memset(bo, 0, sizeof(bo));
        puts("2");
        for (int i = 1; i <= n; i++) {
            if (!bo[i]) {
                int now = i;
                while (now <= n) {
                    cout << now << ' ';
                    bo[now] = 1;
                    now <<= 1;
                }
            }
        }
        puts("");
    }
    return 0;
}

C. Schedule Management

Description

有 $n$ 个工人和 $m$ 个任务，每个工人有擅长的任务，完成需要一个小时，否则需要两个小时，每个工人只能同时做一个任务，问最快多久能完成所有任务

Solution

二分答案 $t$，然后每个人优先完成精通的任务，剩下的时间做其他，判断能不能做完。

Code

#include <bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int t;
int n, m;
int p[200005];
bool check(int x)
{
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; i++) {
        if (p[i] < x) {
            cnt1 += (x - p[i]) / 2;
        } else
            cnt2 += (p[i] - x);
    }
    return cnt1 >= cnt2;
}
signed main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    // freopen("a.out", "r", stdin);
    t = read();
    while (t--) {
        n = read(), m = read();
        int l = 1, r = 0;
        vector<int> a(m + 1);
        memset(p, 0, sizeof(p));
        for (int i = 1; i <= m; i++) {
            a[i] = read();
            p[a[i]]++;
            r = max(r, p[a[i]]);
        }
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        cout << l << endl;
    }
    return 0;
}

Codeforces Round #805 (Div. 3)

A. Round Down the Price

Description

给出一个数 $n$，找出比它小的最大的 $10^x$，输出他们的差

Solution

模拟即可，注意数据范围

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int t;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    t = read();
    while (t--) {
        ll m = read(), now = 1;
        for (int i = 0;; i++) {
            if (m - now >= 0)
                now *= 10;
            else
                break;
        }
        cout << m - now / 10 << endl;
    }
    return 0;
}

B. Polycarp Writes a String from Memory

Description

给出一个字符串，每次只能记三个不同的字符，问最少需要几次才能记下整个字符串？

Solution

模拟跑一遍即可

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int t;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    t = read();
    while (t--) {
        string s;
        int cnt = 0;
        cin >> s;
        map<char, bool> mp;
        for (int i = 0; i < s.length(); i++) {
            if (mp.size() == 3) {
                while (mp.find(s[i]) != mp.end()) {
                    i++;
                }
                cnt++, mp.clear();
                if (i < s.length())
                    mp[s[i]] = 1;
                continue;
            }
            if (mp.find(s[i]) == mp.end()) {
                mp[s[i]] = 1;
            }
        }
        if (!mp.empty())
            cnt++;
        cout << cnt << endl;
    }
    return 0;
}

C. Train and Queries

Description

给出每个站点的值，问能否从一个值向右到达另一个值

Solution

从左到右遍历一次，建一个map存储每个值对应的车站位置，能够保证顺序递增，然后针对每个询问查找数组头尾即可

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int t;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    t = read();
    while (t--) {
        int n = read(), k = read();
        map<ll, vector<int>> mp;
        for (int i = 1; i <= n; i++) {
            int u = read();
            mp[u].push_back(i);
        }
        while (k--) {
            int a = read(), b = read();
            if (mp[a].size() == 0 || mp[b].size() == 0)
                puts("NO");
            else if (mp[a][0] > mp[b].back())
                puts("NO");
            else
                puts("YES");
        }
    }
    return 0;
}

D. Not a Cheap String

Description

给出字符串，字符串的权值为每个字母的权值和，字母的权值和为 c-'a'+1 ，给出一个限额，问删除最少的字符使得字符串权值小于等于限额

Solution

简单来讲就是按照权值从大到小删除字符，但实际实现有很多问题，最终我选择先纪录位置，输出时再判断。

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
int t;
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    t = read();
    while (t--) {
        string s;
        cin >> s;
        ll tot = 0;
        vector<pair<ll, ll>> q;
        for (int i = 0; i < s.length(); i++) {
            ll tmp = s[i] - 'a' + 1;
            q.push_back(make_pair(tmp, i));
            tot += tmp;
        }
        sort(q.begin(), q.end());
        ll p = read();
        vector<ll> sol;
        while (tot > p) {
            auto it = q.back();
            sol.push_back(it.y);
            tot -= 1ll * it.x;
            q.pop_back();
        }
        sort(sol.begin(), sol.end());

        int now = 0;
        for (int i = 0; i < s.length(); i++) {
            if (now < sol.size() && i == sol[now]) {
                now++;
                continue;
            } else
                cout << s[i];
        }
        puts("");
    }
    return 0;
}

E. Split Into Two Sets

Description

每张牌上面有两个数字，现在有n张牌（n为偶数），问能否将这n张牌分成两堆，使得每堆牌中的数字不重复；

Solution

因为需要每堆牌不重复，那牌中的数字必须满足：

• 每个数字出现的次数刚好为2
• 同一张牌上出现的数字不同

所以我们先预处理每个数字出现的位置，把两次位置记录下来，然后跑一边种类并查集，如果存在父亲相等的情况则无法满足。

关于种类并查集的知识可以看 Pecco 佬的算法学习笔记(7)：种类并查集

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
ll read()
{
    ll x = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') {
            w = -1;
        }
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + (ch - '0');
        ch = getchar();
    }
    return w * x;
}
const int N = 2e5 + 5;
int t;
vector<int> v[N];
int f[N << 1];
struct node {
    int a, b;
} p[N];
int getf(int x)
{
    return x == f[x] ? x : f[x] = getf(f[x]);
}
void link(int x, int y)
{
    int xf = getf(x), yf = getf(y);
    if (xf != yf)
        f[xf] = yf;
}
int main()
{
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    // std::cout.tie(0);
    t = read();
    while (t--) {
        int n = read();
        for (int i = 1; i <= n; i++) {
            v[i].clear();
        }
        for (int i = 1; i <= (n << 1); i++) {
            f[i] = i;
        }
        for (int i = 1; i <= n; i++) {
            int a = read(), b = read();
            v[a].pb(i);
            v[b].pb(i);
        }
        bool bo = 1;
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (v[i].size() == 2) {
                p[++cnt].a = v[i][0];
                p[cnt].b = v[i][1];
            } else
                bo = 0;
        }
        for (int i = 1; i <= cnt; i++) {
            if (getf(p[i].a) == getf(p[i].b)) {
                bo = 0;
                break;
            }
            link(p[i].a, p[i].b + n);
            link(p[i].b, p[i].a + n);
        }
        if (bo)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}