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