首页 > ACM题库 > HDU-杭电 > HDU 4346-The Beautiful Road-字符串-[解题报告]HOJ
2015
05-23

HDU 4346-The Beautiful Road-字符串-[解题报告]HOJ

The Beautiful Road

问题描述 :

There is a road from city A to city B.On the road,there are N positions(indexed from 0 to N-1).In order to celebrate the Multi-University training,the mayor of city A commands a worker to insert N flags on the N positions.The color of a flag is either red or green.We call the road is beautiful if and only if there exists at least one pair of non-negative integers (a,b) (0<=a<b<N and (a+b) is an even number) such that both a-th flag and b-th flag are red and (a+b)/2-th flag is green.Otherwise we call the road is ugly.Now,some positions have already been inserted flags.In order to make the road beautiful,the worker must carefully insert the flags on the positions which haven’t been inserted.He wants to know how many different types of beautiful road he can make.The type of the road only depends on the flags’ color.

输入:

The first line of the input is the number of cases. On each case there is a line consists of a string.The length of the string is N.(0<=N<=800).The i-th character of the string is ‘R’ or ‘G’ or ‘?’.'R’ means the flag on the i-th position which has been inserted is red.’G’ means the flag on the i-th position which has been inserted is green.’?’ means the i-th position hasn’t been inserted a flag.

输出:

The first line of the input is the number of cases. On each case there is a line consists of a string.The length of the string is N.(0<=N<=800).The i-th character of the string is ‘R’ or ‘G’ or ‘?’.'R’ means the flag on the i-th position which has been inserted is red.’G’ means the flag on the i-th position which has been inserted is green.’?’ means the i-th position hasn’t been inserted a flag.

样例输入:

4
?G
RG?
???
????

样例输出:

0
1
1
4

题意:

         给出一个字符串,字符串由"R","G","?"组成,若字符串存在2R,且2R中间是一个G,则称该串为“漂亮串”,现考虑将"?"

换成"R""G"的所有字符串,求这些字符串中“漂亮串”的总数。

我们从反面考虑问题,若字符串不是“漂亮串”,则字符串的形式必然为:R…R…R…R,相邻2R的距离相等且距离为奇

数。

       所以我们可以枚举距离,构造“非漂亮串”,毛估总共需要枚举的次数为n*n*(1/1+1/2+…1/n),时间复杂度为O(n^2logn),然后

用总的字符串数(2^k,k"?"总数)减去“非漂亮串”的总数,就是“漂亮串”的总数了。 

 

解释:

    就是我们把任意一个字符串s中的R全部提取出来(只考虑R),如果s不是beautiful
string
的话,那么所有的R一定具有解题思路里面那种形式

否则的话,就一定是beautiful string了,这个可以用反证法证明

 

反证分两步,证明相邻两个R距离不等以及存在距离为偶数

这个证明还是容易的

 

这样对每一个给定字符串,我们根据R的个数分别枚举距离就行了

/*
Pro: 0

Sol:

date:
*/
#include<cstdio>
#include<cstring>
using namespace std;
#define mod 1000000007
int t;
long long mod_pow(int a,int n,int p)
{
    long long ret=1;
    long long A=a;
    while(n){
        if (n & 1)
            ret=(ret*A)%p;
        A=(A*A)%p;
        n>>=1;
    }
    return ret;
}
int main(){
    scanf("%d",&t);
    while( t -- ){
        char str[808];
        scanf("%s",str);
        int len = strlen(str);
        int unknown = 0, r_num = 0;
        for(int i = 0; i < len; i ++){
            if(str[i] == '?') unknown ++;
            else if(str[i] == 'R') r_num ++;
        }
        long long unbea = (r_num == 0);//全为G的是不beautiful的。
        
        for(int i = 0; i < len; i ++){//开始遍历
            if(str[i] == 'R' || str[i] == '?'){//可能是R的情况
                int x = (str[i] == 'R');
                unbea = (unbea + (x == r_num) ) % mod;//这是给出的串只有一个R的情况
                
                for(int dis = 1; dis + i < len; dis += 2){// + i 枚举距离
                    int y = x;
                    for(int sta = i + dis; sta < len; sta += dis){//枚举第二个位置以及以后
                        y += (str[sta] == 'R');
                        if(str[sta] == 'G') break;
                        unbea = (unbea + (y == r_num) )% mod;//如果遍历到的点和R的个数相同
                        //那么,就加上一个不美丽字符串
                        //这一句话包含了(拿样例4做解释)
                        //RRRR
                        //RRRG RRGG
                        //RGGR
                        //GRRR GRRG
                        //GGRR
                    }
                }
            }
        }
        printf("%I64d\n",mod_pow(2,unknown,mod) - unbea);
    }
    return 0;
}

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

参考:http://blog.csdn.net/julyana_lin/article/details/7849006