1.6PTA集练7-5~7-24、7-1、7-2,堆的操作,部落冲突(二分查找)

发布时间:2024年01月09日

7-5 大師と仙人との奇遇 分数 20

#include<iostream>
#include<queue>
using namespace std;
int n;
long long ans=0,num;
priority_queue<long long,vector<long long>,greater<long long>>q;//记录之前买的,用小顶堆,最上面就是最小的
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>num;
        while(!q.empty()&&q.top()<num){
            ans+=(num-q.top());
            q.pop();
        }//先卖掉之前的
        if(i!=n)q.push(num);
    }
    while(!q.empty()){
        ans+=(num-q.top());
        q.pop();
    }
    cout<<ans;
    return 0;
}

?采用优先队列,每天,输入一个数,然后检测之前买的股票能不能在今天卖出去,即堆顶元素和今天的比较,不过记得比较之前要保证队列不空,今天卖完后就把今天的股票买进队列里,最后一天不买

然后最后的时候把所以股票都卖掉

7-6 插入排序 分数 10

#include<iostream>
using namespace std;
int n,arr[101];
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>arr[i];
    for(int i=1;i<n;i++){//表示要插入的元素
        int j=i-1,temp=arr[i];
        while(j>=0&&arr[j]>temp){
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=temp;
        for(int k=0;k<n;k++){
            cout<<arr[k];
            if(k!=n-1)cout<<" ";
        }
        if(i!=n-1)cout<<endl;
    }
    return 0;
}

调整牌堆时,是和插入的新牌比较,如果比它大,就把这张牌往后移,即arr[j+1]=arr[j]

while终止时,j=-1越界,或者指向第一个比他小的元素,这张牌是不应该在这里的,所以就放在后面即j+1的位置上?

7-7 冒泡排序 分数 15

#include<iostream>
using namespace std;
int n,arr[101];
void swap(int i,int j){
    int temp=arr[j];
    arr[j]=arr[i];
    arr[i]=temp;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>arr[i];
    for(int i=n-1;i>0;i--){//表示冒泡的天花板
        bool flag=false;//每次都建立一个标志,标志是否从发生了交换,如果没有的话就说明已经排序完成
        for(int j=0;j<i;j++){//表示冒泡的起点,每次都是从最底端开始冒泡
            if(arr[j]>arr[j+1]){
                swap(j,j+1);
                flag=1;//发生了排序交换
            }
        }
        if(flag){for(int k=0;k<n;k++){
            cout<<arr[k];
            if(k!=n-1)cout<<" ";
        }//只有发生了改变才打印
        if(i!=1)cout<<endl;}else{
            break;//没有的话就直接退出
        }
    }
    return 0;
}

冒泡排序的话,每次确定一个天花板,因为在冒泡的过程中,是最大的元素不断到最大的位置上,所以最大的位置就不用再逐一判断了

然后冒泡都是从最底端开始冒泡,遍历到此时的天花板上,由于这一特性,冒泡排序将会使每次循环都会交换元素,如果一旦有一次没交换元素,那就说明排序已经终止

这一点在插入排序中不适用?

7-8 小球装箱游戏 分数 200

每个球箱的数量一样多,是严格的限制

那就是先排序,然后加入

#include<iostream>
#include<algorithm>
using namespace std;
int n,br=0,bg=0,tr=0,tg=0;
struct node{
    int num,type;
}arr[100005];
bool cmp(node a,node b){
    if(a.num!=b.num){
        return a.num<b.num;
    }else{
        return a.type>b.type;
    }
}
int main(){
    cin>>n;//
    for(int i=1;i<=n;i++){
        cin>>arr[i].num>>arr[i].type;
        if(arr[i].type){
            tg++;
        }else{
            tr++;
        }
    }
    sort(arr+1,arr+n+1,cmp);
    for(int i=1;i<=n/2;i++){
        if(arr[i].type){
            bg++;
        }else{
            br++;
        }
    }
    cout<<tr-br<<" "<<tg-bg<<endl;
    cout<<br<<" "<<bg;
    return 0;
}

7-9 二路归并排序 分数 10

在归并中,先判断是不是为空(不存在),然后是不是递归底层(这里是不做处理,因为只有一个元素),接着就是做递归处理,处理完后进行操作,这个操作就是进行合并,即所谓分治法,向下递归是分,然后“治”,合并。

求叶子结点数量以及树的高度也都是分治的思路

处理到文件尾,就是在while里cin>>n

#include<iostream>
using namespace std;
int n,arr[101];
void merge(int begin,int end){
    if(begin>=end)return;
    int i=begin,j=begin,mid=(begin+end)>>1,k=mid+1;
    int temp[101];
    merge(begin,mid);
    merge(k,end);
    while(j<=mid&&k<=end){
        if(arr[j]<=arr[k]){
            temp[i++]=arr[j++];
        }else{
            temp[i++]=arr[k++];
        }
    }
    while(j<=mid){temp[i++]=arr[j++];}
    while(k<=end){temp[i++]=arr[k++];}
    for(int i=begin;i<=end;i++)arr[i]=temp[i];
        for(int i=0;i<n;i++){
            cout<<arr[i];
            if(i!=n-1)cout<<" ";
        }
    if(begin!=0||end!=n-1)cout<<endl;
}
int main(){
    while(cin>>n){
        for(int i=0;i<n;i++)cin>>arr[i];
        merge(0,n-1);
        cout<<endl;
    }
    return 0;
}

还需要注意的是,递归过程的打印,递归处理是栈的过程,即先到后出,

即最上层的是最后打印的,所谓最后打印就是最后才会结束所有本层的递归语句,即最后是打印

检测是不是最上层,就是检测左右区间,只有左右都是端点,才是最上层,不然的话就分行

7-10 成绩排名 分数 50

注意sort函数是左闭右开的,即处理左边的元素(是处理的第一个元素),不处理右边的元素(是不处理的第一个元素)

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct node{
    int ch,math,id;
}arr[100005];
bool cmp(node a,node b){
    if(a.ch!=b.ch){
        return a.ch>b.ch;
    }else if(a.math!=b.math){
        return a.math>b.math;
    }else{
        return a.id<b.id;
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i].id>>arr[i].ch>>arr[i].math;
    }
    sort(arr+1,arr+n+1,cmp);
    for(int i=1;i<=n;i++)cout<<arr[i].id<<endl;
    return 0;
}

7-11 根据后序序列和中序序列确定二叉树 分数 10

一种写法是递归函数参数是子树大小以及起点,另一种是参数是起点与终点

下面是起点与终点,有问题版

#include<iostream>
using namespace std;
int n,post[12],in[12];
struct node{
    int val;
    node*lchild,*rchild;
    node(int x):val(x),lchild(nullptr),rchild(nullptr){}
};
node* func(int pend,int pbegin,int iend,int ibegin){
    if(iend<ibegin)return nullptr;
    if(iend==ibegin){
        node* root=new node(in[iend]);
        return root;
    }
    int rindex;//根节点在中序的位置,同时也是左子树大小
    for(rindex=ibegin;rindex<=iend;rindex++){
        if(in[rindex]==post[pend]){
            break;
        }
    }
    node* root=new node(post[pend]);
    root->lchild=func(pbegin+rindex-1,pbegin,rindex-1,ibegin);
    root->rchild=func(pend-1,pbegin+rindex,iend,rindex+1);
    return root;
}
int h(node*root){
    if(!root)return 0;
    if(!root->lchild&&!root->rchild)return 1;
    return max(h(root->lchild),h(root->rchild))+1;
}
void pre(node*root){
    if(!root)return;
    cout<<root->val<<" ";
    pre(root->lchild);
    pre(root->rchild);
}
int main(){
    while(cin>>n){
        for(int i=1;i<=n;i++)cin>>post[i];
        for(int i=1;i<=n;i++)cin>>in[i];
        node*root=func(n,1,n,1);
        cout<<h(root)<<" ";
        pre(root);
        cout<<endl;
    }
    return 0;
}

下面这个是没问题的,问题出在了,直接认为根节点在中序中的位置就是此时左子树的大小,实际上并不是,只有当此时中序起点为0时,这个下标才是此时左子树的大小,不然左子树大小就是根节点下标减去中序起点?

#include<iostream>
using namespace std;
int n,post[12],in[12];
struct node{
    int val;
    node*lchild,*rchild;
    node(int x):val(x),lchild(nullptr),rchild(nullptr){}
};
node* func(int pend,int pbegin,int iend,int ibegin){
    if(iend<ibegin)return nullptr;
    if(iend==ibegin){
        node* root=new node(in[iend]);
        return root;
    }
    int rindex;//根节点在中序的位置
    for(rindex=ibegin;rindex<=iend;rindex++){
        if(in[rindex]==post[pend]){
            break;
        }
    }
    node* root=new node(post[pend]);
    int lsize=rindex-ibegin;
    root->lchild=func(pbegin+lsize-1,pbegin,rindex-1,ibegin);
    root->rchild=func(pend-1,pbegin+lsize,iend,rindex+1);
    return root;
}
int h(node*root){
    if(!root)return 0;
    if(!root->lchild&&!root->rchild)return 1;
    return max(h(root->lchild),h(root->rchild))+1;
}
void pre(node*root){
    if(!root)return;
    cout<<" "<<root->val;
    pre(root->lchild);
    pre(root->rchild);
}
int main(){
    while(cin>>n){
        for(int i=1;i<=n;i++)cin>>post[i];
        for(int i=1;i<=n;i++)cin>>in[i];
        node*root=func(n,1,n,1);
        cout<<h(root);
        pre(root);
        cout<<endl;
    }
    return 0;
}

在递归中,依然是先判断空,然后判断递归底层,再就是递归处理部分

减法的理解

还有就是减法的细节,给定区间端点i,j的话,j-i是j和i之间的差距,可以看成j和i之间棍子的数量

另一种看法是i和j之间的端点数量,是只包含1个端点以及中间所有端点的数量

j-i+1是包含两个区间端点的

在这里,求左子树的大小,左端点是序列起点,右端点是根节点位置,显然左端点在左子树里,右端点不在左子树里,所以减法是左子树大小=根节点位置-序列起点,即只包含区间的一个端点的元素数量,即把根节点排除在外的区间元素数量,即左子树大小

然后是要去确定左右子树的后序中序的起点与终点,就是依据子树大小来确定判断,+1-1的细节靠子树大小去试

这里需要注意,递归参数是左右都闭的,也就是说左右是严格包含的,意思就是说这个划定好的端点结点是严格处于左右子树里的(依据左子树大小去判断具体下标),

此时通过左子树大小判断时,就要采用右端点-左端点+1,因为是严格包含在子树里的,所以左右端点都被包含

上面的求法,思路是通过后序起点,然后利用左子树大小,使出来是这个数,

或者由上面减法的理解,左子树的大小也可以是左端点到根节点之间棍子的数量,而如果要定位到根节点的前一个结点,就只需要减少一个棍子,也就是p+l-1就代表右端点,p+l代表根节点位置,是第一个不在左子树里的元素的位置

即求size的大小是减法的元素数量只含一个端点的理解,求具体的下标是棍子间隔的理解?

最后注意输出格式,如果不要每行末尾的空格,空格就改成这样输出

即先输出空格再输出元素就行?

7-12 哈夫曼树 分数 25

相比于直接构造哈夫曼树以及获得哈夫曼编码还是弱了一点

#include<iostream>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int>>q;
int n,num,ans=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>num;
        q.push(num);
    }
    while(q.size()>1){
        int num1=q.top();
        q.pop();
        int num2=q.top();
        q.pop();
        ans+=(num1+num2);
        q.push(num1+num2);
    }
    cout<<ans;
    return 0;
}

思路还是优先队列,通过优先队列来完成有规则的递归,在处理过程中就进行了每步的ans+=,完成了对ans的修改,即同一份数据会在处理过程中不断的被加,如果够小的话,而不用建完树后再对它进行处理去求路径长度

7-13 堆的操作 分数 20

#include<iostream>
using namespace std;
int n,k,arr[1005],cnt=0,id,num,m;
void swap(int i,int j){
    int temp=arr[j];
    arr[j]=arr[i];
    arr[i]=temp;
}
void up(int index){
    int par=index/2;
    while(par>=1){
        if(arr[par]>arr[index]){
            swap(par,index);
            index=par;
            par=index/2;
        }else{
            break;
        }
    }
}
void down(int index){
    int lc=2*index;
    while(lc<=cnt){
        if(lc+1<=cnt){
            lc=arr[lc]<arr[lc+1]?lc:lc+1;
        }
        if(arr[index]>arr[lc]){
            swap(index,lc);
            index=lc;
            lc=index*2;
        }else{
            break;
        }
    }
}
void insert(int x){
    if(cnt>=n)return;
    arr[++cnt]=x;
    up(cnt);
}
void del(){
    swap(1,cnt--);
    down(1);
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        cin>>id;
        if(id==1){
            cin>>num;
            insert(num);
        }else{
            del();
        }
        for(int j=1;j<=cnt;j++){
            cout<<arr[j];
            if(j!= cnt)cout<<" ";
        }
        cout<<endl;
    }
    cin>>m;
    for(int i=1;i<=m;i++)cin>>arr[i];
    cnt=m;
    for(int i=m/2;i>=1;i--){
        down(i);
    }
    for(int i=1;i<=m;i++){
        cout<<arr[i];
        if(i!=m)cout<<" ";
    }
    return 0;
}

上调操作?

?

就是从当前的位置往上找,下标从1开始的话,父母结点就是index/2;

然后操作终止的条件就是没有父母结点,即往上就没有了,即par>=1,只要还有父母结点,就还可能继续操作;然后能够继续上调的标志就是父母比自己大(因为要小顶堆),那就交换,然后更新孩子与父母,继续向上调整,直到不能,或者?没有父母,自己就已经是最小的

下调操作

下调的话可能有两个路径,选那个最小的路径换上来,

能够继续操作的前提是存在孩子结点,首先左孩子是最小的,所以迭代是要让左孩子不越界,接着判断是否存在右孩子,如果存在的话判断出一个最小的,然后尝试与此时的父结点交换,如果能换的话,说明可以继续向下,更新父节点与孩子结点,不然就说明最小的孩子都比此时的父节点大,那么已经满足堆的要求了,就不用再调整了

插入与删除?

在插入的时候有细节就是如果此时堆已经满了的话,就不继续插入,直接返回了,所以需要加一个判断是cnt>=n

如果可以继续插入,就在新位置上放入元素,然后尝试把这个元素往上调整即可

对于删除,是取出堆顶元素,然后就是要让最后的元素放在堆顶上,然后把这个元素往下调整即可

在插入删除时,都要记得对cnt进行相应的操作?

然后是第二部分,快速建堆,此时输入m后记得要更新堆的大小为m,不更新的话保留的依然是上个堆的大小?

朴素建堆就是插入一个就上移调整一个,快速建堆是先都放好,放好后再从最后一个非叶子结点开始调整,进行向下调整,往回往上走,这样的话到上面时,下面的都已经满足了堆的要求

即朴素建堆主要用上调,快速建堆主要用向下调整

7-14 堆的建立 分数 20

说的是调整已经存在的N个元素,所以采用快速建堆

#include<iostream>
using namespace std;
int n,arrmin[10005],arrmax[10005];
void swap(int&i,int&j){
    int temp=i;
    i=j;
    j=temp;
}
void downmin(int index){
    int c=index*2;
    while(c<=n){
        if(c+1<=n){
            c=arrmin[c]<arrmin[c+1]?c:c+1;
        }
        if(arrmin[index]>arrmin[c]){
            swap(arrmin[index],arrmin[c]);
            index=c;
            c=index*2;
        }else{
            break;
        }
    }
}
void downmax(int index){
    int c=index*2;
    while(c<=n){
        if(c+1<=n){
            c=arrmax[c]>arrmax[c+1]?c:c+1;
        }
        if(arrmax[index]<arrmax[c]){
            swap(arrmax[index],arrmax[c]);
            index=c;
            c=index*2;
        }else{
            break;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arrmin[i];
        arrmax[i]=arrmin[i];
    }
    for(int i=n/2;i>=1;i--){
        downmin(i);
        downmax(i);
    }
    for(int i=1;i<=n;i++){
        cout<<arrmax[i];
        if(i!=n)cout<<" ";
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        cout<<arrmin[i];
        if(i!=n)cout<<" ";
    }
    return 0;
}

7-15 折半(二分)查找 分数 20

#include<iostream>
#include<algorithm>
using namespace std;
int n,arr[100005],tar,l,r;
int search(int tar,int l,int r){
    if(l>r)return -1;
    int left=l,right=r,mid=(left+right)>>1;
    while(left<=right){//只要区间里还有元素就可以继续操作
        if(arr[mid]==tar){return mid;}
        else if(arr[mid]<tar){
            left=mid+1;
        }else{
            right=mid-1;
        }
        mid=(left+right)>>1;
    }
    return -1;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    sort(arr,arr+n);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>tar>>l>>r;
        cout<<search(tar,l,r)<<endl;
    }
    return 0;
}

这个查找,先判断是不是空,即l>r,

然后在迭代中,判断能否继续操作,操作的前题是区间里还有元素,即left<=right,然后就是找

如果刚好就返回,小于目标值就往右找,大于目标值就往左找,

后面两种情况由于已经判断过了中间端点,所以在下一轮查找中直接舍弃掉,即查找的过程包含两个区间端点,?

7-16 部落冲突 分数 40

去求每个坐标位置对应的左边的面积,然后去找一个与总面积的一半最接近的位置,而且还要满足左边的大于总的减去左边的,即左边和总的一半的差值必须不是负的,必须是0或者正

要求

#include<iostream>
#include<queue>
using namespace std;
struct node{
    int begin,end,h;
}arr[105];
struct cmp{
    bool operator()(node a,node b){
        return a.begin>b.begin;
    }
}
priority_queue<node,vector<node>,cmp>q;
int n,x,y,w,h,tot=0,maxx=0,minx=1e8;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y>>w>>h;
        arr[i].begin=x;//也就是说绿洲的终止点是在x+w,100处
        arr[i].end=x+w;//端点数量是w+1,但是长度是w,就是连接的棍子数量
        arr[i].h=h;
        maxx=max(maxx,arr[i].end);
        tot+=w*h;
        q.push(arr[i]);
    }
    for(int i=arr[i].begin;i<=maxx;i++){
        int cnt=0;
        while(q.top()<i){
            
        }
    }
    return 0;
}

先按起点从小到大排,然后遍历每个绿洲,如果加上这个绿洲面积不比一般大,那就直接加,并直接下一个

上面的思路是类似于前缀和的,但是由于在输入的时候,左端点与右端点都不知道,所以就很难搞,

可解决

这里就是直接不预处理了,直接二分,在二分的过程中去计算

每次计算都遍历所有的部落,

时间复杂度应该是nlogm的一个级别

上面前缀和的话,每次输入就处理,处理的复杂度是nm差不多,再二分查找,是logm

好像还是在二分过程中去计算会好一点

这个之所以能直接二分,就是是左边累加,一直往右,就是左边面积是递增的,即使不处理也是这样,所以干脆就先不处理了,省去了处理的时间,而是只关注需要的,想要的点的信息,需要的时候就通过Get来计算得到

#include <iostream>
#include <vector>
#include <algorithm>
#include<stack>
#include<queue>
#include <unordered_set>
using namespace std;
#define ll long long
const int N = 105;
struct node {
    int l, r, w, h;
}s[N];
int n;
ll getd(int mid) {
    ll sl = 0, sr = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i].r <= mid) {
            sl += (ll)s[i].w * s[i].h;
        }
        else if (s[i].l >= mid) {
            sr += (ll)s[i].w * s[i].h;
        }
        else {
            sl += (ll)s[i].h * (mid - s[i].l);
            sr += (ll)s[i].h * (s[i].r - mid);
        }
    }
    return sl - sr;
}
//就是说,地图上有很多块,然后划一条线,使这条线上所有左侧的块都归属于A
//剩下的都给B,然后要让A>>B
//自左到右,累积的岛屿面积是不断增加的
//也就是说每个x坐标轴都对应一个值,这个值就是自左到右的岛屿面积,类似于分布函数
 
int main() {
    cin >> n;
    int R = 0, L = 1000;
    for (int i = 1; i <= n; i++) {
        int x, y, w, h;
        cin >> x >> y >> w >> h;
        s[i].l = x, s[i].r = x + w, s[i].w = w, s[i].h = h;
        R = max(R, s[i].r);
        L = min(L, s[i].l);
    }
    int ans = -1;
    ll da = 1e10;
    while (L <= R) {
        int mid = (L + R) >> 1;
        ll t = getd(mid);
        if (t < 0) {
            L = mid + 1;
        }
        else {
            da = min(da, t);
            R = mid - 1;
            ans = mid;
        }
    }
  //  while (ans < R && getd(ans + 1) == da) {
    //    ans++;
    //}
    cout << ans;
    return 0;
}
 
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,x,y,w,h,l=1e8,r=0,ans;
struct node{
    int begin,end,h;
    long long s;
}arr[105];
long long tot=0;
long long gets(int index){
    long long sl=0;
    for(int i=1;i<=n;i++){
        if(arr[i].end<=index){
            sl+=arr[i].s;
        }else if(arr[i].begin<index){
            sl+=(long long)(index-arr[i].begin)*h;
        }
    }
    return sl*2-tot;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y>>w>>h;
        arr[i].begin=x,arr[i].end=x+w,arr[i].h=h,arr[i].s=w*h;
        l=min(l,x),r=max(r,x+w);
        tot+=arr[i].s;
    }
    while(l<=r){
        int mid=(l+r)>>1;
        long long ds=gets(mid);
        if(ds<0){
            l=mid+1;
        }else{
            r=mid-1;
            ans=mid;
        }
    }
    cout<<ans;
    return 0;
}
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,x,y,w,h,l=1e8,r=0,ans;
struct node{
    int begin,end,h;
    long long s;
}arr[105];
long long gets(int index){
    long long sl=0,sr=0;
    for(int i=1;i<=n;i++){
        if(arr[i].end<=index){
            sl+=arr[i].s;
        }else if(arr[i].begin>=index){
            sr+=arr[i].s;
        }else{
            sl+=(long long)(index-arr[i].begin)*arr[i].h;
            sr+=(long long)(arr[i].end-index)*arr[i].h;
        }
    }
    return sl-sr;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y>>w>>h;
        arr[i].begin=x,arr[i].end=x+w,arr[i].h=h,arr[i].s=(long long)w*h;
        l=min(l,x),r=max(r,x+w);
    }
    while(l<=r){
        int mid=(l+r)>>1;
        long long ds=gets(mid);
        if(ds<0){
            l=mid+1;
        }else{
            r=mid-1;
            ans=mid;
        }
    }
    cout<<ans;
    return 0;
}

经过排查发现,问题就出现在数据范围上,就是Longlong ,

首先一定要开long long,?然后涉及Longlong的数据类型,如果是从Int型转过来的,也一定要开Longlong

还有就是longlong*2容易直接爆掉,所以还得是缓行,不能随便的乘,容易爆

这也是(left+right)>>1和left+(right-left)>>1等价,但是保险写后面的原因,因为写前面的话,如果数据比较大,就会爆掉出错

?

总之,这题的思路就是记录范围的左边与右边,然后开始二分查找,使面积差最小,小于0是不能接收的,大于0的话,就尝试继续找,只要还能继续找,就有可能继续缩小这个差距,从而找到最小的面积差

7-17 判断是否二叉排序树 分数 10

#include<iostream>
#include<string>
using namespace std;
    string s;
    int index=0;
struct node{
    int val;
    node*lchild,*rchild;
    node(int x):val(x),lchild(nullptr),rchild(nullptr){}
};
node* cr(){
    if(index>=s.size())return nullptr;
    if(s[index]=='*')return nullptr;
    node* root=new node(s[index++]-'0');
    root->lchild=cr();
    root->rchild=cr();
    return root;
}
bool isbst(node*root){
    if(!root)return true;
    if(!root->rchild&&!root->lchild)return true;
    if(root->rchild&&root->val>root->rchild->val)return false;
    if(root->lchild&&root->val<root->lchild->val)return false;
    return isbst(root->rchild)&&isbst(root->lchild);
}
int main(){
    node*root;
    while(cin>>s){
        index=0;
        node*root=cr();
        if(isbst(root))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

主要是建树的细节 以及处理到文件尾的操作

采用输入string,然后对string做处理从而完成建树

这里需要注意,index表示跟踪现在这个字符串建树建到哪了,每建一个结点,index就往后移一位,表示此时的结点已经被建立了,由于给的是先序的字符串,所以是先建,再递归左右,

递归依旧是,判断是否为空,然后是否为底层,是否满足条件,然后递归处理,本层处理

在每次时,都要把index游标重新置0?

至于BST的判断逻辑,就是是否为空,是否为底层,

再就是每层的判断以及向下递归的部分

每层判断,如果有右孩子且比它大就是错的;有左孩子比他小就是错的,其它都是正确的,就递归向下,保证子树也都是BST即可?

7-18 整型关键字的散列映射?分数 25

#include<iostream>
using namespace std;
int n,p,arr[11000],num;
int main(){
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>num;
        int index=num%p;
        if(!arr[index]){
            arr[index]=num;
            cout<<index;
        }else{
            while(arr[index]&&arr[index]!=num){
                index=(index+1)%p;
            }
            arr[index]=num;
            cout<<index;
        }
        if(i!=n)cout<<" ";
    }
    return 0;
}

就是先计算一下对应的下标,然后计算一下对应的哈希值,如果对应位置没有,就插入,不然的话就进行冲突处理,进行线性冲突处理,然后注意存储范围是模p,即0~p-1,所以就是需要注意一下处理后的坐标在这个范围内,所以index=(index+1)%p;

还有需要注意的一点是,要加入的元素可能有重复的,这也就是说哈希表里不能存重复相同的元素,而arr[index]只能够判断当前格子有没有被占用,不能判断是否和此时要插入的元素相同,所以就是要新增一个判断arr[index]!=num才行,如果不满足这个的话,也会退出循环

即这个while出来的时候,要么是第一个还没被占用的格子,要么是第一个已经存储过的相同元素

7-19 数据结构实验三 图的深度优先搜索 分数 50

#include<iostream>
using namespace std;
int n,m,u,v,g[25][25],cnt=0;
bool vis[25]={0};
void dfs(int u){
    cout<<u<<" ";
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        if(g[u][i]){
            vis[i]=1;
            dfs(i);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        g[u][v]=g[v][u]=1;
    }
    for(int i=0;i<n;i++){
        if(!vis[i]){
            vis[i]=1;
            cnt++;
            dfs(i);
        }
    }
    cout<<endl<<cnt<<endl<<m;
    return 0;
}

用bool类型的vis记录每个结点的访问情况,如果访问过就不继续访问,不然的话就dfs它,下一层在它的基础上进行访问,邻接矩阵可以保证是字典序的访问顺序

在外层,用cnt去记录联通分支数

7-20 抓住那头牛 分数 25

#include<iostream>
#include<queue>
using namespace std;
int n,k,t;
bool vis[100005]={0};
queue<pair<int,int>>q;
int main(){
    cin>>n>>k;
    vis[n]=1;
    q.push({n,0});
    while(!q.empty()){
        int cur=q.front().first;
        t=q.front().second;
        q.pop();
        if(cur==k)break;
        if(cur*2<=100000&&!vis[cur*2]){
            q.push({cur*2,t+1});
            vis[cur*2]=1;
        }
        if(cur-1>=0&&!vis[cur-1]){
            q.push({cur-1,t+1});
            vis[cur-1]=1;
        }
        if(cur+1<=100000&&!vis[cur+1]){
            q.push({cur+1,t+1});
            vis[cur+1]=1;
        }

    }
    cout<<t;
    return 0;
}

为了防止未访问的结点在同一层(上层)中处理后会发生重复入队的情况,所以就是在入队的时候就对vis做操作,而不是在出队处理时再更改vis操作,这样可以保证在上层有多个结点可到达下层同一结点时,会只入队一个结点,从而减少了时间的复杂度

另外就是注意入队时,对下标的控制,即在合法范围内,不会出界,在遍历的时候,即只有下个位置的坐标处于0和1E5之间才会被考虑,否则不入队,直到遍历BFS搜索到目标点

7-21 任务拓扑排序 分数 10

这里就是注意要是字典序

直接层序不行,用邻接矩阵也不行,因为在上层当中,如果有大编号结点的入度比较小,先被减为0了,同时存在小编号结点,同样在上层,但是是后续被减为0的,那么在下一层当中,就会优先去访问那个大编号结点,而不是小编号结点,从而打破了字典序

即建立在层序上的,不能保证为字典序

所以应该是要用优先队列,以小顶堆,编号最小建堆,这样无论是第几层解锁到的结点,都会被优先访问从而保证字典序

#include<iostream>
#include<queue>
using namespace std;
int n,e,in[105],g[105][105],u,v,ans[105],cnt=0;
priority_queue<int,vector<int>,greater<int>>q;
bool vis[105]={0};
int main(){
    cin>>n>>e;
    for(int i=0;i<n;i++)in[i]=0;
    for(int i=1;i<=e;i++){
        cin>>u>>v;
        g[u][v]=1;
        in[v]++;
    }
    for(int i=0;i<n;i++){
        if(!in[i]){
            q.push(i);
            vis[i]=1;
        }
    }
    while(!q.empty()){
        int cur=q.top();
        ans[++cnt]=cur;
        q.pop();
        for(int i=0;i<n;i++){
            if(g[cur][i]&&!vis[i]){
                in[i]--;
                if(!in[i]){
                    vis[i]=1;
                    q.push(i);
                }
            }
        }
    }
    if(cnt==n){
        for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
    }else{
        cout<<"unworkable project";
    }
    return 0;
}

7-22 信使 分数 100

堆优化

#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>>q;
int n,m,cnt=0,u,v,w,dis[105],ans=-1,head[105];
bool vis[105];
struct edge{
    int v,next,w;
}e[1000005];
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)dis[i]=1e8;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    vis[1]=1;
    for(int i=head[1];i;i=e[i].next){
        dis[e[i].v]=e[i].w;
        q.push({e[i].w,e[i].v});
    }
    while(!q.empty()){
        int tar=q.top().second,d=q.top().first;
        q.pop();
        if(vis[tar])continue;
        vis[tar]=1;
        for(int i=head[tar];i;i=e[i].next){
            if(dis[e[i].v]>d+e[i].w){
                dis[e[i].v]=d+e[i].w;
                q.push({d+e[i].w,e[i].v});
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,dis[i]);
    }
    if(ans>=1e8){cout<<-1;}
    else cout<<ans;
    return 0;
}

这部分是链式前向星,注意cnt是边的编号,head记录该起点的第一个边的编号,然后每个边记录下一条边的编号?

接着是堆的定义,这里定义数对,gretaer优先判断第一个数,然后相同时再判断编号

就是第一个是距离,第二个是编号,记得typedef后面要加;

还有就是边,边的结构体数组要开大点?

初始入队,?

入队不会确定结点,只有从优先队列中取出元素时才会确定被访问过,也就是说,当一个结点被访问过时,队列中可能还会存在这个元素,

注意注意,这里vis放的位置和之前那个有所不同,之前那个7-20,是严格的层序,因为是要最早遇到,所以就要避免同一层上,重复的访问到某些结点,所以在第一次遇到的时候,就要vis,因为已经确定到可以访问了,即入队时就Vis

而至于这个有优先顺序的,只有在出队时才会被确定真正访问到,这里就是出队时才vis,这也是拓扑排序要字典序时,在出队时vis,而不是入队时Vis,如果是任意的随便都行

dis始终保持为此时最小的距离

7-23 校园最短路径 分数 10

#include<iostream>
#include<queue>
#include<string>
using namespace std;
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii>>q;
int n,m,w,cnt=0,head[100],pre[100],dis[100];
bool vis[100]={0};
string s,s2;
struct node{
    int v,w,next;
}e[10000];
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void path(int index){
    if(pre[index]==-1){
        cout<<s[index];
        return;
    }
    path(pre[index]);
    cout<<"->"<<s[index];
}
int main(){
    cin>>n>>m>>s;
    for(int i=0;i<n;i++)dis[i]=1e8;
    for(int i=1;i<=m;i++){
        cin>>s2>>w;
        add(s.find(s2[0]),s.find(s2[1]),w);
        add(s.find(s2[1]),s.find(s2[0]),w);
    }
    vis[0]=1,dis[0]=0,pre[0]=-1;
    for(int i=head[0];i;i=e[i].next){
        dis[e[i].v]=e[i].w;
        q.push({e[i].w,e[i].v});
    }
    while(!q.empty()){
        int tar=q.top().second;
        q.pop();
        if(vis[tar])continue;
        vis[tar]=1;
        for(int i=head[tar];i;i=e[i].next){
            if(dis[e[i].v]>dis[tar]+e[i].w){
                dis[e[i].v]=dis[tar]+e[i].w;
                q.push({dis[e[i].v],e[i].v});
                pre[e[i].v]=tar;
            }
        }
    }
    for(int i=0;i<n;i++){
        if(dis[i]>=1e8){
            cout<<"dist[A]["<<s[i]<<"]="<<256<<endl;
            cout<<s[i]<<endl;
        }else{
            cout<<"dist[A]["<<s[i]<<"]="<<dis[i]<<endl;
            path(i);
            cout<<endl;
        }
    }
    return 0;
}

7-24 最小生成树-kruskal算法 分数 15

#include<iostream>
#include<algorithm>
using namespace std;
struct edge{
    int u,v,w;
}e[405];
int n,m,fa[25];
int find(int x){
    if(fa[x]==x){return x;}
    fa[x]=find(fa[x]);
    return fa[x];
}
bool cmp(edge a, edge b){
    return a.w<b.w;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(find(e[i].u)==find(e[i].v))continue;
        fa[find(e[i].u)]=find(e[i].v);
        cout<<min(e[i].u,e[i].v)<<","<<max(e[i].u,e[i].v)<<","<<e[i].w<<endl;
    }
    return 0;
}

用并查集,合并的时候注意是合并根节点,其它就没什么了?

?7-1 冰雹猜想。 分数 10

#include<iostream>
using namespace std;
int n,cnt=0;
int main(){
    cin>>n;
    while(n!=1){
        cout<<n<<" ";
        if(!(n%2)){
            n=n/2;
        }else{
            n=n*3+1;
        }
        cnt++;
    }
    cout<<1<<endl<<"count = "<<cnt+1;
    return 0;
}

这个题目有点问题,变化的次数输出要注意多1次?

7-2 输入正整数n,打印图形。 分数 10

#include<iostream>
using namespace std;
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n-1;i++){
        for(int j=1;j<=n-i;j++){
            cout<<" ";
        }
        for(int j=1;j<=2*i-1;j++){
            cout<<"*";
        }
        for(int j=1;j<=n-i;j++){
            cout<<" ";
        }
        cout<<endl;
    }
    for(int i=1;i<=2*n-1;i++)cout<<"*";
    cout<<endl;
    for(int i=n-1;i>=1;i--){
        for(int j=1;j<=n-i;j++){
            cout<<" ";
        }
        for(int j=1;j<=2*i-1;j++){
            cout<<"*";
        }
        for(int j=1;j<=n-i;j++){
            cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}

文章来源:https://blog.csdn.net/m0_73553411/article/details/135423480
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。