【CCCC】PAT : 团体程序设计天梯赛-练习集 L2 答案，题解，附代码

【CCCC】PAT : 团体程序设计天梯赛-练习集 L2 答案

鉴定完毕，全部水题 ヾ(•ω•`)o

知识点分类（32）：

1、树锯结构（9）：二叉树的存储，编号，遍历顺序转换，求深度，底层节点，从底部向上搜索公共祖先。多叉树存储，遍历，求深度。

2、图论模板（3）：Dijkstra，图的存储遍历，度数统计。

3、其他结构（7）：并查集（4）+链表（2）+栈（1）；

4、模拟水题（8）：好吧大概有一半数据有点坑；

5、零零碎碎（5）：STL（2）+贪心（2）+数学（1）；

L2-AC代码

L2-001

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 510;
const int inf = 99999999;

int n, m, c1, c2;
int e[maxn][maxn], w[maxn];
void Input(){
    cin>>n>>m>>c1>>c2;
    for(int i = 0; i < n; i++)
        cin>>w[i];
    memset(e,0x3f,sizeof(e));
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin>>a>>b>>c;
        e[a][b] = e[b][a] = c;
    }
}

int dis[maxn], vis[maxn];//dist_lenght
int cnt[maxn];//dist_num
int weight[maxn]; //max_power
int pre[maxn];//pre_pass
void Solve(){
    memset(dis,0x3f,sizeof(dis));
    memset(pre,-1,sizeof(pre));
    dis[c1] = 0; 
    cnt[c1] = 1;
    weight[c1] = w[c1];
    for(int i = 0; i < n; i++){
        int u = -1, minn = inf;
        for(int j = 0; j < n; j++){
            if(!vis[j] && dis[j]<minn){
                minn = dis[j];
                u = j;
            }
        }
        if(u==-1)break;
        vis[u] = 1;
        for(int j = 0; j < n; j++){
            if(vis[j])continue;
            if(dis[j]>dis[u]+e[u][j]){
                dis[j] = dis[u]+e[u][j];
                cnt[j] = cnt[u];
                weight[j] = weight[u]+w[j];
                pre[j] = u;
            }else if(dis[j]==dis[u]+e[u][j]){
                cnt[j] += cnt[u];
                if(weight[u]+w[j]>weight[j]){
                    weight[j] = weight[u]+w[j];
                    pre[j] = u;
                }
            }
        }
    }
    //cout<<dis[c2]<<endl;
    cout<<cnt[c2]<<" "<<weight[c2]<<"\n";
}
void Print(int x){
    if(x==-1){
        return ;
    }else{
        Print(pre[x]);
        cout<<x<<" ";
    }
}

int main(){
    Input();
    Solve();
    Print(pre[c2]);
    cout<<c2<<"\n";
    return 0;
}

L2-002

#include<bits/stdc++.h>
using namespace std;

struct node{ int address, key, next;};
map<int,node>ma;//list
bool exsit[100010];
vector<node>l1,l2;//ans

int main(){
    int begin, n;
    cin>>begin>>n;
    for(int i = 0; i < n; i++){
        int x;  cin>>x;
        cin>>ma[x].key>>ma[x].next;
    }
    for(int i = 0; i < n; i++){
        node t; t.address = begin, t.key = ma[begin].key, t.next = ma[begin].next;
        if(!exsit[abs(ma[begin].key)]){
            exsit[abs(ma[begin].key)] = 1;
            l1.push_back(t);
        }else{
            l2.push_back(t);
        }
        begin = ma[begin].next;
        if(begin==-1)break;
    }
    for(int i = 0; i < l1.size(); i++){
        printf("%05d %d ", l1[i].address,l1[i].key);
        if(i != l1.size()-1)
            printf("%05d\n", l1[i+1].address);
        else 
            printf("-1\n");
    }
    for(int i = 0; i < l2.size(); i++){
        printf("%05d %d ", l2[i].address,l2[i].key);
        if(i != l2.size()-1)
            printf("%05d\n", l2[i+1].address);
        else 
            printf("-1\n");
    }    
    return 0;
}

L2-003

#include<bits/stdc++.h>
using namespace std;
struct node{double x, y, z;}a[1010];
bool cmp(node a1, node a2){return a1.z>a2.z;}
int main(){
    int n, x;
    cin>>n>>x;
    for(int i = 1; i <= n; i++)cin>>a[i].x;
    for(int i = 1; i <= n; i++){
        cin>>a[i].y;
        a[i].z = a[i].y/a[i].x;
    }
    sort(a+1,a+n+1,cmp);
    double ans = 0;
    for(int i = 1; i <= n; i++){
        if(a[i].x<=x){
            x -= a[i].x;
            ans += a[i].y;
        }else{
            ans += a[i].z*x;
            break;
        }
    }
    printf("%.2lf\n",ans);
    return 0;
}

L2-004

#include<bits/stdc++.h>
using namespace std;
bool isMirror;
vector<int>pre, post;
void getpost(int l, int r){//build(l,r)
    if(l > r)return ;
    int i = l+1, j = r;//l是根节点，pre[l+1,r]是左右子树
    if(!isMirror){
        while(i<=r && pre[l]>pre[i])i++; //从当前的根节点向后遍历
        while(j>l && pre[l]<=pre[j])j--; //从当前的尾节点向前遍历
    }else{
        while(i<=r && pre[l]<=pre[i])i++;
        while(j>l && pre[l]>pre[j])j--;
    }
    if(i-j!=1)return;//满足性质，存在一个分界点，左边都小于根，右边都大于根
    getpost(l+1,j);//存放左子树
    getpost(i,r);//存放右子树
    post.push_back(pre[l]);//存放根节点
}
int main(){
    int n;  cin>>n;
    pre.resize(n);
    for(int i = 0; i < n; i++)
        cin>>pre[i];
    getpost(0,n-1);
    if(post.size()!=n){
        isMirror = true;
        post.clear();
        getpost(0,n-1);
    }
    if(post.size()!=n){
        cout<<"NO"<<endl;
    }else{
        cout<<"YES"<<endl;
        for(int i = 0; i < n-1; i++)
            cout<<post[i]<<" ";
        cout<<post[n-1];
    }
    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++){
        int t;  cin>>t;
        for(int j = 0; j < t; j++){
            int x;  cin>>x;
            v[i].insert(x);
        }
    }
    int k;  cin>>k;
    for(int i = 0; i < k; i++){
        int a, b;  cin>>a>>b;
        int nc = 0, nt = v[b-1].size();
        for(set<int>::iterator it = v[a-1].begin(); it != v[a-1].end(); it++){
            if(v[b-1].find(*it) == v[b-1].end())nt++;
            else nc++;
        }
        printf("%.2f\%\n",(double)nc/nt*100);
    }
    return 0;
}

L2-006

#include<bits/stdc++.h>
using namespace std;
const int maxn = 55;

int n, post[maxn], mid[maxn];
struct node{int l, r;}tree[maxn];
int build(int l1, int r1, int l2, int r2){//分别对应中序和后序的左右边界
    if(l1 > r1)return 0;
    int rt = post[r2], prt = l1;//1.后序确定根
    while(mid[prt]!=rt)prt++;//2.中序找根的位置
    int cnt = prt-l1;//3.中序确定左子树节点树
    tree[rt].l = build(l1,prt-1,l2,l2+cnt-1);//4.递归左子树
    tree[rt].r = build(prt+1,r1,l2+cnt,r2-1);//5.递归右子树
    return rt;
}

vector<int>ans;
void bfs(int rt){
    queue<int>q; q.push(rt);
    ans.push_back(rt);
    while(q.size()){
        int u = q.front();  q.pop();
        if(tree[u].l != 0){
            q.push(tree[u].l);
            ans.push_back(tree[u].l);
        }
        if(tree[u].r != 0){
            q.push(tree[u].r);
            ans.push_back(tree[u].r);
        }
    }
    for(int i = 0; i < ans.size()-1; i++)
        cout<<ans[i]<<" ";
    cout<<ans[ans.size()-1];
}


int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)cin>>post[i];
    for(int i = 1; i <= n; i++)cin>>mid[i];
    int root = build(1,n,1,n);
    bfs(root);
    return 0;
}

L2-007

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int maxnn = 10010;

int vis[maxnn];//编号i有人
struct member{int name, dad, mum, chi[20]; int num, area;}mem[maxn];
struct family{int name, cnt; double num, area; bool flag;}fam[maxnn];
bool cmp(family a, family b){return a.area!=b.area?a.area>b.area:a.name<b.name;}

int fa[maxnn]; //合并的时候是编号，所以maxnn
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x, int y){//修改：按照最小编号合并
    x=find(x);y=find(y);if(x>y)fa[x]=y;else if(x<y)fa[y]=x;
}

int main(){
    int n;  cin>>n;
    //1.输入每个人并分家
    init(maxnn);
    for(int i = 0; i < n; i++){
        int k;  cin>>mem[i].name>>mem[i].dad>>mem[i].mum>>k;
        vis[mem[i].name]++;
        if(mem[i].dad != -1){
            merge(mem[i].name,mem[i].dad);
            vis[mem[i].dad]++;
        }
        if(mem[i].mum != -1){
            merge(mem[i].name,mem[i].mum);
            vis[mem[i].mum]++;
        }
        for(int j = 0; j < k; j++){
            cin>>mem[i].chi[j];
            merge(mem[i].name,mem[i].chi[j]);
            vis[mem[i].chi[j]]++;
        }
        cin>>mem[i].num>>mem[i].area;
    }
    //2.分完家了，扫描统计每个家的数量
    for(int i = 0; i < n; i++){
        int name = find(mem[i].name);
        fam[name].name = name;
        //fam[name].cnt++;
        fam[name].num += mem[i].num;
        fam[name].area += mem[i].area;
        fam[name].flag = true;
    }
    //3.统计各家庭人数，面积.
    int people = 0;
    for(int i = 0; i < maxnn; i++){
        if(vis[i]!=0)fam[find(i)].cnt++;
        if(fam[i].flag)people++;
    }
    cout<<people<<"\n";
    for(int i = 0; i < maxnn; i++){
        if(fam[i].flag==1){
            fam[i].num /= fam[i].cnt;
            fam[i].area /= fam[i].cnt;
        }
    }
    sort(fam,fam+maxnn,cmp);//先除完再排序
    for(int i = 0; i < people; i++)
        printf("%04d %d %.3f %.3f\n", fam[i].name, fam[i].cnt, fam[i].num, fam[i].area);
    return 0;
}

L2-008

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;  getline(cin,s);
    int ans = 1;//数据5:最小是1
    for(int i = 0; i < s.size(); i++){
        int l = i, r = i+1;
        if(s[l]==s[r]){//偶数串
            l--; r++;
            while(l>=0&&r<s.size() && s[l]==s[r]){l--;r++;}
        }else if(l>0 && s[--l]==s[r]){//奇数串
            l--; r++;
            while(l>=0&&r<s.size() && s[l]==s[r]){l--;r++;}
        }
        l++;r--;
        ans = max(ans,r-l+1);
    }
    cout<<ans<<endl;
    return 0;
}

L2-009

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;

double a[maxn];int b[maxn];//红包金额和个数

int r[maxn];//间接排序
void init(int n){for(int i = 1; i <= n; i++)r[i]=i;}
bool cmp(int x, int y){
    if(abs(a[x]-a[y])>0.01)return a[x]>a[y];//a[x]!=a[y]，精确到0.01
    if(abs(b[x]-b[y])>0.01)return b[x]>b[y];
    return x<y;
}

int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        int k;  cin>>k;
        for(int j = 1; j <= k; j++){
            int ni, pi;
            cin>>ni>>pi;
            double py = pi*1.0/100;
            a[ni] += py;
            a[i] -= py;
            b[ni]++;
        }
    }
    init(n);
    sort(r+1,r+n+1,cmp);
    for(int i = 1; i <= n; i++)
        printf("%d %.2lf\n",r[i],a[r[i]]);
    return 0;
}

L2-010

#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;

int fa[maxn];//朋友
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}

int e[maxn][maxn];//敌人

int main(){
    int n, m, k;
    cin>>n>>m>>k;
    init(n);
    for(int i = 1; i <= m; i++){
        int x, y, z;
        cin>>x>>y>>z;
        if(z==1)merge(x,y);
        else e[x][y] = e[y][x] =1;
    }
    for(int i = 1; i <= k; i++){
        int x, y;  cin>>x>>y;
        if(find(x)==find(y) && e[x][y]==0)cout<<"No problem\n";
        if(find(x)!=find(y) && e[x][y]==0)cout<<"OK\n";
        if(find(x)==find(y) && e[x][y]==1)cout<<"OK but...\n";
        if(find(x)!=find(y) && e[x][y]==1)cout<<"No way\n";
    }
    return 0;
}

L2-011

#include<bits/stdc++.h>
using namespace std;
const int maxn = 55;

int n, pre[maxn], mid[maxn];
struct node{int l, r;}tree[maxn];
int build(int l1, int r1, int l2, int r2){//分别对应中序和先序的左右边界
    if(l1 > r1)return 0;
    int rt = pre[l2], prt = l1;//1.先序确定根
    while(mid[prt]!=rt)prt++;//2.中序找根的位置
    int cnt = prt-l1;//3.中序确定左子树节点树
    //注意在这里反转
    tree[rt].r = build(l1,prt-1,l2+1,l2+cnt);//4.递归左子树
    tree[rt].l = build(prt+1,r1,l2+cnt+1,r2);//5.递归右子树
    return rt;
}

vector<int>ans;
void bfs(int rt){
    queue<int>q; q.push(rt);
    ans.push_back(rt);
    while(q.size()){
        int u = q.front();  q.pop();
        if(tree[u].l != 0){
            q.push(tree[u].l);
            ans.push_back(tree[u].l);
        }
        if(tree[u].r != 0){
            q.push(tree[u].r);
            ans.push_back(tree[u].r);
        }
    }
    for(int i = 0; i < ans.size()-1; i++)
        cout<<ans[i]<<" ";
    cout<<ans[ans.size()-1];
}


int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)cin>>mid[i];
    for(int i = 1; i <= n; i++)cin>>pre[i];
    int root = build(1,n,1,n);
    bfs(root);
    return 0;
}

L2-012

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;

int n, m;
vector<int>v;
void update(int i){
    if(i==1)return ;
    while(i!=1){
        if(v[i]<v[i/2]){
            swap(v[i],v[i/2]);
            i /= 2;
        }else{
            break;
        }
    }
}

void judge1(int x){
    if(v[1]==x)cout<<"T\n";
    else cout<<"F\n";
}
void judge2(int x, int y){
    int px = 0, py = 0;
    for(int i = 1; i <= n; i++){
        if(v[i]==x)px = i;
        if(v[i]==y)py = i;
    }
    if(px>py)swap(px,py);
    if(px%2==0&&py-px==1)cout<<"T\n";//相邻且父节点相同
    else cout<<"F\n";
}
void judge3(int x, int y){
    int px = 0, py = 0;
    for(int i = 1; i <= n; i++){
        if(v[i]==x)px = i;
        if(v[i]==y)py = i;
    }
    if(px*2==py||px*2+1==py)cout<<"T\n";//父子当且仅当2n或2n+1时
    else cout<<"F\n";
}
void judge4(int x, int y){
    int px = 0, py = 0;
    for(int i = 1; i <= n; i++){
        if(v[i]==x)px = i;
        if(v[i]==y)py = i;
    }
    swap(px,py);
    if(px*2==py||px*2+1==py)cout<<"T\n";
    else cout<<"F\n";
}


int main(){
    cin>>n>>m;
    v.resize(n+1);
    for(int i = 1; i <= n; i++){
        cin>>v[i];  update(i);
    }
    for(int i = 1; i <= m; i++){
        int x,y;string z;
        cin>>x>>z;
        if(z=="and"){
            cin>>y>>z>>z;
            judge2(x,y);
        }else{
            cin>>z;
            if(z=="a"){
                cin>>z>>z>>y;
                judge4(x,y);
            }else{
                cin>>z;
                if(z=="root"){
                    judge1(x);
                }else{
                    cin>>z>>y;
                    judge3(x,y);
                }
            }
        }
    }
    return 0;
}

L2-013

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5050;

int x[maxn], y[maxn], vis[maxn];

int fa[maxn];
void init(int n){for(int i = 0; i < n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int count(int n){//统计并查集集合个数
    int cnt = 0;
    for(int i = 0; i < n; i++)//节点从0-n编号
        if(fa[i]==i)cnt++;
    return cnt;
}

int main(){
    int n, m;
    cin>>n>>m;
    init(n);
    for(int i = 1; i <= m; i++){
        cin>>x[i]>>y[i];
        merge(x[i],y[i]);
    }
    int k;  cin>>k;
    int cc1=count(n), cc2;
    for(int i = 1; i <= k; i++){
        int t;  cin>>t;
        vis[t] = 1;//被攻占的不再联通
        init(n);
        for(int j = 1; j <= m; j++){
            if(vis[x[j]]||vis[y[j]])continue;
            merge(x[j],y[j]);
        }
        cc2 = count(n);
        //cout<<cc2<<endl;
        if(cc2==cc1||cc2==cc1+1)
            printf("City %d is lost.\n",t);
        else 
            printf("Red Alert: City %d is lost!\n",t);
        cc1 = cc2;
    }
    if(k==n)printf("Game Over.\n");
    return 0;
}

L2-014

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;  cin>>n;
    set<int>s;
    s.insert(100010);//最少一个队伍
    for(int i = 1; i <= n; i++){
        int t;  cin>>t;
        if(t<*s.rbegin()){//如果找得到队伍
            s.erase(*(s.upper_bound(t)));//找到比他大的第一个值删掉
        }
        s.insert(t);//找到就加，找不到就开
    }
    cout<<s.size()<<endl;
    return 0;
}

L2-015

#include<bits/stdc++.h>
using namespace std;
bool cmp(double a, double b){return a>b;}
int main(){
    int n, k, m;
    cin>>n>>k>>m;
    vector<double>ans;
    for(int i = 1; i <= n; i++){
        int _max=-1, _min=101, _sum=0;
        for(int j = 1; j <= k; j++){
            int x;  cin>>x;
            _sum += x;
            _min = min(_min, x);
            _max = max(_max, x);
        }
        _sum -= _min+_max;
        ans.push_back(_sum*1.0/(k-2));
    }
    sort(ans.begin(),ans.end(),cmp);
    sort(ans.begin(),ans.begin()+m);
    for(int i = 0; i < m-1; i++)
        printf("%.3f ", ans[i]);
    printf("%.3f",ans[m-1]);
    return 0;
}

L2-016

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;

struct node{
    char sex;
    int fa, mo;
    int vi;
}me[maxn];
int flag;
void dfs(int a, int b, int s){
    if(!flag)return ;
    if(a==-1||b==-1)return ;
    if(a==b){
        if(s<=5)flag = 0;
        return ;
    }
    if(s > 5)return ;
    if(!me[a].vi || !me[b].vi)return ;
    dfs(me[a].fa,me[b].fa,s+1);
    dfs(me[a].fa,me[b].mo,s+1);
    dfs(me[a].mo,me[b].fa,s+1);
    dfs(me[a].mo,me[b].mo,s+1);
}

int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        int id, fa, mo; char sx;
        cin>>id>>sx>>fa>>mo;
        me[id].sex = sx;
        me[id].fa = fa;
        me[id].mo = mo;
        me[id].vi = 1;
        //可能判断父母是否能成婚（哭）
        if(fa!=-1)me[fa].sex = 'M';
        if(mo!=-1)me[mo].sex = 'F';
    }
    int k;  cin>>k;
    for(int i = 1; i <= k; i++){
        int a, b;  cin>>a>>b;
        if(me[a].sex==me[b].sex){
            cout<<"Never Mind"<<endl;
        }else{
            flag = 1;
            dfs(a,b,1);
            if(flag)cout<<"Yes\n";
            else cout<<"No\n";
        }
    }
    return 0;
}

L2-017

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;

int a[maxn];

int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++)cin>>a[i];
    sort(a+1,a+n+1);
    int s1 = 0, s2 = 0;
    if(n%2==0){
        for(int i = 1; i <= n/2; i++)
            s1 += a[i];
        for(int i = n/2+1; i <= n; i++)
            s2 += a[i];
        printf("Outgoing #: %d\n",n/2);
        printf("Introverted #: %d\n",n/2);
        printf("Diff = %d\n",s2-s1);
    }else{
        int mid = (n-1)/2;
        for(int i = 1; i <= mid; i++)
            s1 += a[i];
        for(int i = mid+2; i <= n; i++)
            s2 += a[i];
        if(a[mid+2]-a[mid+1]<a[mid+1]-a[mid]){
            s1 += a[mid+1];
            printf("Outgoing #: %d\n",mid);
            printf("Introverted #: %d\n",mid+1);
        }else {
            s2 += a[mid+1];
            printf("Outgoing #: %d\n",mid+1);
            printf("Introverted #: %d\n",mid);
        }
        printf("Diff = %d\n",s2-s1);
    }
    return 0;
}

L2-018

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3010;
//c1[i]表示(c[i])x^i
double c1[maxn], c2[maxn], c3[maxn];
//找c[]中有多少项
int non(double c[], int start){
    int cnt = 0;
    for(int i = start; i >= 0; i--)
        if(abs(c[i])+0.05>=0.1)cnt++;//浮点数>=0.05才算存在
    return cnt;
}
void print(double c[], int start){
    printf("%d",non(c,start));
    if(non(c,start)==0)printf(" 0 0.0");
    for(int i = start; i >= 0; i--)
        if(abs(c[i])+0.05>=0.1)
            printf(" %d %.1f",i,c[i]);
}
int main(){
    //input
    int m, n, max1=-1, max2=-1;
    cin>>m;
    for(int i = 0; i < m; i++){
        int t;  //scanf("%d%lf", &t,&c1[t]);
        cin>>t; cin>>c1[t];
        //scanf("%d",&t);
        //scanf("%lf",&c1[t]);
        max1 = max(max1, t);
    }
    cin>>n;
    for(int i = 0; i < n; i++){
        int t;  //scanf("%d%lf", &t,&c2[t]);
        cin>>t; cin>>c2[t];
        //scanf("%d",&t);
        //scanf("%lf",&c2[t]);
        max2 = max(max2, t);
    }
    //solve,c3是商，c1是余数
    int t1 = max1, t2 = max2;
    while(t1 >= t2){
        double c = c1[t1]/c2[t2];
        c3[t1-t2] = c;
        for(int i = t1, j = t2; j >= 0; j--,i--){
            c1[i] -= c2[j]*c;
        }
        while(abs(c1[t1])<0.000001)t1--;
    }
    //output
    print(c3,max1-max2);
    printf("\n");
    print(c1,t1);
    return 0;
}

L2-019

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;

int a[maxn];

int main(){
    int n;  cin>>n;
    set<string>gz;
    for(int i = 1; i <= n; i++){
        string t;  cin>>t;
        gz.insert(t);
    }
    int m;  cin>>m;
    map<string,int>dz;
    int sum = 0;
    for(int i = 1; i <= m; i++){
        string t; int tt; 
        cin>>t>>tt;
        dz[t] = tt;
        sum += tt;
    }
    sum /= dz.size();
    int ok = 1;
    for(map<string,int>::iterator it = dz.begin(); it != dz.end(); it++){
        if((it->second)>sum && !gz.count(it->first)){
            cout<<(it->first)<<endl;
            ok = 0;
        }
    }
    if(ok)cout<<"Bing Mei You\n";
    return 0;
}

L2-020

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;

int n; double z, r;
vector<int>Tree[maxn];
int Dedao[maxn];

double ans, power[maxn];
void dfs(int u, int cur){
    if(Dedao[u]!=0){
        //double pow = 1;
        //for(int i = 0; i < cur; i++)pow *= r;
        ans += z*power[cur]*Dedao[u];
        return ;
    }
    for(int i = 0; i < Tree[u].size(); i++){
        dfs(Tree[u][i],cur+1);
    }
}

int main(){
    cin>>n>>z>>r;
    r = 1-r*0.01;
    for(int i = 0; i < n; i++){
        int k;  cin>>k;
        if(k!=0){
            for(int j = 0; j < k; j++){
                int x;  cin>>x;
                Tree[i].push_back(x);
            }
        }else{
            cin>>Dedao[i];
        }
    }
    power[0] = 1;
    for(int i = 1; i < maxn; i++)
        power[i] = power[i-1]*r;
    dfs(0,0);
    cout<<(int)ans<<endl;
    return 0;
}

L2-021

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;

string name[maxn]; int k[maxn];
map<int,int>ma[maxn];
int ans[maxn];

int r[maxn];
void init(int n){for(int i = 1; i <= n; i++)r[i]=i;}
bool cmp(int a, int b){
    if(ans[a]!=ans[b])return ans[a]>ans[b];
    return k[a]*1.0/ans[a]<k[b]*1.0/ans[b];
}

int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>name[i]>>k[i];
        for(int j = 1; j <= k[i]; j++){
            int x;  cin>>x;
            ma[i][x]++;
        }
        ans[i] = ma[i].size();
    }
    init(n);
    sort(r+1,r+n+1,cmp);
    /*
    for(int i = 1; i <= 3; i++){
        if(i>n){ //WA2:n=2
            cout<<" -";
        }else{
            if(i==1)cout<<name[r[i]];
            else cout<<" "<<name[r[i]];
        }
    }
    */
    if(n<3){
        if(n==1){
            cout<<name[1]<<" - -";
        }else{
            for(int i = 1; i <= 2; i++)
                cout<<name[r[i]]<<" ";
            cout<<"-";
        }
        return 0;
    }
    for(int i = 1; i < 3; i++){
        cout<<name[r[i]]<<" ";
    }
    cout<<name[r[3]];
    return 0;
}

L2-022

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;

struct node{ int address, data, next;}li[maxn];
vector<node>l1, l2;

int main(){
    int begin, n;
    cin>>begin>>n;
    for(int i = 1; i <= n; i++){
        int x;  cin>>x;  li[x].address = x;
        cin>>li[x].data>>li[x].next;
    }
    int mid = n/2, cnt = 0;
    for(int i = begin; i != -1; i=li[i].next)cnt++;
    mid = cnt/2, cnt = 0;
    for(int i = begin; i != -1; i=li[i].next){
        //cout<<i<<"\n";
        cnt++;
        if(cnt<=mid){
            l1.push_back(li[i]);
        }else{
            l2.push_back(li[i]);
        }
    }
    for(int i=0,j=l2.size()-1; i<l1.size() && j>=0; i++,j--){
        //cout<<i<<" "<<j<<endl;
        printf("%05d %d ", l2[j].address,l2[j].data);
        printf("%05d\n", l1[i].address);
        printf("%05d %d ", l1[i].address,l1[i].data);
        if(j!=0)printf("%05d\n", l2[j-1].address);
        else printf("-1\n");
    }
    if(cnt%2==1){//数据比较坑（第4个点），可能存在不再一个链表上的两个结点,所以要记录链表长度
        printf("%05d %d ",l2[0].address,l2[0].data);
        printf("-1\n");
    }
    return 0;
}

L2-023

#include<bits/stdc++.h>
using namespace std;
const int maxn = 510;

int v, e, k;
int flag, co[maxn], vis[maxn];
vector<int>G[maxn];
void dfs(int u){
    if(vis[u] || !flag)return ;
    vis[u] = 1;
    for(int i = 0; i < G[u].size(); i++){
        if(co[G[u][i]]==co[u]){
            flag = 0; return ;
        }
        dfs(G[u][i]);
    }
}


int main(){
    cin>>v>>e>>k;
    for(int i = 1; i <= e; i++){
        int a, b;  cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int T;  cin>>T;
    while(T--){
        set<int>ss;
        for(int i = 1; i <= v; i++){
            cin>>co[i];  ss.insert(co[i]);
        }
        if(ss.size()!=k){//WA2
            cout<<"No\n";
            continue;
        }
        memset(vis,0,sizeof(vis));
        flag = 1;
        //dfs(v);WA3
        for(int i = 1; i <= v; i++)dfs(i);
        if(flag)cout<<"Yes\n";
        else cout<<"No\n";
    }
    
    return 0;
}

L2-024

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;

int fa[maxn+10];
void init(int n){for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int count(int n){int cnt=0; for(int i = 1; i <= n; i++)if(fa[i]==i)cnt++;return cnt;}

int main(){
    int n;  cin>>n;
    init(maxn);
    set<int>s;
    for(int i = 1; i <= n; i++){
        int k;  cin>>k;
        int t;  cin>>t;  s.insert(t);
        for(int i = 2; i <= k; i++){
            int x;  cin>>x;  s.insert(x);
            merge(t,x);
        }
    }
    cout<<s.size()<<" "<<count(s.size())<<"\n";
    int q;  cin>>q;
    for(int i = 1; i <= q; i++){
        int a, b;  cin>>a>>b;
        if(find(a)==find(b))cout<<"Y\n";
        else cout<<"N\n";
    }
    return 0;
}

L2-025

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;

vector<int>G[maxn];
int num[maxn], tmp[maxn];

int main(){
    int n, m;
    cin>>n>>m;
    for(int i = 1; i <= m; i++){
        int a, b;  cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
        num[a]++; num[b]++;
    }
    int T;  cin>>T;
    while(T--){
        for(int i = 1; i <= n; i++)tmp[i]=num[i];
        int kp;  cin>>kp;
        for(int i = 1; i <= kp; i++){
            int x;  cin>>x;
            for(int j = 0; j < G[x].size(); j++){
                tmp[G[x][j]]--;
            }
            tmp[x] = 0;
        }
        int ok = 1;
        for(int i = 1; i <= n; i++)
            if(tmp[i]>0){ok=0;break;}
        if(ok)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

L2-026

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;

int Hei;
vector<int>Yezi;

vector<int>G[maxn];
void dfs1(int u, int h){
    Hei = max(Hei, h);
    for(int i = 0; i < G[u].size(); i++){
        dfs1(G[u][i], h+1);
    }
}
void dfs2(int u, int h){
    if(h==Hei){
        Yezi.push_back(u);
    }
    for(int i = 0; i < G[u].size(); i++){
        dfs2(G[u][i], h+1);
    }
}

int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        int x;  cin>>x;
        if(x!=-1)G[x].push_back(i);
        else G[0].push_back(i);
    }
    dfs1(0,0);
    dfs2(0,0);
    cout<<Hei<<endl;
    cout<<Yezi[0];
    for(int i = 1; i < Yezi.size(); i++)
        cout<<" "<<Yezi[i];
    return 0;
}

L2-027

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;

string st[maxn]; int sc[maxn];

int r[maxn];
void init(int n){for(int i = 1; i <= n; i++)r[i]=i;}
bool cmp(int a, int b){return sc[a]!=sc[b]?sc[a]>sc[b]:st[a]<st[b];}

int main(){
    int n, g, k;
    cin>>n>>g>>k;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        cin>>st[i]>>sc[i];
        if(sc[i]>=g)ans += 50;
        else if(sc[i]>=60)ans += 20;
    }
    cout<<ans<<endl;
    init(n);
    sort(r+1,r+n+1,cmp);
    int rk=1;
    for(int i=1; i <= n ; i++){//i>=n,RE2
        if(i!=1 && sc[r[i]]!=sc[r[i-1]])rk = i;
        if(rk > k)break;
        cout<<rk<<" "<<st[r[i]]<<" "<<sc[r[i]]<<endl;
    }
    return 0;
}

L2-028

#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;
set<int>happy;
vector<pair<int,int> >ans;
int dd(int x){
    int sum = 0;
    while(x>0){
        sum += (x%10)*(x%10);
        x /= 10;
    }
    return sum;
}
bool is_prime(int x){
    for(int i = 2; i <= sqrt(x)+1; i++)
        if(x%i==0)return false;
    return true;
}
void love(int x){
    int t = x;
    set<int>se;
    while(x!=1 && !se.count(x)){
        se.insert(x);
        x = dd(x);
    }
    if(x==1){
        //if(!is_prime(t))cout<<t<<" "<<se.size()<<"\n";
        //else cout<<t<<" "<<2*se.size()<<"\n";
        if(!is_prime(t))ans.push_back(make_pair(t,se.size()));
        else ans.push_back(make_pair(t,2*se.size()));
        se.erase(t);
        happy.insert(se.begin(),se.end());
    }
}

int main(){
    //cout<<dd(dd(19));
    //love(19);
    //return 0;
    int l, r;
    cin>>l>>r;
    for(int i = l; i <= r; i++){
        love(i);
    }
    for(int i = 0; i < ans.size(); i++){
        if(!happy.count(ans[i].first)){
            cout<<ans[i].first<<" "<<ans[i].second<<"\n";
        }
    }
    if(ans.size()==0){
        cout<<"SAD\n";
    }
    return 0;
}

L2-030

#include<bits/stdc++.h>
using namespace std;
struct node{
    char sex;
    string father;
};
map<string,node>people;
inline int judge(string a, string b){//TLE6
    int i = 1, j;
    for(string A=a; !A.empty(); A=people[A].father,i++){
        j = 1;
        for(string B=b; !B.empty(); B=people[B].father,j++){
            if(i>=5 && j>=5)return 1;//TLE6
            if(A==B && (i<5||j<5))return 0;//WA3,6:任意一个五代内有CA都不行
        }
        //if(i>=5 && j>=5)break; WA6
    }
    return 1;
}

int main(){
    int n;  cin>>n;
    cin.sync_with_stdio(false);//TLE6!!
    string a, b, t;  //TLE6
    for(int i = 0; i < n; i++){
        cin>>a>>b;
        if(b.back()=='n') //+sson
            people[a] = {'m',b.substr(0,b.size()-4)};
        else if(b.back()=='r')//+sdottir
            people[a] = {'f',b.substr(0,b.size()-7)};
        else people[a].sex = b.back();
    }
    int m;  cin>>m;
    //string a, b, t;//TLE6
    for(int i = 0; i < m; i++){
        cin>>a>>t>>b>>t;
        if(people.find(a)==people.end()||people.find(b)==people.end())
            printf("NA\n");//TLE6!!
        else if(people[a].sex == people[b].sex)
            printf("Whatever\n");
        else if(judge(a,b))
            printf("Yes\n");
        else 
            printf("No\n");
    }
    return 0;
}

L2-031

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100010;
vector<int>Tree[maxn];
int rt, in[maxn], Hei, ans;
void dfs1(int u, int h){
    Hei = max(Hei, h);
    for(int i = 0; i < Tree[u].size(); i++){
        dfs1(Tree[u][i], h+1);
    }
}
void dfs2(int u, int h){
    if(h==Hei)ans = u;
    if(ans)return ;
    for(int i = 0; i < Tree[u].size(); i++){
        dfs2(Tree[u][i],h+1);
    }
}
int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        int k;  cin>>k;
        for(int j = 1; j <= k; j++){
            int x;  cin>>x;
            Tree[i].push_back(x);
            in[x]++;
        }
    }
    for(int i = 1; i <= n; i++)
        if(in[i]==0){rt = i; break;}
    //cout<<rt<<endl;
    dfs1(rt,1);
    dfs2(rt,1);
    cout<<ans<<endl;
    return 0;
}

L2-032

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m, k;
    cin>>n>>m>>k;
    while(k--){
        stack<int>s;
        //int ok = 1, cc = 1;
        int cc = 1, mx = 1;
        for(int i = 1; i <= n; i++){
            int x;  cin>>x;
            int ok = 1;
            if(cc==x){cc++; ok = 0;}
            while(s.size() && cc==s.top()){
                //cout<<"asdf "<<s.top()<<" "<<cc<<"\n";
                s.pop(); cc++; ok = 0;
            }
            if(ok)s.push(x);
            mx = max(mx, (int)s.size());
            //cout<<x<<" "<<cc<<"\n";
        }
        while(s.size()==cc){s.pop();cc++;}
        if(cc==n+1 && mx<=m)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}