牛客周赛 Round 76 题解

A. 小红出题

签到

code:

#include <bits/stdc++.h>

using namespace std;

int n;

int main()
{
    cin >> n;
    
    int res = 0;
    for (int i = 1; i <= n; i++)
        if (i % 7 != 6 && i % 7) 
            res += 3;
    
    cout << res << endl;
    
    return 0;
}

B. 串串香

一个字符串中出现次数最多的子串长度一定是 \(1\)，因此只需要统计出现次数最多的字符即可。

code:

#include <bits/stdc++.h>

using namespace std;

int n;
string s;

int main()
{
    cin >> n >> s;
    
    map<char, int> p;
    for (int i = 0; i < n; i++) p[s[i]]++;
    
    char res;
    int cnt = 0;
    for (auto it: p)
        if (it.second > cnt)
            res = it.first, cnt = it.second;
    
    cout << res << endl;
    
    return 0;
}

C. 小红的gcd

对于数组中的每个元素，能够变成的最小数一定是把它和其它所有元素都取 \(gcd\)。

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 100010;

int n;
int a[N];

int gcd(int a, int b)
{
    return b? gcd(b, a % b) : a;
}

signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    int res = 0;
    for (int i = 0; i < n; i++) res = gcd(res, a[i]);
    
    cout << res * n << endl;
    
    return 0;
}

D. 奇偶调整

若要使数组元素之和最小，操作 \(1\)一定要优先作用于最大的偶数，而操作 \(2\)相当于使当前奇数元素减一变成偶数，因此主要作用是提供最大的偶数来进行操作 \(1\)。

• 对于操作 \(1\) 的次数，由于 \(10^9 < 2^{31}\)，因此把数组中的偶数全部操作成 \(1\) 的最大次数不超过 \(n * 31\)。
• 对于操作 \(2\) 的次数，若操作 \(1\) 的次数已经消耗完，则至多只能进行 \(n\) 次操作 \(2\)。

可以用优先队列来实现此操作。

时间复杂度 \(O(n*log)\)

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 100010;

int n, m, k;
int a[N];

signed main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) cin >> a[i];

    priority_queue<int> h1, h2;
    for (int i = 0; i < n; i++)
    {
        if (a[i] % 2 == 0) h1.push(a[i]);
        else h2.push(a[i]);
    }

    while (h2.size() && k || h1.size() && m)
    {
        if (h1.size() && m)
        {
            int t;
            if (h2.size() && k && h2.top() > h1.top())
            {
                t = h2.top() - 1;
                h2.pop();
                k--;
            }
            else 
            {
                t = h1.top();
                h1.pop();
            }
            if (t % 4) h2.push(t / 2);
            else if (t / 4) h1.push(t / 2);
            m--;
        }
        else if (h2.size() && k)
        {
            int t = h2.top() - 1;
            h2.pop();
            k--;
            if (t) h1.push(t);
        }
    }

    int res = 0;
    while (h1.size())
    {
        res += h1.top();
        h1.pop();
    }   

    while (h2.size())
    {
        res += h2.top();
        h2.pop();
    }

    cout << res << endl;

    return 0;
}

E. 幂次进近

二分答案。

使用两个二分来求出最大的满足 \(m1^k \leq n\) 的 \(m1\)，以及最小的满足 \(m2^k \geq n\) 的 \(m2\)，取算式绝对值最小的即可。

当 \(m \geq 2\) 时，\(k\) 最多不超过 \(62\) 就会大于 \(n\)，因此当 \(k\) 过于大时，不需要从 \(1\) 遍历到 \(k\)，及时弹出即可。 唯一需要注意的是要特判 \(m=1\) 的情况。

时间复杂度 \(O(tlogn)\)

code:

#include <bits/stdc++.h>

#define int __int128

using namespace std;

int T;
int n, k;
int res;

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;
}

void print(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

bool check1(int x)
{
    if (x == 1) return true;
    int sum = 1;
    for (int i = 1; i <= k; i++) 
    {
        sum *= x;
        if (sum > n) return false;
    }
    return true;
}

bool check2(int x)
{
    if (x == 1) return x >= n;
    int sum = 1;
    for (int i = 1; i <= k; i++)
    {
        sum *= x;
        if (sum >= n) return true;
    }
    return false;
}

signed main()
{
    T = read();
    while (T--)
    {
        n = read(), k = read();
        
        int l = 1, r = 1e18;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (!check1(mid)) r = mid - 1;
            else l = mid;
        }
        res = l;
        
        l = 1, r = 1e18;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (!check2(mid)) l = mid + 1;
            else r = mid;
        }
        
        int p1 = 1, p2 = 1;
        if (res > 1)
        {
            for (int i = 1; i <= k; i++) p1 *= res;
        }
        for (int i = 1; i <= k; i++)
        {
            p2 *= l;
            if (p2 - n > n - p1) break;
        }
        
        if (n - p1 > p2 - n) res = l;
        
        print(res);
        cout << endl;
    }

    return 0;
}

F. 同位序列

第一步需要求出数组中每个元素的 \(g(x)\)。

对于 \(g(x)\) 的求法，不难发现，如果从右往左找到第一个 \(01\)，把这个 \(1\) 往左移动一位，变成 \(10\)，这时无论右边怎么排列，最终结果一定大于 \(x\)，之后只需从右往左补足 \(1\) 使得 \(1\) 的总个数等于 \(f(x)\) 即可。 当 \(x\) 的二进制表示是 \(1011100\) 时，\(g(x)=110011\)。

由于 \(g(x) > x\)，因此可以对数组从小到大排序，使得 \(g(x)\) 一定在 \(x\) 右边。

接下来考虑 \(dp\)，设 \(f[i]\) 为以 \(a[i]\) 结尾，最长同位序列的长度，则状态转移方程为 \(f[p[g(i)]] = max(f[p[g(i)], f[i] + 1)\)，\(p[g(i)]\) 为 g(i) 对应的下标。

最终需要对最大的 \(f[i]\) 进行逆过程递推，因此可以在 \(dp\) 的过程中记录 \(f[i]\) 对应的上一个下标。

时间复杂度 \(O(nlogn)\)

code:

#include <bits/stdc++.h>

#define int long long
#define x first
#define y second

using namespace std;

const int N = 100010;

int n;
int a[N];
int g[N];
pair<int, int> f[N];

int calc(int x)
{
    int cnt = 0;
    for (int i = 0; i <= 31; i++)
    {
        if (!(x >> i & 1)) continue;
        x -= ((int)1 << i);
        if ((x >> i + 1) & 1) x += ((int)1 << cnt++);
        else
        {
            x += ((int)1 << i + 1);
            break;
        }
    }

    return x;
}

signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a, a + n);

    map<int, int> p;
    for (int i = 0; i < n; i++)
    {
        p[a[i]] = i;
        g[i] = calc(a[i]);
    }

    for (int i = 0; i < n; i++) f[i].y = -1;

    int res = 0, idx = 0;
    for (int i = 0; i < n; i++)
    {
        if (!p.count(g[i])) continue;
        int x = p[g[i]];
        if (f[x].x < f[i].x + 1) 
        {
            f[x] = {f[i].x + 1, i};
            if (res < f[x].x)
            {
                res = f[x].x;
                idx = x;
            }
        }
    }

    vector<int> s;
    while (~idx)
    {
        s.push_back(a[idx]);
        idx = f[idx].y;
    }

    cout << s.size() << endl;
    for (int i = s.size() - 1; i >= 0; i--) cout << s[i] << ' ';
    cout << endl;

    return 0;
}