题目链接:http://nyoj.top/problem/1366

  • 内存限制:128MB 时间限制:3000ms

题目描述

如何设计一个好的数据库不仅仅是一个理论研究问题，也是一个实际应用问题。在关系数据库中不满足规范化理论的数据库设计会存在冗余、插入异常、删除异常等现象。
设R(U)是一个关系模式，U={ A1,A2, ……, An}。其中Ai是关系的属性，X,Y是U的子集。函数依赖 X->Y 定义了数据库中属性集X与Y的依赖关系。根据Armstrong公理，函数依赖满足：
（1） 自反律：若Ai∈X, 则 X->Ai . 特别地，Ai ->Ai . 
（2） 增广律：若 X->Y, 则 ZX->ZY. (ZX 是指集合Z与X的并集 )
（3） 传递律：若 X->Y, Y->Z, 则 X->Z. 
（4） 分解律：若 X->Y, 则 X->Ai ( 若属性Ai∈Y )
（5） 合并律：若 X->Y, X->Z, 则 X->YZ.
已知 F 是关系模式R(U)上的函数依赖集，利用Armstrong公理系统可以推导出更多的函数依赖。设X是属性集U={ A1,A2, ……, An} 的子集， 定义X关于F的闭包XF+
XF+={ Ai | 若X->Ai可以通过Armstrong公理导出}
对于给定的U , F ,X, 请求出XF+

输入描述

第一行：T 表示以下有T组测试数据(1≤T≤5)
对每组数据，
第1行：n m k, n表示U中属性个数(1≤n≤26)，用大写字母表示 。m表示X中属性个数（ 1≤m≤26 ），k个函数依赖(1≤ k ≤ 20)。
第2行: 字符串U  n个大写字母
第3行: 字符串X  m个大写字母
接下来有K行，每行有两个字符串 S T，用一个空格隔开, 表示 S->T

输出描述

对每组测试数据，输出占一行输出XF+，要求按字母序输出。

样例输入

1
6 2 4
ABGDCI
AD
A B
BD I
AG C
C D

样例输出

ABDI

解题思路

题意:给你一个x串，和一些函数依赖，求x的闭包XF+。
思路:直接模拟，先把X串中的元素都标记一下，然后就枚举函数依赖，只要S中的元素都在X中，并且T中的元素没在X中就把T中的元素更新到X中，直到X没有更新为止。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30;
int vis[MAXN];
char ustr[MAXN], xstr[MAXN], s[MAXN][MAXN], t[MAXN][MAXN];
int main() {
    int T, n, m, k, flsg, fltg, temp;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        scanf("%s%s", ustr, xstr);
        for (int i = 0; i < k; i++)
            scanf("%s%s", &s[i], &t[i]);
        memset(vis, 0, sizeof(vis));
        for (int i = 0; xstr[i]; i++)
            vis[xstr[i] - 'A']++;
        while (true) {
            temp = 0;
            for (int i = 0; i < k; i++) {
                flsg = fltg = 0;
                for (int j = 0; s[i][j]; j++)
                    if (!vis[s[i][j] - 'A'])
                        flsg = 1;
                for (int j = 0; t[i][j]; j++)
                    if (!vis[t[i][j] - 'A'])
                        fltg = 1;
                if (!flsg && fltg) {
                    for (int j = 0; t[i][j]; j++)
                        vis[t[i][j] - 'A']++;
                    temp = 1;
                }
            }
            if (!temp)
                break;
        }
        for (int i = 0; i < 26; i++) {
            if (vis[i])
                printf("%c", i + 'A');
        }
        printf("\n");
    }
    return 0;
}