首页 > 代码库 > 辽宁省赛——杨鲁斯卡尔专场-J

辽宁省赛——杨鲁斯卡尔专场-J

2024-07-04 17:56:19   224人阅读

题意：

就是一个人走到一个城市就会记录与该城市相连的城市有多少，最后判断这些城市是否全部相连；

样例输入

8
7 7 4 3 3 3 2 1
10
5 4 3 3 2 2 2 1 1 1

样例输出

NO
YES

解题思路：
其实就是判断无向连通图，sum<=(t)*(t-1)/2公式，sum是边长的和，t是顶点个数。不过需要注意的有几点。1、是当输入有0的时候直接就是no
因为肯定不可能全部连通。2.是当输入等于2的时候可能这个公式判断不了需要自己做处理。

忘了写了打表的代码起就是用数组写的模拟过程，模拟是对的会超时，所以可以用这个打表这个代码也发上来吧，没有写注释
#include<iostream>
#include<stdio.h>
#include<vector>
#include<iterator> 
#include<cstring>
using namespace std;
int pp[11005];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(pp,0,sizeof(pp));
        int temp=2;
        int it,itr;
        int len= n;
        int ccc=0;
        while(temp<=len)
        {         
                  ccc++;
            cout<<temp<<",";
            int i=0,res=0;
            for(it=1;it<=n;it++)
            {
                if(pp[it]) continue;
                i++;
                if(i==temp)
                {
                           
                    len--;
                    pp[it]=1;
                    i=0;
                }                                                
            } 
      
            for(itr=temp+1;itr<=n;itr++)
            {
                if(!pp[itr]) 
                {
                    temp=itr;
                    break;
                }                                  
            }
        } 
        //cout<<ccc<<")))))"; 
       // printf("%d\n",len);       
    }
    system("pause");
    return 0;   
}
View Code

下面是AC代码



具体代码：
#include<iostream>
#include<cstring>
using namespace std;
int num[10005];
int main()
{
    int t,sum,res;
    while(scanf("%d",&t)!=EOF)
    {
        sum=0;
        res=0;
        memset(num,0,sizeof(num));
        for(int i=0;i<t;i++)
        {
            cin>>num[i];
            sum+=num[i];
            if(num[i]==0)
                res=1;
        }
        if(t==2)
        {
            if(sum==2&&res==0)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        else
        {
            if(sum<=(t)*(t-1)/2&&res==0)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
    }
    system("pause");
    return 0;
}
View Code

 


联系
我们