首页 > 程序开发 > 软件开发 > 其他 >

UVa 1592 枚举+字符串查重

2017-04-19

UVa 1592 枚举+字符串查重:给定一个数据库的n行和m列,判断是否存在两个不同列c1、c2,使得这两个列下有两个不同行r1、r2对应的内容都相等。

UVa 1592 枚举+字符串查重:给定一个数据库的n行和m列,判断是否存在两个不同列c1、c2,使得这两个列下有两个不同行r1、r2对应的内容都相等。即[r1][c1]=[r2][c1]且[r1][c2]==[r2][c2]。如下图的第2行、第3行和第2列、第3列。

解题思路

本题是《算法竞赛入门经典》的例题5-9,是STL的综合应用题,考察枚举和字符串操作。

读懂题意之后一般先想到的都是写O(n^4)的四重循环,枚举c1、c2的组合嵌套枚举r1、r2,但是这样子想来也是不合理的,加上用string进行操作,时间上的代价是很明显的。

书上给出的解决办法意思如下:

只枚举c1、c2,然后从上到下扫描每行,每到一行,就把这行c1和c2列的内容作为key一个二元组存到map里,map的value即这一行的行号,那么下次遍历到某一行r2有相同二元组时,即可查到上次出现时的行号,即r1。

思想还是很巧妙的,虽然时间复杂度还是有O(n^3),但测试的时间要求在9000ms以内(额…),所以也是进步啦。
还有一个问题就是,难道每个矩阵里都要存string,用两个string构造一个二元组?代价也很大,而且字符串比较的问题是很耗时的。

书上又提出了解决方法(实在是666):

在将元素存储到矩阵之前,先为每个字符串分配一个int型的编号,这样数据库中的每个单元格都变成了整数,二元组则可以用pair对表示,这种技巧和之前的UVa 12096中所用的思想类似。

比较繁琐的是字符串的读入问题,由于每个字符串中都有空格,又以逗号分隔,因此只能一个个找逗号的位置,把string截取出来了。

int find(char c, int pos = 0) const;//从pos开始查找字符c在当前字符串的位置
string substr(int pos = 0,int n = npos) const;//返回pos开始的n个字符组成的字符串

AC代码

#include 
#include 
#include 
#include

using namespace std;

typedef pair Elem; //c1,c2在r行的字符串组成的的二元组

int num; //字符串的编号
map IDcache; //字符串到ID的映射
int database[10005][15];


void print_database(int row, int col) //输出
{
    for (int i = 0; i pair2row;
            for (int r = 0; r < n; ++r) //对相同c1/c2的每一行遍历
            {
                Elem p = make_pair(database[r][c1], database[r][c2]);//构造ID二元组
                if (pair2row.count(p)) //如果之前行出现过ID二元组,输出结束
                {
                    printf("NO\n");
                    printf("%d %d\n%d %d\n", pair2row[p]+1, r+1, c1+1, c2+1);
                    return;
                }
                else
                    pair2row[p] = r; //二元组p在c1/c2中的所在行为r
            }
        }
    printf("YES\n");
}


int main()
{
    //freopen("E:/Personal/Desktop/test.txt", "r", stdin);
    int n,m;
    string tmp;
    while (cin >> n >> m && n && m)
    {
        getchar(); //吞掉cin的回车
        readData(n, m); //输入数据
        //print_database(n,m); //检查ID矩阵
        findDup(n, m); //查找可能的重复二元组
    }
    return 0;
}

耗时:1260ms
算法复杂度:O(n^3),主要由遍历列、行造成,而map内部由红黑树实现,查找时间仅为O(logN)。

相关文章
最新文章
热点推荐