PAT复习自用——做题解和写过代码的搬运工

//基础数据结构（一）线性表、哈希表、并查集
/*
前言：背好模板，没有难题，哈希表和线性表基本每次必考
*/
-----------------------------
/*
（一）线性表
送分题：按照链表的顺序链接即可，常作为第二道题考查
PAT的考查方式即给出地址，键值，下地址，静态存储到结构体即可
链表的常用操作有：摘除某些性质的节点，节点去重（注意是看绝对值还是真值），节点分类，节点分块
关键是找到一个合适的下标序列，随后串联即可，故简洁的做法是求满足条件序列，存入vector中，最后遍历输出
链表考虑过滤输入数据中不属于其中的节点
*/
//基本工具
const int N = 10010;
struct Node
{
    int addr,value,next;
    //int pre;  //备选
}List[N];

*********//最常用的是直接用下标标记地址
vector<int>res;//存答案序列
unordered_set<int> mp;
set<int> List_addr;//用于查询链表的地址(通常为几位数字)是否存在
for(int i = root1;i!=-1;i = ne[i])mp.insert(i);//set查找碰撞（两个链表公共）元素 
//PAT-1032共享  检测两个链表公共元素就可以使用set检测
-----------------------
/*
模板
*/
const int N = 100100;
struct Node
{
    int addr,value,next;
    void output()
    {
        if(next==-1)printf("%05d %d -1\n",addr,value);
        else printf("%05d %d %05d\n",addr,value,next);
    }
}L[N];
int main()
{
    int root,n,k;
    cin>>root>>n>>k;
    while(n--)
    {
        int x,y,z;cin>>x>>y>>z;
        L[x] = {x,y,z};
    }
    for(int i = root;i!=-1;i = L[i].next){...}
    /*
    需要根据题意编写的代码
    */
    return 0;
}
*************************//万能法：标记下标映射，然后按照题目性质存入res
unordered_map<int,int>pos;//idx---value
void mark()
{
    int idx = 1;
    for(int i = root;i!=-1;i = L[i].next)
        pos[idx++] = i;
}
//有效元素数量
cout<<pos.size()<<endl;
void link(vector<int> res)
{
    for(int i = 0;i<res.size()-1;i++)
    {
        L[pos[res[i]]].next = pos[res[i+1]];
        L[pos[res[i]]].output();
    }
    L[pos[res[res.size()-1]]].next = -1;
    L[pos[res[res.size()-1]]].output();
}
-----------------------
/*
节点去重---定义st表示是否之前访问过，同时，为了方便编码，可以设置pre字段标识前驱
PAT-1097 链表重复数据删除
*/
for(int i = root;i!=-1;i = L[i].next)
    {
        if(!st[abs(L[i].value)])st[abs(L[i].value)] = true;
        else L[L[i].pre].next = L[i].next,L[L[i].next].pre = L[i].pre,
        //实际上直接push到结果里面，最后串联更方便
            de.push_back(i);//de 存储删除节点
    }
-----------------------
/*
节点分类——通常类别有限，故分设若干vector存储分类结果，最后合并到res中，输出它
PAT-1133 链表元素分类
*/
vector<int>ne,sn,bn,res;
for(int i = root;i!=-1;i = L[i].next)
{
    if(L[i].value<0)ne.push_back(i);
    else if(L[i].value<=k)sn.push_back(i);
    else bn.push_back(i);
}
-----------------------
/*
节点分块
PAT-1074 反转链表
*/
int block_idx = 0,cnt=0;//类似分桶操作
for(int i = root;i!=-1;i = L[i].next)
{
    //或者可以定义临时的块，当cnt==k,2k,...时，反转这个临时块，加入res，然后清空临时块，这样更容易
    if(cnt%k==0&&cnt!=0)block_idx++;
    block[block_idx].push_back(i);
    cnt++;
}
//分块反转输出，题意通常要求反转每个块
for(int i = 0;i<block_idx;i++)
    reverse(block[i].begin(),block[i].end());
//简洁写法
for(int i = root;i!=-1;i = L[i].next)
{
    tmp.push_back(i);cnt++;
    if(cnt%k==0)
    {
        reverse(tmp.begin(),tmp.end());
        for(auto c:tmp)res.push_back(c);
        tmp.clear();
    }
}
for(auto c:tmp)res.push_back(c);//最后一块
------------------------
/*
链表合并---存储两个链表，然后按照指定要求操作两个链表的序列合并到res
*/
vector<int> a,b;
int root1,root2;cin>>root1>>root2;
for(int i = root1;i!=-1;i = L[i].next)a.push_back(i);
for(int i = root2;i!=-1;i = L[i].next)b.push_back(i);
int l1 = a.size(),l2 = b.size(),i = 0,j = 0;
if(2*l1<l2)swap(l1,l2),swap(a,b);
while(i<l1&&j<l2)
{
    if(i<l1&&i%2==0&&i!=0)res.push_back(b[j++]);
    else if(i<l1)res.push_back(a[i++]);
}
//之后按照res遍历即可
---------------------------------
/*
（二）哈希表
主要掌握哈希表的stl----set,unordered_map,multiset
了解模拟哈希表的原理，求成功查找长度和失败查找长度

补充：哈希算法的平均查找长度主要取决于负载因子，它反映了哈希表的装满程度
1.哈希表开放定址法
1）线性开址--容易造成聚集现象
英文：with linear probing used to resolve the collisions
2）平方开址--不容易探测到整个哈希表，只有当表长=4j+3的素数才有可能
英文： Quadratic probing (with positive increments only) is used to solve the collisions.
3）随机探测再散列，给出伪随机探测序列
4）再散列法：有多少个散列函数
5）链地址法：又叫开散列表，元素个数不受长度限制，每个位置若出现冲突则挂一组数
6）建立公共溢出区：冲突项都填入溢出区

*/
//基本工具
set<int>s;
s.count(x);//哈希表主要操作就是基于该条语句进行统计
--------------------------------
//模拟哈希表模板
bool is_prime(int n)//确定mod数
{
    if(n<=1)return false;
    if(n==2)return true;
    for(int i = 2;i*i<=n;i++)if(n%i==0)return false;
    return true;
}
int find(int x)//查找---使用平方探测
{
    int t = x % s;//直接查询下标
    for (int k = 0; k < s; k ++ )
    {
        int i = (t + k * k) % s;//发现冲突，试探下个位置，线性探测改为(t+k)%s
        if (!h[i]) return i;//查到空位，即插入
    }
    return -1;//无法插入哈希表
}
int main()
{
    cin >> s >> n;
    while (!is_prime(s)) s ++ ;
    for (int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        int t = find(x);
        if (t == -1) printf("-");
        else
        {
            h[t] = x;
            printf("%d", t);
        }
        if (i != n - 1) printf(" ");
    }
    return 0;
}
-----------------
//求平均查找长度
int find(int x,int &count)
{
    int t = x%s;
    count = 1;
    for(int k = 0;k<s;k++)
    {
        int i = (t+k)%s;
        cnt++;
        if(!h[i]||h[i]==x)return i;
    }
    return -1;
}
for(int i = 0;i<s;i++)int cnt,find(i,cnt),res+=cnt;
printf("%.1lf",res/m);
int search(int x)//返回查找长度
{
    int t = x%s,cnt = 0;
    for(int k = 0;k<s;k++)
    {
        int i = (t+k)%s;
        cnt++;
        if(h[i]==x||!h[i])return cnt;
    }
    return s+1;
}
//求失败查找长度---这里默认元素是不再表里面的，但是这些失败元素都可以映射到0-s-1的位置
//因此只需要枚举0-s-1即可，无关查询序列，因为默认都是查不到的序列
int unsuccess_find(int x)
{
    int k = 0;
    int t = x%s;
    for(int i = 0;i<s;i++)
    {
        int i = (t+k*k)%s;
        if(!h[i])return i+1;//如果可以提前确定查找失败，则这次查找代价较小
    }
    return s+1;//这里说的是对应于表遍历了一遍都没找到空位，这次失败查找代价较大，返回表长+1
}
for(int i = 0;i<s;i++)
    res+=unsuccess_find(i);
printf("%.1lf",res/m);
-----------------------------
/*
数据结构习题---Hashing hard version （哈希逆问题：根据哈希表状态还原输入序列）
本题可以首先尝试手动模拟一下，立即可以发现，映射结果不一致的元素，其映射位置之后试探的所有新地址对应的元素
必定在其之前插入，因此可以确定一个偏序关系，该偏序关系可以使用图来表示，因此求解一个合适的插入序列可以看成
一个拓扑排序问题，此题的限定是，当有多个元素可以插入时，按照value较小的先放入哈希表，因此使用优先队列实现
拓扑排序
*/
#include<iostream>
#include<queue>
#include<unordered_map>
#include<vector>
using namespace std;
const int N = 1010;
int n,seq[N];
unordered_map<int,vector<int>> g;
unordered_map<int,int> in;
vector<int> res;
void topu()
{
    priority_queue<int,vector<int>,greater<int>> q;
    for(int i = 0;i<n;i++)if(in[seq[i]]==0&&seq[i]!=-1)q.push(seq[i]);
    while(!q.empty())
    {
        int t = q.top();
        q.pop();
        res.push_back(t);
        for(auto c:g[t])
        {
            in[c]--;
            if(in[c]==0)q.push(c);
        }
    }
}
int main()
{
    cin>>n;
    for(int i = 0;i<n;i++)cin>>seq[i];
    for(int i = 0;i<n;i++)
    {
        int t = seq[i]%n;
        while(seq[t]!=seq[i]&&seq[i]!=-1)
        {
            g[seq[t]].push_back(seq[i]),in[seq[i]]++;
            t = (t+1)%n;
        }
    }
    topu();
    for(int i = 0;i<res.size();i++)
    {
        cout<<res[i];
        if(i!=res.size()-1)cout<<" ";
    }
    return 0;
}
-----------------------------
/*
（三）并查集
并查集是一种可以动态维护若干个不重叠的集合,
并且支持合并与查询的数据结构.尤其擅长维护各种各样的具有传递性质的关系.
性质详解
传递性质
传递性,
A和B具有性质X，C和B属于一个集合，则C具有性质X

连通集合性质
连通集合性,A和B同属一个集合,B和C同属一个集合,
那么A,B,C都属于同一个集合.

这两个性质可以互相转化，连通一般具有传递性

因此并查集的应用如下
1.判断两个元素是否在一个集合中
2.合并两个集合
*/
----------------------------------
//模板
const int N = 100100;
int p[N];
void init()
{
    for(int i = 0;i<N;i++)
        p[i] = i;
    //初始化只有自环，或可以理解为每个集合只有自己这么一个根节点元素
}
int find(int x)
{
    int a = x;
    while(x!=p[x])x = p[x];
    while(a!=p[a])//执行路径压缩，防止数据中出现链式结构，保证查询复杂度稳定在logn
    {
        int z = p[a];
        p[z] = x;
        a = z;
    }
    return x;
}
//递归版本
int find(int x)
{
    return x==p[x]?x:p[x] = find(p[x]);//同时执行了路径压缩，这个模板好记也好用
}
//合并集合
void merge(int a,int b)
{
    int pa = find(a),pb = find(b);
    p[pa] = pb;//这里可以规定按秩合并的规则
}
-------------------------
/*
连通性应用：判断图连通性，求连通块大小
*/
//PAT-1107 社会集群
//解法一：dfs求连通块元素数
int n;
const int N = 1010;
int g[N][N];
bool st[N];
unordered_map<int,vector<int>> mp;
//动了一点小心思，爱好的编号并非0-idx，而是随机分布的，使用查表更方便
//表的格式是：爱好，拥有此爱好的用户（这些用户具有图连接关系），有点类似基于用户推荐
vector<int>res;
int dfs(int u)
{
    int cnt = 1;
    st[u] = true;
    for(int i = 0;i<n;i++)
        if(g[u][i]&&!st[i])cnt+=dfs(i);
    return cnt;
}
void dfs_travel()
{
    for(int i = 0;i<n;i++)
        if(!st[i])res.push_back(dfs(i));
}
int main()
{
    cin>>n;
    for(int i = 0;i<n;i++)
    {
        int cnt;
        scanf("%d:",&cnt);
        while(cnt--)
        {
            int x;cin>>x;
            mp[x].push_back(i);
        }
    }

    for(auto c:mp)
        for(auto d:c.second)
            for(auto e:c.second)
                if(d!=e)g[d][e] = g[e][d] = 1;
    dfs_travel();
    cout<<res.size()<<endl;
    sort(res.begin(),res.end(),greater<int>());
    for(auto c:res)cout<<c<<" ";
    return 0;
}
//解法二：并查集做法  抓住这里爱好是具有传递性的

int n;
const int N = 1001;
int cnt[N],p[N];
vector<int>hobby[N];
int find(int x)//本题必须使用路径压缩，否则不好确定唯一的集群
{
    return x==p[x]?x:p[x] = find(p[x]);
}
int main()
{
    cin>>n;
    for(int i = 0;i<n;i++)
    {
        int cnt;scanf("%d:",&cnt);
        while(cnt--)
        {
            int x;cin>>x;
            hobby[x].push_back(i);
        }
    }
    for(int i = 0;i<n;i++)p[i] = i;
    for(int i = 0;i<1000;i++)
        for(int j = 1;j<hobby[i].size();j++)
        {
            int a = hobby[i][j],b = hobby[i][0];
            p[find(a)] = find(b);
        }
    int k = 0;
    for(int i = 0;i<n;i++)cnt[find(i)]++;//这里表明必须使用路径压缩，因为要确定集群的数量
    //这里如果使用map存相对更方便一点
    sort(cnt,cnt+n,greater<int>());
    while(cnt[k])k++;
    cout<<k<<endl;
    for(int i = 0;i<k;i++)cout<<cnt[i]<<" ";
    return 0;
}
----------------------
//解决传递关系：
//PAT-1118 森鸟
const int N = 10010;
int p[N],n;
set<int> bird;//为了输出鸟的个数
unordered_map<int,int> group;//需要存储：树--鸟个数
int find(int x)
{
    return x==p[x]?x:p[x] = find(p[x]);
}
int main()
{
    cin>>n;
    for(int i = 0;i<N;i++)p[i] = i;//注意这里初始化的时候不要错写成i<=N,
    //会导致变量p[i]此时指向n的位置，修改n的值导致下面的n很大，该bug极其隐蔽
    while(n--)
    {
        int cnt;cin>>cnt;
        vector<int> tmp;
        while(cnt--)
        {
            int x;cin>>x;
            tmp.push_back(x);
            bird.insert(x);
        }
        for(int j = 1;j<tmp.size();j++)
        {
            int a = tmp[0],b = tmp[j];
            p[find(b)] = find(a);
        }
    }
    for(auto c:bird)
    {
        int x = find(c);
        group[x]++;
    }
    cout<<group.size()<<" "<<bird.size()<<endl;
    int q;cin>>q;
    for(int i = 0;i<q;i++)
    {
        int x,y;cin>>x>>y;
        if(find(x)==find(y))puts("Yes");
        else puts("No");
    }
    return 0;
}
-------------------------
//PAT-1114 家庭财产  需要按秩合并集合，即在合并的时候判断指向关系
unordered_map<int,double>cnt;
unordered_map<int,double>num;
unordered_map<int,double>area;
const int N = 10100;
int p[N],n;
double Num[N],Area[N];
set<int> P;
struct family
{
    int id,cnt;double area,num;
    bool operator <(const family b)const
    {
        if(area==b.area)return id<b.id;
        return area>b.area;
    }
}f[N];
int find(int x)
{
    return x==p[x]?x:p[x] = find(p[x]);
}
void merge(int x,int y)//需要按秩合并集合，即在合并的时候判断指向关系
{
    int px = find(x),py = find(y);
    if(px<py)p[py] = px;
    else p[px] = py;
}
int main()
{
    cin>>n;
    for(int i = 0;i<N;i++)p[i] = i;
    while(n--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        P.insert(x);
        if(y!=-1)merge(x,y),P.insert(y);
        if(z!=-1)merge(x,z),P.insert(z);
        int cnt;cin>>cnt;
        while(cnt--)
        {
            int w;cin>>w;
            merge(x,w);P.insert(w);
        }
        cin>>Num[x]>>Area[x];
    }
    for(auto c:P)
    {
        int pc = find(c);
        if(!cnt.count(pc))cnt[pc] = 0;
        if(!num.count(pc))num[pc] = 0;
        if(!area.count(pc))area[pc] = 0;
        cnt[pc]++;
        num[pc]+=Num[c];
        area[pc]+=Area[c];
    }
    vector<family> res;
    for(auto c:cnt)
    {
        int id = c.first,k = c.second;
        area[id]/=k,num[id]/=k;
        res.push_back({id,k,area[id],num[id]});
    }
    sort(res.begin(),res.end());
    cout<<res.size()<<endl;
    for(auto c:res)
    {
        int id = c.id;
        printf("%04d %d ",id,c.cnt);
        printf("%.3lf %.3lf\n",num[id],area[id]);
    }
    return 0;
}
//PAT-1013 战争中的城市，同类型
int n,m,k;
const int N = 1010,M = N*N/2;
int p[N];
struct Edge
{
    int x,y;
}e[M];
int find(int x)
{
    return p[x]==x?x:p[x] = find(p[x]);
}
int main()
{
    cin>>n>>m>>k;
    for(int i = 0;i<m;i++)cin>>e[i].x>>e[i].y;
    while(k--)
    {
        int x;
        set<int>s;
        scanf("%d",&x);
        for(int i = 1;i<=n;i++)p[i] = i;
        for(int i = 0;i<m;i++)
        {
            int a = e[i].x,b = e[i].y;
            if(x!=a&&x!=b)
            {
                int pa = find(a),pb = find(b);
                p[pa] = pb;
            }
        }
        for(int i = 1;i<=n;i++)
            s.insert(find(i));
        printf("%d\n",s.size()-2);
    }
    return 0;
}