说明

此文章仅作者个人见解。原题链接https://ac.nowcoder.com/acm/contest/104637

A.小苯跑外卖

题目描述

小苯发现自己平均跑一单外卖可以赚 $x$ 元，于是，他给自己定下了目标：每天至少需要赚够 $y$ 元。他想知道，自己每天至少需要跑几单，才能达成他定下的目标。请你帮他算一算吧。

思路

语法题，向上取整即可。时间复杂O(1)。

代码

void solve()
{
   int x , y;
   cin >> x >> y;
   cout << (y % x == 0 ? y / x : (y / x) + 1) << endl;
}

B.小苯的区间删除

题目描述

小苯有一个由 n 个整数组成的数组 {a_1, a_2, ..., a_n}，他想要使得数组中的元素和最大。为此，小苯可以进行任意次以下操作（也可以不操作）：
选择一个长度不超过 k 的区间 [l, r] (1 ≤ l ≤ r ≤ n; r - l + 1 ≤ k)，将 a_l, a_{l+1}, ..., a_r 这段元素删除，并将其余元素按照原有顺序前后拼接起来。换句话说，操作后数组变为：
a_1, a_2, ..., a_{l-1}, a_{r+1}, ..., a_n。
小苯想知道，在可以进行任意次上述操作的前提下，数组中的元素和最大可以变为多少。特别地，空数组的总和视为 0。

思路

思维题，删除操作可有无数次，使得元素和最大。即保证所有的元素都为非负数即可。时间复杂度O(n)。

代码

void solve()
{
   int t;
   cin >> t;
   while (t -- )
   {
        int n , m;
        cin >> n >> m;
        vector<int> a(n + 1);
        for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];

        int ans = 0;
        for (int i = 1 ; i <= n ; i ++ ) if (a[i] > 0) ans += a[i];

        cout << ans << endl;
   }

}

C.小苯的数字消除

题目描述

小苯有一个长度为 n，仅由字符 ‘0’ 和 ‘1’ 构成的字符串 s。下标从 1 开始。
小苯认为 s 的长度过长，他希望用一些“消除”操作，将 s 的长度变得尽可能短。一次“消除”操作描述为：
如果存在这样的 i (1 ≤ i < |s|) 满足 s_i = s_{i+1}，那么小苯可以将 s_i, s_{i+1} 这两个字符消除，其余的字符按原有顺序拼接起来。换句话说，一次操作过后的字符串变为 s = "s_1 s_2 ... s_{i-1} s_{i+2} ... s_{|s|}"（其中，|s| 用于表示字符串 s 的长度）。
小苯为了最小化 s 的长度，因此在开始“消除”操作之前，他可以进行一些“修改”操作。一次“修改”操作描述为：
选择任意一个位置上的字符，将其改为 ‘0’ 或 ‘1’ 中的任意一种。
现在，小苯想知道，他至少需要先进行几次“修改”操作，才能使得存在这样一种“消除”操作的执行方案，使得 s 的长度不超过 1。请你帮他算一算吧。

思路

贪心。使用栈先进后出的特点，将前面的数字存入，遇到相同的数字则退栈，否则入栈。最后会得到类似01010101的串，则操作次数为arr.size() / 2。时间复杂度O(n)。

代码

void solve()
{
    int t;
    cin >> t;
    while (t -- ) 
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        s = " " + s;
        stack<char> stc;
        
        for (int i = 1 ; i <= n ; i ++ )
        {
            if (stc.size() && stc.top() == s[i])
                stc.pop();
            else stc.push(s[i]);
        }
        cout << stc.size() / 2 << endl;
    }
}

D.小苯的数字集合

题目描述

小苯有一个可重的数字集合 N，初始时，集合中恰好有两个正整数 x 和 y。
现在，小苯可以执行若干轮操作，每一轮操作他都会从 N 中选择一个数字 a 和另一个数字 b，并从下述四种中选择一种进行：
∙ 将 a 与 b 进行位与运算（and）的结果加入集合。
∙ 将 a 与 b 进行位或运算（or）的结果加入集合。
∙ 将 a 与 b 进行位异或运算（xor）的结果加入集合。
∙ 将 a 与 b 的最大公约数（gcd）加入集合。
小苯想知道，最少需要经过多少轮操作，才能使得自己的数字集合中出现数字 0，请你帮他算一算吧。
如果您需要更多位运算相关的知识，可以参考 OI-Wiki 的相关章节。相关链接：https://oi-wiki.org/math/bit/#%E4%B8%8E%E6%88%96%E5%BC%82%E6%88%96
最大公约数，指两个整数共有约数中最大的一个。例如，12 和 30 的公约数有 1, 2, 3, 6，其中最大的约数是 6，因此 gcd(12, 30) = 6。

思路

(bfs暴力)可以证明答案不会超过3。因为是可重集合，每次操作后都会加入集合当前操作后的元素，由 a ^ b ^ b = a 可知最少两次操作之后会出现相同的数字，而 a ^ a = 0。所以可知最多三次操作之后就可以得到0。时间复杂度O(n²)。

代码

void solve()
{
    int t;
    cin >> t;
    while (t -- )
    {
        int x , y;
        cin >> x >> y;
        queue<pair<pair<int , int> , int> > q;
        q.push({{x , y} , 0});
        vector<int> vec{x , y};
        while (q.size())
        {
            auto &[a , cnt] = q.front();
            q.pop();
            
            x = a.first , y = a.second;
            
            if (!(x ^ y) || !(x & y) || !(x | y))
            {
                cout << cnt + 1 << endl;
                break;
            }
            
            int g = gcd(x , y);
            int arr[4] = {x ^ y , x & y , x | y , g};
                
            for (auto i : vec)
                for (auto j : arr)
                    q.push({{i , j} , cnt + 1});
            for (auto i : arr)
                vec.push_back(i);
        }
    }
}