[Swust OJ 385]--自动写诗

时间：2021-10-31 02:20:24

题目链接：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。由于字母只用来突出结构，所以如果出现两次同样的字母串，则它们表示的诗句内容不相同。
样例解析：
“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   (和求多边形对角线条数一个道理)
代码如下：
 #include <iostream>

 using namespace std;

 int Hash[ << ], t, cnt;

 char s[];

 int main(){

     cin >> t;

     while (t--){

         int i, bit = ;

         cin >> s;

         for (i = ; i < ; i++)

         if (s[i] == s[i - ])

             bit |=  << i;

         Hash[bit]++;

     }

     for (int i = ; i < ( << ); i++)

         cnt += Hash[i] * (Hash[i] - ) / ;

     cout << cnt << endl;

     return ;

 }

相关文章