尺取法
尺取法思想：解决区间和问题的一种思想，相较于暴力算法，节省了无效枚举的时间
比如要你求一个问题：给你一系列的数，让你找出大于等于某个给定数的区间和的最小长度。
解决思路：只需要找两个指针，起始位置全部为第一个数的位置，如果第一个数小于给定数，其中一个指针（j）向后移，另一个指针（i）不动，知道区间和大于等于给定数，然后移动i，使之向后移动，直到区间和等于给定数，保存方案，继续操作。
例题：
Subsequence
A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.
Input
The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.
Output
For each the case the program has to print the result on separate line of the output file.if no answer, print 0.
Sample Input
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5
Sample Output
2
3
解题：代码：
代码及图片来源：https://blog.csdn.net/qq_38984851/article/details/81087066
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#define MAXN 100100
#define INF 0xfffffff
using namespace std;
int a[MAXN];
int n,m,sum,num;
int main()
{
int t,i,begin1,end1;
scanf("%d",&t);
while(t--)
{
num=INF;
scanf("%d%d",&n,&m);
for(i=0; i<n; i++)
scanf("%d",&a[i]);
begin1=0;
end1=0;
sum=0;
while(1)
{
while(begin1<n&&sum<m) //从前面开始加
{
sum+=a[begin1];
begin1++;
}
if(sum<m)
break;
num=min(num,begin1-end1);开始缩小尺寸
sum-=a[end1];//从第一个开始相减，然后把尺寸一次缩小，尺寸法的前进
end1++;
}
if(num==INF)//说明没有满足求得和大于m
printf("0\n");
else
printf("%d\n",num);
}
return 0;
}
G - WiFi Password Gym - 101608G
Just days before the JCPC, your internet service went down. You decided to continue your training at the ACM club at your university. Sadly, you discovered that they have changed the WiFi password. On the router, the following question was mentioned, the answer is the WiFi password padded with zeros as needed.
A subarray [l, r] of an array A is defined as a sequence of consecutive elements Al, Al + 1, …, Ar, the length of such subarray is r - l + 1. The bitwise OR of the subarray is defined as: Al OR Al + 1 OR … OR Ar, where OR is the bitwise OR operation (check the notes for details).
Given an array A of n positive integers and an integer v, find the maximum length of a subarray such that the bitwise OR of its elements is less than or equal to v.
Input
The first line contains an integer T (1 ≤ T ≤ 128), where T is the number of test cases.
The first line of each test case contains two space-separated integers n and v (1 ≤ n ≤ 105) (1 ≤ v ≤ 3 × 105).
The second line contains n space-separated integers A1, A2, …, An (1 ≤ Ai ≤ 2 × 105), the elements of the array.
The sum of n overall test cases does not exceed 106.
Output
For each test case, if no subarray meets the requirement, print 0. Otherwise, print the maximum length of a subarray that meets the requirement.
Example
Input
3
5 8
1 4 5 3 1
5 10
8 2 6 1 10
4 2
9 4 5 8
Output
5
3
0
Note
To get the value of x OR y, consider both numbers in binary (padded with zeros to make their lengths equal), apply the OR operation on the corresponding bits, and return the result into decimal form. For example, the result of 10 OR 17 = 01010 OR 10001 = 11011 = 27.
题目大意：求n个数中按位或小于等于v的最大长度
ac代码：出处：https://blog.csdn.net/BePosit/article/details/82285326
#include<bits/stdc++.h>
using namespace std;
#define maxn 100050
long long t,n,m,v,a[maxn];
long long r,ans,sum,j;
int main()
{
freopen("wifi.in","r",stdin);
cin>>t;
while(t--)
{
cin>>n>>v;
ans=0;
r=1;
for(int i=0; i<n; i++)
cin>>a[i];
sum=a[0];
for(int i=0; i<n; i++)
{
if(i==r)
{
sum=a[i];
r=i+1;
}
while(r<n&&(a[r]|sum)<=v)
{
sum|=a[r];
r++;
}
if(sum<=v)
ans=max(ans,r-i);
if(r==n)
break;
//确定i指针的下一步位置
sum=a[r];
j=r-1;
while((a[j]|sum)<=v)
{
sum|=a[j];
j--;
}
i=j;
}
cout<<ans<<endl;
}
return 0;
}