Codeforces Round #634(Div.3) 解题报告

发布于 2020-04-14  118 次阅读


A - Candies and Two Sisters
水题，直接输出 $\frac{n-1}{2}$ 就行。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
void solve()
{
    int n;
    cin >> n;
    printf(
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

B - Construct the String
这个题构造方法很多，其中比较简单的一种就是先 abcd...... 这样构造，最后再一直放最后一个字母，即如 abcdddddddd 这种，构造出长度为 a 的串后再循环构造就行，即如 abcddddddabcddddddabcdddd......

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
using namespace std;
const int N = 2050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
int n, a, b;
char s[N];
void solve()
{
    scanf(
    int k = 0;
    for (int i = 1, j = 1; i <= min(a, b); ++i, ++j)
    {
        s[++k] = j + 'a' - 1;
    }
    for (int i = k + 1; i <= min(a, n); ++i)
    {
        s[++k] = b + 'a' - 1;
    }
    for (int i = 1, j = 1; i <= n; ++i, ++j)
    {
        if (j == k + 1)
            j = 1;
        printf(
    }
    puts("");
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

C - Two Teams Composing
将每种数字出现的次数从大到小排序，然后从大到小枚举答案，讨论两种情况：$ans=\max(ans,\min(cnt_i,m-1))$（m 表示数字种数），即选择这一种数字划分到一个集合，剩下的每一种数字取一个丢到另外一个集合；第二种情况是当 $cnt_i>1$ 并且 $cnt_i-1\ge m$ 的时候，$ans=\max(ans,m)$，表示将这一种数字的一部分划分到一个集合，剩下 $m$ 种数字每一种取一个丢到另外一个集合。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
using namespace std;
const int N = 200050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
int n, m, sum;
int cnt[N];
void solve()
{
    scanf(
    mem(cnt, 0, n, int);
    sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        scanf(
        cnt[x]++;
    }
    sort(cnt + 1, cnt + n + 1, greater<int>());
    for (int i = 1; i <= n; ++i)
    {
        if (cnt[i + 1] == 0)
        {
            m = i;
            break;
        }
    }
    sort(cnt + 1, cnt + m + 1);
    int ans = 0;
    for (int i = m; i >= 1; --i)
    {
        ans = max(ans, min(m - 1, cnt[i]));
        if (cnt[i] > 1 && cnt[i] - 1 >= m)
            ans = max(ans, m);
    }
    printf(
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

D - Anti-Sudoku
大水题......只需要将某一种数字全部改成另外一种即可。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
char s[15][15];
void solve()
{
    for (int i = 1; i <= 9;++i)
        scanf(
    for (int i = 1; i <= 9;++i)
    {
        for (int j = 1; j <= 9;++j)
            if(s[i][j]=='1')
                s[i][j] = '2';
    }
    for (int i = 1; i <= 9;++i)
    {
        printf(
    }
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

E1 - Three Blocks Palindrome (easy version)
E2 - Three Blocks Palindrome (hard version)
直接说 E2 吧~
因为要求左右部分数字相同长度也相同，然后每个数大小都只有 $200$，所以可以考虑枚举左右部分的数是什么，然后可以用双指针从两头往中间扫，中间部分也可以通过枚举数来看中间部分最长可以是多少。这个过程可以用 $200$ 个前缀和来优化。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
using namespace std;
const int N = 200050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
int n;
int sum[205][N];
int a[N];
int check(int l, int r)
{
    int mx = 0;
    for (int i = 1; i <= 200; ++i)
    {
        mx = max(mx, sum[i][r - 1] - sum[i][l]);
    }
    return mx;
}
void solve()
{
    scanf(
    for (int i = 1; i <= 200; ++i)
        for (int j = 0; j <= n + 5; ++j)
            sum[i][j] = 0;
    for (int i = 1; i <= n; ++i)
        scanf(
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= 200; ++j)
            sum[j][i] = sum[j][i - 1] + (a[i] == j);
    }
    int ans = 1;
    for (int i = 1; i <= 200; ++i)
    {
        int l = 1, r = n, now = 0;
        while (l < r)
        {
            while (a[l] != i && l <= n)
                l++;
            while (a[r] != i && r > 0)
                r--;
            if (l >= r)
                break;
            now += 2;
            ans = max(ans, now + check(l, r));
            l++, r--;
        }
    }
    cout << ans << '\n';
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}

F - Robots on a Grid
将这个图建出来可以发现这就是一个基环内向树，然后容易发现第一问答案就是所有基环内向树的环的大小之和，接下来对于每一棵基环内向树，我们在环上随便选一个点为根，然后建一个反图，处理每个点到它的距离（设为 $dep_u$），然后看所有 $dep_u\bmod len$（$len$ 表示这个环的大小）相同的点，将这些点打到一个集合内，看这个集合内是否有黑点，有的话第二问答案就 ++。
（昨晚怎么就没想到）

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
using namespace std;
const int N = 1000050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
int n, m;
int col[N];
char S[N];
int dfn[N], dfntot;
int dep[N];
bool vis[N];
int cnt[N];
inline int getid(int x, int y) { return (x - 1) * m + y; }
vector<int> e[N], g[N];
void dfs1(int u, int fa, int &len, int &root)
{
    if (len || root)
        return;
    dfn[u] = ++dfntot;
    for (auto v : e[u])
    {
        if (dfn[v])
        {
            len = dfn[u] - dfn[v] + 1;
            root = v;
            return;
        }
        if (v == fa)
            continue;
        dfs1(v, u, len, root);
    }
}
void dfs2(int u, int fa, int len, int root)
{
    vis[u] = 1;
    if (col[u] == 0)
        cnt[dep[u]] = 1;
    for (auto v : g[u])
    {
        if (v == fa || v == root)
            continue;
        dep[v] = (dep[u] + 1)
        dfs2(v, u, len, root);
    }
}
inline void Init()
{
    int sz = n * m;
    mem(vis, 0, sz, bool);
    mem(dfn, 0, sz, int);
    mem(dep, 0, sz, int);
    dfntot = 0;
    for (int i = 0; i <= n * m; ++i)
        e[i].clear(), g[i].clear();
}
void solve()
{
    scanf(
    Init();
    for (int i = 1; i <= n; ++i)
    {
        scanf(
        for (int j = 1; j <= m; ++j)
        {
            if (S[j] == '0')
                col[getid(i, j)] = 0;
            else
                col[getid(i, j)] = 1;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        scanf(
        for (int j = 1; j <= m; ++j)
        {
            if (S[j] == 'U')
            {
                e[getid(i, j)].push_back(getid(i - 1, j));
                g[getid(i - 1, j)].push_back(getid(i, j));
            }
            if (S[j] == 'D')
            {
                e[getid(i, j)].push_back(getid(i + 1, j));
                g[getid(i + 1, j)].push_back(getid(i, j));
            }
            if (S[j] == 'L')
            {
                e[getid(i, j)].push_back(getid(i, j - 1));
                g[getid(i, j - 1)].push_back(getid(i, j));
            }
            if (S[j] == 'R')
            {
                e[getid(i, j)].push_back(getid(i, j + 1));
                g[getid(i, j + 1)].push_back(getid(i, j));
            }
        }
    }
    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n * m; ++i)
    {
        if (!dfn[i] && !vis[i])
        {
            int len = 0, root = 0;
            dfs1(i, 0, len, root);
            ans1 += len;
            mem(cnt, 0, len, int);
            dfs2(root, 0, len, root);
            for (int i = 0; i < len; ++i)
                ans2 += cnt[i];
        }
    }
    printf(
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}