A.暴力
#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int main()
{
int n,x,y,mi=0;
scanf("%d %d %d",&n,&x,&y);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
int fg = 1;
for(int j=i-x;j<=i+y;j++){
if(j<1||j>n||j==i)continue;
if(a[i]>=a[j]){
fg = 0;break;
}
}
if(fg){
printf("%d\n",i);
break;
}
}
return 0;
}
B.小学数学?
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
double h,l;
cin>>h>>l;
double ans = (l*l-h*h)/(2*h);
printf("%.13lf\n",ans);
return 0;
}
C. 求不同个数在 2 ^(8*I/n)以内的最大个数
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1000005;
int cnt[maxn],sum[maxn];
int a[maxn],b[maxn];
int mp[maxn];
int lowbit(int k){
return k&(-k);
}
void insert(int k){
while(k<maxn){
cnt[k]+=1;
k+=lowbit(k);
}
}
void insert2(int k){
while(k<maxn){
sum[k]+=1;
k+=lowbit(k);
}
}
ll query1(int k){
ll ans = 0;
while(k>0){
ans+=cnt[k];
k-=lowbit(k);
}
return ans;
}
ll query2(int k){
ll ans = 0;
while(k>0){
ans+=sum[k];
k-=lowbit(k);
}
return ans;
}
int main()
{
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);b[i] = a[i];
}
sort(b+1,b+1+n);
int sz = unique(b+1,b+1+n) - (b+1);
ll num = 8*k/n;
if(num>25)
num = 1<<25;
else num = 1<<num;
if(sz<=num){
printf("0");
return 0;
}
for(int i=1;i<=n;i++){
int tp = lower_bound(b+1,b+1+sz,a[i]) - b ;
mp[tp] = a[i];
a[i] = tp;
insert(tp);
}
for(int i=1;i<=sz;i++)insert2(i);
ll ans = n;
for(int i=1;i<=sz;i++)
{
ll tq = query1(i+num-1)-query1(i-1);
ans = min(n-tq,ans);
}
printf("%lld",ans);
return 0;
}
D. 线段树
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int a[maxn];
struct N {
int l,r;
int pre,add;
} node[4*maxn+5];
void build(int p,int l,int r) { //区间编号p
node[p].l = l;
node[p].r = r;
node[p].add = 0;
if(l==r) { //叶子结点直接赋值
node[p].pre = a[l];
return ;
}
int mid = l+r >>1;
build(2*p,l,mid);
build(2*p+1,mid+1,r);
node[p].pre = max(node[p*2].pre,node[p*2+1].pre);//维护区间和
}
void spread(int p) {
if(node[p].add) { //如果标记不为0 向下传递
int v = node[p].add;
node[2*p].pre=max(node[2*p].pre,v),node[2*p].add = max(node[2*p].add,v);
node[2*p+1].pre=max(node[2*p+1].pre,v),node[2*p+1].add = max(node[2*p+1].add,v);
node[p].add = 0;
}
}
void change(int p,int l,int r,int v) {
if(node[p].l==l&&node[p].r==r) { //区间被覆盖 就对其进行修改
node[p].pre = v;
return ;
}
spread(p);
int mid = node[p].l + node[p].r>>1;
if(l<=mid)change(p*2,l,r,v);
if(r>mid)change(p*2+1,l,r,v);
node[p].pre = max(node[2*p].pre ,node[2*p+1].pre);
}
void change2(int p,int l,int r,int v) {
if(node[p].l>=l&&node[p].r<=r) { //区间被覆盖 就对其进行修改
node[p].pre = max(node[p].pre,v);
node[p].add = max(node[p].add,v);
return ;
}
spread(p);
int mid = node[p].l + node[p].r>>1;
if(l<=mid)change2(p*2,l,r,v);
if(r>mid)change2(p*2+1,l,r,v);
node[p].pre = max(node[2*p].pre,node[2*p+1].pre);
}
void query(int p,int l,int r) {
if(l==node[p].l&&r==node[p].r) { //被覆盖 返回值
printf("%d ",node[p].pre);
return ;
}
spread(p);
int ans = 0;
int mid = node[p].r+node[p].l>>1;
if(l<=mid)query(p*2,l,r);
if(r>mid)query(p*2+1,l,r);
}
int main()
{
int n,m;
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
build(1,1,n);
scanf("%d",&m);
while(m--) {
int op;
int l,r,k;
scanf("%d",&op);
if(op==1) {
scanf("%d %d",&k,&r);
change(1,k,k,r);
} else {
scanf("%d",&l);
change2(1,1,n,l);
}
}
int aa;
for(int i=1; i<=n; i++) {
query(1,i,i);
}
return 0;
}