4302. 元素分类
题目链接：4302. 元素分类
分析：
将一组数据进行分类，分为b、c两类，使得b类数据的和 - c类数据的和最大，并将差值输出，其中一类的数据可以为0。
因此我们可以有三种情况：
- 既有正数，也有负数
- 只有正数
- 只有负数
通过分析我们可以很容易知道，将所有正数放入b组，负数放入c组即可得到最大差值。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, b, c;
int a[N];
int main(){
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
if(a[i] >= 0)b += a[i];
else c += a[i];
}
cout << b - c << endl;
return 0;
}
4303. 链表
题目链接：4303. 链表
感想：
这道题题目很长看着有点吓人，我看完题目后还没看明白什么意思，看了一下测试用例，才明白，也不算太难。
由于我没有学过c艹，只是看算法书（书上的代码用的是c艹）的时候顺便学了一点语法，所以对STL的使用不是很熟悉，所以这题我是用纯c写的。
分析：
首先是输入一个q，表示接下来要输入q个链表的值（值由字符串组成），每个链表由两个值，一个是头节点，一个尾节点，而有的链表的尾节点的值会与某个链表头节点的值相同，这种情况则可以将它们合并尾一个链表，且对尾节点更新，题目则是要求我们输出链表数，以及每个链表的头尾节点的值。
1.我们先对数据规模进行分析：
题目测试范围为[1,1000]，并且每个字符串的长度不超过20，由此我们可以计算出该题可用O(n^2)的时间复杂度，假设每个链表都进行头尾比较，则最多大概循环20 * n * n次，也就是20000000次，这个量是足够运行的。
2. 现在我们如何进行合并
我们可以定义一个数组nex[]，用于存储每个链表的下一部分，默认值为0，表示所有链表都是独立的，同时用head[][21]，tail[][21]数组分别存储头尾节点，对所有头节点与尾节点进行匹配，加入匹配成功则在对应得nex下标记录其下一段的下标。
举例：
有这样一组数据
先默认所有链表都是独立的，所以nex内的所有值都是0。
现在我们要对head上的所有值与tail进行一一比较，假设相同，则将tail下标对应nex数组上的值进行修改，改为与他配对的head，表示该链表的后面的值的位置。
以此类推
最后我们输出的时候只需要判断nex[i] 是否大于等于0，等于0说明他后面没有链表，直接输出head[i]，tail[i]，大于0则先输出head[i]，然后在对nex进行递归，找出最后一个链表的下标，在输出。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int q, nex[N];
char head[N][21], tail[N][21];
void dfs(int i){
if(nex[i]){
dfs(nex[i]);
nex[i] = -1;
}
else{
printf("%s\n", tail[i]);
nex[i] = -1;//输出过的标记为-1，以保证不会重复输出
}
}
int main(){
cin >> q;
int p = q;
for(int i = 0; i < q; i++){
scanf("%s %s", head[i], tail[i]);
}
for(int i = 0; i < q; i++){
if(nex[i])continue;//如果nex有值了，由于没有分支，所以就直接跳过
for(int j = 0; j < q; j++){
//if(i == j)continue;
if(!strcmp(tail[i], head[j])){
nex[i] = j;
p--;//每合并一个链表就说明减少了一个
}
}
}
printf("%d\n", p);
for(int i = 0; i < q; i++){
if(nex[i] > 0){//说明后面还有链表相连
printf("%s ", head[i]);
dfs(nex[i]);//找出最后一个
}
else if(nex[i] == 0)printf("%s %s\n", head[i], tail[i]);
}
return 0;
}
4304. 字符串归类
题目链接：4304. 字符串归类
分析：
这道题很容易看出是考我们并查集，我们要用到并查集的方法，用一个数组记录26个字母第一次出现的字符串的下标，再用数组p来存储根节点，把所有相同的归并到一起。差不多算是一个模板题吧，只是需要稍微改动了一下。
举例：
以此类推：
最后所有第一次字母第一次出现的位置都存在数组中，与此同时，我们用并查集进行分类。
代码如下：
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2e5 + 10;
int n, p[N];
int id[26];
char s[55];
int find(int x){
return x == p[x] ? x : find(p[x]);
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++)p[i] = i;
int ans = n;
for(int i = 1; i <= n; i++){
scanf("%s", s);
for(int j = 0; s[j]; j++){
int k = s[j] - 'a';
if(id[k]){
if(find(i) != find(id[k])){
p[find(i)] = find(id[k]);
ans--;
}
}
else id[k] = i;
}
}
printf("%d\n", ans);
return 0;
}