D. Irreducible Anagrams (思维、前缀和、构造)

偏执的太偏执、 2021-07-16 22:40 372阅读 0赞

[题目][Link 1]

题意：一个字符串如果只是其中字符顺序被打乱则称其和原字符串相互为字谜。对于两个互为字谜的字符串，两个字符串按相同的位置分割开成为n(n>=2)个小串，然后每个小串都互为字谜，则称这两个字符串是互为可还原的，现在给我们一个字符串，再给出q次问询，每次问询给出一个区间，要我们判断区间内的字符串是否具有任意一个不可还原的字符串与之对应（不可还原需要两个字符串互为字谜且不是可还原的）。

思路：其实判断其是不是可还原串拆成n个小串变为拆成2个小串就可以了，因为可以拆成n个必定也可以拆成2个。然后我们构造一下哪几种情况可以找到不可还原串  
1.单独一个字母 如： a 因为可还原串要求至少有两段

2.当字符串首尾不一样时 如：acadsdab 我们只需交换首尾，其他位置不变。bcadsdaa，其它部分不变，又保证了一定会有一个不同使之构不成两个字迷。

3.当首位一样时，该字符串有三个不同字符。看一个极端情况 aaaacaaabaaaa 只需让最前面的a与后面那个不同字符b交换，末尾的a与前面的不同字符c交换。baaaaaaaaaaac,因为除了交换的两个其它字符位置不变，会发现一定会有一个字符不同（因为交换的3个字符不相同），最后判断一个区间内是否具有三个不同字符用前缀和即可，因为字母只有26个，时间没问题。

4.其余情况都不能找到不可还原串。

Code:

#include<iostream>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int sum[30][Max];
    
    int main()
    { 
    	string str;cin >> str;
    	str.insert(str.begin(), '#');
    	for (int i = 1;i <= str.size() - 1;i++)
    	{ 
    		int a = str[i] - 'a';
    		for (int j = 0;j <= 29;j++)sum[j][i] = sum[j][i - 1];
    		sum[a][i]++;
    	}
    	int q;cin >> q;
    	while (q--)
    	{ 
    		int l, r;cin >> l >> r;
    		if (r == l || str[l] != str[r])cout << "Yes" << endl;
    		else
    		{ 
    			int ss = 0;
    			for (int i = 0;i <= 29;i++)
    			{ 
    				if (sum[i][r] - sum[i][l] >= 1)ss++;
    			}
    			if (ss >= 3)cout << "Yes" << endl;
    			else cout << "No" << endl;
    		}
    	}
    }

[Link 1]: https://codeforc.es/contest/1291/problem/D