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

學習心得(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>
            国产一区二区三区四区老人| 欧美日韩一区二区三区在线| 激情欧美一区| 午夜免费日韩视频| 裸体歌舞表演一区二区| 亚洲人成精品久久久久| 欧美日韩视频一区二区| 欧美伦理影院| 国产精品成人免费| 国产日韩精品一区| 牛牛国产精品| 午夜精品区一区二区三| 欧美一级二区| 亚洲欧美三级伦理| 亚洲国产成人不卡| 欧美日本在线| 国产精品高清在线| 国精品一区二区三区| 欧美日韩国产综合视频在线观看| 亚洲自拍偷拍福利| 亚洲美女精品成人在线视频| 久久精品视频va| 亚洲亚洲精品在线观看 | 欧美精品在线免费观看| 国产精品99一区二区| 欧美成人免费在线| 久久人人精品| 新片速递亚洲合集欧美合集| 欧美福利网址| 欧美77777| 欧美国产日韩一区二区在线观看| 欧美精品999| 久久香蕉国产线看观看av| 欧美激情综合| 国产中文一区| 午夜在线不卡| 亚洲精品美女久久久久| 国产精品亚洲片夜色在线| 欧美激情一区二区| 国产美女精品视频| 国产日本精品| 日韩亚洲精品电影| 亚洲国产一区二区精品专区| 狠狠久久婷婷| 亚洲第一页中文字幕| 国产亚洲视频在线观看| 日韩视频一区二区三区在线播放免费观看 | 久久久人人人| 久久九九国产精品| 亚洲女女女同性video| 久久一区二区三区超碰国产精品| 国产精品高潮在线| 99av国产精品欲麻豆| 欧美成人精品不卡视频在线观看| 免费观看亚洲视频大全| 久久久久久97三级| 免费日韩av片| 欧美在线亚洲一区| 久久一二三国产| 国产欧美精品va在线观看| 亚洲一区二区欧美日韩| 亚洲麻豆视频| 欧美日韩精品二区| 亚洲婷婷在线| 久久一区国产| 亚洲大胆视频| 久久艳片www.17c.com| 国内自拍一区| 久久这里只有| 久久综合电影一区| 欧美视频在线一区| 国产日韩在线不卡| 亚洲黄色av| 亚洲国产高清一区二区三区| 欧美freesex8一10精品| 亚洲裸体俱乐部裸体舞表演av| 裸体女人亚洲精品一区| 欧美在线地址| 亚洲第一天堂无码专区| 开心色5月久久精品| 樱桃视频在线观看一区| 一区二区三区毛片| 欧美在线亚洲在线| 亚洲精选成人| 国产精品久久久久99| 欧美在线观看视频| 久久亚洲精选| 中文亚洲免费| 久久国产精品久久久久久电车 | 久久精品系列| 久久久综合网站| 欧美日韩在线观看一区二区三区| 在线一区二区三区四区五区| 亚洲综合另类| 亚洲国产岛国毛片在线| 午夜在线精品偷拍| 久久午夜电影网| 一区二区不卡在线视频 午夜欧美不卡'| 欧美一区网站| 欧美亚洲视频| 亚洲精品免费一二三区| 久久综合一区| 亚洲精品国产精品国自产观看浪潮 | 国产精品电影观看| 久久九九精品| 欧美激情小视频| 久久精品国产一区二区三区| 久久一区二区三区av| 午夜在线成人av| 蜜臀av一级做a爰片久久| 午夜精品电影| 国产精品99久久久久久久vr| 久久久久久亚洲精品不卡4k岛国| 一区二区免费在线播放| 欧美一级欧美一级在线播放| 亚洲视频一二区| 久久手机免费观看| 久久国产福利国产秒拍| 欧美精品在线视频| 美女精品视频一区| 国产精品美女黄网| 亚洲欧美日本日韩| 亚洲理论电影网| 影音先锋国产精品| 欧美一区二区三区精品| 亚洲一区影音先锋| 一区二区三区免费观看| 欧美日韩国产欧美日美国产精品| 久久嫩草精品久久久精品一| 国产精品一区二区你懂得| 国产精品久久久久久久免费软件| 国产精品久久久久久久浪潮网站| 亚洲精品乱码久久久久久蜜桃91| 蜜乳av另类精品一区二区| 久久av一区二区| 国产精品久久久久久久久久尿| 亚洲精品乱码久久久久久日本蜜臀 | 国产精品一二三四| 亚洲人成小说网站色在线| 日韩午夜在线| 久久蜜桃资源一区二区老牛| 亚洲私人影吧| 国产自产在线视频一区| 亚洲一区自拍| 亚洲高清在线精品| 久久人91精品久久久久久不卡 | 久久午夜电影| 欧美伊人久久大香线蕉综合69| 欧美sm视频| 麻豆久久婷婷| 欧美大尺度在线| 欧美xx视频| 亚洲黑丝在线| 欧美日韩国产综合网| 99视频在线观看一区三区| 久久精品国产v日韩v亚洲| 久久人人爽人人爽| 欧美gay视频激情| 亚洲伦理自拍| 久久精品青青大伊人av| 欧美福利电影网| 一本大道久久a久久综合婷婷| 欧美日韩亚洲视频一区| 亚洲在线播放电影| 性久久久久久久久久久久| 国产一区再线| 蜜桃av一区二区在线观看| 日韩午夜三级在线| 国产日韩精品一区二区三区| 久久久久久电影| 9l国产精品久久久久麻豆| 国产亚洲精品福利| 欧美**人妖| 亚洲一区二区三区欧美| 欧美成人69av| 性伦欧美刺激片在线观看| 亚洲日本成人在线观看| 亚洲深爱激情| 国产欧美一区二区精品性色| 免费国产一区二区| 亚洲在线视频观看| 欧美激情在线观看| 国户精品久久久久久久久久久不卡 | 欧美另类专区| 欧美伊人精品成人久久综合97 | 久久精品亚洲精品| 99热在线精品观看| 在线免费观看日韩欧美| 国产精品入口| 亚洲激情啪啪| 亚洲高清影视| 女人香蕉久久**毛片精品| 亚洲一区三区电影在线观看| 91久久精品一区二区别| 老牛国产精品一区的观看方式| 亚洲免费视频网站| 一本大道av伊人久久综合| 亚洲黑丝在线| 亚洲国产成人精品女人久久久 | 亚洲网友自拍|