七夕祭摊位布置：满足cl同学的愿望

七夕祭摊位布置：满足cl同学的愿望/n/n七夕节因牛郎织女的传说而被扣上了'情人节'的帽子。于是TYVJ今年举办了一次线下七夕祭。/n/nVani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。/n/nTYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。/n/nVani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。/n/n不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。由于zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。/n/n现在Vani想知道他的两个要求最多能满足多少个。在此前提下，至少需要交换多少次摊点。/n/n### 输入格式/n/n第一行包含三个整数N和M和T，T表示cl对多少个摊点感兴趣。/n/n接下来T行，每行两个整数x, y，表示cl对处在第x行第y列的摊点感兴趣。/n/n### 输出格式/n/n首先输出一个字符串。/n/n如果能满足Vani的全部两个要求，输出both；/n如果通过调整只能使得各行中cl感兴趣的摊点数一样多，输出row；/n如果只能使各列中cl感兴趣的摊点数一样多，输出column；/n如果均不能满足，输出impossible。/n/n如果输出的字符串不是impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。/n/n### 数据范围/n/n1≤N,M≤100000, /n0≤T≤min(N/*M,100000), /n1≤x≤N, /n1≤y≤M/n/n### 输入样例：/n/n2 3 4/n1 3/n2 1/n2 2/n2 3/n/n### 输出样例：/n/nrow 1/n/n### 解答代码内容：/n/n#### 算法1/n/n1. 将所有感兴趣的点找出来，按横纵坐标分别排序，得到两个序列。/n2. 判断两个序列是否有相同长度的前缀，然后判断是row还是column，还是both。/n/n##### 时间复杂度/n/n$O(TlogT)$，其中T为感兴趣摊点数。/n/n##### 参考文献/n/n无/n/n##### python3 代码/n/npython3/nN, M, T = map(int, input().split())/npoints = []/nfor _ in range(T):/n x, y = map(int, input().split())/n points.append((x, y))/n/n# 按横坐标排序/npoints_x = sorted(points, key=lambda x: x[0])/n# 按纵坐标排序/npoints_y = sorted(points, key=lambda x: x[1])/n/n# 判断两个序列是否有相同长度的前缀/nprefix_len = 0/nfor i in range(T):/n if points_x[i] == points_y[i]:/n prefix_len += 1/n else:/n break/n/n# 判断是否能满足Vani的要求/nif prefix_len == T:/n print('both 0')/nelif prefix_len == N:/n print('row 0')/nelif prefix_len == M:/n print('column 0')/nelse:/n print('impossible')/n/n/n#### 算法2/n/n(暴力枚举) $O((n+m)t^2)$/n/n枚举交换的两个位置，分别计算交换后每行和每列cl感兴趣的摊点数，然后判断是否满足条件。取满足条件的最少交换次数。/n/n##### 时间复杂度/n/n$O((n+m)t^2)$，其中n为行数，m为列数，t为感兴趣摊点数。/n/n##### 参考文献/n/n无/n/n##### python3 代码/n/npython3/nN, M, T = map(int, input().split())/npoints = []/nfor _ in range(T):/n x, y = map(int, input().split())/n points.append((x, y))/n/n# 计算每行和每列cl感兴趣的摊点数/nrow_counts = [0] * N/ncol_counts = [0] * M/nfor x, y in points:/n row_counts[x - 1] += 1/n col_counts[y - 1] += 1/n/n# 暴力枚举交换的两个位置/nmin_swap = float('inf')/nfor i in range(T):/n x1, y1 = points[i]/n for j in range(i + 1, T):/n x2, y2 = points[j]/n # 判断是否可以交换/n if x1 == x2 or y1 == y2:/n # 模拟交换/n row_counts[x1 - 1] -= 1/n row_counts[x2 - 1] += 1/n col_counts[y1 - 1] -= 1/n col_counts[y2 - 1] += 1/n # 判断是否满足条件/n if all(row_counts[k] == row_counts[0] for k in range(N)) and all(col_counts[k] == col_counts[0] for k in range(M)):/n min_swap = 1/n # 回溯/n row_counts[x1 - 1] += 1/n row_counts[x2 - 1] -= 1/n col_counts[y1 - 1] += 1/n col_counts[y2 - 1] -= 1/n/n# 判断是否能满足Vani的要求/nif min_swap == float('inf'):/n print('impossible')/nelif all(row_counts[k] == row_counts[0] for k in range(N)) and all(col_counts[k] == col_counts[0] for k in range(M)):/n print('both 0')/nelif all(row_counts[k] == row_counts[0] for k in range(N)):/n print('row 0')/nelif all(col_counts[k] == col_counts[0] for k in range(M)):/n print('column 0')/nelse:/n print('impossible')/n/n/n#### 算法3/n/n(暴力枚举) $O((n+m)t^2)$/n/n由于只有两种调整方式，所以可以枚举行的调整和列的调整，计算出每行和每列cl感兴趣的摊点数，然后判断是否满足条件。取满足条件的最少交换次数。/n/n##### 时间复杂度/n/n$O((n+m)t^2)$，其中n为行数，m为列数，t为感兴趣摊点数。/n/n##### 参考文献/n/n无/n/n##### python3 代码/n/npython3/nN, M, T = map(int, input().split())/npoints = []/nfor _ in range(T):/n x, y = map(int, input().split())/n points.append((x, y))/n/n# 计算每行和每列cl感兴趣的摊点数/nrow_counts = [0] * N/ncol_counts = [0] * M/nfor x, y in points:/n row_counts[x - 1] += 1/n col_counts[y - 1] += 1/n/n# 枚举行的调整/nrow_swap = float('inf')/nfor i in range(N):/n for j in range(i + 1, N):/n # 模拟交换/n row_counts[i] -= 1/n row_counts[j] += 1/n # 判断是否满足条件/n if all(row_counts[k] == row_counts[0] for k in range(N)):/n row_swap = 1/n # 回溯/n row_counts[i] += 1/n row_counts[j] -= 1/n/n# 枚举列的调整/ncol_swap = float('inf')/nfor i in range(M):/n for j in range(i + 1, M):/n # 模拟交换/n col_counts[i] -= 1/n col_counts[j] += 1/n # 判断是否满足条件/n if all(col_counts[k] == col_counts[0] for k in range(M)):/n col_swap = 1/n # 回溯/n col_counts[i] += 1/n col_counts[j] -= 1/n/n# 判断是否能满足Vani的要求/nif row_swap == float('inf') and col_swap == float('inf'):/n print('impossible')/nelif row_swap == float('inf') and col_swap == 1:/n print('column 1')/nelif row_swap == 1 and col_swap == float('inf'):/n print('row 1')/nelif row_swap == 1 and col_swap == 1:/n print('both 0')/nelse:/n print('impossible')/n/n