【PTA-训练day11】L2-023 图着色问题 + L1-039 古风排版

目录

L2-023 图着色问题 - dfs

测试点3：图可能是不联通的 所以不能是dfs(1)

L1-035 情人节 - 15

L1-039 古风排版 - 20

L1-040 最佳情侣身高差 - 10

---

L2-023 图着色问题 - dfs

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

思路：

从点1出发 进行dfs

dfs内 遍历和该点相连的其他点 如果颜色相同则返回false

主函数里遍历1~n的点 一旦有重复的就跳出

因为：图可能是不联通的，所以必须遍历1~n个点

如果1~n个点都满足不重复 则输出Yes 否则输出No

#include 
using namespace std;
 
const int N=510;
int n,m,k;
bool g[N][N];
bool st[N];
int color[N];
 
bool dfs(int u)
{
    st[u]=true;
    for(int i=1;i<=n;i++) //遍历该点相关联的节点
        if(g[u][i])
        {
            if(color[u]==color[i]) return false;
            if(!st[i])
                if(!dfs(i)) return false;
        }
    return true;
}
 
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=g[b][a]=true;
    }
 
    int t;
    cin>>t;
    while(t--)
    {
        set<int>s;
        memset(color,0,sizeof color);
        memset(st,false,sizeof st);
        for(int i=1;i<=n;i++)
        {
            cin>>color[i];
            s.insert(color[i]);
        }
        if(s.size()!=k)
        {
            cout<<"No"<
            continue;
        }
        int i;
        for(i=1;i<=n;i++)
            if(!dfs(i)) break; //一旦有重复的点 则跳出
        if(i-1==n) cout<<"Yes"<//如果上面循环不跳出 说明没有重复的点
        else cout<<"No"<
    }
    return 0;
}

测试点3：图可能是不联通的 所以不能是dfs(1)

#include 
using namespace std;
 
const int N=510;
int n,m,k;
bool g[N][N];
bool st[N];
int color[N];
 
bool dfs(int u)
{
    st[u]=true;
    for(int i=1;i<=n;i++) //遍历该点相关联的节点
        if(g[u][i])
        {
            if(color[u]==color[i]) return false;
            if(!st[i])
                if(!dfs(i)) return false;
        }
    return true;
}
 
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=g[b][a]=true;
    }
 
    int t;
    cin>>t;
    while(t--)
    {
        set<int>s;
        memset(color,0,sizeof color);
        memset(st,false,sizeof st);
        for(int i=1;i<=n;i++)
        {
            cin>>color[i];
            s.insert(color[i]);
        }
        if(s.size()!=k)
        {
            cout<<"No"<
            continue;
        }
        if(dfs(1)) cout<<"Yes"<
        else cout<<"No"<
    }
    return 0;
}

L1-035 情人节 - 15

#include 
using namespace std;
int main()
{
    int cnt=0;
    string s,x2,x14;
    while(true)
    {
        cin>>s;
        if(s==".") break;
        cnt++;
        if(cnt==2) x2=s;
        if(cnt==14) x14=s;
    }
    if(cnt<2) cout<<"Momo... No one is for you ...";
    else if(cnt<14) cout<" is the only one for you...";
    else cout<" and "<" are inviting you to dinner...";
    
}

L1-039 古风排版 - 20

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

#include 
using namespace std;
int main()
{
    char ch[101][101];
    int n,t,m,cnt=0;
    cin>>n;
    cin.get();//接收回车 大坑
    string s;
    getline(cin,s);
    int l=s.size();
    for(int i=0;;i++)
        if((l+i)%n==0)
        {
            t=i;
            break;
        }
    l+=t,m=l/n;
    for(int j=m-1;j>=0;j--)
        for(int i=0;i
        {
            if(s[cnt]=='\0') ch[i][j]=' ';  //注意最后一行最后是'/0'
            else ch[i][j]=s[cnt++];
        }
    for(int i=0;i
    {
        for(int j=0;j
        {
            cout<
        }
        cout<
    }
}

L1-040 最佳情侣身高差 - 10

#include 
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char c;
        double h;
        cin>>c>>h;
        if(c=='M') printf("%.2f\n",h/1.09);
        else printf("%.2f\n",h*1.09);
    }
}