24年OPPO秋季笔试题

257. 小欧过河

链接：https://kamacoder.com/problempage.php?pid=1337

思路：这道题的实际需要求的就是在两个11之间，最多能有多少个0。可以记录在遍历序列的时候，记录有最多个0的1的两个下标，最后再返回其差值。要注意的是，两岸也算1，需要在数组里面也要加上。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int lstIndex = 0;
    int curIndex = 0;
    int res = 0;
    vector<int> nums(n + 2, 0);
    nums[0] = 1;
    nums[n + 1] = 1;
    for (int i = 1; i < n + 1; ++i)
    {
        cin >> nums[i];
    }
    for (int i = 0; i < n + 2; ++i)
    {
        if (nums[i] == 0)
        {
            continue;
        }
        else
        {
            lstIndex = curIndex;
            curIndex = i;
            res = max(res, curIndex - lstIndex);
        }
    }
    cout << res << endl;
    return 0;
}

258. 小欧的数组划分

链接：https://kamacoder.com/problempage.php?pid=1338

思路：这道题可以采用贪心算法，也就是遍历这个数组，然后每一位都进行或运算，直到不满足或运算之后的数字<k，就让答案加1，即分段；然后进行下一区间的或运算。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> nums(n, 0);
    for (int i = 0; i < n; ++i)
    {
        cin >> nums[i];
    }
    int res = 1;
    int sum = 0;
    for (int i = 0; i < n; ++i)
    {
        if (nums[i] > k)
        {
            cout << -1 << endl;
            return 0;
        }
        if (int(sum | nums[i]) < k)
        {
            sum = int(sum | nums[i]);
        }
        else
        {
            res++;
            sum = nums[i];
        }
    }
    cout << res << endl;
    return 0;
}

259.小欧的子序列数量

链接：https://kamacoder.com/problempage.php?pid=1339

思路：这里可以采用动态规划的思想。将dp数组的状态可以表示为第i个数字的前面所包含的[11/114/1145]串的数量。不难发现，如果当前下标的数字是1，且上一个数字是1，就可以把dp[11]的数字加1，反之，则不加。如果遇到了一个数字4，那么dp[114]可以更新为前面dp[11]的数量加上dp[114]已经有的数量。如果遇到了一个数字5则是同理。

#include <iostream>

long long mod=1e9;
using namespace std;

int main()
{
    int n;
    cin >> n;
    cin.ignore();
    string str;
    getline(cin, str);
    int dp[3]{};
    for (int i = 0; i < n; ++i)
    {
        if (str[i] == '1')
        {
            if (i && str[i - 1] == '1')
            {
                dp[0]++;
            }
        }
        else if (str[i] == '4')
        {
            dp[1] = (dp[1] + dp[0]) % (mod + 7);
        }
        else if (str[i] == '5')
        {
            dp[2] = (dp[2] + dp[1]) % (mod + 7);
        }
    }
    cout << dp[2] << endl;
    return 0;
}