本文共 6741 字，大约阅读时间需要 22 分钟。

A

题目大意

n个点 编号从1到n m条有向边，注意是有向边 大概意思就是A认识B，B认识C，那么A也认识C 感觉这题可以用并查集的方式做 不过我不太会 如果不存在这种关系的话输出NO 否则输出YES

题解

用dfs搜 我采用Vector存图，然后这道题可以转化成有向完全图的判断 我们只需要对于连通块进行判断 对于孤儿结点没有必要理睬 对于有向完全图 边的个数为n*(n-1)

#include
   
    using namespace std;const int maxn=15e4+10;typedef long long ll;vector
    
      vr[maxn];int n,m,u,v;int degree[maxn];bool vis[maxn];ll ans;void dfs(int t){
       vis[t]=true;    ++ans;    for(int j=0;j
     
      >n>>m;    for(int i=0;i
      
       >u>>v;        vr[u].push_back(v);        vr[v].push_back(u);        degree[u]++,degree[v]++;    }    ll sum=0;    for(int i=1;i<=n;i++){
           if(!vis[i]&&degree[i]){
               ans=0;            dfs(i);            sum=sum+ans*(ans-1);        }    }    if(m*2==sum)        cout<<"YES"<
      
     
    
   

B

题目大意

一个无向图，使得顶点集V可以分割为两个互不相交的子集A,B，使得所有边两端分别属于两个子集A,B。

题解

其实就是二分图求解过程 采用染色法 判断给你的无向边是否能形成无向图 如果不能形成二分图就输出-1 还有需要注意的一点是题目中对于孤儿结点没有任何要求 随便在哪边都可以 或者都不放也行 代码中在dfs里面没有处理孤儿结点

dfs解法

/*    二分图，dfs染色     用vector数组存每个点的相邻的点，    先将每个点的颜色标为-1，再逐个遍历，    每当找到一个点的颜色是-1时，dfs将其及其相邻点染色；    如果染色时发现该点已经染色了，则须进行判断    1,如果该点的颜色与想给它染的颜色相同，则直接返回（对于写法要注意，刚开始判断放在外面，造成了死循环）     2，如果该点的颜色与想染的颜色不同，则说明产生了矛盾，及该图不能成为二分图，标记并返回     最后打印就好 */#include
   
    #define mst(a,b) memset(a,b,sizeof(a))using namespace std;const int maxn=1e5+10;vector
    
      vr[maxn],co[2];//vr[] 用来存边，co[]用来存每种颜色的点 int n,m,u,v,ff;int color[maxn];void dfs(int t,int c){
       if(!ff)        return;    if(color[t]!=-1){
           if(color[t]!=c)        // 这个判断不能放在外面if中，会少判断要染的颜色正是想要的时候这种情况             ff=0;            return;    }    color[t]=c;    co[c].push_back(t);    for(int j=0;j
     
      >n>>m){
           for(int i=0;i
      
       >u>>v;            vr[u].push_back(v);            vr[v].push_back(u);        }        ff=1;        for(int i=1;i<=n&&ff;i++){
               if(color[i]==-1)            dfs(i,0);        }        //cout<
       
        <
       
      
     
    
   

C

题目大意

给你n个站点，求列车能载的最大人数

题解

每次遍历求最大值即可

#include
   
    using namespace std;const int maxn=1000+10;int n,a[maxn],b[maxn];int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    while(cin>>n){
           for(int i=0;i
    
     >a[i]>>b[i];        }        int remax=b[0];        int ans=b[0];        for(int i=1;i
    
   

D

题目大意

计算每个向量矢量和是否为0

题解

分别对x,y,z计算求和 最后判断三个值是否为0即可（水）

#include
   
    using namespace std;int n,x,y,z;int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    while(cin>>n){
           int sum1=0,sum2=0,sum3=0;        for(int i=1;i<=n;i++){
               cin>>x>>y>>z;            sum1+=x,sum2+=y,sum3+=z;        }        if(!sum1&&!sum2&&!sum3)            cout<<"YES"<
   

E

题目大意

求出幸运数 能被4与7组成的数整除

题解

直接暴力 求出1000内所有与4 7 相关的数，然后遍历就可以了

#include
   
    using namespace std;int n;int a[13]={
   4,7,44,47,74,77,444,447,474,477,744,747,777};int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    while(cin>>n){
           int ff=0;        for(int i=0;i<13;i++){
               if(n%a[i]==0){
                   ff=1;                break;            }        }        if(ff)            cout<<"YES"<
   

F

题目大意

有个散布谣言的人，要把一个谣言传给所有人，有的人相互之间是朋友（只要告诉其中一人，他的朋友就会知道），求最小花费。例如样例一，先告诉1（然后1会告诉4，4再告诉5），这样就只用再告诉2和3就行了，所以最小花费是2+5+3=10。

题解

采用并查集，求每个连通块里面的最小值，然后累加

#include
   
    using namespace std;typedef long long ll;const int maxn=1e5+10;int n,m;int pre[maxn],val[maxn];int find_pre(int x){
       if(x!=pre[x])        pre[x]=find_pre(pre[x]);    return pre[x];}void join(int a,int b){
       int x=find_pre(a);    int y=find_pre(b);    if(x!=y)        pre[x]=y;}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    cin>>n>>m;    for(int i=1;i<=n;i++){
           pre[i]=i;    }    for(int i=1;i<=n;i++)        cin>>val[i];    int a,b;    for(int i=1;i<=m;i++){
           cin>>a>>b;        join(a,b);    }    for(int i=1;i<=n;i++){
           val[find_pre(i)]=min(val[find_pre(i)],val[i]);    }    ll sum=0;    for(int i=1;i<=n;i++){
           if(i==find_pre(i))            sum+=val[i];    }    cout<
    
     <
    
   

G

题目大意

n个人，每个人会一些语言，两个人只要有会一门相同的语言就可以交流，问为了让这n个人都交流，至少还得学多少门语言

题解

采用dfs搜，先确定两个人之间是否有相同的语言，然后连一条边，然后判断连通块的个数，我们至少需要的语言门数是连通块的个数-1 相当于n个顶点 至少需要n-1条边来连接

#include
   
    #define mst(a,b) sizeof(a,b,sizeof(a))using namespace std;const int maxn=100+10;int n,m,k,v;int a[maxn][maxn];int mp[maxn][maxn],vis[maxn];void dfs(int t){
       vis[t]=1;    for(int j=1;j<=n;j++){
           if(mp[t][j]&&!vis[j]){
               dfs(j);        }    }}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    int cnt,ans;    cin>>n>>m;        //mst(vis,0);        //mst(mp,0);        cnt=0,ans=0;        for(int i=1;i<=n;i++){
               cin>>k;            if(k==0)                ++ans;            for(int j=1;j<=k;j++){
                   cin>>v;                a[i][v]=1;            }        }        for(int i=1;i<=n;i++){
               for(int j=i+1;j<=n;j++){
                   for(int k=1;k<=m;k++){
                       if(a[i][k]&&a[j][k]){
                           mp[i][j]=mp[j][i]=1;                    }                }            }        }        for(int i=1;i<=n;i++){
               if(!vis[i]){
                   ++cnt;                dfs(i);            }        }        //cout<<"ans="<
    
     <
    
   

H

题目大意

将两个区域块进行比较大小，一方大就把对面拿过来往后加，先放对面小的，然后放当前自己的，一直放一方赢为止 或者出现了死循环就输出-1

题解

可以直接用数组模拟，用两个数组指针分别指向a和b，指向当前正在比较的两个数，然后将赢的那一方原始数组长度 每次加2 放入赢的两个数 最后我们判断一下 如果指向自己的指针小于等于自己数组长度，那么就是赢的情况，输的那一方肯定是指针已经指出去了。然后我们还要判断死循环比较的那种，就自己取一个上限就好了，比较超过这个上限就输出-1，毕竟这个题n不是很大，也不会比较很多次的 我记得题解好像只要判断比较106次以上就好了 我这里写了1e5+10次。。。 具体参考如下代码

#include
   
    using namespace std;int lena,lenb;const int maxn=1e5+10;int a[maxn],b[maxn];int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    cin>>lena>>lena;    for(int i=1;i<=lena;i++)        cin>>a[i];    cin>>lenb;    for(int i=1;i<=lenb;i++)        cin>>b[i];    int ida=1,idb=1;    int cnt=0;    while(ida<=lena&&idb<=lenb&&lena<=maxn){
           ++cnt;        if(a[ida]>b[idb]){
               a[++lena]=b[idb];            a[++lena]=a[ida];            ++ida;            ++idb;        }        else{
               b[++lenb]=a[ida];            b[++lenb]=b[idb];            ++ida;            ++idb;        }    }    if(lena>maxn)        cout<<-1<
   

I

题目大意

买香蕉，每个香蕉的价格为i*k 累加之后算比自己预算多多少 那就借多少

题解

水题，累加判断超出预算多少即可

#include
   
    using namespace std;typedef long long ll;ll k,n,w;int main(){
       ll ans=0;    cin>>k>>n>>w;    ll nn=0;    for(int i=1;i<=w;i++){
           nn=k*i;        ans+=nn;    }    if(ans>=n)        cout<
    
     <
    
   

J

题目大意

HQ9能输出一段话 +不会输出一段话 给定一段字符串 如果能够输出一段话就YES 否则NO

题解

水题，直接遍历判断是否存在H Q 9字符就可以了

#include
   
    using namespace std;int main(){
       string s;    cin>>s;    bool ff=false;    for(int i=0;i
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/100889526 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！