2022

2024-07-09 08:30| 来源: 网络整理| 查看: 265

F. Foreign Football

一共有\(n\)支队伍，每支队伍的名称为\(s_i\)，给定一个\(n \times n\)的矩阵，\(a_{i,j}\)代表第\(i\)支队伍和第\(j\)支队伍名字的拼接，即\(a_{i,j}=s_i+s_j\)，请你通过该矩阵推断出所有队伍的名称，如果有多个解，输出MANY，如果有唯一解，输出UNIQUE，并输出所有队伍的名称，如果无解，输出NONE

注意：队伍名称非空

\(2 \leq n \leq 500,\sum a_{i,j} \leq 1e6\)

题解：高斯消元 + 字符串哈希如果\(n \geq 3\)，显然我们可以对\(s_1+s_2,s_2+s_3,s_1+s_3\)这三个方程进行高斯消元，如果有唯一解我们就可以得到\(s_1\)的长度，那么我们就能够通过\(s_1\)来确定所有队伍的名称，最后枚举一遍矩阵进行检查，如果检查不通过，输出NONE 对于\(n = 2\)的情况，我们考虑特判，我们不妨枚举\(s_1\)的长度后得到\(s_1,s_2\)，通过字符串哈希\(O(1)\)检查\(a_{1,2}\)和\(a_{2,1}\)能否对应即可，如果能够多次对应，那么输出MANY，其他情况对应输出即可 int n; string s[N][N], ans[N]; double a[10][10]; int h1[M], h2[M], p[M], base = 131; int get_hash1(int l, int r) { return ((h1[r] - h1[l - 1] * p[r - l + 1] % mod) % mod + mod) % mod; } int get_hash2(int l, int r) { return ((h2[r] - h2[l - 1] * p[r - l + 1] % mod) % mod + mod) % mod; } int Gauss(int n, int m) // n行m列的增广矩阵 { int r = 0; // 增广矩阵的秩 for (int j = 1; j

【本文地址】

公司简介

联系我们