PTA刷题记录

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

用一周刷完了 l2 的 40 道题

感想

今天天梯赛结束了简单总结-200 +0 分

题目很难，感觉远胜去年，题面太长，有的感觉表述的不是很清晰

模拟很多，本来 l1 很快就做完了，感觉还挺简单，虽然 l1-7 掉了一个点，但不影响大局，然后就被 l2-1 模拟卡了半小时还不过，果断 l2-2，简单结构体排序，掉了 2 个点，之后看 3 和 4，3 不会，看了半天没看懂样例，考前刷了一堆二叉树感觉挺简单的，这个直接寄了，最后用了 20 分钟把剩下的题看完了（只是看完了），因为知道没戏了，直接开摆了，4 是个 flyoad，也看了半天样例，发现不会。l3 的题考前还打算看看能不能混几分，第一题体面又很长，看了半天，拓扑排序。不会，然后看第二个 dfs，这个我熟，一看逆序，没背过模板又不会了，最后剩了 5 分钟看了看 l2-1，还是没过样例，最后 116 收场，属实太垃圾了。

刷题笔记

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<bits/stdc++.h>
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<int> pre[N];
void dj(int s){
    fill(d,d+N,INF);
    d[s]=0;
    for(int i=0;i<n;i++){
        int u=-1,MIN=INF;
        for(int j=0;j<n;j++){
            if(vis[j]==false&&d[j]<MIN){
                MIN=d[j];
                u=j;
            }
        }
        if(u==-1) return;
        vis[u]=true; //又忘了
        for(int v=0;v<n;v++){
            if(vis[v]==false){
                if(d[u]+G[u][v]==d[v]){
                    pre[v].push_back(u);
                }else if(d[u]+G[u][v]<d[v]){
                    pre[v].clear();
                    pre[v].push_back(u);
                    d[v]=d[u]+G[u][v];
                }
            }
        }
    }
}
vector<int> 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;i<tmp.size();i++){
            ans+=w[tmp[i]];
        }
        if(ans>mv){
            mv=ans;
            path=tmp;
        }
        tmp.pop_back();
        return;
    }
    tmp.push_back(u);
    for(int i=0;i<pre[u].size();i++){
        dfs(pre[u][i]);
    }
    tmp.pop_back();
}

int main(){
    fill(G[0],G[0]+N*N,INF);
    cin>>n>>m>>st>>ed;
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    int t1,t2,t3;
    for(int i=0;i<m;i++){
        cin>>t1>>t2>>t3;
        G[t1][t2]=G[t2][t1]=t3;
    }
    dj(st);
    dfs(ed);
    cout<<cnt<<" "<<mv<<endl;
    for(int i=path.size()-1;i>=0;i--){
        cout<<path[i];
        if(i>0) cout<<" ";
    }
    system("pause");
    return 0;
}

L2-002 链表去重

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

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct Node{
    int cur,next,data;
}node[N];
bool flag[N];
vector<Node> l1,l2;
int main(){
    int p,n;
    cin>>p>>n;
    int a;
    for(int i=0;i<n;i++){
        cin>>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<l1.size()-1;i++){
        printf("%05d %d %05d\n",l1[i].cur,l1[i].data,l1[i].next);
    }
    Node t1=l1.back();
    printf("%05d %d %d\n",t1.cur,t1.data,-1);
    if(!l2.empty()){ //判空
    for(int i=0;i<l2.size()-1;i++){
        printf("%05d %d %05d\n",l2[i].cur,l2[i].data,l2[i].next);
    }
    t1=l2.back();
    printf("%05d %d %d",t1.cur,t1.data,-1);}
    system("pause");
    return 0;
}

L2-003 月饼

简单贪心

#include<bits/stdc++.h>
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<n;i++){
        cin>>nd[i].x;
    }
    for(int i=0;i<n;i++){
        cin>>nd[i].y;
        nd[i].a=1.0*nd[i].y/nd[i].x;
    }
    sort(nd,nd+n,cmp);
    //cout<<nd[0].x;
    double ans=0;
    int i=0;
    while(d>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<bits/stdc++.h>
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(data<root->data) insert(root->left,data);
    else insert(root->right,data);
}
void preOrder(node *root,vector<int> &v){
    if(root==nullptr) return;
    v.push_back(root->data);
    preOrder(root->left,v);
    preOrder(root->right,v);
}
void preOrder2(node *root,vector<int> &v){
    if(root==nullptr) return;
    v.push_back(root->data);
    preOrder2(root->right,v);
    preOrder2(root->left,v);
}

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

void postOrder2(node *root,vector<int> &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<int> v1,v2,v3;
    node *root=nullptr; //指针定义时一定要赋空指针
    int data;
    for(int i=0;i<n;i++){
        cin>>data;
        v1.push_back(data);
        insert(root,data);
    }
    preOrder(root,v2);
    preOrder2(root,v3);
    if(v1==v2){ //原树的先序遍历
        cout<<"YES\n";
        v1.clear();
        postOrder(root,v1);
        for(int i=0;i<n;i++){
            cout<<v1[i];
            if(i<n-1) cout<<" ";
        }
    }else if(v1==v3){ //镜像树的先序遍历
        cout<<"YES\n";
        v1.clear();
        postOrder2(root,v1);//对镜像树后序遍历
        for(int i=0;i<n;i++){
            cout<<v1[i];
            if(i<n-1) cout<<" ";
        }
    }
    else cout<<"NO";
    system("pause");
    return 0;
}

L2-005 集合相似度

// 集合交集
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<set<int>> v(n);
    for(int i=0;i<n;i++){
        set<int> s;
        int t,k;
        cin>>t;
        for(int j=0;j<t;j++){
            cin>>k;
            s.insert(k);
        }
        v[i]=s;
    }
    int m;
    cin>>m;
    set<int> s1,s2;
    for(int j=0;j<m;j++){
        s1.clear(); //一定clear
        s2.clear();
        int t1,t2;
        cin>>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<bits/stdc++.h>
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;k<=R;k++){ //在中序遍历中查找根节点
        if(in[k]==post[postR]){
            break;
        }
    }
    int numLeft=k-L;//左子树节点个数
    //postR 和 k 是根节点， 不包含
    root->left=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<node*> q;
    q.push(root);
    while(!q.empty()){
        node* now=q.front();
        q.pop();
        num++;
        cout<<now->data;
        if(num<n) cout<<" ";
        if(now->left!=nullptr) q.push(now->left); //注意判空
        if(now->right!=nullptr) q.push(now->right);
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>post[i];
    }
    for(int i=0;i<n;i++){
        cin>>in[i];
    }
    node *root=create(0,n-1,0,n-1);
    bfs(root);
    system("pause");
    return 0;
}

L2-007 家庭房产

L2-008 最长对称子串

#include<bits/stdc++.h>
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<l;i++){
        //奇数
        for(int j=0;i-j>=0&&i+j<l;j++){
            if(a[i-j]!=a[i+j]) break;
            ans=max(ans,2*j+1);
        }
        //偶数
        for(int j=0;i-j>=0&&i+j+1<l;j++){
            if(a[i-j]!=a[i+j+1]) break;
            ans=max(ans,2*j+2);
        }
    }
    cout<<ans;
    system("pause");
    return 0;
}

L2-009 抢红包

//简单结构体排序
#include<bits/stdc++.h>
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.id<b.id;
        }else return a.cnt>b.cnt;
    }else return a.y>b.y;
}
int main(){
    int n;
    cin>>n;
    int k;
    for(int i=1;i<=n;i++){
        nd[i].id=i;
        cin>>k;
        int t1,t2;
        for(int j=0;j<k;j++){
            cin>>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<=n;i++){
        printf("%d %.2f",nd[i].id,1.0*nd[i].y/100);
        if(i<=n-1) cout<<endl;
    }
    system("pause");
    return 0;
}

L2-010 排座位

//感觉是并查集，就是并查集
#include<bits/stdc++.h>
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<=n;i++){
        f[i]=i;
    }
    int t1,t2,t3;
    for(int i=0;i<m;i++){
        cin>>t1>>t2>>t3;
        if(t3==1) Union(t1,t2);
        else flag[t1][t2]=flag[t2][t1]=1;
    }
    for(int i=0;i<k;i++){
        cin>>t1>>t2;
        //cout<<Find(t1)<<" "<<Find(t2)<<endl;
        if(Find(t1)==Find(t2)&&flag[t1][t2]!=1) cout<<"No problem";
        else if(Find(t1)!=Find(t2)&&flag[t1][t2]!=1) cout<<"OK";
        else if(Find(t1)==Find(t2)&&flag[t1][t2]==1) cout<<"OK but...";
        else cout<<"No way";
        if(i<k-1) cout<<endl;
    }
    system("pause");
    return 0;
}

L2-011 玩转二叉树

// 也是建树，和6题差不多，一遍过
#include<bits/stdc++.h>
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;k<=r;k++){
        if(in[k]==pre[pl]) break;
    }
    int len=k-l;
    root->right=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<node*> q;
    q.push(root);
    while(!q.empty()){
        node *now=q.front();
        q.pop();
        cout<<now->data;
        num++;
        if(num<n) cout<<" ";
        if(now->left!=nullptr) q.push(now->left);
        if(now->right!=nullptr) q.push(now->right);
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>in[i];
    }
    for(int i=0;i<n;i++){
        cin>>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<bits/stdc++.h>
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;i++){
        f[i]=i;
    }
}
int findf(int x){
    int t=x;
    while(t!=f[t]){
        t=f[t];
    }
    int a=x;
    while(f[a]!=t){
        int z=a;
        f[z]=t;
        a=f[z];
    }
    return t;
    // if(x==f[x]) return x;
    // f[x]=findf(f[x]);
    // return f[x];
}
void Union(int a,int b){
    a=findf(a);
    b=findf(b);
    if(a!=b) f[a]=b;
}
int count(){
    int cnt=0;
    for(int i=0;i<n;i++){
        if(f[i]==i&&vis[i]==false){
            cnt++;
        }
    }
    return cnt;
}
int main(){
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++){
        cin>>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;i<m;i++){
            if(!vis[nd[i].x]&&!vis[nd[i].y]) Union(nd[i].x,nd[i].y);
        }
        cnt2=count();
        if(cnt1<cnt2) printf("Red Alert: City %d is lost!",u);
        else printf("City %d is lost.",u);
        cnt1=cnt2; //集合个数每次都要更新
        if(k>0) cout<<'\n';
        if(cnt3==n) printf("\nGame Over.");
    }
    system("pause");
    return 0;
}

bfs 实现

//尝试bfs搜索实现,我太nb了,一遍过
#include<bits/stdc++.h>
using namespace std;
const int N=510;
vector<int> v[N],lost;
bool inq[N]={false};
int n,m,k,u;
void bfs(int x){
    queue<int> q;
    q.push(x);
    inq[x]=true; //inq队列，判断是否入过队，约等于有没有访问过
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=0;i<v[now].size();i++){
            if(inq[v[now][i]]==false){
                q.push(v[now][i]);
                inq[v[now][i]]=true;
            }
        }
    }
}
int main(){
    cin>>n>>m;
    int t1,t2;
    for(int i=0;i<m;i++){
        cin>>t1>>t2;
        v[t1].push_back(t2);
        v[t2].push_back(t1);
    }
    int sum=0;
    for(int i=0;i<n;i++){
        if(inq[i]==false){
            sum++;
            bfs(i);
        }
    }
    memset(inq,0,sizeof(inq));
    cin>>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;i<lost.size();i++){
            inq[lost[i]]=true;//从lost里给inq赋初值
        }
        for(int i=0;i<n;i++){
            if(inq[i]==false){
                ans++;
                bfs(i);
            }
        }
        if(sum<ans) printf("Red Alert: City %d is lost!",u);
        else printf("City %d is lost.",u);
        sum=ans;
        if(k>0) cout<<'\n';
        if(cnt3==n) printf("\nGame Over.");
    }
    system("pause");
    return 0;
}

L2-014 列车调度

//类似模拟，维护了一个最小值集合的队列
//lower_bound查找>=目标第一个元素 upper_bound >
//这里用upper_bound
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
int main(){
    int n;
    cin>>n;
    int t,cnt=0;
    for(int i=0;i<n;i++){
        cin>>t;
        // 性质决定肯定是有序的，直接upper_bound看有没有更大中的最小值
        vector<int>::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<<cnt;
    system("pause");
    return 0;
}

L2-015 互评成绩

// 简单模拟
#include<bits/stdc++.h>
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<n;i++){
        int t1=100,t2=0,t;
        for(int j=0;j<k;j++){
            cin>>t;
            a[i]+=t;
            t1=min(t1,t);
            t2=max(t2,t);
        }
        a[i]-=(t1+t2); //天才做法
    }
    sort(a,a+n,greater<int>());
    for(int i=m-1;i>=0;i--){
        double d=1.0*a[i]/(k-2);
        printf("%.3f",d);
        if(i>0) cout<<' ';
    }
    system("pause");
    return 0;
}

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

//初看并查集？实际搜索，类似连通块
// 尝试bfs,实际上dfs更简洁
// 用下标表示id的时候，空间尽可能大
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
bool inq[N]={false};
int n,k;
vector<int> v1,v2;
struct node{
    int sex;
    int step;
    int fid,mid;
}nd[N];
vector<int> bfs(int x){ //标准bfs
    queue<int> q;
    vector<int> 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<N;i++){
        nd[i].fid=nd[i].mid=-1;//全部初始化为-1
    }
    for(int i=0;i<n;i++){
        cin>>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<<"Never Mind";
        }else{
            memset(inq,0,sizeof(inq));
            v1=bfs(t1); //t1的5代所有人
            memset(inq,0,sizeof(inq));
            v2=bfs(t2); //t2 5代所有人
            set<int> s;
            int l1=v1.size();
            int l2=v2.size();
            for(int i=0;i<l1;i++){
                s.insert(v1[i]);
            }
            for(int i=0;i<l2;i++){
                s.insert(v2[i]);
            }
            if(l1+l2==s.size()) cout<<"Yes"; //有重复的一去重大小会变
            else cout<<"No";
        }
        if(k>0) cout<<'\n';
    }
//     system("pause");
    return 0;
}

L2-017 人以群分

// 思维题 sort会用就能过
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1); //注意是否是0开始
    for(int i=1;i<=n;i++){
        a[i]+=a[i-1];
    }
    int aa,diff;
    if(n&1){
        aa=n/2;
        diff=a[n]-2*a[aa];
    }else{
        aa=n/2;
        diff=a[n]-2*a[aa];
        if(a[n]-2*a[aa+1]>diff){
            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<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
set<string> s;
vector<string> v,v1;
map<string,int> m;
int main(){
    int n;
    string t1;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>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;i<zz;i++){
        int s1=s.size();
        s.insert(v[i]);
        int s2=s.size();
        if(s2>s1&&zz*m[v[i]]>sum){
            v1.push_back(v[i]);
        }
    }
    if(v1.size()==0) cout<<"Bing Mei You";
    else{
        sort(v1.begin(),v1.end());
        for(int i=0;i<v1.size();i++){
            cout<<v1[i]<<endl;
        }
    }
    system("pause");
    return 0;
}

# 用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<bits/stdc++.h>
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<n;i++){
        cin>>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<k;j++){
                cin>>t;
                s[t]=i;
            }
        }
    }
    cout<<int(ans);
    system("pause");
    return 0;
}

L2-021 点赞狂魔

// 热身赛原题，考试时做出来了，结构体排序
#include<bits/stdc++.h>
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.avg<y.avg;
	else return x.cnt>y.cnt;
}
int main(){
	int n,k,t;
	set<int> s;
	cin>>n;
	for(int i=0;i<n;i++){
		s.clear();
		cin>>nd[i].name;
		cin>>k;
		for(int j=0;j<k;j++){
			cin>>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<<nd[0].name<<" - -";//容易少写
	else if(n==2) cout<<nd[0].name<<' '<<nd[1].name<<" -";
	else cout<<nd[0].name<<' '<<nd[1].name<<' '<<nd[2].name;
	return 0;
}

L2-022 重排链表

L2-023 图着色问题

//初看比较唬人，实际考图邻接表存储
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int v,e,k;
vector<int> g[N];
set<int> sss;
int color[N];
int main(){
    cin>>v>>e>>k;
    int t1,t2;
    for(int i=0;i<e;i++){
        cin>>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<=v;j++){
            cin>>color[j];
            sss.insert(color[j]);
        }
        if(sss.size()!=k) flag=1; // 必须就这几个颜色多了少了都不行
        if(!flag)
            for(int j=1;j<=v;j++){
                if(flag) break;
                int len=g[j].size();
                for(int t=0;t<len;t++){
                    if(color[j]==color[g[j][t]]){
                        flag=1;
                        break;
                    }
                }
            }
        if(flag) cout<<"No"; // 注意yes no大小写
        else cout<<"Yes";
        if(n>0) cout<<endl;
    }
    system("pause");
    return 0;
}

L2-024 部落

//基础并查集
#include<bits/stdc++.h>
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<N;i++){
        f[i]=i;
    }
}

int cnt(){
    int count=0;
    for(int i=1;i<=n;i++){
        if(f[i]==i&&vis[i]) count++;
    }
    return count;
}
int main(){
    int k,t1,t2,t3;
    init();
    cin>>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<=n;i++){
        if(vis[i]) sum++;
    }
    cout<<sum<<' '<<cnt()<<endl;
    cin>>t1;
    while(t1--){{
        cin>>t2>>t3;
        if(findf(t2)==findf(t3)) cout<<'Y';
        else cout<<'N';
        if(t1>0) cout<<'\n';
    }}
    system("pause");
    return 0;
}

L2-025 分而治之

// 和13红色警戒那题差不多，求连通块，并查集，搜索都可以做
// 这里用的并查集码量少
#include<bits/stdc++.h>
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;i++){
        f[i]=i;
    }
}
int count(){
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]&&f[i]==i) cnt++;
    }
    return cnt;
}
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;
}

int main(){
    cin>>n>>m;
    int t1,t2;
    for(int i=0;i<m;i++){
        cin>>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<t3;i++){
            cin>>t2;
            vis[t2]=true;
        }
        for(int i=0;i<m;i++){
            if(!vis[nd[i].x]&&!vis[nd[i].y]) unionf(nd[i].x,nd[i].y);
        }
        int sum1=count();
        //cout<<sum0<<" "<<t3<<" "<<sum1<<endl;
        if(t3+sum1==n) cout<<"YES"; //这里第一次判断错了
        else cout<<"NO";
        if(k>0) cout<<endl;
    }
    system("pause");
    return 0;
}

L2-026 小字辈

// 记忆化搜索 和20题差不多
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N],c[N];
vector<int> 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<=n;i++){
        cin>>t;
        f[i]=t;
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        if(c[i]==-1){
            c[i]=dfs(i);
            sum=max(sum,c[i]);
            v[c[i]].push_back(i);
        }
    }
    cout<<sum<<endl;
    int len=v[sum].size();
    for(int i=0;i<len;i++){
        cout<<v[sum][i];
        if(i<len-1) cout<<' ';
    }
    system("pause");
    return 0;
}

L2-027 名人堂与代金券

// 记忆化搜索 和20题差不多
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int f[N],c[N];
vector<int> 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<=n;i++){
        cin>>t;
        f[i]=t;
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        if(c[i]==-1){
            c[i]=dfs(i);
            sum=max(sum,c[i]);
            v[c[i]].push_back(i);
        }
    }
    cout<<sum<<endl;
    int len=v[sum].size();
    for(int i=0;i<len;i++){
        cout<<v[sum][i];
        if(i<len-1) cout<<' ';
    }
    system("pause");
    return 0;
}

L2-028 秀恩爱分得快

// 模拟 太恶心了，挂了几个测试点，考试的时候我绝对不会改的
// 得用字符串存，正确的我放后面了
// #include<bits/stdc++.h>
// 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<k;i++){
//             cin>>tp[i];
//         }
//         double tt=1.0/k;
//         for(int i=0;i<k;i++){
//             for(int j=i+1;j<k;j++){
//                 if(tp[i]*tp[j]<0 || (tp[i]==0&&tp[j]<0) || (tp[i]<0&&tp[j]==0)) {
//                     a[tp[i]+1000][tp[j]+1000]+=tt;
//                     a[tp[j]+1000][tp[i]+1000]+=tt;
//                 }
//             }
//         }
//     }
//     int t1,t2;
//     cin>>t1>>t2;
//     vector<int> v1,v2;
//     double MAX,MAX1,MAX2;
//     MAX=MAX1=MAX2=a[t1+1000][t2+1000];
//     for(int i=0;i<N;i++){
//         if(a[t1+1000][i]>MAX1){
//             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;i<N;i++){
//         if(a[t2+1000][i]>MAX2){
//             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<<t1<<' '<<t2;
//     else{
//         if(t1>0) sort(v1.begin(),v1.end(),greater<int>());
//         else sort(v1.begin(),v1.end());
//         if(t2>0) sort(v2.begin(),v2.end(),greater<int>());
//         else sort(v2.begin(),v2.end());
//         for(auto i:v1) cout<<t1<<' '<<i<<endl;
//         for(auto i:v2) cout<<t2<<' '<<i<<endl;
//     }
//     system("pause");
//     return 0;
// }

//AC
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a, int b){
	if(abs(a)==1000)return true;
	if(abs(b)==1000)return false;
	return abs(a)<abs(b);
}
int main(){
	//input
	int n, m, sex[1010]={0};
	cin>>n>>m;
	vector<vector<int>>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 <= 2; i++){
		string s;  cin>>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 <= 2; c++){
		for(int i = 0; i < m; i++){
			//Find CP
			int ok = 0;
			for(int j = 0; j < photo[i].size(); j++){
				if(photo[i][j]==cp[c]){
					ok = 1;
					break;
				}
			}
			//Add Love
			if(ok){
				for(int j = 0; j < photo[i].size(); j++){
					if(cp[c]*photo[i][j]<0){
						love[abs(photo[i][j])] += 1.0/photo[i].size();
					}
				}
			}
		}
	}
	//Count maxlove
	double maxx[3] = {0};
	vector<vector<int> >ans(3);
	for(int c = 1; c <= 2; c++){
		for(int i = 1; i <= 1000; i++){
			if(cp[c]*sex[i]<0){
				if(love[i]>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<<ans[1].size()<<" "<<ans[2].size()<<endl;
	//output
	if(maxx[1]==love[abs(cp[2])] && maxx[2]==love[abs(cp[1])]){
		string s1 = to_string(cp[1]), s2 = to_string(cp[2]);
		if(cp[1]==1000)s1="0";
		if(cp[1]==-1000)s1="-0";
		if(cp[2]==1000)s2="0";
		if(cp[2]==-1000)s2="-0";
		cout<<s1<<" "<<s2<<endl;
		return 0;
	}
	for(int c = 1; c <= 2; c++){
		sort(ans[c].begin(), ans[c].end(),cmp);
		for(int i = 0; i < ans[c].size(); i++){
			string s1 = to_string(cp[c]), s2 = to_string(ans[c][i]);
			if(cp[c]==1000)s1 = "0";
			if(cp[c]==-1000)s1 = "-0";
			if(ans[c][i]==1000)s2 = "0";
			if(ans[c][i]==-1000)s2 = "-0";
			cout<<s1<<" "<<s2<<endl;
		}
	}
	return 0;
}

L2-029 特立独行的幸福

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int l,r;
bool vis[N]={false};
bool vis2[N]={false};//设置两个vis数组
vector<int> v[N];
bool isprime(int x){
    if(x==1) return false;
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0) return false;
    }
    return true;
}
int f(int x){
    int ans=0;
    while(x){
        ans+=((x%10)*(x%10));
        x/=10;
    }
    return ans;
}
int judge(int x){
    int t=x;
    set<int> 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<=r;i++){
        vis2[i]=judge(i); //先全判断一边
    }
    int flag=0;
    for(int i=l;i<=r;i++){
        if(!vis[i]&&vis2[i]){
            flag=1;
            int len=v[i].size();
            cout<<i<<' '<<(isprime(i)?len*2:len)<<endl;
        }
    }
    if(!flag) cout<<"SAD";
    system("pause");
    return 0;
}

L2-030 冰岛人

#include<bits/stdc++.h>
using namespace std;
struct people{
    char sex;
    string father;
};
unordered_map<string,people> 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<5||j<5)) return 0;
        }
    }
    return 1;
}
int main(){
    int n,m;
    string str,a,b;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>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<m;i++){
        cin>>a>>str>>b>>str; // 姓没用
        if(p.find(a)==p.end()||p.find(b)==p.end()) cout<<"NA\n"; //find 约等于map自带
        else if(p[a].sex==p[b].sex) cout<<"Whatever\n";
        else cout<<(judge(a,b)?"Yes\n":"No\n");
    }
    system("pause");
    return 0;
}


	// cin >> 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<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
// vector<int> 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<=n;i++){
        cin>>k;
        while(k--){
            cin>>t;
            pre[t]=i;
        }
    }
    int u=-1,MAX=-1;
    for(int i=1;i<=n;i++){
        if(geth(i)>MAX){
            MAX=geth(i);
            u=i;
        }
    }
    cout<<u;
    system("pause");
    return 0;
}

L2-032 彩虹瓶

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

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    while(k--){
        stack<int> s; //stack没有clear 直接重新定义
        int flag=0;
        memset(a,0,sizeof(a));
        int t1=1,t2;
        int cnt1=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            t2=a[i];
            if(t2==t1){
                t1++;
                while(!s.empty()&&s.top()==t1){
                    s.pop();
                    t1++;
                }
            }else{
                s.push(t2);
                if(s.size()>m){ // 把=改成>就过了 下面写的都是对的
                    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<<"NO"<<endl; continue;}
        if(t1==n+1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    system("pause");
    return 0;
}

L2-033 简单计算器

// 栈基础
#include<bits/stdc++.h>
using namespace std;
int n;
stack<int> s1;
stack<char> s2;
int main(){
    cin>>n;
    int t1,d1,d2;
    char t2;
    for(int i=0;i<n;i++){
        cin>>t1;
        s1.push(t1);
    }
    for(int i=0;i<n-1;i++){
        cin>>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<<s1.top();
    system("pause");
    return 0;
}

L2-034 口罩发放

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

//完全二叉树直接数组存
#include<bits/stdc++.h>
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<=n;i++){
        cout<<tree[i];
        if(i<n) cout<<' ';
    }
    system("pause");
    return 0;
}

L2-036 网红点打卡攻略

// 模拟
#include<bits/stdc++.h>
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<m;i++){
        cin>>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<=k;i++){
        set<int> s;
        int flag=0;
        cin>>t1;
        memset(r,-1,sizeof(r));
        r[0]=0;
        for(int j=1;j<=t1;j++){
            cin>>r[j]; //标错下标了
        }
        r[t1+1]=0; //这里设置了结束后面就不用判断了
        int ans=0;
        for(int j=0;j<=t1;j++){
            // cout<<r[j]<<' '<<r[j+1]<<endl;
            if(cost[r[j]][r[j+1]]==0){
                // cout<<cost[r[j]][r[j+1]]<<endl;
                flag=1;
                break;
            }
            // cout<<cost[r[j]][r[j+1]]<<endl;
            ans+=cost[r[j]][r[j+1]];
            int pre=s.size();
            s.insert(r[j]);
            if(s.size()==pre){
                flag=1;
                break;
            }
        }
        if(flag||s.size()!=n+1||cost[r[t1]][0]==0) continue;
        cnt++;
        if(ans<MIN){
            MIN=ans;
            u=i;
        }
    }
    cout<<cnt<<'\n'<<u<<' '<<MIN;
    system("pause");
    return 0;
}

L2-037 包装机

// 栈、队列
#include<bits/stdc++.h>
using namespace std;
queue<int> q[110];
stack<int> st;
map<char,int> mp;
vector<int> v;
void init(){
    for(int i=0;i<26;i++){
        mp[i+'A']=i;
    }
}
int main(){
    int n,m,s;
    string str;
    init();
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++){
        cin>>str;
        for(int j=0;j<m;j++){
            // cout<<mp[str[j]]<<endl;
            q[i].push(mp[str[j]]);
        }
    }
    int t,t1,t2;
    while(cin>>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<v.size();i++){
        cout<<char(v[i]+'A');
    }
    system("pause");
    return 0;
}

L2-038 病毒溯源

// 一个pre数组的事 记忆化搜索
// vector 重载 < 直接用
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int pre[N];
int height[N];
int u=-1,MAX=-1;
vector<int> 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<int>& _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<n;i++){
        cin>>t1;
        for(int j=0;j<t1;j++){
            cin>>t2;
            pre[t2]=i;
        }
    }
    for(int i=0;i<n;i++){
        if(geth(i)>MAX){
            MAX=geth(i);
            vv.clear();
            vv.push_back(i);
        }else if(geth(i)==MAX){
            vv.push_back(i);
        }
    }
    cout<<MAX<<endl;
    vector<vector<int>> ans;
    for(int i=0;i<vv.size();i++){
        vector<int> v;
        dfs(vv[i],v);
        ans.push_back(v);
    }
    sort(ans.begin(),ans.end());
    vector<int> v=ans[0];
    for(int i=0;i<ans[0].size();i++){
        cout<<ans[0][i];
        if(i<ans[0].size()-1) cout<<' ';
    }
    system("pause");
    return 0;
}

L2-039 清点代码库

// map vector
// map pair类型变量 类似结构体
// 用结构题存map 重载<排序 vector自带<
#include<bits/stdc++.h>
using namespace std;
map<vector<int>,int> mp; // 只能用来统计数量，不能重载运算符
// 重新用node来保存
struct node
{
    vector<int> v;
    int cnt;
};

vector<int> v;

int cmp(node x,node y){
    if(x.cnt==y.cnt) return x.v<y.v;
    else return x.cnt>y.cnt;
}
vector<node> ans;
int main(){
    int n,m,t;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        v.clear();
        for(int j=0;j<m;j++){
            cin>>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<<ans.size()<<endl;
    sort(ans.begin(),ans.end(),cmp);
    for(int i=0;i<ans.size();i++){
        cout<<ans[i].cnt;
        for(int j=0;j<m;j++){
            cout<<' '<<ans[i].v[j];
        }
        cout<<endl;
    }
    system("pause");
    return 0;
}

L2-040 哲哲打游戏

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

L3-001 凑零钱

L3-002 特殊堆栈

L3-003 社交集群

L3-004 肿瘤诊断

L3-005 垃圾箱分布

L3-006 迎风一刀斩

L3-007 天梯地图

L3-008 喊山

L3-009 长城

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

// BST建立并判断完全二叉树
#include<bits/stdc++.h>
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<node*> q;
    root->nid=1;
    q.push(root);
    while (!q.empty())
    {
        node *now=q.front();
        q.pop();
        cout<<now->data;
        ans++;
        if(ans<n) cout<<' ';
        if(now->left!=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<n;i++){
        cin>>t;
        insert(root,t);
    }
    bfs(root);
    cout<<endl;
    if(maxn==n) cout<<"YES"; //用完全二叉树性质判断 最大节点id和个数一样
    else cout<<"NO";
    system("pause");
    return 0;
}