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