牛客练习赛11




A:假的线段树

题目

链接:https://www.nowcoder.com/acm/contest/59/A
来源:牛客网

给你一个长为n的序列a,有m次操作

1.把区间[l,r]内所有x变成y

2.查询区间[l,r]内第k小值

对于100%的数据,1 <= n, m , ai <= 1000

输入描述

第一行两个数n,m
第二行n个数表示序列a
后面m行
1 l r x y :把区间[l,r]中所有x变成y
2 l r k :查询区间[l,r]中的第k小值

输出描述

对于每个询问,输出一个数表示答案

示例输入

3 3
2 3 3
2 1 3 1
1 1 3 3 1
2 1 3 2

示例输出

2
1

题解

数据量小.1000*1000的复杂度,可以暴力过.第K小直接排序即可.

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int n,m;
int num[maxn];

void solve1(){
    int l,r,x,y;
    scanf("%d%d%d%d",&l,&r,&x,&y);
    for(int i=l;i<=r;++i){
        if(num[i]==x)num[i]=y;
    }
}

void solve2(){
    int l,r,k;
    scanf("%d%d%d",&l,&r,&k);
    int copy[maxn];
    for(int i=l;i<=r;++i){
        copy[i]=num[i];
    }
    sort(copy+l,copy+r+1);
    printf("%d\n",copy[l+k-1]);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&num[i]);
    }
    int query;
    for(int i=0;i<m;++i){
        scanf("%d",&query);
        if(query==1) solve1();
        else solve2();
    }

    return 0;
}

D:求距离

题目

链接:https://www.nowcoder.com/acm/contest/59/D
来源:牛客网

给你一个1 -> n的排列,现在有一次机会可以交换两个数的位置,求交换后最小值和最大值之间的最大距离是多少?

水题

输入输出格式看链接吧

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=110;
int num[maxn];
int main(){
    int n,mi=1,ma=1;
    num[0]=0;
    scanf("%d",&n);
    scanf("%d",&num[1]);
    for(int i=2;i<=n;++i){
        scanf("%d",&num[i]);
        if(num[i]<num[mi]) mi=i;
        if(num[i]>num[ma]) ma=i;
    }
    int min_id=min(mi,ma),max_id=max(mi,ma);
    int a=n-min_id,b=min_id-1,c=n-max_id,d=max_id-1;
    printf("%d\n",max(a,max(b,max(c,d))));
    return 0;
}

E:求最值

链接:https://www.nowcoder.com/acm/contest/59/E
来源:牛客网

给你一个长为n的序列a

定义f(i,j)=(i-j)2+g(i,j)2
g是这样的一个函数

求最小的f(i,j)的值,i!=j

题解

这道题数据水,可以直接枚举距离1和距离2水过.

代码

#include<bits/stdc++.h>
#define TREE_SIZE (1<<(20))
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=100010;
long long sum_z[maxn],sum_f[maxn];
int n,num[maxn];

inline long long g(int i,int j){
    register long long sum=0;
    long long k=min(i,j),l=max(i,j);
    sum=sum_z[n]-(sum_z[k]+sum_f[j+1]);
    return sum;
}

int main(){
    scanf("%d",&n);
    sum_z[0]=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&num[i]);

        sum_z[i]=sum_z[i-1]+num[i];
    }
    sum_f[n]=0;
    for(int i=n;i>=1;--i){
        sum_f[i]=sum_f[i+1]+num[i];
    }
    long long res=1000000000;
    for(int i=2;i<=n;++i){
        int T=min(1000,i);
        for(int j=1;j<T;++j){
            long long reg=g(i-j,i);
            //printf("i:%d,j:%d,reg:%d\n",i,j,reg);
            long long ans=j*j+reg*reg;
            res=min(res,ans);
        }
    }
    printf("%lld\n",res);
    return 0;
}


但是这道题是平面最近点对