[Swust OJ 385]

[Swust OJ 385]

题目链接：/

 

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。由于字母只用来突出结构，所以如果出现两次同样的字母串，则它们表示的诗句内容不相同。
样例解析：
“ABCCCDA”和“DEZZZBF”两句形式相同，可以组成1对对偶佳句。
“LLLMNNO”、“AAABCCD”和“KKKXPPQ”形式都相同，任取两个共可组成3对不同的对偶佳句。 Input 第一行，一个整数N，2≤N≤100000
以下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 }

View Code

 

转载于:.html