A题 Price List
巨水..........水的不敢相信。
#include <cstdio>
typedef long long LL;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m,x;
scanf("%d%d",&n,&m);
LL sum = ;
; i < n; i++)
{
int x;
scanf("%d",&x);
sum = sum + (LL)x;
}
; i < n; i++)
{
LL x;
scanf("%lld",&x);
if(x > sum)
printf(");
else
printf(");
}
printf("\n");
}
;
}
这道题可以用线段树做，查询最大值，每次删掉一个点，等于单点更新一到两个点。之后复原一下即可。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem0(x) memset(x,0,sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
+ ];
LL MAX[ << ];
int t;
] , MAX[rt << | ]);}
void build(int l,int r,int rt)
{
] - a[l]); return ;}
;
build(lson);
build(rson);
pushup(rt);
}
void update(int p,int add,int l,int r,int rt)
{
if(l == r) {t = MAX[rt]; MAX[rt] = add; return ;}
;
if(p <= m)
update(p,add,lson);
else
update(p,add,rson);
pushup(rt);
}
LL query_max(int ll,int rr,int l,int r,int rt)
{
if(ll <= l && rr >= r) return MAX[rt];
LL ans = ;
;
if(ll <= m)
ans = max(ans,query_max(ll,rr,lson));
if(rr > m)
ans = max(ans,query_max(ll,rr,rson));
return ans;
}
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
mem0(a);
mem0(MAX);
scanf("%d",&n);
; i <= n; i++)
{
scanf("%d",&a[i]);
}
build(,n-,);
LL ans = ;
; i <= n; i++)
{
int t1,t2;
&& i != n)
{
update(i,abs(a[i+]-a[i-]),,n-,),t1 = t;
update(i-,abs(a[i+]-a[i-]),,n-,),t2 = t;
}
else
{
if(i != n)
update(i,,,n-,),t1 = t;
)
update(i-,,,n-,),t2 = t;
}
ans = ans + query_max(,n-,,n-,);
&& i != n)
{
update(i,t1,,n-,);
update(i-,t2,,n-,);
}
else
{
if(i != n)
update(i,t1,,n-,);
)
update(i-,t2,,n-,);
}
}
printf("%I64d\n",ans);
}
;
}
但是这道题的正解是O（n）的算法。不是线段树。
真的感觉 被 虐智商。人家五分钟搞定这道题= =。
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
+ ;
int a[maxn], r_max[maxn], l_max[maxn];
int main()
{
int T,n;
LL ans;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
; i <= n; i++)
{
scanf("%d",&a[i]);
}
l_max[] = ;
; i <= n; i++)
{//r_max 从左边开始到i的最大值
l_max[i] = max(l_max[i-], abs(a[i] - a[i-]));
}
r_max[n] = ;
; i >= ; i--)
{//l_max 从右边开始到i的最大值
r_max[i] = max(r_max[i+], abs(a[i+] - a[i]));
}
ans = (LL) l_max[n-] + (LL) r_max[];
; i < n; i++)
{
ans = ans + (LL) max(l_max[i-], max(r_max[i+], abs(a[i-] - a[i+]) ) );
}
printf("%I64d\n",ans);
}
;
}
多少个区间里的第k大的数不小于 m。其实就是说如果这个区间里面能找到，k个大于等于m的数，那么这个区间肯定就满足条件，后面的就不需要管了。
尺取法!!!!
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
+ ];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int T,n,m,k;
scanf("%d",&T);
; i < T; i++)
{
scanf("%d%d%d",&n,&m,&k);
; i <= n; i++)
scanf("%d",&a[i]);
;
LL ans = ;
;
; i <= n; i++)
{
while(cnt < k && r < n)
{
r++;
cnt += (a[r] >= m);
}
if(cnt < k) break;
ans = ans + (LL) n - r + ;
cnt -= (a[i] >= m);
}
printf("%I64d\n",ans);
}
;
}
D题