3 条题解
-
1
/***************************************** 备注: ******************************************/ #include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 2e3 + 10; const int INF = 0x3f3f3f3f; int t , n , k; string a[N]; int num1[30];//第一串字母出现次数 int num2[30];//其他串字母出现次数 int sum[N];//差异值 int main() { cin >> t; while( t-- ) { cin >> k >> n; for(int i = 0; i < k ; i++) cin >> a[i]; //求第一组数据每个字母出现的次数 if( k == 1) { printf("YES\n"); continue; } bool flag = 0 , flag1 = 0; memset(num1, 0 , sizeof(num1)); memset(num2, 0 , sizeof(num2)); memset(sum, 0 , sizeof(sum)); for(int i = 1; i < k; i++)//枚举2~k-1组数据 { for(int j = 0; j < n; j++) { num1[a[0][j] - 'a']++;//第一组数据每个字母出现次数 num2[a[i][j] - 'a']++;//其他组每个字母出现次数 if(a[0][j] != a[i][j])//第i组数据与第一组数据的差异值 sum[i]++; } //判断每个字母出现次数是否相同 for(int i = 0; i < 26; i++) if(num1[i] != num2[i]) { flag = 1; break; } //有一串出现次数与第一串不一祥 if(flag) { break; } } if(flag) { printf("NO\n"); continue; } //标记是否有相同字母 for(int i = 0 ; i < 26; i++) if(num1[i]) { flag1 = 1; break; } int anssum = 0; bool flag2 = 0; for(int i = 0 ; i < n; i++)//枚举每一个字符 { for(int j = i + 1; j < n; j++)//枚举待交换字符 { anssum = 0; for(int l = 1; l < k; l++)//枚举除第一串外的字符串 { int cnt = sum[l];//第l串字符与第一串字符的差异数 //交换字符ij后对第l串的影响 if(a[0][i] != a[l][i]) cnt--; if(a[0][j] != a[l][j]) cnt--; if(a[0][i] != a[l][j]) cnt++; if(a[0][j] != a[l][i]) cnt++; if((cnt == 0 && flag1) || cnt == 2) anssum++; else break; } if(anssum == k - 1) { printf("YES\n"); flag2 = 1; break; } } if(flag2) break; } if(!flag2) printf("NO\n"); } return 0; }
信息
- ID
- 2306
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 159
- 已通过
- 18
- 上传者