P1551 亲戚

题目描述

规定：\(x\) 和 \(y\) 是亲戚，\(y\) 和 \(z\) 是亲戚，那么 \(x\) 和 \(z\) 也是亲戚。如果 \(x\)，\(y\) 是亲戚，那么 \(x\) 的亲戚都是 \(y\) 的亲戚，\(y\) 的亲戚也都是 \(x\) 的亲戚。第一行：三个整数 \(n,m,p\)，（\(n,m,p \le 5000\)），分别表示有 \(n\) 个人，\(m\) 个亲戚关系，询问 \(p\) 对亲戚关系。以下 \(m\) 行：每行两个数 \(M_i\)，\(M_j\)，\(1 \le M_i,~M_j\le N\)，表示 \(M_i\) 和 \(M_j\) 具有亲戚关系。接下来 \(p\) 行：每行两个数 \(P_i,P_j\)，询问 \(P_i\) 和 \(P_j\) 是否具有亲戚关系。

试解

#include "iostream"
#include <bits/stdc++.h>
using namespace std;
int n,m,p;
int fa[10010];
int myFind(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];}
void myUnion(int a,int b){fa[myFind(a)]= myFind(b);}
int main(){
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)fa[i]=i;
    int x,y;
    while(m--){
        cin>>x>>y;
        myUnion(x,y);
    }
    while(p--){
        cin>>x>>y;
        if(myFind(x)== myFind(y))cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

批改

\(A\)了

P1536 村村通

题目描述

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

试解

#include "iostream"
#include <bits/stdc++.h>
using namespace std;
int fa[1010];
int myF(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];}
void myU(int a,int b){fa[myF(a)]=myF(b);}
int n,m;
bool vis[1010];
int main(){
    while (true){
        cin>>n;
        if(!n)break;
        cin>>m;
        for(int i=1;i<=n;i++){
            fa[i]=i;
            vis[i]= false;
        }
        int x,y;
        while(m--){
            cin>>x>>y;
            myU(x,y);
        }
        int ans=0;

        for(int i=1;i<=n;i++){
            if(vis[myF(i)])continue;
            vis[myF(i)]= true;
            ans++;
        }
        cout<<ans-1<<endl;
    }
}

批改

\(A\)了

P3370 字符串哈希

题目描述

如题，给定 \(N\) 个字符串（第 \(i\) 个字符串长度为 \(M_i\)，字符串内包含数字、大小写字母，大小写敏感），请求出 \(N\) 个字符串中共有多少个不同的字符串。

喜欢的板子

#include<iostream>
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull base=131;
ull a[10010];
char s[10010];
int n,ans=1;
int prime=233317;
ull mod=212370440130137957ll;

ull hashe(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod+prime;
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s);
        a[i]=hashe(s);
    }
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++)
    {
        if(a[i]!=a[i+1])
            ans++;
    }
    printf("%d",ans);
}

这个板子的数字是真硬

P3405 Cities and States S

题目描述

为了让奶牛在智力上受到刺激，农夫约翰在谷仓的墙上放了一张美国地图。由于奶牛在谷仓里花了很多时间盯着这张地图，他们开始注意到一些奇怪的关系。例如，城市Flint，在MI省，或者Miami在FL省，他们有一种特殊的关系：“Flint”市前两个字母就是“FL”省，迈阿密前两个字母是“MI”省。

让我们说，两个城市是一个“特殊的一对”，如果他们满足这个属性，来自不同的省。奶牛想知道有多少特殊的城市存在。请帮助他们解决这个有趣的地理难题！

输入格式

输入的第一行包含（），地图上的城市数量。

下一行包含两个字符串：一个城市的名称（字符串至少2个最多10个大写字母），和它的两个字母的州代码（一串2个大写字母）。注意状态代码可能像ZQ，这并不是一个真正的美国。同一名称的多个城市可以存在，但它们将处于不同的州。

试解

#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int>ump[100005];
int n,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        string a,b;
        cin>>a>>b;
        int A=a[0]*26+a[1];
        int B=b[0]*26+b[1];
        ans+=ump[B][A];
        if(A==B)ans-=ump[A][B];
        ump[A][B]++;
    }
    printf("%d",ans);
    return 0;
}

不用\(map\)用数组也行。

看了一下后面的题好像也是map应用啊。。也许是让我手敲数据结构？改天再做