Atcoder 177

連結

B Substring

雙重循環

#include <cmath>
#include<iostream>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int main()
{
    string s,t;
    cin>>s>>t;
    int ans=INF;
    for(int i=0;i<s.size()-t.size()+1;i++)
    {
        int cnt=0,k=i;
        for(int j=0;j<t.size();j++)
        {
            if(s[k]!=t[j]) cnt++;
            k++;
        }         
        ans=min(ans,cnt);
    }
    cout<<ans<<endl;

    return 0;
}
           

D friends——并查集

分組數就是集合包含的最大元素個數。

#include <cmath>
#include<iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=2e5+10,INF=0x3f3f3f3f;
LL p[N],siz[N];
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    cin>>n>>m;
    LL ans=-INF;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        siz[i]=1;
    }
    while (m--) {
        int a,b;
        cin>>a>>b;
        if(find(a)==find(b)) continue;        
        siz[find(b)]+=siz[find(a)];
        p[find(a)]=find(b);
      //  ans=max(siz[find(b)],ans);
    }

    for(int i=1;i<=n;i++)//周遊集合根節點
    if(find(i)==i) ans=max(ans,siz[i]);//周遊所有的點，如果x=p[x],說明x是一個根節點，可以獲得它所在的集合的最大值

    cout<<ans<<endl;
    
    return 0;
}