热身赛学习

引言

已经打了两次热身赛和一次cf了，这两天因为这个学了一点东西，记录一下……

知识是连贯的，往往想看一个东西，就要先看另一个东西，所以我由浅入深的写一下……

迭代器

迭代器介绍

迭代器是一种变量，跟指针类似，是STL库里的一种。迭代器是与容器搭配使用的，指向容器里的某个元素，然后通过迭代器可以读写指向它的元素，我的理解是类似指向数组下标的一种变量。

迭代器的使用

1. 正向迭代器

   容器类名: :iterator 迭代器名；

2. 反向迭代器

   容器类名: :reverse_iterator 迭代器名；

3. 常量正向迭代器

   容器类名: : const_iterator 迭代器名;

4. 常量反向迭代器

   容器类名: : const_reverse_iterator 迭代器名;

5. 迭代器使用实例

   vector<int> a;
   vector<int>::iterator pr;
   for(int i = 0; i < 3; i++)
   {
   
       a.push_back(i);
   }
   
   cout << a.size()<<endl;
   cout << a.back()<<endl;
   
   cout << "使用数组形式遍历vector内容"<< endl;
   for(int i = 0; i < a.size(); i++){
       cout << a[i] << "  " ;
   }
   
   cout << "使用正向迭代器形式遍历vector内容"<< endl;
   for(pr = a.begin(); pr != a.end(); pr++){
   
       //这里*pr就是迭代器pr指向的元素
       cout << *pr << "  ";
   }
   
   cout << endl;
   
   cout << "使用反向迭代器形式遍历vector内容"<< endl;
   vector<int>::reverse_iterator prr;
   
   for(prr = a.rbegin(); prr != a.rend(); prr++){
   
       cout << *prr * 3 << "  ";
   }
   
   cout << endl;

vector

vector介绍：

vector是一种顺序容器。顺序容器有可变长数组vector、双向链表list、双端队列deque。

顺序容器的特点是容器元素的位置与他们的值无关。

vector的成员函数：

vector()                        //无参构造函数，将容器初始化为空

vector(int n)                 //将容器初始化为有 n 个元素

vector(int n, const T & val)             
//假定元素的类型是 T，此构造函数将容器初始化为有 n 个元素，每 个元素的值都是 val

vector(iterator first, iterator last)            
//first 和 last 可以是其他容器的迭代器。一般来说，本构造函数初始化的结果就是将 vector 容器的内容变成与其他容器上的区间 [first, last) —致

void clear()                                  //  删除所有元素

bool empty()                                 // 判断容器是否为空

void pop_back()                           // 删除容器末尾的元素

void push_back( const T & val)    将 val 添加到容器末尾

int size()                                      //  返回容器中元素的个数

T & front()                                     // 返回容器中第一个元素的引用

T & back()                                     // 返回容器中最后一个元素的引用

iterator insert(iterator i, const T & val)           
//将 val 插入迭代器 i 指向的位置，返回 i

iterator insert( iterator i, iterator first, iterator last)          
//将其他容器上的区间 [first, last) 中的元素插入迭代器 i 指向的位置

iterator erase(iterator i)                    
//删除迭代器 i 指向的元素，返回值是被删元素后面的元素的迭代器

iterator erase(iterator first, iterator last)            
//   删除容器中的区间 [first, last)

void swap( vector <T> & v)             //将容器自身的内容和另一个同类型的容器 v 互换

vector的示例用法：

#include<iostream>
#include<vector>

int main(){

int a[4] = {1,3 ,2, 5};

vector<int> v(a,a+4); //将数组a的内容写入v
cout << "1) v.size = " << v.end() - v.begin() << endl;

cout << "2) " << "use iterator ";
vector<int>::iterator p ;
for(p = v.begin(); p != v.end();p++)
    cout << *p << " ";
cout << endl;

//删除第二个元素
v.erase(v.begin() + 1);
cout << "3) " << "after delete second element ";
for(p = v.begin(); p != v.end();p++)
    cout << *p << " ";
cout << endl;

//在第二个元素后加入13
v.insert(v.begin()+1,13);
cout << "4) " << "insert 13 after second element ";
for(p = v.begin(); p != v.end();p++)
    cout << *p << " ";
cout << endl;


//使用vector的其他构造函数
vector<int> pa(5,10);
cout << "5) " << "use another struct function ";
for(p = pa.begin(); p != pa.end();p++)
    cout << *p << " ";
cout << endl;

//将V插在pa开头
pa.insert(pa.begin(),v.begin(),v.end());
cout << "6) " << "insert all of v into pa ";
for(p = pa.begin(); p != pa.end();p++)
    cout << *p << " ";
cout << endl;

//删除第二个到第四个之间的元素
pa.erase(pa.begin() + 1,pa.begin()+3);
cout << "7) " << "after delete elements that locate at 2th and 4th ";
for(p = pa.begin(); p != pa.end();p++)
    cout << *p << " ";
cout << endl;

return 0;
}

顺序容器常用成员函数：

int size() //返回容器对象中元素的个数
  
bool empty() //判断容器是否为空

begin()：返回指向容器中第一个元素的迭代器。

end()：返回指向容器中最后一个元素后面的位置的迭代器。

rbegin()：返回指向容器中最后一个元素的反向迭代器。

rend()：返回指向容器中第一个元素前面的位置的反向迭代器。

erase(...)：从容器中删除一个或几个元素
  
clear()：从容器中删除所有元素。

front()：返回容器中第一个元素的引用。

back()：返回容器中最后一个元素的引用。

push_back()：在容器末尾增加新元素。

pop_back()：删除容器末尾的元素。

insert(...)：插入一个或多个元素

并查集

理解算法

并查集是一种树形的数据结构，用于初一一下不交集的合并以及查询问题。有一个联合-查找算法，定义了用于次数据结构的两个操作：

• Find：确定元素属于哪一个子集。这个确定方法就是不断向上查找找到它的根节点，它可以被用来确定两个元素是否属于同一子集。

• Union：将两个子集合并成同一个集合。

  

由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法，MakeSet，用于建立单元素集合。有了这些方法，许多经典的划分问题可以被解决.

为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，Find(x) 返回 x 所属集合的代表，而 Union 使用两个集合的代表作为参数。

并查集树

并查集（树）是一种将一个集合以树形结构进行组合的数据结构，如上图所示。其中每一个节点保存着到它的父节点的引用

在并查集树中，每个集合的代表即是集合的根节点。

• “查找”根据其父节点的引用向根行进直到到底树根。

• “联合”将两棵树合并到一起，这通过将一棵树的根连接到另一棵树的根。

  实现这样操作的代码如下：

int fa[N]; \\存各个元素的代表元素 
int find(int x)
{
    if(fa[x]==x) return x;
    return find(fa[x]);
 } 
void union(int x,int y)
{
    int xroot=find(x);
    int yroot=find(y);
    fa(xroot)=yroot;
}

这是并查集森林最基本的表示方法，但这种方法创建的树可能会不平衡，所以要进行优化。

优化方法一：按秩合并

第一种方法，称为“按秩合并”，即总是将更小的树连接至更大的树上。因为影响运行时间的是树的深度，更小的树添加到更深的树的根上将不会增加秩除非它们的秩相同。在这个算法中，术语“秩”替代了“深度”，因为同时应用了路径压缩时（见下文）秩将不会与高度相同。单元素的树的秩定义为0，当两棵秩同为r的树联合时，它们的秩r+1。

优化后的代码：

struct node
 {
     int parent;
     int rank;
 }fa[N]; //存各个元素的代表元素
int find(int x)
{
    if(fa[x].parent==x) return x;
    return find(fa[x].parent);
 } 
 
void merge(int x,int y)
{
    int xroot=find(x);
    int yroot=find(y);
    if(xroot==yroot)
    return;
  //x和y不在同一个集合，合并他们
    if(fa[xroot].rank<fa[yroot].rank)
        fa[xroot].parent=yroot;
    else if(fa[xroot].rank>fa[yroot].rank)
        fa[yroot].parent=xroot;
    else
    {
        fa[yroot].parent=xroot;
        fa[xroot].rank++;
    }
}

优化合并二：路径压缩

第二个优化，称为“路径压缩”，是一种在执行“查找”时扁平化树结构的方法。关键在于在路径上的每个节点都可以直接连接到根上；他们都有同样的表示方法。为了达到这样的效果，Find递归地经过树，改变每一个节点的引用到根节点。得到的树将更加扁平，为以后直接或者间接引用节点的操作加速。

优化后的代码：

struct node
 {
     int parent;
     int rank;
 }fa[N]; //存各个元素的代表元素
int find(int x)
{
    if(fa[x].parent==x) return x;
    return fa[x].parent=find(fa[x].parent);
 } 

总结

并查集概念

并查集是ACM中非常常见的一种数据结构，我也是因为这个看的。并查集可以判断相互关联的元素属于几个集合，也可以用来判断图结构中的两点是否是联通的。并查集的设计思路是：

在程序执行过程中任意元素一定输于以下三种状态：

1. 即f[i]=i，在该种状态下的元素可能是未被合并（初始状态），也可能是经过合并但是选择的父节点就是这个节点

2. 已有父节点并且就是当前状态下真正的父节点（其实是最正常的状态，第二种状态也包含第一种情况）。

3. 已有父节点但并非当前状态下真正的父节点，可能是以前的父节点，由merge函数可以看出，当合并两个节点时只是合并两个节点的父节点，当这个节点的父节点不是本身的时候这个节点的父节点就不会被更改成新的父节点，这种状态在统计集合数量的时候是危险的，因为回使得集合数量增多，但其实并不用担心这个问题，仔细考察getf函数（查找父节点）的时候就会发现f[a]=getf(f[a])这样一段代码，原来getf函数不仅返回了每个节点的父亲，还顺便修改了每个节点的f[]值使它和他父亲的f[]值一致，所以每当该节点或这个节点的子节点被merge再次合并地时候，这个节点的f[]就会被修改成正确值，但是问题就来了，万一该节点没有被再次合并怎么办？保险一点的操作应该是在merge完所有的节点之后再getf以下所有的节点，这样所有的节点就正确了。

并查集应用

1. 用来合并集合元素，并确定结合数量，查寻元素属于哪个集合。

2. 在图结构里（图里的点便是元素），确定两点是否处于联通状态，应用举例：

   1）Kruskal法最小生成树

   思路：将所有的边依照长度大小排序，依次从小到大进行行选泽，每次选中一边，就将边两端的点用并查集合并，如果选择的边经并查集查询已经联通，那么跳过这条边

   问题

   给定一个有权值的图，找出联通图内所有节点的最小路径。

   数据

   6 9

   2 4 11

   3 5 13

   4 6 3

   5 6 4

   2 3 6

   4 5 7

   1 2 1

   3 4 9

   代码

   //
   
   //  main.cpp
   
   //  图的最小生成树之kruskal算法
   
   //
   
   //  Created by 张嘉韬 on 16/3/18.
   
   //  Copyright ? 2016年 张嘉韬. All rights reserved.
   
   //
   
    
   
   #include <iostream>
   
   #include <cstring>
   
   #include <algorithm>
   
   using namespace std;
   
   int f[50];
   
   struct line
   
   {
   
       int u;
   
       int v;
   
       int w;
   
   }lines[50];
   
   int cmp(const void *a,const void *b)
   
   {
   
       return (*(line *)a).w>(*(line *)b).w?1:-1;
   
   }
   
   void init(int n)
   
   {
   
       for(int i=1;i<=n;i++) f[i]=i;
   
   }
   
   int getf(int a)
   
   {
   
       if(f[a]==a) return a;
   
       else
   
       {
   
           f[a]=getf(f[a]);
   
           return f[a];
   
       }
   
   }
   
   int  merge(int a,int b)
   
   {
   
       int t1,t2;
   
       t1=getf(a);
   
       t2=getf(b);
   
       if(t1!=t2)
   
       {
   
           f[t2]=t1;
   
           return 1;
   
       }
   
       else return 0;
   
   }
   
   int main(int argc, const char * argv[]) {
   
       freopen("/Users/zhangjiatao/Desktop/input.txt","r",stdin);
   
       int n,m,sum;
   
       sum=0;
   
       cin>>n>>m;
   
       init(n);
   
       for(int i=0;i<=m-1;i++)
   
       {
   
           cin>>lines[i].u>>lines[i].v>>lines[i].w;
   
       }
   
       qsort(lines,m,sizeof(lines[0]),cmp);
   
       for(int i=0;i<=m-1;i++) cout<<lines[i].w<<" ";
   
       cout<<endl;
   
       for(int i=0;i<=m-1;i++)
   
       {
   
           if(merge(lines[i].u,lines[i].v)==1)
   
           {
   
               sum+=lines[i].w;
   
               cout<<i+1<<" ";
   
           }
   
       }
   
       cout<<endl;
   
       cout<<sum<<endl;
   
       return 0;
   
   }

并查集的模板

1. 问题

给定m组n个元素之间的关系，问这些元素属于个集合

2. 输入

10 8

1 2

3 4

5 2

4 6

2 6

8 7

9 7

1 6

2 4

3. 代码

#include <iostream>

#include <cstring>

using namespace std;

int f[50];

void init(int n)

{

    for(int i=1;i<=n;i++) f[i]=i;

}

int getf(int a)

{

    if(f[a]==a) return a;

    else

    {

        f[a]=getf(f[a]);

        return f[a];

    }

}

void merge(int a,int b)

{

    int t1,t2;

    t1=getf(a);

    t2=getf(b);

    if(t1!=t2)

    {

        f[t2]=t1;

    }

}

void print(int n)

{

    for(int i=1;i<=n;i++) cout<<"("<<i<<")"<<f[i]<<" ";

    cout<<endl;

}

int main(int argc, const char * argv[]) {

    freopen("/Users/zhangjiatao/Desktop/input.txt","r",stdin);

    int n,m,a,b,sum;

    sum=0;

    cin>>n>>m;

    init(n);

    for(int i=1;i<=m;i++)

    {

        cin>>a>>b;

        merge(a,b);

        print(n);

    }

    for(int i=1;i<=n;i++)

    {

        f[i]=getf(i);

    }

    for(int i=1;i<=n;i++)

        if(f[i]==i) sum++;

    cout<<sum<<endl;

    return 0;

}

题解

F - Firetrucks Are Red

题意

每个人都有描述自己的一串数字，人与人之间能通过这些数字联系。给出n个人的特殊数字，问这些人能不能通过这些数字建立联系，如果可以输出建立联系的两个人的序号和建立关系的数字；如果不能 ，就输出 “impossible”。

• $$1 \le n\le 2 \bullet10^5$$
• $$1 \le m_i\le 2 \bullet10^5$$
• $$1 \le d_{i,j}\le10^9$$

思路：

这道题目主要是队友做的，用的并查集，我不太会并查集，在学习并查集后补的这道题。思路就是用map将每一个$d_{i,j}$和$i$对应，然后用并查集建立图。如果所有点的父亲节点都是1，则可以联系，用dfs遍历一下图就可以；如果不是就输出“impossible”。

代码：

#include<bits/stdc++.h>


using namespace std;
const double pi = acos(-1.0);
typedef long long ll;
const int N=400005;
struct pr
{
    int v;
    ll w;
};
ll n,m,x;
int a[N],fa[N];
map<int,int> mp;
vector<pr>ve[N];

int father(int x)
{
    if(fa[x]==x)
    return x;
    else 
    return fa[x]=father(fa[x]);
}
void solve_m(int u)
{
    cin>>x;
    if(mp.count(x))
    {
        int v=mp[x];
        if(father(v)==father(u))
        return;
        else
        {
            fa[father(u)]=father(v);
            ve[v].push_back(pr{u,x});
            ve[u].push_back(pr{v,x});
        }
    }
    else mp[x]=u;
}

void dfs(int u,int fa)
{
    for(pr p:ve[u])
    {
        int v=p.v;
        if(v==fa) continue;
        cout<<u<<' '<<v<<' '<<p.w<<endl;
        dfs(v,u);
    }
}
int main()
{
    mp.clear();
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        ve[i].clear();
    }
    for(int i=1;i<=n;i++)
    {
        cin>>m;
        for(int j=1;j<=m;j++)
        {
            solve_m(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(father(i)!=father(1))
        {
         cout<<"impossible"<<endl;
         return 0;
        }
        
    }
    dfs(1,0);
     return 0;
}