第一题太水,跳过了. NanoApe Loves Sequence
题目描述:
退役狗 NanoApe 滚回去学文化课啦！ 在数学课上，NanoApe 心痒痒又玩起了数列。他在纸上随便写了一个长度为 nnn 的数列，他又根据心情随便删了一个数，这样他得到了一个新的数列，然后他计算出了所有相邻两数的差的绝对值的最大值。 他当然知道这个最大值会随着他删了的数改变而改变，所以他想知道假如全部数被删除的概率是相等的话，差的绝对值的最大值的期望是多少。 输入描述
第一行为一个正整数 T，表示数据组数。 每组数据的第一行为一个整数 n。 第二行为 n 个整数 1<=Ai<=109 输出描述
对于每组数据输出一行一个数表示答案。 为防止精度误差，你需要输出答案乘上 n 后的值。 输入: 1
4
1 2 3 4
输出:
6
题解:这题直接求出区间最大和次大,然后求出每两点之间的绝对值之差,然后去一个个点枚举就行了,时间复杂度O(n),注意处理边界,还有个地方就是每次删掉点后距离并不是两个间隔之和,而是要
重新算一下的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define N 100050
typedef long long LL;
int a[N];
int del[N];
int main()
{
int tcase;
scanf("%d",&tcase);
while(tcase--){
int n;
scanf("%d",&n);
int MAX = -,SMAX = -;
int MAX_ID=,SMAX_ID = ;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
if(i>){
del[i] = abs(a[i]-a[i-]);
if(MAX<del[i]){
SMAX = MAX;
MAX = del[i];
MAX_ID = i;
}else if(SMAX<del[i]){
SMAX = del[i];
SMAX_ID = i;
}
}
}
LL ans = ;
for(int i=;i<n;i++){
int len = abs(a[i+]-a[i-]);
if(len>MAX){
ans+=del[i]+del[i+];
}else {
///下面三句缺一不可
if(MAX_ID==i&&SMAX_ID==i+||SMAX_ID==i&&MAX_ID==i+) ans+=len;
else if(MAX_ID==i||MAX_ID==i+) ans+=SMAX;
else ans+=MAX;
}
}
if(MAX_ID==){
ans+=SMAX;
}else{
ans+=MAX;
}
if(MAX_ID==n){
ans+=SMAX;
}else{
ans+=MAX;
}
printf("%I64d\n",ans);
}
}
NanoApe Loves Sequence Ⅱ
问题描述
退役狗 NanoApe 滚回去学文化课啦！ 在数学课上，NanoApe 心痒痒又玩起了数列。他在纸上随便写了一个长度为 n 的数列，他又根据心情写下了一个数 m。 他想知道这个数列中有多少个区间里的第 k 大的数不小于 m，当然首先这个区间必须至少要有 k 个数啦。 输入描述
第一行为一个正整数 TTT，表示数据组数。 每组数据的第一行为三个整数 n,m,k。 第二行为 n 个整数 1<=Ai<=109 输出描述
对于每组数据输出一行一个数表示答案。 输入
1
7 4 2
4 2 7 7 6 5 1 输出
18 题解:这题迷惑人的地方就是区间第k大,感觉很难,但是其实我们可以将问题转换一下,只要对于每个区间,有k个比m大的数这个区间就是合法的,所以对于区间的左端点,我们可以去枚举,然后利用尺取法求出右端点,假如右端点是 j，左端点是 i, 这个里面有 k 个大于 m 的数了,那么以i为左端点 [i-j]并上[i,n] 这段区间都是可行的,在l=i的时候,[i,j],[i,j+1]...[i,n],总共多了(n-j+1)个区间,计数即可.
ps:我那个下面r-1是因为每次出来的时候右端点已经右移了一位.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define N 200050
typedef long long LL;
int a[N];
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
int l =, r = ;
LL ans = ;
int sum = ;
while(l<=n){
while(sum<k&&r<=n){
if(a[r++]>=m) sum++;
}
if(sum==k) ans+=(n-(r-1)+); ///右端点可行,那么后面的都可行
if(a[l]>=m) sum--;
l++;
}
printf("%lld\n",ans);
}
return ;
}
i，表示这个数列。 1≤T≤10, 2≤n≤200000, 1≤k≤n/2, 1≤m,Ai≤1091 \le T \le 10,~2 \le n \le 200000,~1 \le k \le n/2,~1 \le m,A_i \le 10^91≤T≤10, 2≤n≤200000, 1≤k≤n/2, 1≤m,Ai≤109
i，表示这个数列。 1≤T≤10, 3≤n≤100000, 1≤Ai≤1091 \le T \le 10,~3 \le n \le 100000,~1 \le A_i \le 10^91≤T≤10, 3≤n≤100000, 1≤Ai≤109