A. Balanced Substring

题意
从给定的$ab$串中找到任意一个$a,b$数量相等的子串并输出。如果找不到输出$-1-1$.

分析

如果一个较大的子串符合要求，则其中必然出现"$ab$“或者”$ba$"，故只找这两种串即可。

另外$n\le 50$，随便你怎么暴力。

代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;

signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        bool flag = 0;
        for(int i = 0; i < s.size() - 1; ++i){
            if(s[i] != s[i + 1]){
                cout << i + 1 << ' ' << i + 2 << endl;
                flag = 1;
                break;
            }
        }
        if(!flag) cout << -1 << ' ' << -1 << endl;
    }
}

B. Chess Tournament

题意

有$n$个人两两比赛，他们分两种人，第一种人不能够有败绩，第二种人希望赢至少一局，存在平局。

问有没有可能构造出满足所有人的最终结果，如果有，输出任意一个结果。

分析

对于第一种人，他们不能有败绩，所以他们对局直接全部设为平局即可。

对于第二种人，他们要在内部赢其他人至少一次。对于第 $i$ 个人，可以贪心地选取当前剩余未比场次最多的人 $j$ 来让 $i$ 赢 $j$。也可以直接让所有第二种人构成一个环，环上箭头尾部赢，头部输，除环以外剩下的对局随便填满即可。总之$n\le 50$，随便怎么搞

代码（贪心）

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
// #define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
struct node
{
    int id, s, type;
}a[55];
char m[55][55];
bool vis[55][55];
signed main()
{
    // DDLC_ESCAPE_PLAN_FAILED;
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        mem(vis);
        fors(i, 1, n){
            a[i].id = i;
            scanf("%1d", &a[i].type);
            a[i].s = n; // 未比场数
        }
        vector<int> v;
        fors(i, 1, n){
            if(a[i].type == 2) v.pb(i);
            else{
                fors(j, 1, n){
                    if(i == j) continue;
                    m[i][j] = m[j][i] = '=';
                    vis[i][j] = vis[j][i] = 1;
                    a[j].s--, a[i].s--;
                }
            }
        }
        bool flag = 1;
        for(int i = 0; i < v.size(); ++i){
            int mx = 0, mxi;
            for(int j = 0; j < v.size(); ++j){
                if(i == j) continue;
                if(mx < a[v[j]].s && !vis[v[i]][v[j]]){
                    mx = a[v[j]].s;
                    mxi = v[j];
                }
            }
            if(mx == 0){
                flag = 0;
                break;
            }
            a[v[i]].s--, a[mxi].s--;
            m[v[i]][mxi] = '+', m[mxi][v[i]] = '-';
            vis[v[i]][mxi] = vis[mxi][v[i]] = 1;
        }
        fors(i, 1, n){
            fors(j, 1, n){
                if(!vis[i][j]){
                    m[i][j] = '+', m[j][i] = '-';
                    vis[i][j] = vis[j][i] = 1;
                }
            }
        }
        if(!flag) cout << "NO" << endl;
        else{
            cout << "YES" << endl;
            fors(i, 1, n){
                fors(j, 1, n){
                    if(i == j){
                        cout << 'X';
                        continue;
                    }
                    cout << m[i][j];
                }
                cout << endl;
            }
        }
    }
    return 0;
}

C. Jury Meeting

题意

有$n$个数，你需要把他们进行排列，排列完后，从左至右，每个数依次减去1。当一个数减为0后，它就会被跳过，不再减去。然后再从1开始，重复这个步骤，直到所有数都变成0。

你需要保证在这个过程中，不会有一个位置被连续减了两次，求满足条件的排列数。

分析

一个位置被连续减了两次当且仅当除了它以外全都是0.

剩下的这个被连续减去的肯定也只可能是最大值了。

显然可以知道：

1. 数列中所有数都相同时，全部排列都符合条件
2. 数列中最大值与次大值相差大于1，且最大值只有1个时，无论如何都不会满足条件
3. 数列中最大值出现次数超过1时，全部排列都符合条件（和情况1相似）

故我们只需要讨论的情况只剩下：数列中最大值与次大值相差1，且最大值只出现一次的情况。

要不使最大值被连续减去多次，当且仅当排列中最大值的后面存在次大值。

例如$3,3,4$最后会被减成$0,0,1$，再减一次$0,0,0$，第三个位置就被连续减了两次。但是$3,4,3$的话，最后减成$0,1,0$，最后减去第二个位置，但是第二个位置上一个减去的是第三个位置，不连续。

所以我们找到一种排列，最大值的后面有次大值即可。

为了稍微简化计算，不妨考虑其互斥情况：最大值后面没有次大值。

那么我们利用高中排列组合的“插空法”。假设$n$个数中，有$1$个最大值，$c2$个次大值。从$n$个位置中选择$c2+1$个位置，然后选出位置的最后一个放上最大值，其余位置用次大值进行全排列，剩下的$n-c2-1$个位置再用其余数全排列，得到$C_n^{c2+1}\cdot A_{c2}^{c2}\cdot A_{n-c2-1}^{n-c2-1}$，所以最终答案是
$$ans=A_n^n-C_n^{c2+1}\cdot A_{c2}^{c2}\cdot A_{n-c2-1}^{n-c2-1}$$
（当然，正向考虑并不比这个互斥情况复杂，直接$ans=C_n^{c2+1}\cdot C_{c2}^1\cdot A_{c2}^{c2}\cdot A_{n-c2-1}^{n-c2-1}$，昨晚有点多此一举）

具体实现上使用了Lucas定理，复杂度$O(nlogn)$，注意最后做减法的时候取模。

代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 10;
int pi[maxn];
const int mod = 998244353LL;
int qpow(int a, int b)
{
    int ans = 1;
    a %= mod;
    while(b)
    {
        if(b & 1){
            ans = ans * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}
int C(int n, int m)
{
    if(m > n) return 0;
    int ans = 1;
    fors(i, 1, m){
        int a = (n + i - m) % mod;
        int b = i % mod;
        ans = ans * (a * qpow(b, mod - 2) % mod) % mod;  
    }
    return ans % mod;
}
void prework()
{
    pi[0] = 1;
    pi[1] = 1;
    fors(i, 1, maxn - 1){
        pi[i] = (pi[i - 1] * i) % mod;
    }
}
int a[maxn];
signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    int t;
    cin >> t;
    prework();
    while(t--)
    {
        int n;
        cin >> n;
        fors(i, 1, n) cin >> a[i];
        int mx = 0;
        fors(i, 1, n) mx = max(mx, a[i]);
        int tmx = 0;
        fors(i, 1, n){
            if(a[i] > tmx && a[i] != mx) tmx = a[i];
        }
        int c1 = 0, c2 = 0;
        fors(i, 1, n){
            if(a[i] == mx) c1++;
            else if(a[i] == tmx) c2++;
        }
        if(c2 == 0 || c1 > 1){
            cout << pi[n] << endl;
        }
        else if(mx - tmx > 1){
            cout << 0 << endl;
        }
        else{
            int ans = C(n, c1 + c2);
            ans = (ans * pi[c1]) % mod;
            ans = (ans * pi[c2]) % mod;
            ans = (ans * pi[n - c1 -c2]) % mod;
            ans = pi[n] - ans;
            ans += 2 * mod;
            ans %= mod;
            cout << ans << endl;
        }
    }
    return 0;
}

D. Inconvenient Pairs

题意

在一个坐标从$(0,0)$到$(1e6,1e6)$的正方形框里，有$n$条横直线，$m$条纵直线。输入保证边界也是直线之一。现在有$k$个点分布在各个确定的直线上，只能通过已经画出的线移动，当一对点之间的最短路大于他们之间的曼哈顿距离时，这对点称为inconvenient，问有多少对inconvenient的点。

分析

当一个点在横线竖线的交点上时，它肯定不做贡献，到任意其他的点的最短路程都是曼哈顿距离。

但当两个点同在横线上但不是同一个横线上时，就有可能做贡献了。竖线同理。

如果两个点在横线上，且不在同一横线上，而且他们都被夹在相邻的两竖线之间，那么肯定就是inconvenient pair了，竖线同理。

我们需要算出，任意两相邻竖线之间有多少条在横线上的点，并排除掉在同一横线上的情况，然后计算答案。

具体就是用map存有哪些横（纵）边，然后对每个纵（横）边上的点用二分查找查出它在哪两个横（纵）边之间，答案先加上目前已统计的这两条横边之间的点的数目，再减去点所在纵边上原来有的点的数目。

代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 10;
int v[maxn], h[maxn];
signed main()
{
    DDLC_ESCAPE_PLAN_FAILED;
    int t;
    cin >> t;
    while(t--)
    {
        map<int, bool> verti, horiz;
        map<pair<int, int>, int> onY, onX;
        map<int, int> cntx, cnty;
        int n, m, k;
        cin >> n >> m >> k;
        fors(i ,1, n) cin >> v[i], verti[v[i]] = 0;
        fors(i, 1, m) cin >> h[i], horiz[h[i]] = 0;
        int x, y;
        int ans = 0;
        fors(i, 1, k){
            cin >> x >> y;
            if(verti.count(x) && horiz.count(y)) continue;
            else{
                int px = lower_bound(v + 1, v + 1 + n, x) - v;
                int py = lower_bound(h + 1, h + m + 1, y) - h;
                if(verti.count(x)){
                    ans += cnty[py] - onX[{py, x}];
                    cnty[py]++, onX[{py, x}]++;
                }
                else{
                    ans += cntx[px] - onY[{px, y}];
                    cntx[px]++, onY[{px, y}]++;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

最后

以上就是可靠御姐为你收集整理的Educational Codeforces Round 113 (Rated for Div. 2) 个人题解 ABCDA. Balanced SubstringB. Chess TournamentC. Jury MeetingD. Inconvenient Pairs的全部内容，希望文章能够帮你解决Educational Codeforces Round 113 (Rated for Div. 2) 个人题解 ABCDA. Balanced SubstringB. Chess TournamentC. Jury MeetingD. Inconvenient Pairs所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。