青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

學習心得(code)

superlong@CoreCoder

  C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
  74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

公告

文字可能放在http://blog.csdn.net/superlong100,此處存放代碼

常用鏈接

留言簿(4)

我參與的團隊

搜索

  •  

最新隨筆

最新評論

  • 1.?re: Poj 1279
  • 對于一個凹多邊形用叉積計算面積 后能根據結果的正負來判斷給的點集的時針方向?
  • --bsshanghai
  • 2.?re: Poj 3691
  • 你寫的這個get_fail() 好像并是真正的get_fail,也是說fail指向的串并不是當前結點的子串。為什么要這樣弄呢?
  • --acmer1183
  • 3.?re: HDU2295[未登錄]
  • 這個是IDA* 也就是迭代加深@ylfdrib
  • --superlong
  • 4.?re: HDU2295
  • 評論內容較長,點擊標題查看
  • --ylfdrib
  • 5.?re: HOJ 11482
  • 呵呵..把代碼發在這里很不錯..以后我也試試...百度的編輯器太爛了....
  • --csuft1

閱讀排行榜

評論排行榜

#include <iostream>
#include 
<string>
#define EPS 1e-6
#define MAXN 101
#define zero(x) (((x)>0?(x):-(x))<EPS)
using namespace std;

int DEBUG;
int n, m, num;

struct tree
{
    tree 
*next[52], *fail;
    
int id, L;
};

struct point
{
    
double x, y;
    
void data(int i, int j)
    {x 
= i; y = j;}
    
void write(){printf("%.0lf %.0lf\n",x, y);}
};

tree 
*root, *p;

tree arr[
1000005];
int  indexx;

int map(char ch)
{
    
if(ch <= 'Z'return ch - 'A';
    
else          return ch - 'a';
}

void newn()
{
    arr[indexx].fail 
= NULL;
    arr[indexx].id 
= 0;
    arr[indexx].L 
= -1;
    
for(int i = 0; i < 52; i ++) arr[indexx].next[i] = 0;
}

void init()
{
    indexx 
= 0;
    newn();
    root 
= &arr[indexx ++];
}

void insert(char ch[], int id, int L)
{
    
int t, i = 0;
    p 
= root;
    
while(ch[i])
    {
        t 
= map(ch[i]);
        
if(p->next[t] == 0)
        {
            newn();
            p
->next[t] = &arr[indexx ++];
        }
        p 
= p->next[t];
        i 
++;
    }
    p
->= L - 1;
    p
->id = id;
}

tree 
*que[1000005];

void get_fail()
{
    
int close = -1, open = 0;
    p 
= root;    p->fail = root;
    que[
0= p;
    
while(close < open)
    {
        p 
= que[++close];
        
for(int i = 0; i < 52; i ++)
        {
            
if(p->next[i] == 0)
            {
                
if(p == root) p->next[i] = root;
                
else          p->next[i] = p->fail->next[i];
            }
            
else
            {
                
if(p == root) p->next[i]->fail = root;
                
else          p->next[i]->fail = p->fail->next[i];
                que[
++open] = p->next[i];
            }
        }
    }
}

char  list[101][101];
point line[
101][2];

int mv[8][2= {{01}, {10}, {11}, {-1-1}, {0-1}, {-10}, {1-1}, {-11}};

bool ok(int x, int y)
{
return x < n && x >= 0 && y < m && y >= 0;}


void query(int inix, int iniy, int way)//way => direction
{
    
int t, i = 0, x = inix, y = iniy;
    
    tree 
*q;
    p 
= root;
    
while( ok(x, y) )
    {
        t 
= map(list[x][y]);
        
while(!p->next[t] && p != root) p = p->fail;
        p 
= p->next[t];
        
if(!p) p = root; q = p;
        
while( q != root && q->fail)
        {
            
if(q->id)
            {
                
int i = q->id;
                point end;
                end.data(x, y);    
                line[i][
1= end;
                
                point sta;
                sta.data(x 
- q->* mv[way][0], y - q->* mv[way][1]);
                line[i][
0= sta;
                
                q
->id = 0;
            }
            q 
= q->fail;
        }
        i 
++;
        x 
+= mv[way][0];
        y 
+= mv[way][1];
    }
}

int tu[101][101];

//計算cross product (P1-P0)x(P2-P0)
double xmult(point p1,point p2,point p0){
    
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

//判三點共線
int dots_inline(point p1,point p2,point p3){
    
return zero(xmult(p1,p2,p3));
}

//判點是否在線段上,包括端點
int dot_online_in(point p,point l1,point l2){
    
return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<EPS&&(l1.y-p.y)*(l2.y-p.y)<EPS;
}

//判兩點在線段同側,點在線段上返回0
int same_side(point p1,point p2,point l1,point l2){
    
return xmult(l1,p1,l2)*xmult(l1,p2,l2)>EPS;
}

//判兩線段相交,包括端點和部分重合
int intersect_in(point u1,point u2,point v1,point v2){
    
if (!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))
        
return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);
    
return dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2);
}

//計算兩直線交點,注意事先判斷直線是否平行!
point intersection(point u1,point u2,point v1,point v2){
    point ret
=u1;
    
double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
            
/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x
+=(u2.x-u1.x)*t;
    ret.y
+=(u2.y-u1.y)*t;
    
return ret;
}

bool connect(int i, int j)
{
    point s1, s2, e1, e2, p;
    s1 
= line[i][0];
    e1 
= line[i][1];
    s2 
= line[j][0];
    e2 
= line[j][1];
    
    
if(intersect_in(s1, e1, s2, e2))
        p 
= intersection(s1, e1, s2, e2);
    
else return false;
        
    
if( p.x - (int)p.x > EPS || p.y - (int)p.y > EPS) return false;
    
return true;
    
}

void bulid()
{
    
int i, j;
    memset(tu, 
0sizeof(tu));
    
//線段相交構圖 
    for(i = 1; i <= num; i ++)
    {
        
for(j = i + 1; j <= num; j ++)
        
if( connect(i, j) )
        {
            tu[i][j] 
= true;
            tu[j][i] 
= true;
        }
    }
}

int cnt;
bool h[101];

void dfs(int x)
{
    
int i;
    
for(i = 1; i <= num; i ++)
    
if(!h[i] && tu[x][i])
    {
        h[i] 
= 1;
        cnt 
++;
        dfs(i);
    }
}

void search(int n,int mat[][MAXN],int* dfn,int* low,int now,int& ret,int* key,int& cnt,int root,int& rd,int* bb){
    
int i;
    dfn[now]
=low[now]=++cnt;
    
for (i=1;i<=n;i++)
        
if (mat[now][i]){
            
if (!dfn[i]){
                search(n,mat,dfn,low,i,ret,key,cnt,root,rd,bb);
                
if (low[i]<low[now])
                    low[now]
=low[i];
                
if (low[i]>=dfn[now]){
                    
if (now!=root&&!bb[now])
                        key[ret
++]=now,bb[now]=1;
                    
else if(now==root)
                        rd
++;
                }
            }
            
else if (dfn[i]<low[now])
                low[now]
=dfn[i];
        }
}

int key_vertex(int n,int mat[][MAXN],int* key){
    
int ret=0,i,cnt,rd,dfn[MAXN],low[MAXN],bb[MAXN];
    
for (i=1;i<=n;dfn[i++]=bb[i]=0);
    
for (cnt=0,i=1;i<=n;i++)
        
if (!dfn[i]){
            rd
=0;
            search(n,mat,dfn,low,i,ret,key,cnt,i,rd,bb);
            
if (rd>1&&!bb[i])
                key[ret
++]=i,bb[i]=1;
        }
    
return ret;
}

bool solve()
{
    
//查詢 
    for(int i = 0; i < n; i ++)
    
for(int J = 0; J < m; J ++)
    {
        query(i, J, 
0); query(i, J, 4);
        query(i, J, 
1); query(i, J, 5);
        query(i, J, 
2); query(i, J, 6);
        query(i, J, 
3); query(i, J, 7);
    }
    
//建圖 
    bulid();
    memset(h ,
0 ,sizeof(h));
    cnt 
= 1;
    h[
1= 1;
    
//連通性 
    dfs(1);
    
if(cnt != num)     return false;
    
int key[101];
    
//割點 
    cnt = key_vertex(num, tu, key);
    
if(cnt > 0return false;
    
return true;
    
}

int main()
{
    DEBUG 
= 0;
    freopen(
"in1.txt","r",stdin);
    
while(scanf("%d %d %d"&n, &m, &num), n+m+num)
    {
        
for(int i = 0; i < n; i ++) scanf("%s", list[i]);
        
char temp[101];
        
//AC自動機 
        init();
        
for(int i = 1; i <= num; i ++)
        {
            scanf(
"%s", temp);
            
int l = strlen(temp);
            insert(temp, i, l);        
        }
        get_fail();
        
//構圖求解 
        if(solve()) puts("Yes");
        
else        puts("No");
    }
    
while(1);
}

posted on 2009-09-10 16:33 superlong 閱讀(215) 評論(0)  編輯 收藏 引用
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            伊人久久大香线蕉av超碰演员| 亚洲女女做受ⅹxx高潮| 日韩系列在线| 亚洲人成绝费网站色www| 一区二区三区无毛| 亚洲第一在线综合网站| 亚洲国产精品悠悠久久琪琪| 一区二区亚洲精品国产| 在线观看亚洲视频啊啊啊啊| 曰韩精品一区二区| 亚洲精品免费观看| 午夜伦理片一区| 久久高清国产| 蜜桃av一区| 亚洲精品视频免费观看| 亚洲性图久久| 久久免费精品视频| 亚洲午夜伦理| 亚洲激情视频网站| 国产欧美69| 一区二区视频欧美| 亚洲精品自在久久| 午夜在线电影亚洲一区| 久久中文在线| 日韩亚洲在线观看| 欧美一区二区视频网站| 欧美成人嫩草网站| 国产精品成人播放| 一区二区在线免费观看| 一区二区三区视频在线播放| 欧美在线综合视频| 亚洲激情在线激情| 宅男精品导航| 免费在线国产精品| 国产女主播一区| 一本久道综合久久精品| 久久久久久亚洲综合影院红桃 | 一区二区三区免费网站| 久久精品国产99| 亚洲人成网站777色婷婷| 欧美在线日韩| 欧美日韩一区二区免费在线观看| 国产亚洲a∨片在线观看| 一本久道久久综合狠狠爱| 久久夜色精品国产欧美乱极品| 99热免费精品在线观看| 久久亚洲精品网站| 国产精品制服诱惑| 欧美成人精品1314www| 在线中文字幕一区| 免费日韩视频| 国产伦精品一区二区三区高清版 | 欧美高清视频在线播放| 亚洲精品一区中文| 久久精品一级爱片| 国产精品综合久久久| 在线视频亚洲欧美| 亚洲国产日韩欧美在线99 | 免费久久99精品国产自| 国产午夜精品一区二区三区欧美| 99re66热这里只有精品4| 久久精品欧美| 久久精品国产精品| 亚洲一二三四久久| 欧美mv日韩mv国产网站| 激情欧美一区二区三区在线观看| 亚洲欧美日韩精品久久奇米色影视| 亚洲国产小视频在线观看| 久久精品一区二区三区四区| 国产日韩欧美综合| 久久成人精品电影| 香蕉久久精品日日躁夜夜躁| 国产精品永久免费观看| 久久精品91久久久久久再现| 亚洲一区二区三区视频| 国产精品美女久久久免费| 亚洲欧美激情视频| 亚洲欧洲av一区二区| 国产午夜精品一区二区三区欧美| 欧美资源在线| 久久国产主播| 亚洲欧洲日本一区二区三区| 亚洲激情校园春色| 欧美日一区二区在线观看 | 亚洲国产成人久久综合| 美女黄色成人网| 亚洲另类视频| 一区二区激情小说| 国产精品视频免费在线观看| 欧美伊人久久| 久久野战av| 99在线|亚洲一区二区| 亚洲一区二区三区在线看| 久久久噜噜噜久久| 亚洲乱码一区二区| 亚洲一区国产| 亚洲国产成人不卡| 99精品视频网| 永久免费毛片在线播放不卡| 亚洲国产精品精华液网站| 欧美日韩国产影片| 亚洲深夜激情| 亚洲女同在线| 亚洲免费网址| 免费视频一区二区三区在线观看| 蜜桃伊人久久| 狠狠色狠狠色综合| 激情综合自拍| 亚洲精品女人| 欧美精品97| 欧美专区亚洲专区| 欧美国产日韩精品| 欧美在线视频一区| 欧美激情日韩| 老司机精品导航| 韩日欧美一区| 99xxxx成人网| 国产一区久久| 一本色道久久综合亚洲精品婷婷 | 欧美v日韩v国产v| 国产精品国产自产拍高清av| 欧美成人高清视频| 国产精品毛片在线| 91久久精品国产| …久久精品99久久香蕉国产| 亚洲欧美国产视频| 国产精品99久久久久久久久 | 亚洲成人中文| 国产一区二区三区自拍| 亚洲视频免费在线观看| 亚洲伦理网站| 欧美精品1区| 欧美激情国产日韩| 樱桃国产成人精品视频| 亚洲一区二区免费在线| 宅男精品视频| 欧美激情亚洲综合一区| 男女精品网站| 在线成人小视频| 亚洲二区免费| 亚洲高清激情| 久久免费的精品国产v∧| 久久久人成影片一区二区三区| 国产精品婷婷| 亚洲欧美激情一区| 久久爱www久久做| 国产一区二区三区四区| 亚洲欧美综合一区| 久久久国产午夜精品| 国产日韩欧美综合| 久久九九电影| 欧美电影专区| 99riav1国产精品视频| 欧美精品国产一区| 亚洲欧洲一区二区三区在线观看| 亚洲美女淫视频| 欧美日韩喷水| 亚洲欧美国产不卡| 久久美女性网| 亚洲国产二区| 欧美日韩免费高清| 亚洲一区二区免费在线| 久久久久久夜| 欧美激情综合色| 日韩性生活视频| 亚洲一区二区三区四区在线观看 | 欧美日本国产一区| 中文久久精品| 久久综合九色综合欧美就去吻| 亚洲国产精品久久久久| 欧美成人四级电影| 亚洲午夜小视频| 久久精品国产亚洲a| 一区二区激情| 国产精品九九| 久久精品72免费观看| 欧美高清不卡在线| 亚洲视频精品| 伊甸园精品99久久久久久| 欧美日韩麻豆| 久久亚洲综合色| 亚洲欧美在线免费| 亚洲国产综合视频在线观看| 香港成人在线视频| 亚洲免费av观看| 激情成人综合| 国产精品手机在线| 欧美电影免费观看大全| 午夜天堂精品久久久久| 亚洲精品一区二区三区99| 久久久水蜜桃av免费网站| 一区二区三区|亚洲午夜| 狠色狠色综合久久| 国产精品高精视频免费| 免费亚洲婷婷| 久久久久久久一区| 亚洲欧美日韩网| 一本大道久久a久久精品综合| 免费日韩精品中文字幕视频在线| 香蕉国产精品偷在线观看不卡|