头像

床前明月光

东北烧烤大联盟


访客:1024

离线:2小时前



修改成注释中的样子就会segment fault ……

这道题为什么用char op[2];就能通过,而直接用char op;,然后把%s换成%c就过不了???

#include<iostream>
using namespace std;
const int N=100010;
int p[N];
int n,m;
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)p[i]=i;
    while(m--)
    {
        // char op;
        // int a,b;
        // scanf("%c %d %d",&op,&a,&b);
        // if(op=='M')p[find(a)]=find(b);
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='M')p[find(a)]=find(b);

        else
        {
            if(find(a)==find(b))puts("Yes");
            else puts("No");
        }
    }
    return 0;
}


活动打卡代码 AcWing 836. 合并集合

并查集能干什么?
1. 将两个集合合并;
2. 询问两个集合是否在一个集合当中
如果用暴力做法做以上两个问题,时间复杂度很高
用并查集时间复杂度近乎O(1)

做法
1. 用树的形式来存储两个集合(不一定是二叉树);
2. 根节点的编号代表集合的编号;
3. 每个节点要存储下来父节点的编号,p[x]表示x的父节点编号;
4. 查询每个点属于哪个集合,就找一下父节点,不是树根就继续向上找,直到找到树根为止

Q1:如何判断一个点是不是树根?
if(p[x]==x)
Q2:如何求x所在的集合编号?
while(p[x]!=x)x=p[x];
Q3:如何合并两个集合?
把一棵树插到另一棵树上,p[x]x的集合编号,p[y]y的集合编号,p[x]=y;

优化(路径压缩)(还有按秩合并,不过用到的较少)
对于Q2那一步的时间复杂度依旧很高。
改进方法:只要找到了一次根节点,那么就把这条路径上的所有点都指向根节点

#include<iostream>
using namespace std;
const int N=100010;
int p[N];//储存父节点
int find(int x)//返回x的根节点,同时路径压缩
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)p[i]=i;
    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='M')p[find(a)]=find(b);
        else
        {
            if(find(a)==find(b))puts("Yes");
            else puts("No");
        }
    }

    return 0;
}

PS:为什么用char op[2]来读取操作而不是直接用char op;
因为用%s能直接过滤掉前边输入的回车,%c不行;
%c也可以用,但是要注意所有的scanf()末尾都要加上\n

scanf()char op,%c来进行读取

#include<iostream>
using namespace std;
const int N=100010;
int p[N];
int n,m;
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d\n",&n,&m);
    for(int i=1;i<=n;++i)p[i]=i;
    while(m--)
    {
        char op;
        int a,b;
        scanf("%c%d%d\n",&op,&a,&b);
        if(op=='M')p[find(a)]=find(b);
        else
        {
            if(find(a)==find(b))puts("Yes");
            else puts("No");
        }
    }

    return 0;
}


活动打卡代码 AcWing 826. 单链表

用数组模拟链表

#include<iostream>

using namespace std;
const int N=100010;
//head:头节点的下标
//e[i]:节点i的值
//ne[i]:节点i的next的下标
//idx:存储当前要用到的点
int head,e[N],ne[N],idx;
int m;

void init()//初始化
{
    head=-1;
    idx=0;
}

void add_to_head(int x)//将x插到头节点
{
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}

void add(int k,int x)//将x插入到下标为k的点的后面
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}

void del(int k)//删除第k个节点后面的节点
{
    ne[k]=ne[ne[k]];
}

int main()
{
    cin>>m;
    init();
    while(m--)
    {
        char op;
        cin>>op;
        int x,k;
        if(op=='H')
        {
            cin>>x;
            add_to_head(x);
        }
        else if(op=='D')
        {
            cin>>k;
            if(!k)head=ne[head];
            else del(k-1);//这里我感觉是要加个else的
        }
        else
        {
            cin>>k>>x;
            add(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i])cout<<e[i]<<' ';

    return 0;
}

删除操作那里我觉得是要加个else的,否则会出现ne[-1]的情况

scanf()char op;的版本
注意处理%c前面可能存在的回车

#include<iostream>
using namespace std;
const int N=100010;
int e[N],ne[N],head;
int idx;
int m;
void init()
{
    head=-1;
    idx=0;
}
void add_to_head(int x)
{
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}
void del(int k)
{
    ne[k]=ne[ne[k]];
}

void add(int k,int x)
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}

int main()
{
    scanf("%d\n",&m);
    init();
    while(m--)
    {
        char op;
        scanf("%c",&op);
        int k,x;
        if(op=='H')
        {
            scanf("%d\n",&x);
            add_to_head(x);
        }
        else if(op=='D')
        {
            scanf("%d\n",&k);
            if(!k)head=ne[head];
            else del(k-1);
        }
        else 
        {
            scanf("%d%d\n",&k,&x);
            add(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i])printf("%d ",e[i]);

    return 0;
}


活动打卡代码 AcWing 838. 堆排序

什么是堆?

#include<iostream>
#include<algorithm>
using namespace std;

const int N=100020;
int n,m;
int h[N],cnt;//用‘size’当变量名有可能会报错……

void down(int u)
{
    int t=u;
    if(u*2<=cnt&&h[u*2]<h[t])t=u*2;//注意这里‘&&’连接的两端不能交换判断顺序
    if(u*2+1<=cnt&&h[u*2+1]<h[t])t=u*2+1;//否则有可能会发生越界
    if(u!=t)
    {
        swap(h[u],h[t]);
        down(t);//递归下一层
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&h[i]);
    cnt=n;
    //建堆,时间复杂度 O(n)
    for(int i=n/2;i;--i)down(i);//为什么从n/2的位置开始?
    while(m--)
    {
        printf("%d ",h[1]);
        h[1]=h[cnt--];
        down(1);
    }

    return 0;
}

为什么是n/2???
1.因为我们要从最后一个有儿子的节点开始down(x);
2.堆一共有n个节点,由定义可知,n号元素是最后一个元素,那么他的父亲也就是最后一个有儿子的节点,而n号元素的父亲下标刚好是n/2,所以从n/2开始down(x).

为什么这样建堆时间复杂度是O(n)
假设堆是一个节点为n的满二叉树,从倒数第二层开始down(x),则倒数第二层的n/4个节点都要down(x)一层,倒数第三层的n/8个节点要down(x)两层……以此类推,则以上的所有的节点down(x)完有:
$$ S=n\times(\frac{1}{2^2}+\frac{2}{2^3}+\frac{3}{2^4}+\frac{4}{2^5}…………) $$
由错位相减可得:
$$ 2S=n\times(\frac{1}{2^1}+\frac{2}{2^2}+\frac{3}{2^3}+\frac{4}{2^4}…………) $$
$$ S=2S-S=n\times(\frac{1}{2^1}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}…………) $$
$$ <n\times(\frac{1}{2^1}\times\frac{1-\frac{1}{2^{(n+1)}}}{1-\frac{1}{2^1}}) $$
$$ =n\times(1-\frac{1}{2^{(n+1)}})<n=O(n) $$




AcWing 838. 堆排序
一、堆的功能
1. 插入一个数;
2. 求集合当中的最小值;
3. 删除最小值;
4. 删除任意一个元素(STL无法直接做到);
5. 修改任意一个元素(STL无法直接做到);

二、什么是堆
1. 完全二叉树;
2. 小根堆,每个点都小于等于左右儿子;
3. 每个点都是以自己为根的子树的最小值;

三、堆的存储
一维数组, 一号元素是根节点,x的左儿子:2xx的右儿子:2x+1(完全二叉树状的数据结构都这么存)

四、堆的操作
1. down(x),可以把节点往下移,把大的值与左右儿子里最小的那个进行交换;
2. up(x),可以把节点往上移,把小的值往上移进行交换;
3. 在堆的末尾插入一个值:heap[size++]=x,up(size),最小值heap[1]
4. 删除最小值,用堆的最后一个元素覆盖第一个元素,heap[1]=heap[size],size--,down(1),(因为尾节点比头节点更容易删除);
5. 删除任意一个元素,heap[k]=heap[size],size--,down(k),up(k);
6. 修改任意一个元素,heap[k]=x,down(x),up(x);

PS:下标如果从0开始,那么左儿子2x也是0,会发生冲突

acwing 838代码




本题排序是升序,所以堆排序用最大堆,在排序过程中,走m次后,堆后面的数字是m个最大的数字,且已经按升序排列好了,同时前方堆顶元素为未排序区的最大值

进行下一次堆排时,要找到第一个比堆顶小的元素,也就是未排序区的最后一个元素,进行交换,同时维护未排序区的堆
堆?(以小根堆为例,大根堆则反之)
AcWing 838. 堆排序

#include<iostream>
using namespace std;

const int N=110;
int a[N],b[N];
int n;
void down(int u,int size)
{
    int t=u;
    if(u*2<=size&&b[t]<b[u*2])t=u*2;
    if(u*2+1<=size&&b[t]<b[u*2+1])t=u*2+1;

    if(t!=u)
    {
        swap(b[t],b[u]);
        down(t,size);
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)cin>>b[i];
    int p=2;
    while(p<=n&&b[p]>=b[p-1])p++;
    int k=p;
    while(p<=n&&a[p]==b[p])p++;
    if(p==n+1)
    {
        puts("Insertion Sort");
        while(k>1&&b[k]<b[k-1])swap(b[k],b[k-1]),k--;
    }
    else
    {
        puts("Heap Sort");
        p=n;
        while(b[1]<=b[p])p--;
        swap(b[1],b[p]);
        down(1,p-1);
    }

    cout<<b[1];
    for(int i=2;i<=n;++i)cout<<' '<<b[i];

    return 0;
}



#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k;
struct Student
{
    string id;
    int scores[6]={-2,-2,-2,-2,-2,-2};
    int total_score=0;
    int cnt=0,sum=0;
    int rank;
    bool operator<(const Student& t)const
    {
        if(total_score!=t.total_score)return total_score>t.total_score;
        if(sum!=t.sum)return sum>t.sum;
        return id<t.id;
    }
};

vector<Student>grades;
unordered_map<string,Student>students;

int main()
{
    scanf("%d %d %d",&n,&k,&m);
    int a[k+10];
    for(int i=1;i<=k;++i)scanf("%d",&a[i]);
    for(int i=0;i<m;++i)
    {
        char user_id[10];
        int problem_id,score;
        scanf("%s %d %d",user_id,&problem_id,&score);
        students[user_id].id=user_id;
        if(students[user_id].scores[problem_id]<score)
        {
            if(score==-1)students[user_id].scores[problem_id]=0;
            else students[user_id].scores[problem_id]=score,students[user_id].cnt++;
            if(score==a[problem_id])students[user_id].sum++;
        }
    }
    char s[n+10][10];
    for(int i=1;i<=n;++i)sprintf(s[i],"%05d",i);
    for(int i=1;i<=n;++i)if(students.count(s[i]))grades.push_back(students[s[i]]);
    for(int i=0;i<grades.size();++i)
    {
        for(int j=1;j<=k;++j)
            if(grades[i].scores[j]!=-1&&grades[i].scores[j]!=-2)
            {
                grades[i].total_score+=grades[i].scores[j];
            }
    }
    sort(grades.begin(),grades.end());
    for(int i=0;i<grades.size();++i)
        if(!i||grades[i].total_score!=grades[i-1].total_score)grades[i].rank=i+1;
        else grades[i].rank=grades[i-1].rank;
    for(int i=0;i<grades.size();++i)
    {
        if(grades[i].cnt!=0)
        {
            printf("%d %s %d",grades[i].rank,grades[i].id.c_str(),grades[i].total_score);
            for(int j=1;j<=k;++j)
                if(grades[i].scores[j]!=-1&&grades[i].scores[j]!=-2)printf(" %d",grades[i].scores[j]);
                else printf(" -");
            printf("\n");
        }
    }

    return 0;
}


活动打卡代码 AcWing 1561. PAT 评测

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;;

const int K=6;
int p_score[K];
int n,k,m;
struct Student
{
    string id;
    int grade[K];
    int total,cnt;
    Student(){}
    Student(string _id):id(_id)//构造函数
    {
        for(int i=1;i<=k;++i)grade[i]=-2;
        total=cnt=0;
    }
    void calc()//满分题的个数,同时计算总分
    {
        for(int i=1;i<=k;++i)
        {
            total+=max(0,grade[i]);
            if(grade[i]==p_score[i])cnt++;
        }
    }
    bool has_submit()//是否有编译通过的题目
    {
        for(int i=1;i<=k;++i)
            if(grade[i]>=0)return true;
        return false;
    }
    bool operator<(const Student& t)const
    {
        if(total!=t.total)return total>t.total;
        if(cnt!=t.cnt)return cnt>t.cnt;
        return id<t.id;
    }
};
vector<Student>res;
unordered_map<string,Student>students;
int main()
{
    cin>>n>>k>>m;
    for(int i=1;i<=k;++i)cin>>p_score[i];
    while(m--)
    {
        string u_id;
        int p_id,grade;
        cin>>u_id>>p_id>>grade;
        if(students.count(u_id)==0)students[u_id]=Student(u_id);
        students[u_id].grade[p_id]=max(students[u_id].grade[p_id],grade);
    }
    for(auto& item:students)
    {
        auto& s=item.second;
        if(s.has_submit())
        {
            s.calc();
            res.push_back(s);
        }
    }
    sort(res.begin(),res.end());
    for(int i=0,rank=1;i<res.size();++i)
    {
        if(i&&res[i].total!=res[i-1].total)rank=i+1;
        cout<<rank<<' '<<res[i].id<<' '<<res[i].total;

        for(int j=1;j<=k;++j)
            if(res[i].grade[j]==-2)cout<<" -";
            else cout<<' '<<max(0,res[i].grade[j]);
        cout<<endl;
    }

    return 0;
}

整整提交了三十次才过,考虑问题还是不够全面

另外,我才发现acwing的调试模式,能读的数据量是有限的…………

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k;
struct Student
{
    string id;
    int scores[6]={-2,-2,-2,-2,-2,-2};
    int total_score=0;
    int cnt=0,sum=0;
    int rank;
    bool operator<(const Student& t)const
    {
        if(total_score!=t.total_score)return total_score>t.total_score;
        if(sum!=t.sum)return sum>t.sum;
        return id<t.id;
    }
};

vector<Student>grades;
unordered_map<string,Student>students;

int main()
{
    scanf("%d %d %d",&n,&k,&m);
    int a[k+10];
    for(int i=1;i<=k;++i)scanf("%d",&a[i]);
    for(int i=0;i<m;++i)
    {
        char user_id[10];
        int problem_id,score;
        scanf("%s %d %d",user_id,&problem_id,&score);
        students[user_id].id=user_id;
        if(students[user_id].scores[problem_id]<score)
        {
            if(score==-1)students[user_id].scores[problem_id]=0;
            else students[user_id].scores[problem_id]=score,students[user_id].cnt++;
            if(score==a[problem_id])students[user_id].sum++;
        }
    }
    char s[n+10][10];
    for(int i=1;i<=n;++i)sprintf(s[i],"%05d",i);
    for(int i=1;i<=n;++i)if(students.count(s[i]))grades.push_back(students[s[i]]);
    for(int i=0;i<grades.size();++i)
    {
        for(int j=1;j<=k;++j)
            if(grades[i].scores[j]!=-1&&grades[i].scores[j]!=-2)
            {
                grades[i].total_score+=grades[i].scores[j];
            }
    }
    sort(grades.begin(),grades.end());
    for(int i=0;i<grades.size();++i)
        if(!i||grades[i].total_score!=grades[i-1].total_score)grades[i].rank=i+1;
        else grades[i].rank=grades[i-1].rank;
    for(int i=0;i<grades.size();++i)
    {
        if(grades[i].cnt!=0)
        {
            printf("%d %s %d",grades[i].rank,grades[i].id.c_str(),grades[i].total_score);
            for(int j=1;j<=k;++j)
                if(grades[i].scores[j]!=-1&&grades[i].scores[j]!=-2)printf(" %d",grades[i].scores[j]);
                else printf(" -");
            printf("\n");
        }
    }

    return 0;
}


活动打卡代码 AcWing 1538. 链表排序

本题先将结构体存入map,然后存入vector,方便排序,在此不使用数组模拟链表
(一般做图论问题时用数组模拟链表)

#include<iostream>
#include<unordered_map>
#include<algorithm>
#include<vector>
using namespace std;

struct Node
{
    string address;
    int key;
    string next;

    bool operator<(const Node& t)const
    {
        return key<t.key;
    }
};
vector<Node>nodes;
unordered_map<string,Node>map;
int main()
{
    int n;
    char head[10];
    scanf("%d %s",&n,head);
    while(n--)
    {
        char address[10],next[10];
        int key;
        scanf("%s%d%s",address,&key,next);
        map[address]={address,key,next};
    }

    for(string i=head;i!="-1";i=map[i].next)nodes.push_back(map[i]);
    printf("%d ",nodes.size());
    if(nodes.empty())puts("-1");
    else
    {
        sort(nodes.begin(),nodes.end());
        printf("%s\n",nodes[0].address.c_str());
        for(int i=0;i<nodes.size();++i)
        {
            if(i+1==nodes.size())
                printf("%s %d -1\n",nodes[i].address.c_str(),nodes[i].key);
            else        
                printf("%s %d %s\n",nodes[i].address.c_str(),nodes[i].key,nodes[i+1].address.c_str());
        }
    }
    return 0;
}

数组模拟单链表(y总基础班讲的数组模拟)




如果你已经安装了numpy,先使用pip命令 “pip uninstall numpy”(这条如果不行可以百度一下其他命令)将其卸载,然后进入pycharm,file->settings->project interpreter->点击 ‘+’ ,然后查找numpy,安装即可。希望对你有帮助!

其他模块或者包的安装也可如法炮制