最长连续不重复子序列
给定一个长度为 nn 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 nn。
第二行包含 nn 个整数（均在 0∼1050∼105 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤1051≤n≤105
输入样例：
输出样例：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6;
ll q[N], c[N];
ll n;
int res;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++){
cin>>q[i];
}
for(int i=1, j=1; i<=n; i++){
c[q[i]]++;
while(c[q[i]]>1){
c[q[j]]--;
j++;
}
res=max(res, i-j+1);
}
cout<<res<<endl;
return 0;
}
|
前缀和
输入一个长度为 nn 的整数序列。
接下来再输入 mm 个询问，每个询问输入一对 l,rl,r。
对于每个询问，输出原序列中从第 ll 个数到第 rr 个数的和。
输入格式
第一行包含两个整数 nn 和 mm。
第二行包含 nn 个整数，表示整数数列。
接下来 mm 行，每行包含两个整数 ll 和 rr，表示一个询问的区间范围。
输出格式
共 mm 行，每行输出一个询问的结果。
数据范围
1≤l≤r≤n1≤l≤r≤n,
1≤n,m≤1000001≤n,m≤100000,
−1000≤数列中元素的值≤1000−1000≤数列中元素的值≤1000
输入样例：
输出样例：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6;
ll n, m;
ll q[N],s[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1; i<=n; i++){
cin>>q[i];
s[i]=s[i-1]+q[i];
}
int l, r;
while(m--){
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
|
子矩阵的和
输入一个 nn 行 mm 列的整数矩阵，再输入 qq 个询问，每个询问包含四个整数 x1,y1,x2,y2x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，qn，m，q。
接下来 nn 行，每行包含 mm 个整数，表示整数矩阵。
接下来 qq 行，每行包含四个整数 x1,y1,x2,y2x1,y1,x2,y2，表示一组询问。
输出格式
共 qq 行，每行输出一个询问的结果。
数据范围
1≤n,m≤10001≤n,m≤1000,
1≤q≤2000001≤q≤200000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
|
输出样例：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1010;
ll n, m, q;
int arr[N][N], sum[N][N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>q;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin>>arr[i][j];
sum[i][j]=arr[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
}
}
int x1, y1, x2, y2;
while(q--){
cin>>x1>>y1>>x2>>y2;
cout<<sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]<<endl;
}
return 0;
}
|
数组元素的目标和
给定两个升序排序的有序数组 AA 和 BB，以及一个目标值 xx。
数组下标从 00 开始。
请你求出满足 A[i]+B[j]=xA[i]+B[j]=x 的数对 (i,j)(i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,xn,m,x，分别表示 AA 的长度，BB 的长度以及目标值 xx。
第二行包含 nn 个整数，表示数组 AA。
第三行包含 mm 个整数，表示数组 BB。
输出格式
共一行，包含两个整数 ii 和 jj。
数据范围
数组长度不超过 105105。
同一数组内元素各不相同。
1≤数组元素≤1091≤数组元素≤109
输入样例：
输出样例：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int a[N], b[N];
int n, m, x;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>x;
for(int i=0; i<n; i++){
cin>>a[i];
}
for(int j=0; j<m; j++){
cin>>b[j];
}
for(int i=0, j=m-1; i<n, j>=0; i++){
while(a[i]+b[j]>x){
j--;
}
if(a[i]+b[j]==x){
cout<<i<<" "<<j<<endl;
break;
}
}
return 0;
}
|
A-B 数对
题目描述
给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数 N,C。
第二行，N 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足 A−B=C 的数对的个数。
输入输出样例
输入 #1复制
输出 #1复制
说明/提示
对于 75% 的数据，1≤N≤2000。
对于 100% 的数据，1≤N≤2×105，0≤a**i<230，1≤C<230。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6;
ll n, x;
ll res;
ll q[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>x;
for(int i=1; i<=n; i++){
cin>>q[i];
}
sort(q+1, q+1+n);
for(int i=1,j=1,k=1; i<=n; i++){
while(j<=i && q[i]-q[j]>=x){
j++;
}
while(k<=i && q[i]-q[k]>x){
k++;
}
res+=j-k;
}
cout<<res<<endl;
return 0;
}
|
递增三元组
给定三个整数数组
A=[A1,A2,…AN]A=[A1,A2,…AN],
B=[B1,B2,…BN]B=[B1,B2,…BN],
C=[C1,C2,…CN]C=[C1,C2,…CN],
请你统计有多少个三元组 (i,j,k)(i,j,k) 满足：
- 1≤i,j,k≤N1≤i,j,k≤N
- Ai<Bj<CkAi<Bj<Ck
输入格式
第一行包含一个整数 NN。
第二行包含 NN 个整数 A1,A2,…ANA1,A2,…AN。
第三行包含 NN 个整数 B1,B2,…BNB1,B2,…BN。
第四行包含 NN 个整数 C1,C2,…CNC1,C2,…CN。
输出格式
一个整数表示答案。
数据范围
1≤N≤1051≤N≤105,
0≤Ai,Bi,Ci≤1050≤Ai,Bi,Ci≤105
输入样例：
输出样例：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6;
ll a[N], b[N], c[N];
ll res;
ll n;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++) cin>>b[i];
for(int i=1; i<=n; i++) cin>>c[i];
sort(a+1, a+1+n);
sort(b+1, b+1+n);
sort(c+1, c+1+n);
for(ll indexA=1, indexB=1, indexC=1; indexB<=n; indexB++){
while(indexA<=n && a[indexA]<b[indexB]){
indexA++;
}
while(indexC<=n && c[indexC]<=b[indexB]){
indexC++;
}
res+=(indexA-1)*(n-indexC+1);
}
cout<<res<<endl;
return 0;
}
|
Diamond Collector S
题目描述
奶牛 Bessie 一直喜欢闪闪发光的物体，她最近在业余时间开始了一项爱好——挖掘钻石！她收集了 N 颗大小各不相同的钻石（N≤50,000），并希望将它们中的一部分放在谷仓里的两个展示柜中展示。
由于 Bessie 希望每个展示柜中的钻石大小相对接近，她决定如果两颗钻石的大小相差超过 K，就不能将它们放在同一个展示柜中（如果两颗钻石的大小相差恰好为 K，则可以将它们一起展示在同一个展示柜中）。给定 K，请帮助 Bessie 确定她可以在两个展示柜中一起展示的最大钻石数量。
输入格式
输入文件的第一行包含 N 和 K（0≤K≤1,000,000,000）。
接下来的 N 行每行包含一个整数，表示一颗钻石的大小。所有钻石的大小均为正数且不超过 1,000,000,000。
输出格式
输出一个正整数，表示 Bessie 可以在两个展示柜中一起展示的最大钻石数量。
[显示翻译](javascript:void 0)
题意翻译
输入输出样例
输入 #1复制
输出 #1复制
题目描述
奶牛 Bessie 一直喜欢闪闪发光的物体，她最近在业余时间开始了一项爱好——挖掘钻石！她收集了 N 颗大小各不相同的钻石（N≤50,000），并希望将它们中的一部分放在谷仓里的两个展示柜中展示。
由于 Bessie 希望每个展示柜中的钻石大小相对接近，她决定如果两颗钻石的大小相差超过 K，就不能将它们放在同一个展示柜中（如果两颗钻石的大小相差恰好为 K，则可以将它们一起展示在同一个展示柜中）。给定 K，请帮助 Bessie 确定她可以在两个展示柜中一起展示的最大钻石数量。
输入格式
输入文件的第一行包含 N 和 K（0≤K≤1,000,000,000）。
接下来的 N 行每行包含一个整数，表示一颗钻石的大小。所有钻石的大小均为正数且不超过 1,000,000,000。
输出格式
输出一个正整数，表示 Bessie 可以在两个展示柜中一起展示的最大钻石数量。
显示翻译
题意翻译
输入输出样例
输入 #1复制
7 3
10
5
1
12
9
5
14
输出 #1复制
5
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6;
ll n, k;
ll q[N], arr[N];
ll res=1;
ll cnt_lr[N], cnt_rl[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=1; i<=n; i++){
cin>>q[i];
}
sort(q+1, q+1+n);
for(ll i=1, j=1; i<=n; i++){
while(q[i]-q[j]>k && j<=i){
j++;
}
cnt_lr[i]=max(cnt_lr[i-1], i-j+1);
}
for(ll i=n, j=n; i>=1; i--){
while(q[j]-q[i]>k && j>=i){
j--;
}
cnt_rl[i]=max(cnt_rl[i+1], j-i+1);
}
for(ll i=1; i<=n; i++){
res=max(cnt_lr[i]+cnt_rl[i+1], res);
}
cout<<res<<endl;
return 0;
}
|
