首页 > ACM题库 > HDU-杭电 > HDU 4626-Jinkeloid-模拟-[解题报告]HOJ
2015
09-17

HDU 4626-Jinkeloid-模拟-[解题报告]HOJ

Jinkeloid

问题描述 :

After listening several songs of Jinkeloid,I come up with this problem :).
There is a string s only consist of first 20 lowercase English letters.
And we have several queries,each time I have k letters c1, c2, …, ck,and I wonder how many consecutive substring of string s that each ci has occur even times in it.
Two substring with the same content but different position are considered different.

输入:

The first line contains integer T(1<=T<=5),denote the number of the test cases.
For each test cases,the first line contains a string s(1<= length of s <= 105),the second line contains a number Q (Q<= 3 * 104),denote the number of queries.
Then Q lines follows,each lines start with a number k(1<= k<= 5),then contains k lowercase English letters c1, c2, …, ck(There won’t be duplicated ci).

输出:

The first line contains integer T(1<=T<=5),denote the number of the test cases.
For each test cases,the first line contains a string s(1<= length of s <= 105),the second line contains a number Q (Q<= 3 * 104),denote the number of queries.
Then Q lines follows,each lines start with a number k(1<= k<= 5),then contains k lowercase English letters c1, c2, …, ck(There won’t be duplicated ci).

样例输入:

1
cacca
5
3 c a b
2 c b
2 a b
3 c b a
2 a b

样例输出:

2
7
6
2
6
Hint
Remember 0 is also a even number,so occur zero times is ok. Thanks Jinkeloid for this problem :).

盯着CLJ那神奇的两行代码看了半天啊,最近我的智商真心让我感到蛋蛋的忧伤,,,,,

各位出题人能不能不要在题解上加上任何带情感色彩的词语啊啊啊啊啊。。。

比如,“简单的dp”。。。。。。研究了一下午,,,233333333

说到这个题,其实可以通过预处理之后,对于每个询问,用容斥来做,或者像标称那样暴力,枚举一个集合的母集,然后减掉。题解都说的很清楚了,我就不多说什么了,毕竟是别人的思路。。。。

就贴一贴那段神奇的“简单的dp”,你能看出两个循环后cnt数组变成了什么吗??反正我是折腾了半天(还是得从dp的角度去理解),一步步模拟只能知其然啊。。。

其实思想类似与倍增的DP,我觉得这道题最精髓的就是下面这个了,,,

        for(int j = 0; j < 20; j++) {
            for(int i = 0; i < 1<<20; i++) if(i>>j&1) {
                cnt[i^(1<<j)] += cnt[i];
            }
        }

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/crazy_ac/article/details/9886789