PTA-搜索补题

最近几天特别消极，做题时逻辑不清晰也不是那么想做，最后做的一塌糊度…

1.图着色问题

一开始没用set做,最后没全对,后来用set就过了(注释掉的部分是在网上看的别人的).

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <set>
#include <map>
#define ll long long

using namespace std;
int n,e,v,k;
int g[550][550];
int sd,ed;
//struct node
//{
//    int ss,ee;
//};

int main()
{
    cin>>v>>e>>k;
//    node g[e];
    memset(g,0,sizeof(g));
    for(int i=1; i<=e; i++)
    {
//        cin>>g[i].ss>>g[i].ee;
        cin>>sd>>ed;
        g[sd][ed] = g[ed][sd] = 1;
    }
    int q,col[550];
    cin>>q;
    int flag;
    while(q--)
    {
        set<int>s;
        memset(col,0,sizeof(col));
        for(int i=1; i<=v; i++)
        {
            cin>>col[i];
            s.insert(col[i]);
        }
        if(s.size()!=k)
        {
            cout<<"No"<<endl;
            continue;
        }
        else
        {
            flag=1;
//            for(int i=1; i<=e; i++)
//            {
//                if(col[g[i].ss] == col[g[i].ee])
//                {
//                    flag=0;
//                    break;
//                }
//            }
            for(int i=1; i<=v; i++)
            {
                for(int j=1; j<=v; j++)
                {
                    if(i!=j&&col[i]==col[j]&&g[i][j])
                    {
                        flag=0;
                        goto label;
                    }
                }
            }
            label:
            if(flag)
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }
    return 0;
}

           

2.功夫传人

网上看的题解

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <set>
#include <map>
#define ll long long

using namespace std;
const int N = 1e5+10;
vector<int>child[N];
double val[N];
double sum=0;
double z,r;

void DFS(int id,double w)
{
    if(val[id])
    {
        sum+=w*val[id];
    }
    else
    {
        for(int i=0; i<child[id].size(); i++)
        {
            DFS(child[id][i],w*r);
        }
    }
    return;
}

int main()
{
    int k,n,id;
    double g[550][550];
    memset(g,0,sizeof(g));
    cin>>n>>z>>r;
    r = (100-r)/100;
    for(int i=0; i<n; i++)
    {
        cin>>k;
        if(k == 0)
        {
            cin>>val[i];
        }
        else
        {
            for(int j=0; j<k; j++)
            {
                cin>>id;
                child[i].push_back(id);
            }
        }
    }
    DFS(0,z);
    cout<<(int)sum<<endl;
    return 0;
}

           

3.红色警戒

用DFS计算一下连通分量,每去除一个点计算一下连通分量,如果比之前的连通分量增加了>=2,则red alert,否则city is lost.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <set>
#include <map>
#define ll long long

using namespace std;
const int N = 1e5+10;
int n,m,u,v;
int g[550][550];
bool vis[N];

void DFS(int s)
{
    for(int i=0; i<n; i++)
    {
        if(!vis[i]&&g[s][i])
        {
            vis[i]=1;
            DFS(i);
        }
    }
}

int main()//连通分量增加的数量>=警报会响
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>u>>v;
        g[u][v] = g[v][u] = 1;
    }
    int num=0;
    for(int i=0; i<n; i++)
    {
        if(!vis[i])
        {
            DFS(i);
            num++;
        }
    }
    int q,id;
    cin>>q;
    for(int k=1; k<=q; k++)
    {
        cin>>id;
        memset(vis,0,sizeof(vis));
        for(int i=0; i<n; i++)
        {
            if(g[id][i]&&id!=i)
                g[i][id] = g[id][i] = 0;
        }
        int cnt=0;
        for(int i=0; i<n; i++)
        {
            if(!vis[i])
            {
                DFS(i);
                cnt++;
            }
        }
        if(cnt-num>=2)
            printf("Red Alert: City %d is lost!\n",id);
        else
            printf("City %d is lost.\n",id);
        num = cnt;
    }
    if(q>=n)
        cout<<"Game Over."<<endl;
    return 0;
}
//https://blog.csdn.net/weixin_43824158/article/details/88814438