Contents
Problem
找出 r1 , r2 列的 c1 行是一樣的，還有r1 , r2 列的 c2 行是一樣的。
Solution
加快字串查詢，這邊用 std::unordered_map<string, int> 來處理，再存進 data[][] 裡。
接著窮舉任兩行，每窮舉出一組 (c1,c2) 就跑每一列，看有沒有兩列的字串是一樣的。而比對的方法是對每一組 (c1,c2) 的字串建 map ，只要先前有建過了代表重複了。
一個方法是用 std:: map<pair<int, int>, int> ，key 值存的是 c1,c2 的字串，已由先前所建 map ，轉成兩個數字了，所以用 std::pair<int,int> 來存，value 則是存在第幾列。如此一來就可知道重複的是哪兩列(當前列 和 value)。
另一個方法是直接用 pairing function 來建 hash table
LL s1 = data[r][c1], s2 = data[r][c2];//取出在 r 列的兩行字串
LL temp = (s1 + s2 - 2)*(s1 + s2 - 1) / 2 + s2;//hash: pairing function
其餘操作同上一個方法。
Code
(1)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
typedef long long LL;
using namespace std;
int main()
{
int n, m;
unordered_map<string, int> str_map;
int data[10001][11];
while (scanf("%d%d", &n, &m) != EOF)
{
getchar();
str_map.clear();
int count = 1;
string s;
char c;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
data[i][j] = 0;//init
while ((c = getchar()) != ',' && c != '\n')
s += c;
//替字串建 map
if (!str_map.count(s))
str_map[s] = count++;
data[i][j] = str_map[s];
s.clear();
}
unordered_map<LL, int> col_data;//某列任意兩行的資料
bool flag = true;
//窮舉任兩行
for (int c1 = 0; c1 < m&&flag; c1++)
for (int c2 = c1 + 1; c2 < m&&flag; c2++)
{
for (int r = 0; r < n; r++)
{
LL s1 = data[r][c1], s2 = data[r][c2];//取出在 r 列的兩行字串
LL temp = (s1 + s2 - 2)*(s1 + s2 - 1) / 2 + s2;//hash: pairing function
if (!col_data.count(temp))
col_data[temp] = r;//存進這對字串在哪列
else
{
puts("NO");
printf("%d %d\n%d %d\n", col_data[temp] + 1, r + 1, c1 + 1, c2 + 1);
flag = false;
break;
}
}
col_data.clear();
}
if (flag)
puts("YES");
}
return 0;
}
(2)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
using namespace std;
int main()
{
int n, m;
unordered_map<string, int> str_map;
int data[10001][11];
while (scanf("%d%d", &n, &m) != EOF)
{
getchar();
str_map.clear();
int count = 1;
string s;
char c;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
data[i][j] = 0;//init
while ((c = getchar()) != ',' && c != '\n')
s += c;
if (!str_map.count(s))
str_map[s] = count++;
data[i][j] = str_map[s];
s.clear();
}
map<pair<int, int>, int> col_data;
bool flag = true;
for (int c1 = 0; c1 < m&&flag; c1++)
for (int c2 = c1 + 1; c2 < m&&flag; c2++)
{
for (int r = 0; r < n; r++)
{
int s1 = data[r][c1], s2 = data[r][c2];
pair<int, int> d(s1, s2);
if (!col_data.count(d))
col_data[d] = r;
else
{
puts("NO");
printf("%d %d\n%d %d\n", col_data[d] + 1, r + 1, c1 + 1, c2 + 1);
flag = false;
break;
}
}
col_data.clear();
}
if (flag)
puts("YES");
}
return 0;
}