• 欢迎光临~

刷洛谷题单【数据结构1-3】

开发技术 开发技术 2022-07-22 次浏览

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_jle 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<<"Yesn";
        else cout<<"Non";
    }
    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应用啊。。也许是让我手敲数据结构?改天再做

程序员灯塔
转载请注明原文链接:刷洛谷题单【数据结构1-3】
喜欢 (0)