UVa 398 18-Wheeler Caravans (aka Semigroups)

题目描述

集合SSS上的二元运算是一个函数，将SSS中每个有序元素对映射到SSS中的唯一元素。如果对于所有x,y∈Sx, y \in Sx,y∈S有x#y=y#xx \# y = y \# xx#y=y#x，则称该运算是可交换的（commutative\texttt{commutative}commutative）。如果对于所有x,y,z∈Sx, y, z \in Sx,y,z∈S有(x#y)#z=x#(y#z)(x \# y) \# z = x \# (y \# z)(x#y)#z=x#(y#z)，则称该运算是可结合的（associative\texttt{associative}associative）。

一个具有可结合二元运算的集合<S,#><S, \#><S,#>称为半群（semigroup\texttt{semigroup}semigroup）。如果二元运算既是可结合的又是可交换的，则称为可交换半群。

输入格式

输入第一行包含整数nnn（1≤n≤261 \leq n \leq 261≤n≤26）。下一行包含nnn个唯一的小写字母（不一定按字母顺序排列）。接下来nnn行是“乘法”表的主体，每行包含nnn个小写字母。第一行对应表的第一行，依此类推。行和列的顺序与定义集合元素的行中的顺序一致。

表之后，输入文件包含一行整数nnn（0≤n≤260 \leq n \leq 260≤n≤26）。如果n>0n > 0n>0，则还有另一个集合和对应的表。如果n=0n = 0n=0，则到达输入文件末尾。

输出格式

对于每个集合和表，输出：

1. S = {a,b,c,d}（按输入顺序）
2. 一行：空格 +#|+ 元素（无空格或逗号）
3. 一行：空格 +-++nnn个连字符
4. nnn行：空格 + 元素 +|+ 该行表体（无空格）
5. 一个空行
6. 以下结果之一：
   • COMMUTATIVE SEMIGROUP
   • SEMIGROUP BUT NOT COMMUTATIVE (x#y IS NOT EQUAL TO y#x)
   • NOT A SEMIGROUP: x#y = z WHICH IS NOT AN ELEMENT OF THE SET
   • NOT A SEMIGROUP: (x#y)#z IS NOT EQUAL TO x#(y#z)
7. 一行303030个连字符
8. 一个空行

样例输入

3 abc abc bca cab 3 abc abc bca cad 4 acdb aaaa aaca aada aaab 5 abcde aaaaa bbabb cccbc ddddd eeeee 0

样例输出

S = {a,b,c} #|abc -+--- a|abc b|bca c|cab COMMUTATIVE SEMIGROUP ------------------------------ S = {a,b,c} #|abc -+--- a|abc b|bca c|cad NOT A SEMIGROUP: c#c = d WHICH IS NOT AN ELEMENT OF THE SET ------------------------------ S = {a,c,d,b} #|acdb -+---- a|aaaa c|aaca d|aada b|aaab SEMIGROUP BUT NOT COMMUTATIVE (c#d IS NOT EQUAL TO d#c) ------------------------------

---

题目分析

问题的本质

这是一个代数结构验证问题。给定一个有限集合和一个二元运算的乘法表，需要判断：

1. 运算结果是否都在集合内（封闭性）
2. 运算是否可结合（结合律）
3. 运算是否可交换（交换律）

算法步骤

1. 封闭性检查：表中所有结果都必须在集合中
2. 结合律检查：对所有a,b,c∈Sa, b, c \in Sa,b,c∈S，验证(a#b)#c=a#(b#c)(a \# b) \# c = a \# (b \# c)(a#b)#c=a#(b#c)
3. 交换律检查：对所有a,b∈Sa, b \in Sa,b∈S，验证a#b=b#aa \# b = b \# aa#b=b#a

复杂度

• n≤26n \leq 26n≤26，结合律检查需O(n3)O(n^3)O(n3)，约175761757617576次，完全可行

---

参考代码

// 18-Wheeler Caravans (aka Semigroups)// UVa ID: 398// Verdict: Accepted// Submission Date: 2016-07-08// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intn,cases=0;while(cin>>n,n){vector<char>elements(n);vector<string>table(n);map<char,int>location;// 读取元素for(inti=0;i<n;i++){cin>>elements[i];location[elements[i]]=i;}// 读取乘法表for(inti=0;i<n;i++){cin>>table[i];}// 输出表头if(cases++)cout<<endl;cout<<"S = {";for(inti=0;i<n;i++){if(i>0)cout<<",";cout<<elements[i];}cout<<"}"<<endl;cout<<" #|";for(inti=0;i<n;i++)cout<<elements[i];cout<<endl;cout<<" -+"<<string(n,'-')<<endl;for(inti=0;i<n;i++)cout<<" "<<elements[i]<<"|"<<table[i]<<endl;cout<<endl;// 封闭性检查for(inti=0;i<n;i++)for(intj=0;j<n;j++){charresult=table[i][j];if(location.find(result)==location.end()){cout<<"NOT A SEMIGROUP: "<<elements[i]<<"#"<<elements[j];cout<<" = "<<result<<" WHICH IS NOT AN ELEMENT OF THE SET"<<endl;gotoexit_processing;}}// 结合律检查for(inti=0;i<n;i++)for(intj=0;j<n;j++)for(intk=0;k<n;k++){charleft=table[location[table[i][j]]][k];charright=table[i][location[table[j][k]]];if(left!=right){cout<<"NOT A SEMIGROUP: (";cout<<elements[i]<<"#"<<elements[j]<<")#"<<elements[k];cout<<" IS NOT EQUAL TO ";cout<<elements[i]<<"#("<<elements[j]<<"#"<<elements[k]<<")"<<endl;gotoexit_processing;}}// 交换律检查for(inti=0;i<n;i++)for(intj=0;j<n;j++){if(table[i][j]!=table[j][i]){cout<<"SEMIGROUP BUT NOT COMMUTATIVE (";cout<<elements[i]<<"#"<<elements[j];cout<<" IS NOT EQUAL TO ";cout<<elements[j]<<"#"<<elements[i]<<")"<<endl;gotoexit_processing;}}cout<<"COMMUTATIVE SEMIGROUP"<<endl;exit_processing:cout<<string(30,'-')<<endl;}return0;}