昨天耍白痴
2000名变7000名
因为我写错一个地方
干你娘
今天还不错
不过一直出错
有够靠北
直接错8次+40分钟
不过还是2500名
爽
第一题
找两个相邻的子阵列
他们都是递增的
思路
暴力找
```cpp
class Solution {
public:
bool hasIncreasingSubarrays(vector<int>& nums, int k)
{
int n = nums.size();
if(k == 1 && n > 1)return 1;
int a = 0;
int b = 0;
for(int i = 0 ; i+2*k-1 < n ; i ++)
{
int ok = 1;
a = i;
b = a+k;
// cout << nums[a] << " " << nums[b] << endl;
for(int j = 0 ; j < k-1 ; j ++)
{
if(nums[a+j] >= nums[a+j+1])ok = 0;
if(nums[b+j] >= nums[b+j+1])ok = 0;
// cout << nums[a+j] << " " << nums[b+j] << endl;
}
if(ok)return 1;
}
return 0;
}
};
```
第二题
这次要在阵列里面找最长的
两个相邻递增阵列
的k值
思路
直到怎么找之后
直接用二分搜找k值
结果超时
把找的方法改一下
改成用prefix纪录递增的方式
就过了
```cpp
class Solution {
public:
vector<int> paper;
bool hi( int k)
{
int n = paper.size();
if(k == 1 && n > 1)return 1;
for(int i = 0 ; i+2*k-1 < n ; i ++)
{
int a = i + k-1;
int b = a + k;
if(paper[a] >= k && paper[b] >= k)return 1;
}
return 0;
}
int maxIncreasingSubarrays(vector<int>& nums)
{
int len = nums.size();
int l = 1 ;
int r = len/2;
paper.resize(len,1);
for(int i = 0 ; i < len-1 ; i ++)
{
if(nums[i] < nums[i+1])
{
paper[i+1] = paper[i] +1 ;
}
}
// for(int i = 0 ; i < len ; i ++)cout << paper[i] << " ";
while(l<=r)
{
int m = (l+r)/2;
if(hi(m))
{
l = m+1;
}
else
{
r = m-1;
}
}
return r;
}
};
```
第三题
要找所有subsequence
就是可以删子阵列的元素但不改变顺序
要让他们相邻元素相差小于1
然后把全部subsequence里的元素加起来
问你是多少
思路
因为要一直看之前出现的数字
只要看+1-1
所以很适合用map dp
然后是dp的思路
而且要用map记录这数字当结尾的值跟数量
每次更新都要去+1-1的地方拿值跟数量
全部加起来就好了
0.0
```cpp
class Solution {
public:
int sumOfGoodSubsequences(vector<int>& nums)
{
unordered_map<long long,pair<long long,long long>> paper;
int res = 0;
int n = nums.size();
for(int i = 0 ; i < n ; i ++)
{
res += nums[i];
res%=1000000007;
long long cur = 0 ;
if(paper.find(nums[i]-1)!=paper.end())
{
long long tmp = (long long)paper[nums[i]-1].first + (long long)n
ums[i]*(long long)paper[nums[i]-1].second;
paper[nums[i]].first += tmp;
cur += tmp;
cur %= 1000000007;
paper[nums[i]].second += paper[nums[i]-1].second;
paper[nums[i]].first%= 1000000007;
paper[nums[i]].second%= 1000000007;
// cout << "!";
}
if(paper.find(nums[i]+1)!=paper.end())
{
long long tmp = (long long)paper[nums[i]+1].first + (long long)n
ums[i]*(long long)paper[nums[i]+1].second;
paper[nums[i]].first += tmp;
cur += tmp;
cur %= 1000000007;
paper[nums[i]].second += paper[nums[i]+1].second;
paper[nums[i]].first%= 1000000007;
paper[nums[i]].second%= 1000000007;
// cout << "?";
}
res += cur;
res%= 1000000007;
paper[nums[i]].first += nums[i];
paper[nums[i]].first%= 1000000007;
paper[nums[i]].second += 1;
// for(auto k : paper)
// {
// cout << k.first << " " << k.second.first << " " << k.second.s
econd ;
// cout << endl;
// }
// cout << res << endl;
}
// for(auto k : paper)
// {
// cout << k.first << " " << k.second ;
// cout << endl;
// }
return res;
}
};
```