头像

wyc1996

哈尔滨工业大学




在线 



wyc1996
4分钟前

题目描述

在这个问题中,您必须分析特定的排序算法----超快速排序。

该算法通过交换两个相邻的序列元素来处理n个不同整数的序列,直到序列按升序排序。

对于输入序列9 1 0 5 4,超快速排序生成输出0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

算法:归并排序求逆序对

时间复杂度:$N·log(N)$

C++代码

#include<iostream>
#include<cstring>

using namespace std;
const int N=500010;
typedef long long LL;
int w[N];
int tmp[N];

LL merge_sort(int l,int r)
{
    if(l>=r)return 0;
    int mid=l+r>>1;
    LL res=merge_sort(l,mid)+merge_sort(mid+1,r);

    int i=l,j=mid+1,k=0;
    while(i<=mid && j<=r){
        if(w[i]<=w[j])tmp[k++]=w[i++];
        else{
            res+=mid-i+1;
            tmp[k++]=w[j++];
        }
    }
    while(i<=mid)tmp[k++]=w[i++];
    while(j<=r)tmp[k++]=w[j++];
    for(int i=l,j=0;i<=r;i++,j++)w[i]=tmp[j];
    return res;
}

int main()
{
    int n;
    while(cin>>n,n){
        for(int i=0;i<n;i++)scanf("%d",&w[i]);
        cout<<merge_sort(0,n-1)<<endl;
    }
    return 0;
}



wyc1996
1小时前

题目描述

依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。

算法:对顶堆

时间复杂度:$N·log(N)$

对顶堆算法的典型应用,动态求序列的中位数
对顶堆算法基本仅用在这种情况

C++代码

#include<iostream>
#include<queue>

using namespace std;

int main()
{
    int T;
    cin>>T;
    while(T--){
        int id,n;
        scanf("%d%d",&id,&n);
        printf("%d %d\n",id,(n+1)/2);

        priority_queue<int,vector<int>,greater<int>>up;
        priority_queue<int>down;
        int cnt=0;

        for(int i=1;i<=n;i++){
            int t;
            scanf("%d",&t);
            if(down.empty() || t<=down.top())down.push(t);
            else up.push(t);
            if(down.size()>up.size()+1)up.push(down.top()),down.pop();
            if(up.size()>down.size())down.push(up.top()),up.pop();
            if(i&1){
                cout<<down.top()<<" ";
                if(++cnt%10==0)puts("");
            }
        }
        if(cnt%10)puts("");
    }
    return 0;
}



wyc1996
4小时前

题目描述

从前有个人名叫 WNB,他有着天才般的记忆力,他珍藏了许多许多的宝藏。

在他离世之后留给后人一个难题(专门考验记忆力的啊!),如果谁能轻松回答出这个问题,便可以继承他的宝藏。

题目是这样的:给你一大串数字(编号为 1 到 N,大小可不一定哦!),在你看过一遍之后,它便消失在你面前,随后问题就出现了,给你 M 个询问,每次询问就给你两个数字 A,B,要求你瞬间就说出属于 A 到 B 这段区间内的最大数。

一天,一位美丽的姐姐从天上飞过,看到这个问题,感到很有意思(主要是据说那个宝藏里面藏着一种美容水,喝了可以让这美丽的姐姐更加迷人),于是她就竭尽全力想解决这个问题。

但是,她每次都以失败告终,因为这数字的个数是在太多了!

于是她请天才的你帮他解决。如果你帮她解决了这个问题,可是会得到很多甜头的哦!

算法:RMQ(ST表)

时间复杂度:$Nlog(N)$

ST表(RMQ)主要解决区间最值的查询

C++代码

//RMQ问题:用于求解区间的最值问题
//本质是利用倍增的思想和DP的手段进行的预处理
#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;
const int N=200010;
const int M=20;
int w[N];
int f[N][M];  //状态表示的含义:以i开始,长度为1<<j这段区间的最值
int n,m;

void init()
{
    //先枚举长度 再枚举起点
    //保证在枚举长度比较大的区间之前 长度较小的区间已经被计算过
    for(int j=0;j<M;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            if(!j)f[i][j]=w[i];
            else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
        }
    }
}
//区间最值查询
int query(int l,int r)
{
    int len=r-l+1;
    int k=log(len)/log(2);
    //可以确保覆盖整个区间
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    init();
    cin>>m;
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        cout<<query(l,r)<<endl;
    }
    return 0;
}



wyc1996
4小时前

题目描述

有N个元素,编号1.2..N,每一对元素之间的大小关系是确定的,关系具有反对称性,但不具有传递性。

注意:不存在两个元素大小相等的情况。

也就是说,元素的大小关系是N个点与N*(N-1)/2条有向边构成的任意有向图。

然而,这是一道交互式试题,这些关系不能一次性得知,你必须通过不超过10000次提问来获取信息,每次提问只能了解某两个元素之间的关系。

现在请你把这N个元素排成一行,使得每个元素都小于右边与它相邻的元素。

你可以通过我们预设的bool函数compare来获得两个元素之间的大小关系。

例如,编号为a和b的两个元素,如果元素a小于元素b,则compare(a,b)返回true,否则返回false。

将N个元素排好序后,把他们的编号以数组的形式输出,如果答案不唯一,则输出任意一个均可。

算法:二分

时间复杂度:$O(N^2·log(N))$

C++代码

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

// 不一定一定要具有单调的全局关系才能进行二分
//二分不需要严格的边界关系
class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int>res(1,1);
        for(int i=2;i<=N;i++){
            //找到小于等于i的最大的位置
            int l=0,r=res.size()-1;
            while(l<r){
                int mid=l+r+1>>1;
                if(compare(res[mid],i))l=mid;
                else r=mid-1;
            }
            //现将结果插入到序列的末尾
            res.push_back(i);
            //将最末尾的结果交换到r+1
            for(int j=res.size()-2;j>r;j--)swap(res[j],res[j+1]);
            if(compare(i,res[r]))swap(res[r],res[r+1]);
        }
        return res;
    }
};



wyc1996
5小时前

题目描述

农夫约翰的农场由 N 块田地组成,每块地里都有一定数量的牛,其数量不会少于1头,也不会超过2000头。

约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 F 块地,其中 F 会在输入中给出。

在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

算法:二分+前缀和+双指针

时间复杂度:$O(log(n)+2·n)$

(1)一部分的最值问题是可以使用二分进行求解的
(2)求某个前缀的最小值可以使用双指针算法优化掉一重循环

C++代码

#include<iostream>

using namespace std;
const int N=100010;
double w[N],a[N];
int n,k;

bool judge(double avg)
{   
    //维护前缀与均值的大小
    for(int i=1;i<=n;i++)a[i]=a[i-1]+w[i]-avg;
    double mins=0;

    for(int i=k;i<=n;i++){
        mins=min(mins,a[i-k]);
        //在i处之前的k个位置的最小值
        if(a[i]-mins>=0)return true;
    }
    return false;
}

int main()
{
    cin>>n>>k;

    double l=0,r=0;
    for(int i=1;i<=n;i++){
        scanf("%lf",&w[i]);
        r=max(r,w[i]);
    }

    while(r-l>1e-5){
        double mid=(r+l)/2;
        if(judge(mid))l=mid;
        else r=mid;
    }
    printf("%d\n",(int)(1000*r));
    return 0;
}



wyc1996
16小时前

题目描述

给定一个长度为 nn 的数列 $a_1,a_2,…,a_n$每次可以选择一个区间 [l,r],使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列可能有多少种。

算法:差分

时间复杂度:$O(N)$

C++代码

#include<iostream>
#include<cstring>

using namespace std;
const int N=100010;
int a[N],b[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i]-a[i-1];
    }

    //p是序列中差分值大于0的所有的和
    //q是序列中差分小于0的所有的和
    long long p=0,q=0;
    for(int i=2;i<=n;i++){
        if(b[i]>0)p+=b[i];
        else if(b[i]<0)q-=b[i];
    }
    cout<<max(p,q)<<endl;
    cout<<abs(p-q)+1<<endl;
    return 0;
}



wyc1996
17小时前

题目描述

地图上有 N 个目标,用整数$X_i,Y_i,X_i,Y_i$表示目标在地图上的位置,每个目标都有一个价值$W_i$。

注意:不同目标可能在同一位置。

现在有一种新型的激光炸弹,可以摧毁一个包含 R×R 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆炸范围,即那个正方形的边必须和x,y轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

算法:二维前缀和

时间复杂度:$O(N^2)$

注意

(1)题目中的表述可能会带来困扰,如何理解边长和爆炸的范围之间的关系?不如以下图作为理解
QQ截图20201129214029.jpg
目标不在边界范围存在,而是在中心存在,这样可以避免考虑其中的爆炸边界的问题

C++代码

#include<iostream>
#include<cstring>

using namespace std;
const int N=5010;
int g[N][N];

int main()
{
    int n,r;
    cin>>n>>r;
    r=min(r,5001);

    for(int i=0;i<n;i++){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        ++x,++y;
        g[x][y]+=w;
    }

    for(int i=1;i<=5001;i++)
        for(int j=1;j<=5001;j++)
            g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];

    int res=0;
    for(int i=r;i<=5001;i++){
        for(int j=r;j<=5001;j++){
            res=max(res,g[i][j]-g[i-r][j]-g[i][j-r]+g[i-r][j-r]);
        }
    }
    printf("%d\n",res);
    return 0;
}



wyc1996
18小时前

算法:分治递归

时间复杂度:$T·\log_{4}{n}$

需要注意

(1)为了计算方便,将房屋的编号都减去1,编号从0开始
(2)0号和3号的坐标需要画图(或者用数学的方法)求出坐标变换

C++代码

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;
typedef long long LL;
typedef pair<int,int>PII;

PII get_location(int n,LL m)
{
    if(!n)return {0,0};
    //block 每一个子区间的标号的数量 len每个子区间边的长度
    LL block=1ll<<2*n-2,len=1ll<<n-1;

    //求出下一级的坐标
    auto p=get_location(n-1,m%block);

    int x=p.first,y=p.second;
    int z=m/block;

    //对四个区域进行坐标变换
    if(!z)return {y,x};
    else if(z==1)return {x,y+len};
    else if(z==2)return {x+len,y+len};
    return {2*len-1-y,len-1-x};
}

int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++){
        int n;
        LL a,b;
        cin>>n>>a>>b;
        auto p=get_location(n,a-1);
        auto q=get_location(n,b-1);
        double x=p.first-q.first;
        double y=p.second-q.second;
        printf("%.0lf\n",sqrt(x*x+y*y)*10);
    }
    return 0;
}



wyc1996
1天前

题目描述

假设现在有两个自然数A和B,S是$A^B$的所有约数之和。

请你求出S mod 9901的值是多少。

算法:分治递归

(1)将a进行质因数的分解(算数基本定理进行分解)
(2)利用约数之和的求解公式,分奇数和偶数对结果进行分治求解

时间复杂度:$\sqrt{(a)}·log(a·b)$

C++代码

#include<iostream>
#include<cstring>

using namespace std;
const int mod=9901;

//快速幂
int qmi(int a,int b,int p)
{
    int res=1;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

//按照项数为奇数还是偶数进行分治递归求解
int sum(int p,int k)
{
    if(k==1)return 1;
    if(k%2==0)return (1+qmi(p,k/2,mod))*sum(p,k/2)%mod;
    return (sum(p,k-1)+qmi(p,k-1,mod))%mod;
}

int main()
{
    int a,b;
    cin>>a>>b;
    int res=1;

    //进行质因数分解(算数基本定理)
    for(int i=2;i*i<=a;i++){
        if(a%i==0){
            int cnt=0;
            while(a%i==0){
                cnt++;
                a/=i;
            }
            res=res*sum(i,cnt*b+1)%mod;
        }        
    }
    if(a>1)res=res*sum(a,b+1)%mod;
    if(!a)res=0;
    cout<<res<<endl;
    return 0;
}



wyc1996
1天前

算法:递推

全局变量记录最优解
(1)先对第一行的操作进行所有情况的枚举
(2)从第一行开始对接下来的行进行递推(若g[i][j]=0,则必须要按g[i+1][j])
(3)由最后一行的状态进行判断,是否成功,成功则更新全局变量最优解

时间复杂度:$2^N·N^2·5·T$

在本题中N=5,T为多组测试数据,5为”十”字形的五个方向

C++代码

#include<iostream>
#include<cstring>

using namespace std;
const int N=6;
char g[N][N],backup[N][N];
int dx[5]={-1,0,1,0,0};
int dy[5]={0,1,0,-1,0};

void turn(int x,int y)
{
    for(int i=0;i<5;i++){
        int a=x+dx[i],b=y+dy[i];
        if(a<0 || a>=5 || b<0 || b>=5)continue;
        g[a][b]^=1;   // ASCII 特性决定
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        for(int i=0;i<5;i++)scanf("%s",backup[i]);

        int res=10;
        for(int op=0;op<32;op++){
            int cnt=0;
            memcpy(g,backup,sizeof g);

            for(int i=0;i<5;i++){
                if(op>>i&1){
                    turn(0,i);
                    cnt++;
                }
            }

            for(int i=0;i<4;i++){
                for(int j=0;j<5;j++){
                    if(g[i][j]=='0'){
                        turn(i+1,j);
                        cnt++;
                    }
                }
            }

            bool success=true;
            for(int i=0;i<5;i++){
                if(g[4][i]=='0'){
                    success=false;
                    break;
                }
            }
            if(success)res=min(res,cnt);
        }
        if(res>6)res=-1;
        printf("%d\n",res);
    }
    return 0;
}