2024牛客多校第九场

牛客第九场反思

K. kill The Monsters

题意概述

有 $n$ 个怪兽,每个怪兽血量为 $a_i$
有两种操作：
- 使得所以的怪兽的血量减少1
- 使得某一个怪兽得血量变成 $[\frac{a_i}{k}]$
- $k$ 是给定的
问最少操作次数

思路

最主要的问题就是到底使用哪一种操作
可以这样想：让某一头怪兽成为基准，大于这个基准的进行操作二变得小于等于这个基准，然后结果就是次数 $cnt$ 加上基准的血量。这样尽可能的让每一次操作贡献最大
那么让哪一个成为基准呢？肯定是让结果最小的那个成为基准
首先肯定能求出来一个最大次数，这个是我们能够接受的上限
可以尝试让每一个成为基准看哪一个会使得结果最小
很难算好像，但是如果基准在最前面就好了
我们可以将所有的数存到一个优先队列里面
从最大的开始，那么结果就是它的血量
然后让最大的数 $maxn$ 去除以 $k$ , 如果它比老二小，老二就成为了老大，可以变成了新的基准
如果老大还是老大，重复上面的步骤
这样每个数成为基准时，大于它的数小于等于它的次数就算出来了

代码

#include <bits/stdc++.h>
//#define int long long
#define pair std::pair<int,int>
#define endl '\n'
using lli = long long;
using ull = unsigned long long;

int nums[100010] = {0};
std::priority_queue<pair> que;
void solve()
{
    int n = 0, k = 0;
    std::cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        std::cin >> nums[i];
        que.emplace(nums[i], i);
    }
    if (k == 1)
    {
        std::cout << que.top().first << endl;
        return;
    }
    int maxn = que.top().first;
    int tmp = 0;
    while(maxn)
    {
        maxn /= k;
        tmp++;
    }
    int cntmaxn = n * tmp;
    int cnt = 0, ans = cntmaxn;
    while(cnt <= cntmaxn && !que.empty())
    {
        pair t = que.top();
        que.pop();
        int tmpres = std::max(t.first / k, que.top().first) + (++cnt);
        ans = std::min(tmpres, ans);
        que.emplace(t.first / k, t.second);
    }
    std::cout << ans << endl;
    
}

signed main()
{
    solve();
    return 0;
}

I. Interesting Numbers

题意概述

给定一个数 $n (1 <= n <= 60，且n是偶数)$
给一个范围 $L, R（保证L,R都是n位的数$
求在这个范围中的数中，左右两半都是完全平方数的数有几个

思路

左右两边看成独立的两个部分
统计这个部分到9999999...这个数能有几个完全平方数，最后相乘就是一个数能产生的个数
L，R都这样算
答案就是用L产生的个数减去R产生的个数

代码

#include <bits/stdc++.h>
typedef __int128 i128;
using lli = long long int;
inline void read(i128 &n, std::string s)
{
    int sz = s.size();
    for (int i = 0; i < sz; i++)
    {
        n = n * 10 + s[i] - '0';
    }
}

inline void print(i128 n)
{
    if (n > 9)
    {
        print(n / 10);
    }
    putchar(n % 10 + '0');
}

i128 st = 1, up = 0;
i128 leftfind(i128 x) // 找的的mid mid * mid <= x
{
    i128 l = 0, r = 1e15;
    i128 mid = 0;
    while(l + 1 < r)
    {
        mid = (l + r) / 2;
        if (mid * mid <= x)
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    return l;
}

i128 rightfind(i128 x) // 找的的mid mid * mid >= x
{
    i128 l = 0, r = 1e15;
    i128 mid = 0;
    while(l + 1 < r)
    {
        mid = (l + r) / 2;
        if (mid * mid < x)
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    return r;
}

i128 process(std::string s, std::string t)
{
    i128 nums = 0, numt = 0;
    read(nums, s); read(numt, t);
    i128 x = rightfind(nums), y = rightfind(numt);
    if (x * x > nums) return (up - x + 1) * (up + 1);
    return (up - x) * (up + 1) + (up - y + 1);
}

signed main()
{
    int n = 0;
    std::cin >> n;
    for (int i = 1; i <= n / 2; i++)
    {
        st *= 10;
        //print(st);
        //std::cout << '\n';
    }
    st -= 1;
    // print(st);
    // std::cout << '\n';
    up = leftfind(st);
    // print(up);
    // std::cout << '\n';
    std::string l, r;
    std::cin >> l >> r;
    std::string l1 = l.substr(0, n / 2), l2 = l.substr(n / 2, n / 2);
    std::string r1 = r.substr(0, n / 2), r2 = r.substr(n / 2, n / 2);
    // i128 num = 0;
    // read(num, l1);
    // lli x = rightfind(num);
    // std::cout << x;
    i128 cnt1 = process(l1, l2);
    i128 cnt2 = process(r1, r2);
    // print(cnt1);
    // std::cout << '\n';
    // print(cnt2);
    // std::cout << '\n';
    i128 res = cnt1 - cnt2;
    if (n == 2 && r == "99") res++;
    print(res);
    return 0;
}