【PTA-训练day6】L2-016 愿天下有情人都是失散多年的兄妹+ L1-011 帅到没朋友

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

PTA | 程序设计类实验辅助教学平台

思路：

先记录每个人的父母 然后k组查询

分别用dfs搜索两个人的族谱 五服之内出现的人都标记

如果搜索第二个人时 出现已标记的人 说明这两个有共同的祖先

#include 
using namespace std;
 
const int N=1e5+10;
bool st[N];
bool f=false;
char sex[N];
vector<int> v[N];
 
void dfs(int u,int d)
{
    if(d>=5) return; //五服之外就return
    st[u]=true; //把该点标记
    for(int i=0;isize();i++) //遍历该点的所有长辈 如果有的长辈被标记过 说明两个人有共同的祖先
    {
        if(st[v[u][i]]) f=true;
        dfs(v[u][i],d+1);
    }
}
 
int main()
{
    int n;
    cin>>n;
    for(int i=0;i
    {
        int id;
        cin>>id;
        char c;
        cin>>c;
        sex[id]=c;
        int fa,ma;
        cin>>fa>>ma;
        if(~fa) 
        {
            sex[fa]='M';
            v[id].push_back(fa);
        }
        if(~ma)
        {
            sex[ma]='F';
            v[id].push_back(ma);
        }
    }
        int k;
        cin>>k;
        while(k--)
        {
            int x,y;
            cin>>x>>y;
            f=false;
            memset(st,false,sizeof st); //每次查询 st数组都要清空
            dfs(x,0);
            dfs(y,0);
            if(sex[x]==sex[y]) cout<<"Never Mind"<
            else{
                if(!f) cout<<"Yes"<
                else cout<<"No"<
            }
        }
}

L1-017 到底有多二 - 15

PTA | 程序设计类实验辅助教学平台

import java.util.*;
 
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        String s=sc.next();
        int cnt=0,n=s.length();
        for(int i=0;iif(s.charAt(i)=='2') cnt++;
        double bei=1;
        if((s.charAt(n-1)-'0')%2==0) bei*=2; //因为判断负数时n的值会改变 所以这个要放在前面
        if(s.charAt(0)=='-')
        {
            bei*=1.5;
            n-=1;
        }
        System.out.printf("%.2f%%",cnt*1.0/n*bei*100);
    }
}

L1-018 大笨钟 - 10

PTA | 程序设计类实验辅助教学平台

1、java版

接收字符的过程比较麻烦

import java.util.*;
 
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        String[] num=sc.next().split(":");
        int hh=Integer.parseInt(num[0]),mm=Integer.parseInt(num[1]);
        if(hh>=0&&hh<=11||hh==12&&mm==0)
        {
            System.out.printf("Only %02d:%02d.  Too early to Dang.",hh,mm);
            
        }else
        if(mm==0) 
        {
            int n=hh-12;
            while(n-->0) System.out.print("Dang");
        }else{
            int n=hh-11;
            while(n-->0) System.out.print("Dang");
        }
    }
}

2、c++版 

#include 
using namespace std;
 
int main()
{
    int hh,mm;
    char ch;
    cin>>hh>>ch>>mm;
    if(hh>=0&&hh<=11||hh==12&&mm==0) printf("Only %02d:%02d.  Too early to Dang.",hh,mm);
    else if(mm==0) 
    {
        int n=hh-12;
        while(n--) cout<<"Dang";
    }
    else{
        int n=hh-11;
        while(n--) cout<<"Dang";
    }
}

L1-020 帅到没朋友 - 20

PTA | 程序设计类实验辅助教学平台

1、java版 - 最后一个点超时 喜闻乐见

思路：

• 把朋友圈里出现过的id都存入set里，其中要注意如果朋友圈只有一个人，这种情况是不存入朋友圈的
• 因为输出时，不能重复输出id，且要保证输出顺序，所以用LinkedHashSet
• 之前set中出现过的id就不输出，否则存入LinkedHashSet的res容器里
• 最后输出我用了2种方法：一个是把set转化为string数组；一个是直接输出set

 set转化为string数组版：

import java.util.*;
 
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Set st=new HashSet<>();
        Set res=new LinkedHashSet<>();
        while(n-->0)
        {
            int k=sc.nextInt();
            if(k==1) //如果朋友圈就他一个人 说明答案也要输出他 也就是不存入set
            {
                String s=sc.next();
                continue;
            }
            while(k-->0)
            {
                String s=sc.next();
                st.add(s);
            }
        }
        int m=sc.nextInt();
        int cnt=0;
        for(int i=0;i
        {
            String t=sc.next();
            if(st.contains(t)) continue;
            cnt++;
            res.add(t);
        }
        if(cnt==0) System.out.print("No one is handsome");
        else
        {
            String[] ans=res.toArray(new String[]{}); //这里是把set转化为string数组
            for(int i=0;i
            {
                if(i!=0) System.out.print(" ");
                System.out.print(ans[i]);
            }
        }
    }
}

 直接输出set版：

import java.util.*;
 
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        Set st=new HashSet<>();
        Set res=new LinkedHashSet<>();
        while(n-->0)
        {
            int k=sc.nextInt();
            if(k==1) //如果朋友圈就他一个人 说明答案也要输出他 也就是不存入set
            {
                String s=sc.next();
                continue;
            }
            while(k-->0)
            {
                String s=sc.next();
                st.add(s);
            }
        }
        int m=sc.nextInt();
        int cnt=0;
        for(int i=0;i
        {
            String t=sc.next();
            if(st.contains(t)) continue;
            cnt++;
            res.add(t);
        }
        if(cnt==0) System.out.print("No one is handsome");
        else
        {   
            boolean f=true;
            for(Object x:res)
            {
                if(f)
                {
                    System.out.print(x);
                    f=false;
                }
                else System.out.print(" "+x);
            }
        }
    }
}

2、c++版

#include 
using namespace std;
 
int main()
{
    int n;
    cin>>n;
    set st;
    while(n--)
    {
        int k;
        cin>>k;
        string s;
        if(k==1)
        {
            cin>>s;
            continue;
        }
        while(k--)
        {
            cin>>s;
            st.insert(s);
        }
    }
    int m,cnt=0;
    cin>>m;
    set res;
    while(m--)
    {
        string s;
        cin>>s; //要根据输入顺序输出
        if(!st.count(s)&&!res.count(s)) //如果朋友圈中无记录且答案不重时
        {
            if(cnt==0)cout<
            else cout<<" "<
            res.insert(s);
            cnt++;
        }
    }
    if(cnt==0) cout<<"No one is handsome";
}