1.元素分类

思路：正数一组,负数一组.累加求和.

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
       int n;cin>>n;
       vector<int>pos;
       vector<int>neg;
       for(int i=1;i<=n;i++)
       {
               int x;cin>>x;
               if(x>=0)pos.push_back(x);
               else neg.push_back(x);
       }
       int ans=0;
       for(int i=0;i<pos.size();i++)ans+=pos[i];
       for(int i=0;i<neg.size();i++)ans-=neg[i];
       cout<<ans<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        //freopen("test.in","r",stdin);
        solve();
        return 0;
}

2.链表

思路：
有点类似T3的字符串并查集,
实际上由于只是寻找映射关系,并不会实际使用到并查集合并集合.只是查询当前字母是否出现过,若出现则合并到之前所属集合即可.

AC Code：

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
struct node{
        string head;
        string pail;
};
node ans[30010];
void solve()
{
       int n;cin>>n;
       int res1=0;
       map<string,int>mp;
       for(int i=1;i<=n;i++)
       {
               string a,b;
               cin>>a>>b;//a是头b 是尾 
               if(!mp[a])mp[a]=++res1,ans[res1].head=a;
               mp[b]=mp[a];
               ans[mp[b]].pail=b;
       }
       cout<<res1<<endl;
       for(int i=1;i<=res1;i++)cout<<ans[i].head<<' '<<ans[i].pail<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
   //     freopen("test.in","r",stdin);
        solve();
        return 0;
}

3.字符串归类

思路：
纯粹的字符串类型并查集.
将每次出现的字母合并到同一个集合,最后统计集合数量即可.

AC Code：

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int p[26];//26个字母的祖先
bool vis[26];
int find(int x)
{
        return p[x]==x?x:p[x]=find(p[x]);
}
void solve()
{
       int n;cin>>n;
       for(int i=0;i<26;i++)p[i]=i;//初始化
       memset(vis,false,sizeof vis);
       for(int i=1;i<=n;i++)
       {
               string s;cin>>s;
               int res=find((s[0]-'a'));
               vis[(s[0]-'a')]=true;
               for(auto c:s)
               {
                       int cnt=(c-'a');
                       int fb=find(cnt);
                       vis[(c-'a')]=true;
                       p[fb]=res;
               }
       }
       int ans=0;
       for(int i=0;i<26;i++)
       {
               int fa=find(i);
               if(vis[fa])
               {
                       vis[fa]=false;
                       ans++;
               }
       }
       cout<<ans<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
      //  freopen("test.in","r",stdin);
        solve();
        return 0;
}