Educational Codeforces Round 113 (Rated for Div. 2)(部分题解)ABC

63 阅读 0 评论 42 点赞

我是靠谱客的博主陶醉白开水，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 113 (Rated for Div. 2)(部分题解)ABC，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A

点击此处查看对应的题目.
本题模拟
本题由于数据量很小，所以直接会根据题意模拟即可，用三循环找出a与b数量想同的区间。

时间复杂度 $O(n^3)$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int l,r;
bool st;

void solve()
{
    l = 0,r = 0;st = false;
    int n;
    cin >> n;
    string s;
    cin >> s;
    for(int i = 0;i < n - 1;i ++){
        for(int j = i + 1;j < n;j ++){
            int num_a = 0,num_b = 0;
            for(int k = i;k <= j;k ++){
                if(s[k] == 'a') num_a ++;
                else num_b ++;
            }
            if(num_a == num_b){
                    l = i,r = j;
                    st = true;
                    return;
            }
        }
    }
}
int main()
{
    int t;
    cin >> t;
    while(t -- ){
        solve();
        if(st) cout << l + 1 << " " << r + 1 << 'n';
        else puts("-1 -1");
    }
    return 0;
}

B

点击此处查看对应的题目.
本题模拟
通过题意我们可以知道，每个运动员比赛后有两种情况，一是保证所有比赛都不输，二是所有比赛至少赢一局。

在每一场比赛中，对于第一种情况，判定其为平局为最优解。而只要处于第二种情况的运动超过两个则可以进行依次输出“+”、“-”的，否则由于+，-不平衡无法得到最后的结果。

时间复杂度 $O (n)$

#include<bits/stdc++.h>
using namespace std;
const int N = 500;
char g[N][N];
int n;

void solve()
{
    string s;
    cin >> n >> s;

    vector<int> v;
    for(int i = 0;i < n;i ++)
        if(s[i] == '2')
            v.push_back(i);

    int b = v.size();
    if(b == 2 || b == 1) puts("NO");
    else{
        puts("YES");
        for(int i = 0;i < n;i ++)
            for(int j = 0;j < n;j ++)
                g[i][j] = '=';

        for(int i = 0;i < n;i ++) g[i][i] = 'X';
        for(int i = 0;i < b;i ++){
            int x = v[i],y = v[(i + 1) % b];
            g[x][y] = '+';
            g[y][x] = '-';
        }

        for(int i = 0;i < n;i ++,puts(""))
            for(int j = 0;j < n;j ++)
                cout << g[i][j];
    }
}
int main()
{
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
    return 0;
}

C

点击此处查看对应的题目.
本题涉及算法：组合数学
注意，如果至少有两个成员具有 $a_i$ 的最大值，那么任何排列都是好的。

现在我们考虑只有一个最大值的情况。我们来看看什么时候排列合适。设 $x$ 为任务数最多的评审团成员的索引。然后，在第一轮的讨论中，他们将是唯一一个告诉自己任务的人，因为评审团的其他成员已经告诉了他们所有的任务。因此，通过 $a_x−1)$ 讨论后，应该有一个陪审团成员在第 $x$ 个陪审团成员之后告诉任务。

设k为数组 $a = a x - 1$ 中的元素个数。然后，如果 $k$ 个陪审员中至少有一个在排列中追随陪审员 $x$ ，那么排列就很好。利用这个，我们将计算坏排列的数量。让我们确定排列中的元素不等于 $a_x$ 或 $a_{x}−1$ ，它们有 $n - k - 1$ ，那么方法的数量是 $A^{n−k−1}_{n}=frac{n!}{(k+1)}!$ 它仍然是放置 $k + 1$ 个元素，使最大值在它们的最后一个位置，有 $k!$ 这样的方式。

时间复杂度 $O (n)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10,mod = 998244353,INF = 1e9;
int a[N];

void solve()
{
    int n,maxn = -INF,cnt = 0,k = 0;
    cin >> n;
    for(int i = 0;i < n;i ++){
        cin >> a[i];
        maxn = max(maxn,a[i]);
    }
    for(int i = 0;i < n;i ++){
        if(a[i] == maxn) cnt ++;
        if(a[i] == maxn - 1) k ++;
    }
    int ans = 1,sub = 1;
    for(ll i = 1;i <= n;i ++) {
        ans = ans * i % mod;
        if(i != k + 1) sub = sub * i % mod;
    }
    if(cnt == 1) ans = (ans - sub + mod) % mod;
    cout << ans << 'n';
}
int main()
{
    int t;
    cin >> t;
    while(t -- ){
        solve();
    }
    return 0;
}