题目链接:http://acm.swust.edu.cn/problem/0385/
Time limit(ms): 5000 Memory limit(kb): 65535
Description
江油是李白故里。马可波罗来到李白故里,突然诗性大发,准备吟诗两句。
众所周知,诗句讲究对仗。马可波罗中文水平有限,所以想从已知的佳句中找出两句对偶的,组合出一些新的诗句。
为了简化问题,小马只选择七个字的佳句,并把它们的形式化成了字母(按意群将句子分组、断开)。例如“海上明月共潮生”可化为“AABBCCD”,也可以化为“YYQQZZH”,即字母只起显示结构的作用,与句子内容无关。
两个句子按照字母的连续性分段后,如果各成分的字数依次相同,则这两个句子对偶。例如:例如“QBLLLDE”和“DEZZZBF”,将第一句按照字母的连续性分为5段:Q、B、LLL、D、E,每段长度分别为1、1、3、1、1,而第二句经过断句后,各段的长度也分别为1、1、3、1、1,因此这两个句子对偶。
注:“AABCCCD”和“EEFBBBE”这类句子也算作对偶:第二个句子中两次出现“E”,但“E”是断开的,所以断句情况仍为:2、1、3、1。由于字母只用来突出结构,所以如果出现两次同样的字母串,则它们表示的诗句内容不相同。
样例解析:
众所周知,诗句讲究对仗。马可波罗中文水平有限,所以想从已知的佳句中找出两句对偶的,组合出一些新的诗句。
为了简化问题,小马只选择七个字的佳句,并把它们的形式化成了字母(按意群将句子分组、断开)。例如“海上明月共潮生”可化为“AABBCCD”,也可以化为“YYQQZZH”,即字母只起显示结构的作用,与句子内容无关。
两个句子按照字母的连续性分段后,如果各成分的字数依次相同,则这两个句子对偶。例如:例如“QBLLLDE”和“DEZZZBF”,将第一句按照字母的连续性分为5段:Q、B、LLL、D、E,每段长度分别为1、1、3、1、1,而第二句经过断句后,各段的长度也分别为1、1、3、1、1,因此这两个句子对偶。
注:“AABCCCD”和“EEFBBBE”这类句子也算作对偶:第二个句子中两次出现“E”,但“E”是断开的,所以断句情况仍为:2、1、3、1。由于字母只用来突出结构,所以如果出现两次同样的字母串,则它们表示的诗句内容不相同。
样例解析:
“ABCCCDA”和“DEZZZBF”两句形式相同,可以组成1对对偶佳句。
“LLLMNNO”、“AAABCCD”和“KKKXPPQ”形式都相同,任取两个共可组成3对不同的对偶佳句。
Input
第一行,一个整数N,2≤N≤100000
以下N行,每行都有一个由七个大写字母组成的字符串,代表一个佳句。
以下N行,每行都有一个由七个大写字母组成的字符串,代表一个佳句。
Output
一个整数:这些佳句可以拼凑成的对偶佳句的种类数。
Sample Input
5 ABCCCDA LLLMNNO DEZZZBF AAABCCD KKKXPPQ |
Sample Output
| 4 |
Hint
解题思路:
1、利用位运算按以下规则处理每一个字符串s,对应每一个字符信息放在一个数bit的每一位中,得到每一个字符对应的数bit
(1) if(s[i]==s[i-1]) bit_t=1; bit_t代表数bit的第i位;
(2) if(i==0||s[i]!=s[i-1]) bit_t=0;
2、由于只有7个字符,二进制状态下bit最多7位,那么bit的范围在[0,126] 之间,(二进制下就是,[0000000,1111110])
3、开一个126的hash数组,对于每一个bit有(hash[bit]++),代表了当前这种结构的“诗”的句数
4、总对数cnt=hash[0]*(hash[0]-1)/2+***+hash[n]*(hash[n]-1)/2 (和求多边形对角线条数一个道理)
代码如下:
1 #include <iostream> 2 using namespace std; 3 int Hash[1 << 7], t, cnt; 4 char s[8]; 5 int main(){ 6 cin >> t; 7 while (t--){ 8 int i, bit = 0; 9 cin >> s; 10 for (i = 1; i < 7; i++) 11 if (s[i] == s[i - 1]) 12 bit |= 1 << i; 13 Hash[bit]++; 14 } 15 for (int i = 0; i < (1 << 7); i++) 16 cnt += Hash[i] * (Hash[i] - 1) / 2; 17 cout << cnt << endl; 18 return 0; 19 }