PTA刷题笔记

2023年6月16日上午6:41 • 数据结构和算法 • 阅读 125

两周之内刷完GPLT L2和L3的题，持续更新，包括AK代码，坑点，和少量评论

PTA刷题记录

仓库地址: https://github.com/Haorical/Code/tree/master/PTA/GPLT

两周之内刷完GPLT L2和L3的题，持续更新，包括AK代码，坑点，和少量评论

用一周刷完了l2的40道题

刷题笔记

dj vis数组置为真
链表判空不用数量，判断结尾
注意数据类型比较，段错误可能int double比较/无限循环/数组给小了
指针定义时赋空
镜像树left right互换就行
union()时间过长建议不用
bfs入队判空
并查集有时不用路径压缩 Union
make_heap()
并查集查连通块很简单
lower_bound查找>=目标第一个元素 upper_bound >
set判断有无重复
sort() begin end
py sort()容易超时
注意yes no大小写
数组建树时注意递归结束条件

题目分类

dj最短路
模拟链表
简单贪心
二叉搜索树实现
set操作 set_intersection() set_union()使用
给两个遍历序列建树再层序遍历
并查集+结构体排序码量大
暴力模拟动态规划(过不了)
结构体排序
并查集
给两个遍历序列镜像建树
堆实现(小/大)
并查集/搜索求连通块
思维题 upper_bound()使用容器操作
简单模拟
搜索求连通块
思维题 sort()使用
多项式除法
模拟 map vector set使用
记忆化搜索
结构体排序
模拟链表
图邻接表存储
并查集
并查集/搜索求连通块
记忆化搜索
结构体排序
模拟
数学+模拟
map使用
记忆化搜索
栈使用
基础栈
恶心模拟
完全二叉树数组存储
模拟
栈+队列
记忆化搜索 vector排序
map+vector
简单模拟

题目

L2-001 紧急救援

简单的dj模板题

#include
using namespace std;
const int N=510;
const int INF=0x3fffffff;
int n,m,st,ed;
int G[N][N];
int d[N],w[N];
bool vis[N]={false};
vector pre[N];
void dj(int s){
    fill(d,d+N,INF);
    d[s]=0;
    for(int i=0;i path,tmp;
int mv=0,cnt=0;
void dfs(int u){
    if(u==st){
        cnt++;
        tmp.push_back(u);
        int ans=0;
        for(int i=0;imv){
            mv=ans;
            path=tmp;
        }
        tmp.pop_back();
        return;
    }
    tmp.push_back(u);
    for(int i=0;i>n>>m>>st>>ed;
    for(int i=0;i>w[i];
    }
    int t1,t2,t3;
    for(int i=0;i>t1>>t2>>t3;
        G[t1][t2]=G[t2][t1]=t3;
    }
    dj(st);
    dfs(ed);
    cout<=0;i--){
        cout<0) cout<

L2-002 链表去重

数组模拟链表，list存储链表

#include
using namespace std;
const int N=100010;
struct Node{
    int cur,next,data;
}node[N];
bool flag[N];
vector l1,l2;
int main(){
    int p,n;
    cin>>p>>n;
    int a;
    for(int i=0;i>a;
        cin>>node[a].data>>node[a].next;
        node[a].cur=a;
    }
    l1.push_back(node[p]);
    flag[abs(node[p].data)]=true;
    p=node[p].next;
    for(int i=p;i!=-1;){  //巨坑 不要判断节点个数 判断链表下一个地址是不是-1
        if(flag[abs(node[i].data)]==false){
            flag[abs(node[i].data)]=true;
            Node tp=l1.back(); //取最后节点
            l1.pop_back(); //弹出
            tp.next=node[i].cur; //更改上个节点的指针
            l1.push_back(tp);
            l1.push_back(node[i]);
        }else{
            if(!l2.empty()){ //判空
                Node tp=l2.back();
                l2.pop_back();
                tp.next=node[i].cur;
                l2.push_back(tp);
            }
            l2.push_back(node[i]);
        }
        i=node[i].next;
    }
    for(int i=0;i

L2-003 月饼

简单贪心

#include
using namespace std;
const int N=1010;
struct Node{
    double x,y; //测试点3 月饼数量可能为小数
    double a;
}nd[N];
int cmp(Node x,Node y){
    return x.a>y.a;
}
int main(){
    int n;
    double d; //段错误 int double类型比较造成
    cin>>n>>d;
    for(int i=0;i>nd[i].x;
    }
    for(int i=0;i>nd[i].y;
        nd[i].a=1.0*nd[i].y/nd[i].x;
    }
    sort(nd,nd+n,cmp);
    //cout<0){
        if(d>=nd[i].x){
            n--;
            d-=nd[i].x;
            ans+=nd[i].y;
        }else{
            ans+=d*nd[i].a;
            break;
            d=0;
        }
        if(n==0) break;
        i++;
    }
    printf("%.2f",ans);
    //system("pause");
    return 0;
}
//简单贪心

L2-004 这是二叉搜索树吗？

// 二叉搜索树
// 代码量比较大
#include
using namespace std;
struct node{
    int data;
    node *left,*right;
};
void insert(node* &root,int data){
    if(root==nullptr){
        root=new node;
        root->data=data;
        root->left=root->right=nullptr;
        return;
    }
    if(datadata) insert(root->left,data);
    else insert(root->right,data);
}
void preOrder(node *root,vector &v){
    if(root==nullptr) return;
    v.push_back(root->data);
    preOrder(root->left,v);
    preOrder(root->right,v);
}
void preOrder2(node *root,vector &v){
    if(root==nullptr) return;
    v.push_back(root->data);
    preOrder2(root->right,v);
    preOrder2(root->left,v);
}

void postOrder(node *root,vector &v){
    if(root==nullptr) return;
    postOrder(root->left,v);
    postOrder(root->right,v);
    v.push_back(root->data);
}

void postOrder2(node *root,vector &v){
    if(root==nullptr) return;
    postOrder2(root->right,v);
    postOrder2(root->left,v);
    v.push_back(root->data);
}
int main(){
    int n;
    cin>>n;
    vector v1,v2,v3;
    node *root=nullptr; //指针定义时一定要赋空指针
    int data;
    for(int i=0;i>data;
        v1.push_back(data);
        insert(root,data);
    }
    preOrder(root,v2);
    preOrder2(root,v3);
    if(v1==v2){ //原树的先序遍历
        cout<

L2-005 集合相似度

// 集合交集
#include
using namespace std;
int main(){
    int n;
    cin>>n;
    vector> v(n);
    for(int i=0;i s;
        int t,k;
        cin>>t;
        for(int j=0;j>k;
            s.insert(k);
        }
        v[i]=s;
    }
    int m;
    cin>>m;
    set s1,s2;
    for(int j=0;j>t1>>t2;
        t1--,t2--;
        set_intersection(v[t1].begin(),v[t1].end(),v[t2].begin(),v[t2].end(),inserter(s1,s1.begin())); //集合函数用法
        // set_union(v[t1].begin(),v[t1].end(),v[t2].begin(),v[t2].end(),inserter(s2,s2.begin()));
        int nc=s1.size(),nt=v[t1].size()+v[t2].size()-nc; //不用union就不会超时了
        double ans=1.0*nc/nt*100; //乘1.0
        printf("%.2f%%\n",ans);
    }
    system("pause");
    return 0;
}

L2-006 树的遍历

#include
using namespace std;
const int N=50;
struct node{
    int data;
    node *left,*right;
};
int pre[N],in[N],post[N];
int n;
node* create(int postL,int postR,int L,int R){ //建立二叉树
    if(postL>postR) return nullptr;
    node *root=new node;
    root->data=post[postR]; //后序数组最后是根节点
    int k;
    for(k=L;kleft=create(postL,postL+numLeft-1,L,k-1); //建立左子树 更新中序R=k-1
    root->right=create(postL+numLeft,postR-1,k+1,R);//建立右子树 更新中序L=k+1
    return root;
}
int num=0;
void bfs(node *root){
    queue q;
    q.push(root);
    while(!q.empty()){
        node* now=q.front();
        q.pop();
        num++;
        cout<data;
        if(numleft!=nullptr) q.push(now->left); //注意判空
        if(now->right!=nullptr) q.push(now->right);
    }
}
int main(){
    cin>>n;
    for(int i=0;i>post[i];
    }
    for(int i=0;i>in[i];
    }
    node *root=create(0,n-1,0,n-1);
    bfs(root);
    system("pause");
    return 0;
}

L2-007 家庭房产

L2-008 最长对称子串

#include
using namespace std;
const int N=1010;
char a[N];
int main(){
    cin.getline(a,N);
    int l=strlen(a);
    int ans=0;
    for(int i=0;i=0&&i+j=0&&i+j+1

L2-009 抢红包

//简单结构体排序
#include
using namespace std;
const int N=1e4+10;
struct node{
    int id,cnt;
    int y;
}nd[N];
int cmp(node a,node b){
    if(a.y==b.y){
        if(a.cnt==b.cnt){
            return a.idb.cnt;
    }else return a.y>b.y;
}
int main(){
    int n;
    cin>>n;
    int k;
    for(int i=1;i>k;
        int t1,t2;
        for(int j=0;j>t1>>t2;
            nd[t1].id=t1;
            nd[t1].y+=t2;
            nd[t1].cnt++;
            nd[i].y-=t2;
        }
    }
    sort(nd+1,nd+n+1,cmp);
    for(int i=1;i

L2-010 排座位

//感觉是并查集，就是并查集
#include
using namespace std;
const int N=110;
int f[N];
int flag[N][N];
int Find(int x){
    if(x==f[x]) return x;
    int a=Find(f[x]);
    return a;
}
void Union(int a,int b){
    a=Find(a);
    b=Find(b);
    if(a!=b) f[a]=b; //容易错
}
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i>t1>>t2>>t3;
        if(t3==1) Union(t1,t2);
        else flag[t1][t2]=flag[t2][t1]=1;
    }
    for(int i=0;i>t1>>t2;
        //cout<

L2-011 玩转二叉树

// 也是建树，和6题差不多，一遍过
#include
using namespace std;
const int N=50;
struct  node
{
    int data;
    node *left,*right;
};

int pre[N],in[N],n;

node* create(int pl,int pr,int l,int r){
    if(pl>pr) return nullptr; //return条件
    node *root=new node;
    root->data=pre[pl];
    int k;
    for(k=l;kright=create(pl+1,pl+len,l,k-1);
    root->left=create(pl+len+1,pr,k+1,r);
    return root;
}
int num=0;
void bfs(node* root){
    queue q;
    q.push(root);
    while(!q.empty()){
        node *now=q.front();
        q.pop();
        cout<data;
        num++;
        if(numleft!=nullptr) q.push(now->left);
        if(now->right!=nullptr) q.push(now->right);
    }
}
int main(){
    cin>>n;
    for(int i=0;i>in[i];
    }
    for(int i=0;i>pre[i];
    }
    node *root=create(0,n-1,0,n-1);
    bfs(root);
    system("pause");
    return 0;
}

L2-012 关于堆的判断

L2-013 红色警报

并查集实现

// 并查集通过查祖宗节点可以找到有几个集合，用来查连通块数量很好用
// 改成循环还是段错误，数组开小了
// 尝试搜索，csdn都用的dfs,不过bfs不是用来求连通块更好用吗？？？
#include
using namespace std;
const int N=510;
int n,m;
bool vis[N]={false};
int f[N];
struct node{
    int x,y;
}nd[10*N];//这里开小了，应该按m道路条数最大值开，不用城市数开。
void init(){
    for(int i=0;i>n>>m;
    init();
    for(int i=0;i>nd[i].x>>nd[i].y;
        Union(nd[i].x,nd[i].y);
    }
    int cnt1=count(),cnt2=0,cnt3=0;
    int k,u;
    cin>>k;
    while(k--){
        cin>>u;
        cnt3++;
        vis[u]=true;
        init();//每次都要初始化
        for(int i=0;i0) cout<

bfs实现

//尝试bfs搜索实现,我太nb了,一遍过
#include
using namespace std;
const int N=510;
vector v[N],lost;
bool inq[N]={false};
int n,m,k,u;
void bfs(int x){
    queue q;
    q.push(x);
    inq[x]=true; //inq队列，判断是否入过队，约等于有没有访问过
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=0;i>n>>m;
    int t1,t2;
    for(int i=0;i>t1>>t2;
        v[t1].push_back(t2);
        v[t2].push_back(t1);
    }
    int sum=0;
    for(int i=0;i>k;
    int ans,cnt3=0;
    while(k--){
        cnt3++;
        cin>>u;
        ans=0;
        memset(inq,0,sizeof(inq));//每次初始化
        lost.push_back(u);
        for(int i=0;i0) cout<

L2-014 列车调度

//类似模拟，维护了一个最小值集合的队列
//lower_bound查找>=目标第一个元素 upper_bound >
//这里用upper_bound
#include
using namespace std;
vector v;
int main(){
    int n;
    cin>>n;
    int t,cnt=0;
    for(int i=0;i>t;
        // 性质决定肯定是有序的，直接upper_bound看有没有更大中的最小值
        vector::iterator it=upper_bound(v.begin(),v.end(),t);
        if(it==v.end()){
            v.push_back(t);//没有直接插进去
            cnt++;
        }else{
            int j=it-v.begin();//有就替换掉
            v[j]=t;
        }
    }
    cout<

L2-015 互评成绩

// 简单模拟
#include
using namespace std;
const int N=1e4+10;
int a[N];
int n,k,m;
int main(){
    cin>>n>>k>>m;
    for(int i=0;i>t;
            a[i]+=t;
            t1=min(t1,t);
            t2=max(t2,t);
        }
        a[i]-=(t1+t2); //天才做法
    }
    sort(a,a+n,greater());
    for(int i=m-1;i>=0;i--){
        double d=1.0*a[i]/(k-2);
        printf("%.3f",d);
        if(i>0) cout<

L2-016 愿天下有情人都是失散多年的兄妹

//初看并查集？实际搜索，类似连通块
// 尝试bfs,实际上dfs更简洁
// 用下标表示id的时候，空间尽可能大
#include
using namespace std;
const int N=1e5+10;
bool inq[N]={false};
int n,k;
vector v1,v2;
struct node{
    int sex;
    int step;
    int fid,mid;
}nd[N];
vector bfs(int x){ //标准bfs
    queue q;
    vector v;
    v.push_back(x);
    q.push(x);
    nd[x].step=1;
    while (!q.empty()){
        int now=q.front();
        q.pop();
        if(nd[now].step==5) break;
        if(inq[nd[now].fid]==false&&nd[now].fid!=-1){
            q.push(nd[now].fid);
            inq[nd[now].fid]=true;
            nd[nd[now].fid].step=nd[now].step+1;
            v.push_back(nd[now].fid);
        }
        if(inq[nd[now].mid]==false&&nd[now].mid!=-1){
            q.push(nd[now].mid);
            inq[nd[now].mid]=true;
            nd[nd[now].mid].step=nd[now].step+1;
            v.push_back(nd[now].mid);
        }
    }
    return v;
}
int main(){
    cin>>n;
    int t1,t2,t3;
    char s;
    for(int i=0;i>t1>>s>>t2>>t3;
        nd[t1].sex=(s=='M'?1:0);
        nd[t1].fid=t2;
        if(t2!=-1) nd[t2].sex=1; //要标记父母性别
        nd[t1].mid=t3;
        if(t3!=-1) nd[t3].sex=0;
    }
    cin>>k;
    while(k--){
        cin>>t1>>t2;
        if(nd[t1].sex==nd[t2].sex){
            cout< s;
            int l1=v1.size();
            int l2=v2.size();
            for(int i=0;i0) cout<

L2-017 人以群分

// 思维题 sort会用就能过
#include
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i>a[i];
    }
    sort(a+1,a+n+1); //注意是否是0开始
    for(int i=1;idiff){
            diff=a[n]-2*a[aa+1];
            aa++;
        }
    }
    printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d",n-aa,aa,diff);
    system("pause");
    return 0;
}

L2-018 多项式A除以B

L2-019 悄悄关注

//简单模拟
#include
using namespace std;
const int N=5e3+10;
set s;
vector v,v1;
map m;
int main(){
    int n;
    string t1;
    cin>>n;
    for(int i=0;i>t1;
        s.insert(t1);
    }
    int k;
    cin>>k;
    int zz=k;
    int t2,sum=0;
    while(k--){
        cin>>t1>>t2;
        v.push_back(t1);
        m[t1]=t2;
        sum+=t2;
    }
    for(int i=0;is1&&zz*m[v[i]]>sum){
            v1.push_back(v[i]);
        }
    }
    if(v1.size()==0) cout<

用python很简单，但是最后一个样例超时了，我也不会优化，换成c++
a=input().split()
n=int(a[0])
del(a[0])
sum=0
k=int(input())
l1=[]
d1={}
for i in range(k):
    t1,t2=input().split()
    l1.append(t1)
    d1[t1]=int(t2)
    sum+=int(t2)
sum=sum/k
l2=[]
for i in l1:
    if i not in a and d1[i]>sum:
        l2.append(i)
l2.sort()
for i in l2:
    print(i,end=' ')

L2-020 功夫传人

// 并查集变形？
#include
using namespace std;
const int N=1e5+10;
int s[N];
int height[N];
int finds(int x){
    if(x==0) return 0;
    if(height[x]==0) height[x]=finds(s[x])+1; //记忆化搜索，没有的话，最后一个点会超时
    return height[x];
}
int main(){
    int n;
    double z,r;
    cin>>n>>z>>r;
    int k,t;
    double ans=0;
    for(int i=0;i>k;
        if(k==0){
            cin>>t;
            int sh=finds(i);
            double d=z*pow(1-r/100,sh)*t;
            ans+=d;
        }
        else{
            for(int j=0;j>t;
                s[t]=i;
            }
        }
    }
    cout<

L2-021 点赞狂魔

// 热身赛原题，考试时做出来了，结构体排序
#include
using namespace std;
const int N=110;
struct node{
    string name;
    int cnt;
    int avg;
}nd[N];
int cmp(node x,node y){
    if(x.cnt==y.cnt) return x.avgy.cnt;
}
int main(){
    int n,k,t;
    set s;
    cin>>n;
    for(int i=0;i>nd[i].name;
        cin>>k;
        for(int j=0;j>t;
            s.insert(t);
        }
        nd[i].cnt=s.size();
        nd[i].avg=k-nd[i].cnt;
    }
    sort(nd,nd+n,cmp);
    if(n==1) cout<

L2-022 重排链表

L2-023 图着色问题

//初看比较唬人，实际考图邻接表存储
#include
using namespace std;
const int N=1e5+10;
int v,e,k;
vector g[N];
set sss;
int color[N];
int main(){
    cin>>v>>e>>k;
    int t1,t2;
    for(int i=0;i>t1>>t2;
        g[t1].push_back(t2);
        g[t2].push_back(t1);
    }
    int n;
    cin>>n;
    while(n--){
        memset(color,0,sizeof(color));
        sss.clear();// 记得clear
        int flag=0;
        for(int j=1;j>color[j];
            sss.insert(color[j]);
        }
        if(sss.size()!=k) flag=1; // 必须就这几个颜色多了少了都不行
        if(!flag)
            for(int j=1;j0) cout<

L2-024 部落

//基础并查集
#include
using namespace std;
const int N=1e4+10;
int f[N],n=0;
bool vis[N]={false};
int findf(int x){
    if(x==f[x]) return x;
    f[x]=findf(f[x]);
    return f[x];
}
void unionf(int a,int b){
    a=findf(a);
    b=findf(b);
    if(a!=b) f[a]=b;
}

void init(){
    for(int i=1;i>k;
    while(k--){
        cin>>t1>>t2;
        vis[t2]=true;
        t1--;
        n=max(n,t2);
        while(t1--){
            cin>>t3;
            n=max(n,t3); //忘了写1 4测试点没过
            vis[t3]=true;
            unionf(t2,t3);
        }
    }
    int sum=0;
    for(int i=1;i>t1;
    while(t1--){{
        cin>>t2>>t3;
        if(findf(t2)==findf(t3)) cout<0) cout<

L2-025 分而治之

// 和13红色警戒那题差不多，求连通块，并查集，搜索都可以做
// 这里用的并查集码量少
#include
using namespace std;
const int N=1e5+10;
int f[N],n,m;
bool vis[N]={false};
struct node{
    int x,y;
}nd[N];
void init(){
    for(int i=1;i>n>>m;
    int t1,t2;
    for(int i=0;i>t1>>t2;
        nd[i].x=t1;
        nd[i].y=t2;
    }
    int k;
    cin>>k;
    while(k--){
        memset(vis,0,sizeof(vis));
        init();
        int t3;
        cin>>t3;
        for(int i=0;i>t2;
            vis[t2]=true;
        }
        for(int i=0;i0) cout<

L2-026 小字辈

// 记忆化搜索 和20题差不多
#include
using namespace std;
const int N=1e5+10;
int f[N],c[N];
vector v[N];
int dfs(int s){
    if(s==-1) return 0;
    if(c[s]==-1) c[s]=dfs(f[s])+1;
    return c[s];
}
int main(){
    int n,t;
    cin>>n;
    memset(c,-1,sizeof(c));
    for(int i=1;i>t;
        f[i]=t;
    }
    int sum=0;
    for(int i=1;i

L2-027 名人堂与代金券

// 记忆化搜索 和20题差不多
#include
using namespace std;
const int N=1e5+10;
int f[N],c[N];
vector v[N];
int dfs(int s){
    if(s==-1) return 0;
    if(c[s]==-1) c[s]=dfs(f[s])+1;
    return c[s];
}
int main(){
    int n,t;
    cin>>n;
    memset(c,-1,sizeof(c));
    for(int i=1;i>t;
        f[i]=t;
    }
    int sum=0;
    for(int i=1;i

L2-028 秀恩爱分得快

// 模拟 太恶心了，挂了几个测试点，考试的时候我绝对不会改的
// 得用字符串存，正确的我放后面了
// #include
// using namespace std;
// const int N=2010;
// double a[N][N];
// int tp[N];
// int main(){
//     int n,m,k;
//     cin>>n>>m;
//     while(m--){
//         cin>>k;
//         memset(tp,0,sizeof(tp));
//         for(int i=0;i>tp[i];
//         }
//         double tt=1.0/k;
//         for(int i=0;i>t1>>t2;
//     vector v1,v2;
//     double MAX,MAX1,MAX2;
//     MAX=MAX1=MAX2=a[t1+1000][t2+1000];
//     for(int i=0;iMAX1){
//             MAX1=a[t1+1000][i];
//             v1.clear();
//             v1.push_back(i-1000);
//         }else if(a[t1+1000][i]==MAX1){
//             v1.push_back(i-1000);
//         }
//     }

//     for(int i=0;iMAX2){
//             MAX2=a[t2+1000][i];
//             v2.clear();
//             v2.push_back(i-1000);
//         }else if(a[t2+1000][i]==MAX2){
//             v2.push_back(i-1000);
//         }
//     }
//     if(MAX1==MAX2&&MAX==MAX1) cout<0) sort(v1.begin(),v1.end(),greater());
//         else sort(v1.begin(),v1.end());
//         if(t2>0) sort(v2.begin(),v2.end(),greater());
//         else sort(v2.begin(),v2.end());
//         for(auto i:v1) cout<
using namespace std;
bool cmp(int a, int b){
    if(abs(a)==1000)return true;
    if(abs(b)==1000)return false;
    return abs(a)>n>>m;
    vector>photo(m);
    for(int i = 0; i < m; i++){
        int k;  cin>>k;
        for(int j = 0; j < k; j++){
            string s;  cin>>s;
            if(s=="0")s="1000";
            if(s=="-0")s="-1000";
            int tmp = stoi(s);
            photo[i].push_back(tmp);
            sex[abs(tmp)] = tmp;
        }
    }
    int cp[3];
    for(int i = 1; i >s;
        if(s=="0")s="1000";
        if(s=="-0")s="-1000";
        cp[i] = stoi(s);
    }
    //Search Photo
    double love[1010] = {0};
    for(int c = 1; c  >ans(3);
    for(int c = 1; c maxx[c]){
                    maxx[c] = love[i];
                    ans[c].clear();
                    ans[c].push_back(sex[i]);
                }else if(love[i]==maxx[c]){
                    ans[c].push_back(sex[i]);
                }
            }
        }
    }
    //cout<

L2-029 特立独行的幸福

#include
using namespace std;
const int N=1e4+10;
int l,r;
bool vis[N]={false};
bool vis2[N]={false};//设置两个vis数组
vector v[N];
bool isprime(int x){
    if(x==1) return false;
    for(int i=2;i s;
    int pre;
    while(1){
        pre=s.size();
        s.insert(x);
        if(s.size()==pre) return false;
        if(x==1) return true;
        x=f(x);
        v[t].push_back(x);
        vis[x]=true; //被求出来的一定是不独立的，标记
    }
}
int main(){
    cin>>l>>r;
    for(int i=l;i

L2-030 冰岛人

#include
using namespace std;
struct people{
    char sex;
    string father;
};
unordered_map p;
int judge(string a,string b){
    int i=1,j;
    for(string A=a;!A.empty();A=p[A].father,i++){
        j=1;
        for(string B=b;!B.empty();B=p[B].father,j++){
            if(i>=5&&j>=5) return 1;
            if(A==B&&(i>n;
    for(int i=0;i>a>>b;
        // 先名后姓
        // male 男 female 女
        if(b.back()=='n') p[a]={'m',b.substr(0,b.size()-4)};
        else if(b.back()=='r') p[a]={'f',b.substr(0,b.size()-7)}; // b.size() b.length not sizeof(b)
        else p[a].sex=b.back();
    }
    cin>>m;
    for(int i=0;i>a>>str>>b>>str; // 姓没用
        if(p.find(a)==p.end()||p.find(b)==p.end()) cout<> m;
    // for (int i = 0; i < m; i++) {
    //  cin >> a >> str >> b >> str;  //姓氏没有用
    //  if (people.find(a) == people.end() || people.find(b) == people.end())       printf("NA\n");
    //  else if (people[a].sex == people[b].sex)        printf("Whatever\n");
    //  else    printf("%s\n", judge(a, b) ? "Yes" : "No");
    // }

L2-031 深入虎穴

// 很直白的搜索 dfs bfs差不多 记忆化搜索。。
#include
using namespace std;
const int N=1e5+10;
// vector v[N];
// 貌似一个pre数组就可以 对每个节点遍历深度
int pre[N];
// 先找入口 用pre的话,入口都不用找
int height[N];

int geth(int s){
    if(s==-1) return 0;
    if(height[s]==0) height[s]=geth(pre[s])+1;
    return height[s];
}

int main(){
    int n;
    memset(pre,-1,sizeof(pre));
    cin>>n;
    int k,t;
    for(int i=1;i>k;
        while(k--){
            cin>>t;
            pre[t]=i;
        }
    }
    int u=-1,MAX=-1;
    for(int i=1;iMAX){
            MAX=geth(i);
            u=i;
        }
    }
    cout<

L2-032 彩虹瓶

// 初看栈使用 数据比较弱
#include
using namespace std;
const int N=1e3+10;
int a[N];

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    while(k--){
        stack s; //stack没有clear 直接重新定义
        int flag=0;
        memset(a,0,sizeof(a));
        int t1=1,t2;
        int cnt1=0;
        for(int i=1;i>a[i];
        }
        for(int i=1;im){ // 把=改成>就过了 下面写的都是对的
                    flag=1;
                    break;
                }
            }
            // int t3=-1;
            // if(!s.empty()) t3=s.top();
            // while(t3==t1){
            //     t1++;
            //     s.pop(); // pop之后size要-1
            //     cnt1--;
            //     if(s.empty()) break;
            //     t3=s.top();
            // }
        }
        if(flag){ cout<

L2-033 简单计算器

// 栈基础
#include
using namespace std;
int n;
stack s1;
stack s2;
int main(){
    cin>>n;
    int t1,d1,d2;
    char t2;
    for(int i=0;i>t1;
        s1.push(t1);
    }
    for(int i=0;i>t2;
        s2.push(t2);
    }
    while (!s2.empty())
    {
        d1=s1.top();
        s1.pop();
        d2=s1.top();
        s1.pop();
        t2=s2.top();
        s2.pop();
        if(t2=='+') s1.push(d1+d2);
        if(t2=='-') s1.push(d2-d1);
        if(t2=='*') s1.push(d1*d2);
        if(t2=='/') {if(d1==0){printf("ERROR: %d/0",d2); return 0;} s1.push(d2/d1); }
    }
    cout<

L2-034 口罩发放

L2-035 完全二叉树的层序遍历

//完全二叉树直接数组存
#include
using namespace std;
int n;
int tree[40];
void creat(int root){
    if(root>n) return; //注意递归结束条件
    creat(root*2);
    creat(root*2+1);
    cin>>tree[root];
}
int main(){
    cin>>n;
    creat(1);
    for(int i=1;i

L2-036 网红点打卡攻略

// 模拟
#include
using namespace std;
const int N=210;
int cost[N][N],r[N];
int main(){
    int n,m;
    cin>>n>>m;
    int t1,t2,t3;
    for(int i=0;i>t1>>t2>>t3;
        cost[t1][t2]=cost[t2][t1]=t3;
    }
    int k;
    cin>>k;
    int MIN=0x3fffffff,u=-1,cnt=0;
    for(int i=1;i s;
        int flag=0;
        cin>>t1;
        memset(r,-1,sizeof(r));
        r[0]=0;
        for(int j=1;j>r[j]; //标错下标了
        }
        r[t1+1]=0; //这里设置了结束后面就不用判断了
        int ans=0;
        for(int j=0;j

L2-037 包装机

// 栈、队列
#include
using namespace std;
queue q[110];
stack st;
map mp;
vector v;
void init(){
    for(int i=0;i>n>>m>>s;
    for(int i=1;i>str;
        for(int j=0;j>t){
        if(t==-1) break;
        if(t==0){
            if(!st.empty()) // 记得判空即可
            {
                t2=st.top();
                st.pop();
                v.push_back(t2);
            }
        }
        else{
            if(!q[t].empty()){ // 判空
                t1=q[t].front();
                q[t].pop();
                if(st.size()==s){
                    t2=st.top();
                    st.pop();
                    v.push_back(t2);
                }
                st.push(t1);
            }
        }
    }
    for(int i=0;i

L2-038 病毒溯源

// 一个pre数组的事 记忆化搜索
// vector 重载 < 直接用
#include
using namespace std;
const int N=1e4+10;
int pre[N];
int height[N];
int u=-1,MAX=-1;
vector vv;

int geth(int s){
    if(s==-1) return 0;
    if(height[s]==0) height[s]=geth(pre[s])+1;
    return height[s];
}

void dfs(int s,vector& _v){
    if(s==-1) return;
    dfs(pre[s],_v);
    _v.push_back(s);
}

int main(){
    int n,t1,t2;
    memset(pre,-1,sizeof(pre));
    cin>>n;
    for(int i=0;i>t1;
        for(int j=0;j>t2;
            pre[t2]=i;
        }
    }
    for(int i=0;iMAX){
            MAX=geth(i);
            vv.clear();
            vv.push_back(i);
        }else if(geth(i)==MAX){
            vv.push_back(i);
        }
    }
    cout<> ans;
    for(int i=0;i v;
        dfs(vv[i],v);
        ans.push_back(v);
    }
    sort(ans.begin(),ans.end());
    vector v=ans[0];
    for(int i=0;i

L2-039 清点代码库

// map vector
// map pair类型变量 类似结构体
// 用结构题存map 重载
using namespace std;
map,int> mp; // 只能用来统计数量，不能重载运算符
// 重新用node来保存
struct node
{
    vector v;
    int cnt;
};

vector v;

int cmp(node x,node y){
    if(x.cnt==y.cnt) return x.vy.cnt;
}
vector ans;
int main(){
    int n,m,t;
    cin>>n>>m;
    for(int i=0;i>t;
            v.push_back(t);
        }
        mp[v]++;
    }
    for(auto i:mp){
        node tn;
        tn.v=i.first;
        tn.cnt=i.second;
        ans.push_back(tn);
    }
    cout<

L2-040 哲哲打游戏

// 简单模拟
#include
using namespace std;
const int N=1e5+10;
vector v[N];
int ad[N];
int main(){
    int n,m,k,t;
    cin>>n>>m;
    for(int i=1;i>k;
        for(int j=0;j>t;
            v[i].push_back(t);
        }
    }
    int p,q;
    int now=1;
    for(int j=0;j>p>>q;
        if(p==0){
            now=v[now][q-1];
        }
        if(p==1){
            ad[q]=now;
            cout<

L3-001 凑零钱

L3-002 特殊堆栈

L3-003 社交集群

L3-004 肿瘤诊断

L3-005 垃圾箱分布

L3-006 迎风一刀斩

L3-007 天梯地图

L3-008 喊山

L3-009 长城

L3-010 是否完全二叉搜索树

// BST建立并判断完全二叉树
#include
using namespace std;
int n;
int maxn=1;
struct node{
    int nid; //用nid来模拟数组存数的下标
    int data;
    node *left,*right;
};
void insert(node* &root,int data){
    if(root==nullptr){
        root=new node;
        root->data=data;
        root->left=root->right=nullptr;
        return; // 记得return
    }
    if(data>root->data) insert(root->left,data);
    else insert(root->right,data);
}

int ans=0;
void bfs(node* root){
    queue q;
    root->nid=1;
    q.push(root);
    while (!q.empty())
    {
        node *now=q.front();
        q.pop();
        cout<data;
        ans++;
        if(ansleft!=nullptr){
            q.push(now->left);
            now->left->nid=now->nid*2; //nid*2
            maxn=max(now->left->nid,maxn);
        }
        if(now->right!=nullptr){
            q.push(now->right);
            now->right->nid=now->nid*2+1; //nid*2+1
            maxn=max(now->right->nid,maxn);
        }
    }
    // 写到这，不会判断是不是完全二叉树了
}
int main(){
    cin>>n;
    int t;
    node *root=nullptr;
    for(int i=0;i>t;
        insert(root,t);
    }
    bfs(root);
    cout<

L3-011 直捣黄龙

L3-012 水果忍者

L3-013 非常弹的球

L3-014 周游世界

L3-015 球队”食物链”

L3-016 二叉搜索树的结构

L3-017 森森快递

L3-018 森森美图

L3-019 代码排版

L3-020 至多删三个字符

L3-021 神坛

L3-022 地铁一日游

L3-023 计算图

L3-024 Oriol和David

L3-025 那就别担心了

L3-026 传送门

L3-027 可怜的复杂

L3-028 森森旅游

L3-029 还原文件

L3-030 可怜的简单题

Original: https://www.cnblogs.com/haorical/p/PTA_CODE.html
Author: haorical
Title: PTA刷题笔记

原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/621254/

转载文章受原作者版权保护。转载请注明原作者出处！

数据结构和算法

【自取】最近整理的，有需要可以领取学习：

Linux核心资料大放送~

全栈面试题汇总（持续更新&可下载）

一个提高学习100%效率的工具！

【超详细】深度学习面试题目！

LeetCode Python刷题答案下载！

LeetCode Java版刷题答案下载！

LeetCode C++ 版本，抓紧保存！

LeetCode GO语言刷题答案下载！

逻辑与“&&”和按位与“&”的区别

一、逻辑与（&&）：逻辑与的结果只有true和false，例如 5&&7 = true 5&&0 = false 二、按位与（&a…

数据结构和算法 2023年6月8日
00108
归并排序

跳转地址归并排序的重点是合并，利用双指针算法，排序的是否稳定是指如果两个数的大小相同，在经过排序后相对位置不变，那么这个排序就是稳定的，否则就是不稳定的归并排序的思路是将数组按…

数据结构和算法 2023年6月8日
00121
[数据结构-平衡树]普通 FHQ_Treap从入门到精通(注释比代码多系列)

芝士前置知识名内容一颗每个节点的左儿子val都比自己小,右儿子val都比自己大的树 Treap 堆和平衡树的结合(Tree+Heap),其中的pri变量满足堆的性质(父亲的比…

数据结构和算法 2023年6月7日
0083
字典树

（本篇仅代表本人自己的观点，请路过大佬勿喷）字典树，又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种，适用于实现字符串快速检索的多叉树，典型应用是用于统计，排序和保…

数据结构和算法 2023年6月8日
00135
UidGenerator springboot2集成篇

由于并没有提供springboot集成版本，网上找的都缺少必须步骤，我这里梳理一下详细的uid-generator与springboot2集成的步骤 uid-generator与s…

数据结构和算法 2023年6月7日
00107
关于 C++ 实现 sha256 以及导入库的注意事项

FishC 也发了：https://fishc.com.cn/thread-215914-1-1.html（好的文章从不需要精美的排版）首先我们要确定：我不会写也不想写 SHA2…

数据结构和算法 2023年6月8日
0096
题目1

题目描述小X和小C是一个演播厅的负责人。由于最近全市开展了”演讲的力量”的活动，导致小X和小C需要对1个演讲进行安排，但要注意，这个演讲会重复 (O) 次…

数据结构和算法 2023年6月8日
0080
springmvc controller自动打印出入参数以及打印其他有用信息

com.xxx包下加了@RestController注解的controller 打印的日志规格如下：包含：ip地址、url、全限定类名+方法名、请求时间、请求参数（支持多个）、响应…

数据结构和算法 2023年6月7日
0094
单调栈/单调队列入门详解

404. 抱歉，您访问的资源不存在。可能是网址有误，或者对应的内容被删除，或者处于私有状态。代码改变世界，联系邮箱 contact@cnblogs.com 园子的商业化努力-困…

数据结构和算法 2023年6月8日
00114
将博客搬至CSDN

本文作者：ztxcsl，使用署名-非商业性使用 4.0 国际进行许可 Original: https://www.cnblogs.com/ztxcsl/p/15880535.htm…

数据结构和算法 2023年6月12日
00109
【JS】112. 路径总和

代码 DFS var hasPathSum = function(root, targetSum) { //找到没有根了，那么就说明这条路行不通 if(!root){ return…

数据结构和算法 2023年6月8日
0093
Java中的Lambda表达式

Lambda来源于希腊字母入，发音为 /’læmdə/对高数有所了解的人都知道λ用于声明一个数学逻辑系统，表示根据XX的输入参数，会返回某个Y结果。这正是编程语言中函数…

数据结构和算法 2023年6月8日
0096
微信公众号/订阅号留言板使用介绍

前言由于新申请的微信公众号没有留言功能了，没有留言就无法跟读者进行互动，写出去的文章好像得不到反馈一样，像一个人的独角戏，感觉有蛮难受的，所以就制作了一个小程序用于留言，来代替原…

数据结构和算法 2023年6月16日
00175
DP 做题记录

(Problem:)你有 (A) 枚正能量骰子，(6) 个面分别显示的是 ([+1, +6]) 的值。你有 (B) 枚负能量骰子，(6) 个面分别显示的是 ([-6, -1]) 的…

数据结构和算法 2023年6月12日
0088
力扣算法JS LC [53. 最大子数组和] LC [122. 买卖股票的最佳时机 II]

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。示例 1：输入：nums = [-2…

数据结构和算法 2023年6月12日
0097
题解0008：棋盘游戏-uf0_金币灰黄

题目链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1451 （信奥一本通1451）题目描述：输入俩棋盘（4*4），一半黑子（…

数据结构和算法 2023年6月12日
0087

2024 年 5 月
一	二	三	四	五	六	日
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31