讨论/技术交流/🐱 第 50 场夜喵双周赛/
🐱 第 50 场夜喵双周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 最少操作使数组递增
4 分 - 统计一个圆中点的数目
5 分 - 每个查询的最大异或值
6 分 - 使字符串有序的最少操作次数

2

又是完赛后五分钟调完最后一题,吐了……

#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;

class Solution
{
public:
    int a[26], inv[3050];

    void getinv()
    {
        inv[1] = 1;
        for (int i = 2; i <= 3040; ++i)
            inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
        for (int i = 2; i <= 3040; ++i)
            inv[i] = (1LL * inv[i] * inv[i - 1]) % mod;
    }

    int makeStringSorted(string s)
    {
        memset(a, 0, sizeof(a));
        int n = s.size();
        ll ans = 0;
        getinv();
        ll tt = 1;
        for (int i = n - 1; i >= 0; i--)
        {
            int x = s[i] - 'a';
            a[x]++;
            if (i == n - 1)
                continue;
            tt = (tt * (n - 1 - i)) % mod;

            for (int j = 0; j < x; j++)
            {
                if (a[j] == 0)
                    continue;
                ll t = tt;
                for (int k = 0; k < 26; k++)
                {
                    if (a[k] == 0)
                        continue;
                    if (k != j)
                        t = (t * inv[a[k]]) % mod;
                    else if (a[k] != 1)
                        t = (t * inv[a[k] - 1]) % mod;
                }
                ans = (ans + t) % mod;
            }
        }
        return ans;
    }
};
展开全部 57 讨论