Ⅰ.L2-021 点赞狂魔---STL应用

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。输入格式：输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。输出格式：统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。输入样例：5bob 11 101 102 103 104 105 106 107 108 108 107 107peter 8 1 2 3 4 3 2 5 1chris 12 1 2 3 4 5 6 7 8 9 1 2 3john 10 8 7 6 5 4 3 2 1 7 5jack 9 6 7 8 9 10 11 12 13 14输出样例：jack chris john

思路：使用集合(自动去重) 统计每个人点赞不同博文的数量。输出前3个人，不足3人输出“-”

#include
    
     using namespace std;int n;set
     
       se;struct node{    int size;    string name;    int aclSize;};node ans[105];bool cmp(node a,node b){    if(a.size == b.size){        return a.aclSize < b.aclSize;    }    return a.size > b.size;}int main(){    cin>>n;    for(int i=1;i<=n;i++){        string name;        cin>>name;        ans[i].name = name;        int k;        cin>>k;        ans[i].aclSize = k;        for(int j=1;j<=k;j++){            int d;            cin>>d;            se.insert(d);        }        ans[i].size = se.size();        se.clear();    }    sort(ans+1,ans+n+1,cmp);    int first = 1;    for(int i=1;i<=3 && i<=n;i++){        if(first){            cout<
     
    

Ⅱ.L2-022 重排链表--数组模拟链表

给定一个单链表 L请编写程序将链表重新排列为 L例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。输入格式：每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。接下来有N行，每行格式为：Address Data Next其中Address是结点地址；Data是该结点保存的数据，为不超过10​5​​ 的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。输出格式：对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。输入样例：00100 600000 4 9999900100 1 1230968237 6 -133218 3 0000099999 5 6823712309 2 33218输出样例：68237 6 0010000100 1 9999999999 5 1230912309 2 0000000000 4 3321833218 3 -1

思路：结构体模拟链表，具体做法不太好表达，看代码吧

转载至：

#include
    
     #include
     
      #include
      
       using namespace std;const int maxn = 1e5;struct Node{    int address;    int key;    int next;    int num; //结点的最终位置下标 }node[maxn]; //存放数据 后面改变下标后也存放输出结果 bool vis[maxn];bool cmp(Node a,Node b){    return a.num
      
     
    

Ⅲ.L2-023 图着色问题---图着色dfs、bfs、邻接点问题

图着色问题是一个著名的NP完全问题。给定无向图G=(V,E)，问可否用K种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。输入格式：输入在第一行给出3个整数V（0
    

思路：只需判断邻接点是否颜色相等，bfs和dfs或者直接暴力看邻接边的两端点。

还有一些特殊样例：当k(颜色数) != 输入的颜色数 也不符合条件

dfs做法 23分 wa了一个点：

#include
    
     using namespace std;vector
     
       g[510];int v,e,k,n;set
      
        se;int vis[510];int col[510];bool flag = true;void dfs(int x){    if(!flag)return;    vis[x] = 1;    int color = col[x];    for(int i=0;i
       
        >v>>e>>k;    for(int i=1;i<=e;i++){        int d1,d2;        cin>>d1>>d2;        g[d1].push_back(d2);        g[d2].push_back(d1);    }    cin>>n;    while(n--){        memset(vis,0,sizeof(vis));        for(int i=1;i<=v;i++){            int d;            cin>>d;            se.insert(d);            col[i] = d;        }        if(se.size()!=k){            cout<<"No"<
       
      
     
    

其他暴力做法—查看邻接矩阵中的 邻接边两端点颜色是否相等

参考代码：

Ⅳ.L2-024 部落--并查集

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。输入格式：输入在第一行给出一个正整数N（≤104），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人：K P[1] P[2] ⋯ P[K]其中K是小圈子里的人数，P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过10​4。之后一行给出一个非负整数Q（≤104），是查询次数。随后Q行，每行给出一对被查询的人的编号。输出格式：首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。输入样例：43 10 1 22 3 44 1 5 7 83 9 6 4210 53 7输出样例：10 2YN

思路：并查集，同一部落的属于同一集合

#include
    
     using namespace std;const int maxn = 10010;int n;int father[maxn];set
     
       se;set
      
        se2;//查找 int find(int x){    if(father[x]==x) return x;    return father[x]=find(father[x]);} //合并 void unite(int x,int y){    x=find(x);    y=find(y);    if(x!=y)    father[x]=y;}//初始化 void init(){    for(int i=1;i<=maxn-5;i++){ //注意这里初始化 不能初始化成maxn  ----段错误有时也不提醒..大坑         father[i] = i;    }}int main(){    cin>>n;    init();    for(int i=1;i<=n;i++){        int k;        cin>>k;        int d;        cin>>d;        se.insert(d);//se集合中加入第一个元素         int fa = d;        for(int j=2;j<=k;j++){            cin>>d;            se.insert(d);            unite(fa,d);//合并         }    }    for(set
       
        ::iterator it = se.begin();it!=se.end();it++){        se2.insert(find(*it));//se2集合查询 有多少个根(部落数量)     }    printf("%d %d\n",se.size(),se2.size());    int q;    cin>>q;    while(q--){        int pa,pb;        cin>>pa>>pb;        pa = find(pa);        pb = find(pb);        if(pa==pb){            puts("Y");        }else{            puts("N");        }    }    return 0;}