【补题】 1

蓝桥杯小白赛 

​​​​​​​3.小蓝的金牌梦【算法赛】 - 蓝桥云课 (lanqiao.cn)

数组长度为质数，最大的子数组和

素数 + 前缀和

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define N 100010
int ans[N];int s[N];vector<int> prime;
bool is_prime[N];void Era(int n) {is_prime[0] = is_prime[1] = true;for (int i = 2; i <= n; ++i) {if (!is_prime[i]) {prime.push_back(i);if ((int)i * i > n) continue;for (int j = i * i; j <= n; j += i) is_prime[j] = true;}}
}
void Eratosthenes(int n) {is_prime[0] = is_prime[1] = false;for (int i = 2; i <= n; ++i) is_prime[i] = true;for (int i = 2; i <= n; ++i) {if (is_prime[i]) {prime.push_back(i);if ((long long)i * i > n) continue;for (int j = i * i; j <= n; j += i)// 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i// 的倍数开始，提高了运行速度is_prime[j] = false;  // 是 i 的倍数的均不是素数}}
}
signed main() {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int maxn = -1e18;;int n, t;cin >> n;for (int i = 1; i <= n; ++i) {cin >> t;s[i] = s[i-1] + t;}Era(n);for (int i = 0; i < prime.size(); ++i) {for (int j = prime[i]; j <= n; ++j) {maxn = max(maxn, s[j]-s[j-prime[i]]);}}// for (auto x:prime) {//   cout << x << ' ';// }cout << maxn << endl;return 0;
}

4.合并石子加强版【算法赛】 - 蓝桥云课 (lanqiao.cn)

数学

a*b + (a+b)*c == a*b + a* c + b*c == b*c + (b+c)*a

#include "bits/stdc++.h"
using namespace std;
#define int unsigned long long
signed main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n, t, sum=0, free=0;cin>>n;// cin >> sum;for(int i=0;i<n;++i){cin >> t;free += t*sum;sum += t;// free += ;}cout << free << endl;return 0;
}

力扣双周赛

100130. 找到两个数组中的公共元素 - 力扣（LeetCode）

看错题意

class Solution {
public:vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> set1(nums1.begin(), nums1.end());unordered_set<int> set2(nums2.begin(), nums2.end());vector<int> ans(2);for (int x: nums1) ans[0] += set2.count(x);for (int x: nums2) ans[1] += set1.count(x);return ans;}
};

 总结

set1(nums1.begin(), nums2.end())  容器可以直接根据另一个容器初始化

set.count(x)         如果找到数值为x的元素，返回1；找不到，返回0

100152. 消除相邻近似相等字符 - 力扣（LeetCode）

 看成首位也需要判断(环)

贪心，贪第二个

class Solution {
public:int removeAlmostEqualCharacters(string word) {int cnt = 0;for (int i = 0; i < word.size() - 1; ++i){if (abs((word[i]-word[i+1])) <= 1) {// word[i+1] = 'A';++i;++cnt;}}return cnt;}
};

2958. 最多 K 个重复元素的最长子数组 - 力扣（LeetCode）

暴力超时

子数组：1 哈希表 2 滑动窗口

class Solution {
public:int maxSubarrayLength(vector<int>& nums, int k) {int ans = 0, left = 0;unordered_map<int, int> cnt;for (int right = 0; right < nums.size(); ++right) {++cnt[nums[right]];while (cnt[nums[right]] > k) {--cnt[nums[left++]];}ans = max(ans, right - left + 1);}return ans;}
};

本周计划：

盛最多水的容器 接雨水_哔哩哔哩_bilibili

同向双指针 滑动窗口【基础算法精讲 03】_哔哩哔哩_bilibili

2958. 最多 K 个重复元素的最长子数组 - 力扣（LeetCode） 

2560. 打家劫舍 IV - 力扣（LeetCode）