subarrays专题

[ABC369C] Count Arithmetic Subarrays

首先看了下题意大致题意就是让你在长度为的序列找出所有的等差数列。 -----------------------------------------------------------------------------------------我是分界线我的思路了，就是先从2开始计算等差数列，从3开始判断，如果是等差数列的话就继续累加，如果不是判断它是否是第一个等差数列，是就直接，如果

Codeforces Round #323 (Div. 1) C. Superior Periodic Subarrays

每个i位置对于某个 s s，会支配所有xmodlen=imodlenx \mod len = i \mod len的位置，其中 x x是[l+j]∗s[l+j]*s。也就是说 xmodgcd(s,len)=imodgcd(s,len) x \mod gcd(s,len) = i \mod gcd(s,len)。举个例子 n=3,s=2，则a[1]≥a[1],a[2],a[3]:1

Codeforces 1631 B. Fun with Even Subarrays —— 贪心

This way 题意: 给你一个长度为n的数组a，你每次可以选择一个长度为2k的连续区间（k不定），将后k个数一一对应赋值给前k个数，问你最终要使得a中所有元素相等，需要至少多少次操作。题解：想错了…我以为是前赋值后或者后赋值前，这样情况就比较复杂了，暂时想到的方法是区间DP，还有一些奇奇怪怪的DP。但是2e5的范围不能接受，以后再想想怎么做，或许也会凭此出一道题目。既然是后赋值

codeforces582C. Superior Periodic Subarrays

传送门：http://codeforces.com/problemset/problem/582/C 思路：首先观察题目条件，对于一个数a[i]能出现在“Superior Periodic Subarrays” 首先它要满足对于任意k属于N，a[i]>=a[i+k*n] 并且对于任意k属于N，a[i]>=a[i+k*s] 那么就是任意k属于N，a[i]>=a[i+k*d](d=gcd

Leetcode 3101. Count Alternating Subarrays

Leetcode 3101. Count Alternating Subarrays 1. 解题思路2. 代码实现题目链接：3101. Count Alternating Subarrays 1. 解题思路这一题我们只需要用贪婪算法对原数组进行切分，使得每一段都是最大的交错子序列，然后，我们要获得所有交错子序列的个数，就只需要在每一段上进行 C n + 1 2 C_{n+1}^2 Cn+

Codeforces Round 841 (Div. 2) C. Even Subarrays

题目思路： #include <bits/stdc++.h>using namespace std;#define int long long#define pb push_back#define fi first#define se second#define lson p << 1#define rson p << 1 | 1const int maxn =

Leetcode 3036. Number of Subarrays That Match a Pattern II

Leetcode 3036. Number of Subarrays That Match a Pattern II 1. 解题思路2. 代码实现 3036. Number of Subarrays That Match a Pattern II 1. 解题思路这一题其实有点水，因为本质上还是一道套路题目，和前两周的两道题目一样，都是考察的z算法： Leetcode 3031. Mini

Educational Codeforces Round 145 (Rated for Div. 2)C. Sum on Subarrays（构造）

很意思的一道构造题题意：给一个 n 、 k n、k n、k，让构造长度为n的数组满足，子数组为整数的个数为k个，负数的为 k − ( n + 1 ) ∗ n / 2 k-(n+1)* n/2 k−(n+1)∗n/2,每个数的范围为 [ − 1000 , 1000 ] [-1000,1000] [−1000,1000] 这种构造题可以考虑就是前一段可以一直用一样的、最小的。我们观察可以发现

Leetcode 3013. Divide an Array Into Subarrays With Minimum Cost II

Leetcode 3013. Divide an Array Into Subarrays With Minimum Cost II 1. 解题思路2. 代码实现题目链接：3013. Divide an Array Into Subarrays With Minimum Cost II 1. 解题思路这一题的话思路上的话我一开始是想着偷懒直接用动态规划，结果果然还是遇到了超时的问题，因为

Leetcode 2962. Count Subarrays Where Max Element Appears at Least K Times

Leetcode 2962. Count Subarrays Where Max Element Appears at Least K Times 1. 解题思路2. 代码实现题目链接：2962. Count Subarrays Where Max Element Appears at Least K Times 1. 解题思路这一题思路上同样很直接，就是找到最大的元素所在的全部的位置坐

leetcode 1031. Maximum Sum of Two Non-Overlapping Subarrays

leetcode 1031. Maximum Sum of Two Non-Overlapping Subarrays 题意：给你一个数组，再给你一个L，M，求在这个数组里面，两个不重合的长度分别为L，M的最的最大和。思路：先预处理一个dp[i][2]; dp[i][0]表示以i为开头，长度为L的值。 dp[i][1]表示以i为开头，长度为M的值。在两层for，遍历i，j分别表示

[python 刷题] 1248 Count Number of Nice Subarrays

[python 刷题] 1248 Count Number of Nice Subarrays 题目如下： Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of n