题目
After learning a lot about space exploration, a little girl named Ana wants to change the subject.
Ana is a girl who loves palindromes (string that can be read the same backwards as forward). She has learned how to check for a given string whether it’s a palindrome or not, but soon she grew tired of this problem, so she came up with a more interesting one and she needs your help to solve it:
You are given an array of strings which consist of only small letters of the alphabet. Your task is to find how many palindrome pairs are there in the array. A palindrome pair is a pair of strings such that the following condition holds: at least one permutation of the concatenation of the two strings is a palindrome. In other words, if you have two strings, let’s say “aab” and “abcac”, and you concatenate them into “aababcac”, we have to check if there exists a permutation of this new string such that it is a palindrome (in this case there exists the permutation “aabccbaa”).
Two pairs are considered different if the strings are located on different indices. The pair of strings with indices (i,j) is considered the same as the pair (j,i).
题目大意
给定一组由小写字母组成的字符串，判定这些字符串两两组合，随意排列能否组成一列回文。最终输出字符串能组成回文的对数数目。
输入
The first line contains a positive integer N (1≤N≤100000), representing the length of the input array.
Each of the next N lines contains a string (consisting of lowercase English letters from ‘a’ to ‘z’) — an element of the input array.
The total number of characters in the input array will be less than 1000000.
输出
Output one number, representing how many palindrome pairs there are in the array.
输入样例1
3
aa
bb
cd
输出样例1
1
输入样例2
6
aab
abcac
dffe
ed
aa
aade
输出样例2
6
题目分析
这是我在ACM集训时碰见的一个针对复杂度分析的题目。首先分析一下题目，题目在判断两个字符串能否排列成为一条回文，那么想要满足这个条件，就需要保证 组合的两个字符串相加后，26个字母各自对应的个数均为偶数，或者仅有一种字符的个数为奇数。 输入一组中字符串个数最大范围在 1 0 5 10^5 105,很显然不能用逐个相加，随后逐项比较，计算有多少个奇数的办法。这样产生的复杂度为 O ( N 2 ) O(N^2) O(N2),会超时。
那么我们可以另想一下，这里26个字母，我们所需要的也不过是它们对应的两种状态，奇数个或者偶数个，完全可以用二进制数来表示。由此，我们可以用一个26位长的二进制数来代表每一位字母的状态。而两个字符串各个字符相加，同样也就可以用每一位 异或 来表示。
两数异或得到的结果，若是满足要求，也无非两种，第一种全为0，第二种含有一位1。那么在进行判断时，含有一位1的情况又需要多层判定，又回到了最初的算法复杂度，容易超时。那么我们可以反过来，将一位字符串的二进制数与26种仅含一位1的二进制数异或，若是存在与结果相同的字符串二进制数，那么证明这两串字符串可以组成回文
代码
#include <iostream>
#include <map>
#include <string>
using namespace std;typedef long long ll;
map<int,int>mp;//用map存各字符串出现次数；例如aabb,vvdd均为00....000
ll ans,num;
int main(){
int T;cin>>T;string str;for(int i = 0;i<T;++i){
cin >> str;num = 0;for(int j = 0;j<str.size();++j){
num^=(1<<(str[j]-'a'));//存储字符串为二进制数}for(int j = 0;j<26;++j){
ans+=mp[num^(1<<j)];//与逐个1相异或，判定是否存在对应的字符串}ans+=mp[num];//若是存在两字符串二进制数相同情况的处理++mp[num];//储存出现次数}cout << ans<<endl;return 0;
}
链接
http://codeforces.com/contest/1046/problem/H