牛客周赛 Round 66 题解

A. 小苯吃糖果

签到

code:

#include <bits/stdc++.h>

using namespace std;

int a[3];

int main()
{
    cin >> a[0] >> a[1] >> a[2];
    
    sort(a, a + 3);
    
    cout << max(a[0] + a[1], a[2]);
    
    return 0;
}

B. 小苯的排列构造

构造一个 \(n\) 到 \(1\) 的排列即可

code:

#include <bits/stdc++.h>

using namespace std;

int T;
int n;

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        
        for (int i = n; i >= 1; i--) cout << i << ' ';
        cout << endl;
    }
    
    return 0;
}

C. 小苯的最小整数

由于 \(n <= 1e10\), 因此最多进行 \(10\) 次操作 \(n\) 就会恢复原来的数值。

考虑暴力枚举操作次数。

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

int T;
int n;

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        
        int res = n;
        for (int i = 1; i <= 10; i++)
        {
            int c = 1, t = n;
            while (t >= 10) c *= 10, t /= 10;
            n = n % c * 10 + n / c;
            res = min(res, n);
        }
        
        cout << res << endl;
    }
    
    return 0;
}

D && E. 小苯的蓄水池

并查集，每次将区间所有节点都添加到 \(r\) 的集合中。

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 200010;

int n, m;
int a[N];
int p[N], s[N], c[N];

int find(int x)
{
    if (x != p[x]) return p[x] = find(p[x]);
    return x;
}

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

signed main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; i++) a[i] = read();

    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        c[i] = 1;
        s[i] = a[i];
    }

    while(m--)
    {
        int op;
        op = read();
        if (op == 1)
        {
            int l, r;
            l = read(), r = read();
            for (int i = find(l); i < find(r); i = find(i + 1))
            {
                c[find(r)] += c[i];
                s[find(r)] += s[i];
                p[find(i)] = find(r);
            }
        }
        else
        {
            int p;
            p = read();
            printf("%.8lf\n", (double)s[find(p)] / c[find(p)]);
        }
    }

    return 0;
}

F. 小苯的字符提前

不知道该怎么讲。

code:

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int T;
int n, k;
string s;
int c[26];
int res[N];

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k >> s;
        
        for (int i = 0; i < 26; i++) c[i] = 0;
        for (int i = 0; i < n; i++) c[s[i] - 'a']++;
        
        int h = 0;
        while (k > c[h]) k -= c[h++];
        
        vector<int> t;
        for (int i = 0; i < n; i++)
            if (s[i] - 'a' == h)
                t.push_back(i);
        
        int id = 0, l = 1, r = t.size();
        for (int i = 0; i < t.size(); i++)
        {
            if (t[i] == n - 1) continue;
            if (s[t[i] + 1] < s[t[i]]) 
            {
                while (id <= i) res[id++] = l++;
            }
            else if (s[t[i] + 1] > s[t[i]])
            {
                while (id <= i) res[id++] = r--;
            }
        }
        while (id < t.size()) res[id++] = l++;
        
        int head = 0;
        while (res[head] != k) head++;
        
        cout << s[t[head]];
        for (int i = 0; i < n; i++)
        {
            if (i == t[head]) continue;
            cout << s[i];
        }
        cout << endl;
    }

    return 0;
}

G. 小苯的数位MEX

数位 \(dp\)

#include <bits/stdc++.h>

#define int long long

using namespace std;

int T;
int x, k;
int f[10][1024];
vector<int> num;

int dp(int u, int op, int lead, int st, int m)
{
    if (u == -1)
    {
        int mex = 0;
        while (st >> mex & 1) mex++;
        return mex == m;
    }
    if (!op && !lead && ~f[u][st]) return f[u][st];

    int res = 0, maxv = op? num[u] : 9;
    for (int i = 0; i <= maxv; i++)
    {
        if (lead && i == 0) res += dp(u - 1, op && i == maxv, 1, st, m);
        else res += dp(u - 1, op && i == maxv, 0, st | (1 << i), m);
    }
    
    return op? res : f[u][st] = res;
}

int calc(int n, int m)
{
    num.clear();
    while (n)
    {
        num.push_back(n % 10);
        n /= 10;
    }

    memset(f, -1, sizeof f);

    return dp(num.size() - 1, 1, 1, 0, m);
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> x >> k;
        
        for (int i = 10; i >= 0; i--)
        {
            int res = calc(x + k, i) - calc(x - 1, i);
            if (res)
            {
                cout << i << ' ' << res << endl;
                break;
            }
        }
    }

    return 0;
}