首页 > ACM题库 > HDU-杭电 > HDU 3058-Generator-递推-[解题报告]HOJ
2014
03-01

HDU 3058-Generator-递推-[解题报告]HOJ

Generator

问题描述 :

We can generate a random string by generating a sequence of random characters and concatenating them together. Each character is chosen independently from the first n letters in the English alphabet with equal probability. Only capital letters are used in this problem. The generation is stopped as soon as one of specific patterns occurs in the random string.

Your task is to predict the expected length of the generated string.

输入:

Standard input will contain multiple test cases.

First line is the number of case x.

Each test case consists of integer N (1<=N<=8) which is the number of letters used, and M (1<=M<=10) which is the number of patterns used. The following M lines contain the patterns which are non-empty strings consisting of letters chosen from the first N upper case English letters. The length of any pattern will not exceed 10.

输出:

Standard input will contain multiple test cases.

First line is the number of case x.

Each test case consists of integer N (1<=N<=8) which is the number of letters used, and M (1<=M<=10) which is the number of patterns used. The following M lines contain the patterns which are non-empty strings consisting of letters chosen from the first N upper case English letters. The length of any pattern will not exceed 10.

样例输入:

4
2 1
A
2 1
ABA
3 1
AAAAA
2 2
A
AA

样例输出:

2.00
10.00
363.00
2.00


trie图上递推+高斯消元, 卡精度题,代码挫了,C++过不了(long double也不行),G++可以过 , 对于结果比较大的数据会出错

比如  

8 1

AAAAAAAAAAA

这组数据我的代码在C++和G++输出就不同,还有就是有double中的运算尽量应尽量避免除法运算,精度损失较大 


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
#include <cctype>
#include <utility>   
#include <map>
#include <string>  
#include <climits> 
#include <set>
#include <string>    
#include <sstream>
#include <utility>   
#include <ctime>

using std::priority_queue;
using std::vector;
using std::swap;
using std::stack;
using std::sort;
using std::max;
using std::min;
using std::pair;
using std::map;
using std::string;
using std::cin;
using std::cout;
using std::set;
using std::queue;
using std::string;
using std::istringstream;
using std::make_pair;
using std::getline;
using std::greater;
using std::endl;
using std::multimap;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned UNS;
typedef pair<int, int> PAIR;
typedef multimap<int, int> MMAP;

const int MAXN(110);
//const int SIGMA_SIZE(26);
const int MAXM(110);
const int MAXE(4000010);
const int MAXH(18);
const int INFI((INT_MAX-1) >> 1);
const double EPS(1e-11);
const int MOD(10007);
const ULL LIM(1000000000000000ull);

inline bool EZ(double temp)
{
    return fabs(temp) < EPS;
}

struct MAT
{
    int r, c;
    double arr[MAXN][MAXN];
    MAT(int tr, int tc): r(tr), c(tc)
    {}
    MAT()
    {}
    void reset()
    {
        for(int i = 0; i < r; ++i)
            for(int j = 0; j < c; ++j)
                arr[i][j] = 0;
    }
    void identity()
    {
        reset();
        for(int i = 0; i < r; ++i)
            arr[i][i] = 1;
    }
    
    /* 模2方程组消元
    int XOR_eliminate()
    {
        int rank = 0, temp;
        for(int i = 0; i < r; ++i)
        {
            temp = i;
            for(int k = i; k < r; ++k)
                if(arr[k][i]){temp = k; break;}
            if(arr[temp][i] == 0) 
            { is_free[i] = true; continue;}
            is_free[i] = false;
            ++rank;
            if(temp != i) 
                for(int k = 0; k < c; ++k) 
                    swap(arr[i][k], arr[temp][k]);
            for(int k = i+1; k < r; ++k)
                if(arr[k][i])
                    for(int k2 = i; k2 < c; ++k2)
                        arr[k][k2] ^= arr[i][k2];
        }
        for(int i = r-1; i >= 0; --i)
        {
            for(int j = i+1; j < c-1; ++j)
                arr[i][c-1] ^= arr[j][c-1]&arr[i][j];
            if(arr[i][i] == 0 && arr[i][c-1] != 0)
                return -1;                      //有矛盾解
        }
        return rank; //返回矩阵的秩
    }
	*/
	void gauss_eliminate()
    {
        int temp;
        double mmx;
        for(int i = 0; i < r; ++i)
        {
            temp = i;
            mmx = fabs(arr[i][i]);
            for(int j = i+1; j < r; ++j)
                if(fabs(arr[j][i]) > mmx)
                {
                    mmx = fabs(arr[j][i]);
                    temp = j;
                }
            if(temp != i) for(int j = 0; j < c; ++j) swap(arr[temp][j],arr[i][j]);
            for(int j = c-1; j >= i; --j)
                for(int k = i+1; k < r;s ++k)
                    arr[k][j] -= arr[k][i]/arr[i][i]*arr[i][j];
        
        }
        for(int i = r-1; i >= 0; --i)
        {
            for(int j = i+1; j < c-1; ++j)
                arr[i][c-1] -= arr[j][c-1]*arr[i][j];
            arr[i][c-1] /= arr[i][i];
        }
    }


    void gauss_jordan()
    {
        int temp;
        for(int i = 0; i < r; ++i)
        {
            temp = i;
            for(int j = i+1; j < r; ++j)
                if(fabs(arr[j][i]) > fabs(arr[temp][i])) temp = j;
            if(EZ(arr[temp][i])) continue;
            if(temp != i)
                for(int j = 0; j < c; ++j)
                    swap(arr[temp][j], arr[i][j]);
            for(int j = 0; j < r; ++j)
                if(j != i)
                    for(int k = c-1; k >= i; --k)
                        arr[j][k] -= arr[j][i]/arr[i][i]*arr[i][k];
        }
    }
};

MAT mat;

int SIGMA_SIZE;
int que[MAXN];
int front, back;

struct AC
{
    int ch[MAXN][8];
    int f[MAXN];
    bool val[MAXN];
    int size;
    
    void init()
    {
        memset(ch[0], 0, sizeof(ch[0]));
        f[0] = 0;
        val[0] = false;
        size = 1;
    }
    inline int idx(char temp)
    {
        return temp-'A';        
    }
    
    void insert(char *S)
    {
        int u = 0, id;
        for(; *S; ++S)
        {
            id = idx(*S);
            if(!ch[u][id])
            {
                memset(ch[size], 0, sizeof(ch[size]));
                val[size] = false;
                ch[u][id] = size++;
            }
            u = ch[u][id];
        }
        val[u] = true;
    }  
    void construct()
    {
        front = back = 0;
        int cur, u;
        for(int i = 0; i < SIGMA_SIZE; ++i)
        {
            u = ch[0][i];
            if(u)
            {
                que[back++] = u;
                f[u] = 0;
            }
        }
        while(front < back)
        {
            cur = que[front++];
            for(int i = 0; i < SIGMA_SIZE; ++i)
            {
                u = ch[cur][i];
                if(u)
                {
                    que[back++] = u;
                    f[u] = ch[f[cur]][i];
                    val[u] |= val[f[u]];
                }
                else
                    ch[cur][i] = ch[f[cur]][i];
            }
        }
    }
};

AC ac;

bool vis[MAXN];

void dfs(int cur)  //列方程时两边同时乘上SIGMA_SIZE,这样就可以避免处以SIGMA_SIZE,否则精度损失较大,G++也过不了
{
    if(vis[cur])
        return;
    vis[cur] = true;
    mat.arr[cur][cur] = SIGMA_SIZE;
    if(ac.val[cur])
        mat.arr[cur][ac.size] = 0;
    else
        mat.arr[cur][ac.size] = SIGMA_SIZE;   
    for(int i = 0; i < SIGMA_SIZE; ++i)
    {
        int tv = ac.ch[cur][i];
        if(!ac.val[cur])
			mat.arr[cur][tv] -= 1.0;
        dfs(tv);
    }
}

char str[15];

int main()
{
    int TC, n_case(0);
    scanf("%d", &TC);
    while(TC--)
    {
        int m;
        scanf("%d%d", &SIGMA_SIZE, &m);
        ac.init();
        for(int i = 0; i < m; ++i)
        {
            scanf("%s", str);
            ac.insert(str);
        }
        ac.construct();
        mat.r = ac.size;
        mat.c = ac.size+1;
        mat.reset();
        memset(vis, 0, sizeof(vis));
        dfs(0);
		mat.gauss_eliminate();
		printf("%.2f\n", mat.arr[0][ac.size]);
    }
    return 0;
}

参考:http://blog.csdn.net/gyarenas/article/details/8981187


  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;