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

學(xué)習(xí)心得(code)

superlong@CoreCoder

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

公告

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

常用鏈接

留言簿(4)

我參與的團(tuán)隊

搜索

  •  

最新隨筆

最新評論

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

//判兩點在線段同側(cè),點在線段上返回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));
    
//線段相交構(gòu)圖 
    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();
        
//構(gòu)圖求解 
        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>
            久久久久久久性| 亚洲欧洲偷拍精品| 国产欧美69| 日韩亚洲在线观看| 欧美成人中文字幕在线| 亚洲视频图片小说| 欧美日韩亚洲精品内裤| 亚洲欧洲一级| 亚洲区欧美区| 久久琪琪电影院| 在线观看91精品国产麻豆| 久久久久一区| 久久国产精品亚洲77777| 国产网站欧美日韩免费精品在线观看 | 欧美日韩在线精品| 亚洲国产精品久久精品怡红院| 久久九九精品99国产精品| 亚洲欧美日本国产专区一区| 欧美系列亚洲系列| 欧美一级理论片| 欧美亚洲视频| 1769国产精品| 亚洲精品在线电影| 亚洲自拍偷拍视频| 亚洲在线不卡| 久久视频在线看| 亚洲免费小视频| 国产毛片精品国产一区二区三区| 在线视频日韩精品| 99成人在线| 欧美另类在线播放| 亚洲午夜免费视频| 亚洲一区三区电影在线观看| 国产精品日韩欧美大师| 久久久久久久999| 免费观看一区| 欧美视频1区| 欧美日韩在线影院| 亚洲精品免费看| 玖玖精品视频| 亚洲一区二区在线视频| 日韩一级欧洲| 久久久国产视频91| 一本色道久久精品| 欧美大片免费观看| 在线精品福利| 久久久久在线观看| 午夜在线成人av| 欧美色精品天天在线观看视频| 91久久综合| 欧美国产一区在线| 久久久亚洲欧洲日产国码αv| 国产精品视频| 亚洲摸下面视频| 亚洲一区二区精品| 欧美视频在线免费| 亚洲自拍都市欧美小说| 在线亚洲欧美视频| 欧美视频一区二区三区四区| 99精品福利视频| 亚洲精品一区中文| 欧美日韩在线播放三区| 一本色道久久| 9久re热视频在线精品| 欧美日韩日本国产亚洲在线 | 亚洲视频免费| 国产精品多人| 欧美一区视频| 欧美在线视频日韩| 亚洲福利专区| 亚洲剧情一区二区| 欧美体内she精视频| 母乳一区在线观看| 亚洲精选在线| 亚洲一区在线免费观看| 老牛影视一区二区三区| 老司机午夜免费精品视频| 久久riav二区三区| 国产精品欧美激情| 国产精品视频一二| 免费av成人在线| 欧美人成网站| 久久精品一区二区三区四区| 毛片精品免费在线观看| 亚洲天堂激情| 久久不射中文字幕| 亚洲精品一区二区网址 | 91久久久国产精品| 欧美另类一区二区三区| 久久av一区二区三区漫画| 久久久精品动漫| 亚洲视频在线观看网站| 欧美一区1区三区3区公司| 亚洲国产高清自拍| 一区二区三区欧美视频| 亚洲成人原创| 亚洲一区二区在线免费观看| 亚洲国产99| 亚洲欧美日产图| 日韩网站免费观看| 久久av资源网| 国产精品99久久久久久宅男| 久久精品盗摄| 亚洲欧美在线免费观看| 免费在线观看精品| 欧美一区二区三区久久精品茉莉花| 老色批av在线精品| 欧美在线影院| 欧美性猛交99久久久久99按摩| 久久综合九色综合欧美狠狠| 欧美日韩国产一区二区| 免费不卡在线观看av| 国产精品超碰97尤物18| 欧美成人一区在线| 国产一区二区三区久久久| 日韩午夜在线观看视频| 亚洲国产精品热久久| 欧美一级淫片播放口| 亚洲在线黄色| 欧美午夜电影一区| 日韩一区二区高清| 一区二区三区成人| 欧美精品免费视频| 欧美福利网址| 在线观看亚洲精品| 久久久国产精品一区二区中文| 午夜亚洲性色福利视频| 欧美三级乱码| 一二美女精品欧洲| 在线视频日韩精品| 欧美肉体xxxx裸体137大胆| 亚洲激情第一区| 亚洲精品一级| 欧美人与性动交cc0o| 欧美日韩一区二区高清| 欧美黄色影院| 亚洲激情女人| 免费一级欧美在线大片| 欧美日韩精品免费观看视频完整| 午夜精品久久久久久99热软件| 亚洲国产精品第一区二区| 欧美一级一区| 一区二区三区四区五区在线| 国内一区二区三区在线视频| 欧美日韩免费观看一区二区三区 | 国产农村妇女精品| 免费观看久久久4p| 欧美一区二区成人6969| avtt综合网| 欧美激情一区二区三区四区| 欧美在线亚洲一区| 亚洲已满18点击进入久久| 最新亚洲激情| 亚洲福利在线视频| 久久先锋影音| 久久久久国产精品人| 亚洲成人在线视频网站| 欧美国产第一页| 亚洲视频香蕉人妖| 久久久久久一区| 99ri日韩精品视频| 国产欧美91| 欧美激情第三页| 亚洲欧美日韩国产中文在线| 狼人天天伊人久久| 99热这里只有精品8| 国产啪精品视频| 你懂的国产精品永久在线| 亚洲午夜在线视频| 欧美福利电影网| 性刺激综合网| 亚洲激情另类| 国产嫩草一区二区三区在线观看 | 国产精品多人| 麻豆成人综合网| 亚洲视频一区在线观看| 欧美肥婆bbw| 久久久久中文| 亚洲欧美日韩专区| 亚洲欧洲一级| 亚洲第一页在线| 国产欧美日韩精品专区| 欧美黑人一区二区三区| 久久成人免费电影| 一区二区日韩精品| 亚洲福利专区| 久久久综合激的五月天| 亚洲免费视频网站| 亚洲精选中文字幕| 在线观看视频亚洲| 国产一区在线播放| 国产精品视频网址| 欧美午夜在线| 欧美日韩免费一区二区三区视频 | 99在线热播精品免费| 蜜桃精品一区二区三区| 久久精品中文字幕一区| 午夜国产精品视频| 美女精品在线| 亚洲视频高清|