打卡信奥刷题（651）用C++信奥P8396[普及组/提高] [CCC2022 S2] Good Groups

[CCC2022 S2] Good Groups

题目背景

请注意：这道题是 CCO 2022 J4 Good Groups 的加强版。

管理备注：似乎没有加强。

题目描述

一个班级会被分成 g g g 个组，每个组有三个人，这种分组方式可能会违反两种规定：

1. 一些学生必须在同一小组；
2. 一些学生必须不在同一小组。

现在校长找到了你，问学生违反了多少个规定。

输入格式

第一行一个整数 x x x。

接下来 x x x 行，每行两个学生名字 n a m e 1 1 , n a m e 1 2 name1_1,name1_2 name11​,name12​ ，表示这两个学生必须被分配到同一个小组。

接下来一个整数 y y y。

接下来 y y y 行，每行两个学生名字 n a m e 2 1 , n a m e 2 2 name2_1,name2_2 name21​,name22​ ，表示这两个学生必须不在同一个小组。

接下来一个整数 g g g。

接下来 g g g 行，每行三个学生名字 n a m e 3 1 , n a m e 3 2 , n a m e 3 3 name3_1,name3_2,name3_3 name31​,name32​,name33​，表示这三个学生现在被分在一个小组。

输出格式

输出一个整数，表示学生违反了多少个规定。

样例 #1

样例输入 #1

1
ELODIE CHI
0
2
DWAYNE BEN ANJALI
CHI FRANCOIS ELODIE

样例输出 #1

0

样例 #2

样例输入 #2

3
A B
G L
J K
2
D F
D G
4
A C G
B D F
E H I
J K L

样例输出 #2

3

提示

样例 2 解释：

1. A \rm A A 和 B \rm B B 必须在同一组，这一点违反了。
2. G \rm G G 和 L \rm L L 必须在同一组，这一点违反了。
3. J \rm J J 和 K \rm K K 必须在同一组，这一点没有违反。
4. D \rm D D 和 F \rm F F 必须不在同一组，这一点违反了。
5. D \rm D D 和 G \rm G G 必须不在同一组，这一点没有被违反。

以上 5 5 5 条共违反 3 3 3 条，所以输出 3 3 3。

对于 20 % 20\% 20% 的数据： 1 ≤ g ≤ 50 1\le g\le 50 1≤g≤50， 1 ≤ x ≤ 50 1\le x\le 50 1≤x≤50， y = 0 y=0 y=0。

对于另外 35 % 35\% 35% 的数据： 1 ≤ g ≤ 50 1\le g\le 50 1≤g≤50， 1 ≤ x ≤ 50 1\le x\le 50 1≤x≤50， 1 ≤ y ≤ 50 1\le y\le 50 1≤y≤50。

对于 100 % 100\% 100% 的数据： 1 ≤ g ≤ 1 0 5 1\le g\le 10^5 1≤g≤105， 1 ≤ x ≤ 1 0 5 1\le x\le 10^5 1≤x≤105， 1 ≤ y ≤ 1 0 5 1\le y\le 10^5 1≤y≤105。

C++实现

#include <bits/stdc++.h>
using namespace std;
namespace P{
int t1,t2,t3,i;
string n1[2][100005],n2[2][100005];
string a,b,c;
map <string,int> g;
void solve(){
cin>>t1;
for (i=1;i<=t1;i++)
cin>>n1[0][i]>>n1[1][i];
cin>>t2;
for (i=1;i<=t2;i++)
cin>>n2[0][i]>>n2[1][i];
cin>>t3;
for (i=1;i<=t3;i++){
cin>>a>>b>>c;
g[a]=g[b]=g[c]=i;
}
int ans=0;
for (i=1;i<=t1;i++)
if (g[n1[0][i]]!=g[n1[1][i]])
ans++;
for (i=1;i<=t2;i++)
if (g[n2[0][i]]==g[n2[1][i]])
ans++;
cout<<ans;
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
return P::solve(),0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容