3 条题解

  • 1
    @ 2023-10-15 11:58:41
    /*****************************************
    备注:
    ******************************************/
    #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
    上传者