DQS DQS

HIT Summer Training Day2 搜索

in 算法,搜索,模拟赛read (229) 文章转载请注明来源!

17题的五个小时的单刷ACM好累啊…


A : hoj - 1797

迷宫。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 200;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

char mp[SZ][SZ];
int n,m;

struct haha
{
    int x,y;
};

queue<haha> q;
bool vis[SZ][SZ];

int bfs(int x,int y)
{
    memset(vis,0,sizeof(vis));
    q.push((haha){x,y});
    vis[x][y] = 1;
//    printf("%d %d\n",x,y);
    while(q.size())
    {
        haha u = q.front(); q.pop();
        for(int i = 0;i < 4;i ++)
        {
            int x = u.x + dx[i];
            int y = u.y + dy[i];
            if(x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && mp[x][y] == '.')
            {
                vis[x][y] = 1;
                q.push((haha){x,y});
            }
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            if(vis[i][j]) ans ++;
    return ans;
}

int main()
{
    while(scanf("%d%d",&m,&n) && n)
    {
        getchar();
        for(int i = 1;i <= n;i ++)
            scanf("%s",mp[i] + 1);
        int sx,sy;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                if(mp[i][j] == '@')
                    {sx = i,sy = j; break;}
        printf("%d\n",bfs(sx,sy));
    }

    return 0;
}


B : poj - 3984

还是迷宫。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 20;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int mp[SZ][SZ],n = 5,m = 5;

struct haha
{
    int x,y;
    void print() { printf("(%d, %d)\n",x - 1,y - 1); }
}pre[SZ][SZ],ans[50];

queue<haha> q;
bool vis[SZ][SZ];

int bfs(int x,int y)
{
    q.push((haha){x,y});
    vis[x][y] = 1;
    while(q.size())
    {
        haha u = q.front(); q.pop();
        for(int i = 0;i < 4;i ++)
        {
            int x = u.x + dx[i];
            int y = u.y + dy[i];
            if(x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && !mp[x][y])
            {
                vis[x][y] = 1;
                pre[x][y] = u;
                q.push((haha){x,y});
            }
        }
    }
    int ex = n,ey = m,t = 1;
    while(ex != x || ey != y)
    {
        ans[t ++] = (haha){ex,ey};
        int xx = ex,yy = ey;
        ex = pre[xx][yy].x; ey = pre[xx][yy].y;
    }
    ans[t] = (haha){x,y};
    for(int i = t;i >= 1;i --)
        ans[i].print();
}

int main()
{
    for(int i = 1;i <= 5;i ++)
        for(int j = 1;j <= 5;j ++)
            scanf("%d",&mp[i][j]);
    bfs(1,1);
    return 0;
}


C : hoj - 3237

这个好像是权限题…

题意是在一个n*m的地图上有空地、墙、加油站(不止一个),初始有油L,每走一步消耗一格,为0就不能走了,在加油站可以把油加满到L。问从左上角走到右下角能否走到。

注意加油站不止一个。

对于判重,若走到这个点并且油量比之前走过这个点时油量要多,则可以拓展。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 200;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int n,m,L;
char mp[SZ][SZ];
int vis[SZ][SZ];


bool dfs(int sx,int sy,int rst)
{
    if(sx == n && sy == m) return true;
    if(rst <= 0) return false;
    if(rst <= vis[sx][sy]) return false;
    vis[sx][sy] = rst;
    for(int i = 0;i < 4;i ++)
    {
        int x = sx + dx[i];
        int y = sy + dy[i];
        if(x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] != '#')
        {
            if(mp[x][y] == '+')
                if(dfs(x,y,L))
                    return true;
            if(mp[x][y] == '.')
                if(dfs(x,y,rst - 1))
                    return true;
        }
    }
    return false;
}

int main()
{
//    freopen("233.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while(T --)
    {
        memset(vis,0,sizeof(vis));
        scanf("%d%d%d",&n,&m,&L);
        getchar();
        for(int i = 1;i <= n;i ++)
            scanf("%s",mp[i] + 1);
        if(dfs(1,1,L)) puts("Yes");
        else puts("No");
        /*for(int i = 1;i <= n;i ++,puts(""))
            for(int j = 1;j <= m;j ++)
                printf("%d ",vis[i][j]);*/
    }

    return 0;
}


D : gym - 100952E

在n*m上放置k个人,需要满足p个形如“a不能和b相邻”的条件。问总放置方案数。

因为答案不超过900w,暴力即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 510;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int a[SZ];
int n,m,k,p,ans;
bool can[SZ][SZ];
int mp[SZ][SZ];

bool ok(int sx,int sy,int a)
{
    for(int i = 0;i < 4;i ++)
    {
        int x = sx + dx[i];
        int y = sy + dy[i];
        if(x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y])
        {
            int b = mp[x][y];
            if(can[a][b]) return false;
        }
    }
    return true;
}

void dfs(int x,int y,int now)
{
    if(y == m + 1) x ++,y = 1;
    if(x == n + 1)
    {
        if(now == (1 << k + 1) - 2)
        {
            ans ++;
        /*    for(int i = 1;i <= n;i ++,puts(""))
                for(int j = 1;j <= m;j ++)
                    printf("%d ",mp[i][j]);
                    puts("");*/
        }
        return ;
    }
    for(int i = 1;i <= k;i ++)
    {
        if(!(1 << i & now) && ok(x,y,i))
        {
            mp[x][y] = i;
            dfs(x,y + 1,now | (1 << i));
            mp[x][y] = 0;
        }
    }
    dfs(x,y + 1,now);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        ans = 0;
        memset(can,0,sizeof(can));
        scanf("%d%d%d%d",&n,&m,&k,&p);
        for(int i = 1;i <= p;i ++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            can[x][y] = can[y][x] = 1;
        }
        dfs(1,1,0);
        if(ans == 0) puts("impossible");
        else printf("%d\n",ans);
    }
    return 0;
}


E : codeforces - 377A

在n*m的地图上有墙和空地,初始时空地形成一个联通块,求一种将k个空地变为墙并且使联通块数量还为1的方案。

直接做就WA到死(such as me)。因为太不好处理了。

可以考虑在联通块内搜empty_num - k个点,剩下的全部填成墙。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 510;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int a[SZ][SZ];
bool vis[SZ][SZ];
int n,m,k;
char mp[SZ][SZ];
int sum = 0,t = 0;

int dfs(int sx,int sy)
{
    vis[sx][sy] = 1;
    if(++ t == sum)
        return true;
    for(int i = 0;i < 4;i ++)
    {
        int x = sx + dx[i];
        int y = sy + dy[i];
        if(x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && mp[x][y] == '.')
            if(dfs(x,y)) return true;
    }
    return false;
}

void work()
{
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            if(mp[i][j] == '.')
                sum ++;
    sum -= k;
    int flag = 1;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            if(mp[i][j] == '.' && flag)
                dfs(i,j),flag = 0;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            if(mp[i][j] == '.' && !vis[i][j])
                mp[i][j] = 'X';
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    getchar();
    for(int i = 1;i <= n;i ++)
        scanf("%s",mp[i] + 1);
    work();
    for(int i = 1;i <= n;i ++,puts(""))
        for(int j = 1;j <= m;j ++)
            printf("%c",mp[i][j]);
    return 0;
}


F : hoj - 1448

三维迷宫。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 200;
const int dx[] = {0,1,0,-1,0,0};
const int dy[] = {1,0,-1,0,0,0};
const int dz[] = {0,0,0,0,1,-1};

char mp[SZ][SZ][SZ];
int n,m,z;

struct haha
{
    int x,y,z,s;
};

queue<haha> q;
bool vis[SZ][SZ][SZ];

int bfs(int sx,int sy,int sz,int ex,int ey,int ez)
{
    while(q.size()) q.pop();
    memset(vis,0,sizeof(vis));
    q.push((haha){sx,sy,sz,0});
    vis[sx][sy][sz] = 1;
//    printf("%d %d\n",x,y);
    while(q.size())
    {
        haha u = q.front(); q.pop();
        if(u.x == ex && u.y == ey && u.z == ez)
            return u.s;
        for(int i = 0;i < 6;i ++)
        {
            int x = u.x + dx[i];
            int y = u.y + dy[i];
            int z = u.z + dz[i];
            if(x >= 1 && x <= n && y >= 1 && y <= m && z >= 1 && z <= ::z && !vis[x][y][z] && mp[x][y][z] != '#')
            {
                vis[x][y][z] = 1;
                q.push((haha){x,y,z,u.s + 1});
            }
        }
    }
    return -1;
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&z) && n)
    {
        getchar();
        for(int i = 1;i <= n;i ++,getchar())
            for(int j = 1;j <= m;j ++)
                scanf("%s",mp[i][j] + 1);
        int sx,sy,sz,ex,ey,ez;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                for(int k = 1;k <= z;k ++)
                    if(mp[i][j][k] == 'S')
                        sx = i,sy = j,sz = k;
                    else if(mp[i][j][k] == 'E')
                        ex = i,ey = j,ez = k;
        int ans = bfs(sx,sy,sz,ex,ey,ez);
        if(ans == -1) puts("Trapped!");
        else printf("Escaped in %d minute(s).\n",ans);
    }

    return 0;
}


G : hoj - 2120

给一个有向图判断是不是有向树。

注意判断树为空时也是树。

垃圾题,本来挺简单可是用各种方法恶心你。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int SZ = 1000010;

int n,m;
int head[SZ],nxt[SZ],to[SZ],tot = 1,rd[SZ];

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

bool vis[SZ];

bool dfs(int u)
{
    if(vis[u]) return false;
    vis[u] = 1;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!dfs(v)) return false;
    }
    return true;
}

bool check()
{
    if(n == 0 && m == 0) return true;
    if(n == 1 || m != n - 1) return false;
    int rt;
    for(int i = 1,flag = 0;i <= n;i ++)
        if(!rd[i])
        {
            if(!flag) flag = 1,rt = i;
            else return false;
        }
    for(int i = 1;i <= n;i ++)
        if(i != rt && rd[i] != 1)
            return false;
    if(!dfs(rt)) return false;
    for(int i = 1;i <= n;i ++)
        if(!vis[i])
            return false;
    return true;
}

int lsh[SZ];

void init()
{
    memset(head,0,sizeof(head));
    tot = 1;
    memset(vis,0,sizeof(vis));
    m = 0;
    memset(lsh,0,sizeof(lsh));
    memset(rd,0,sizeof(rd));
}

int ipx[SZ],ipy[SZ];

int main()
{
    int flag = 0,T = 1;
    while(233)
    {
        init();
        int x,y;
        while(scanf("%d%d",&x,&y) && x)
        {
            if(x < 0) { flag = 1; break; }
            m ++;
            ipx[m] = x,ipy[m] = y;
            lsh[++ lsh[0]] = x;
            lsh[++ lsh[0]] = y;
        }
        if(flag) break;
        sort(lsh + 1,lsh + 1 + lsh[0]);
        n = unique(lsh + 1,lsh + 1 + lsh[0]) - lsh - 1;
        for(int i = 1;i <= m;i ++)
        {
            ipx[i] = lower_bound(lsh + 1,lsh + 1 + n,ipx[i]) - lsh;
            ipy[i] = lower_bound(lsh + 1,lsh + 1 + n,ipy[i]) - lsh;
            build(ipx[i],ipy[i]); rd[ipy[i]] ++;
        }
        //cout << n << " " << m << endl;
        if(check())
            printf("Case %d is a tree.\n",T ++);
        else
            printf("Case %d is not a tree.\n",T ++);
    }
    return 0;
}


H : poj1011

这个题写了好多遍了…………

注意答案一定在最大值maxn和长度之和sum之间,且一定是sum的一个约数。

枚举答案验证。

剪枝:

1.优先选长的匹配,因为短的更灵活。

2.一个木棍只和比他短的匹配即可,因为长的已经和它匹配过了。

3.如果一个木棍作为第一根木棍失配,那么这个答案一定是错误的,不需要继续验证。因为这根木棍永远不会被再次利用。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 510;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int a[SZ];
int n;
bool use[SZ];

bool dfs(int len,int now,int cnt,int pos)
{
    if(cnt == 0) return true;

    for(int i = pos;i >= 1;i --)
    {
        if(!use[i] && now + a[i] <= len)
        {
            use[i] = 1;
            if(now + a[i] != len)
            {
                if(dfs(len,now + a[i],cnt,i - 1))
                    return true;
                use[i] = 0;
                if(now == 0) return false;
            }
            else
            {
                if(dfs(len,0,cnt - 1,n))
                    return true;
                use[i] = 0;
                return false;
            }
        }
    }
    return false;
}

int main()
{
    while(scanf("%d",&n) && n)
    {
        memset(use,0,sizeof(use));
        int sum = 0,maxn = 0;
        for(int i = 1;i <= n;i ++)
            scanf("%d",&a[i]),sum += a[i],maxn = max(maxn,a[i]);
        sort(a + 1,a + 1 + n);
        int ans = 0;
        for(int len = maxn;len <= sum;len ++)
        {
            memset(use,0,sizeof(use));
            if(sum % len == 0)
            {
                if(dfs(len,0,sum / len,n))
                    { ans = len; break;}
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}


I : LYDSY - 2570


J : poj - 1077

裸的八数码。两年多没写了竟然还1A…

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;

typedef long long LL;

const int SZ = 1000010;
const int INF = 1000000010;
const int mod = 1e9+7;
const int calc[20][3] = {{3,3},{1,1},{1,2},{1,3},{2,1},{2,2},{2,3},{3,1},{3,2},{3,3}};
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
const char opt[] = {'r','d','l','u'};

struct sta
{
    int mp[5][5],f,h,step;
    char path[30];
    void get_hash()
    {
        int ans = 0;
        for(int i = 1;i <= 3;i ++)
            for(int j = 1;j <= 3;j ++)
                ans = ((LL)ans * 10 + mp[i][j]) % mod;
        h = ans;
    }
    void get_f()
    {
        int ans = 0;
        for(int i = 1;i <= 3;i ++)
            for(int j = 1;j <= 3;j ++)
            {
                int d = mp[i][j];
                ans += abs(calc[d][0] - i) + abs(calc[d][1] - j);
            }
        f = ans + step;
    }

    void print()
    {
        for(int i = 1;i <= 3;i ++,puts(""))
            for(int j = 1;j <= 3;j ++)
                printf("%d ",mp[i][j]);
    }

}s,e;

bool operator <(sta a,sta b)
{
    return a.f > b.f;
}

map<int,bool> h;
priority_queue<sta> q;

void bfs(sta s)
{
    h[s.h] = 1;
    q.push(s);
    while(q.size())
    {
        sta u = q.top(); q.pop();
        int sx,sy;
        bool flag = 0;
        for(int i = 1;i <= 3;i ++)
            for(int j = 1;j <= 3;j ++)
            {
                if(u.mp[i][j] == 0)
                    sx = i,sy = j;
                if(u.mp[i][j] != e.mp[i][j])
                    flag = 1;
            }
        if(!flag)
        {
            for(int i = 1;i <= u.step;i ++)
                printf("%c",u.path[i]);
            return ;
        }
        for(int i = 0;i < 4;i ++)
        {
            int x = sx + dx[i];
            int y = sy + dy[i];
            if(x >= 1 && x <= 3 && y >= 1 && y <= 3)
            {
                sta v = u;
                swap(v.mp[x][y],v.mp[sx][sy]);
                v.path[++ v.step] = opt[i];
                v.get_hash(); v.get_f();
                if(h[v.h]) continue;
                h[v.h] = 1;
                q.push(v);
            }
        }
    }
    puts("unsolvable");
}

int main()
{
    e.mp[1][1] = 1;e.mp[1][2] = 2;e.mp[1][3] = 3;
    e.mp[2][1] = 4;e.mp[2][2] = 5;e.mp[2][3] = 6;
    e.mp[3][1] = 7;e.mp[3][2] = 8;e.mp[3][3] = 0;
    for(int i = 1;i <= 9;i ++)
    {
        char c[2];
        scanf("%s",c);
        int x;
        if(c[0] == 'x') x = 0;
        else x = c[0] - '0';
        s.mp[(i - 1) / 3 + 1][(i - 1) % 3 + 1] = x;
    }
    s.get_hash(); s.get_f();
    bfs(s);
    return 0;
}


K : poj - 1088

滑雪。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 510;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int a[SZ][SZ],dp[SZ][SZ];
int n,m,k;

int dfs(int sx,int sy)
{
    if(dp[sx][sy]) return dp[sx][sy];
    int ans = 1;
    for(int i = 0;i < 4;i ++)
    {
        int x = sx + dx[i];
        int y = sy + dy[i];
        if(x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] < a[sx][sy])
            ans = max(ans,dfs(x,y) + 1);
    }
    return dp[sx][sy] = ans;
}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            scanf("%d",&a[i][j]);
    int ans = 0;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            ans = max(ans,dfs(i,j));
    printf("%d\n",ans);
    return 0;
}


L : hoj - 1053


M : hoj - 1442


N : hoj - 1030

给一张地图,问空地与空地的最长路是多少。

和树上最长路一样,两遍bfs。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int SZ = 2010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

char mp[SZ][SZ];
int n,m;

struct haha
{
    int x,y,step;
};

queue<haha> q;
bool vis[SZ][SZ];

haha bfs(int x,int y)
{
    while(q.size()) q.pop();
    memset(vis,0,sizeof(vis));
    q.push((haha){x,y,0});
    vis[x][y] = 1;
    int maxn = -1;
    haha ans;
    while(q.size())
    {
        haha u = q.front(); q.pop();
        if(u.step > maxn) maxn = u.step,ans = u;
        for(int i = 0;i < 4;i ++)
        {
            int x = u.x + dx[i];
            int y = u.y + dy[i];
            if(x >= 1 && x <= n && y >= 1 && y <= m && !vis[x][y] && mp[x][y] == '.')
            {
                vis[x][y] = 1;
                q.push((haha){x,y,u.step + 1});
            }
        }
    }
    return ans;
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        scanf("%d%d",&m,&n);
        getchar();
        for(int i = 1;i <= n;i ++)
            scanf("%s",mp[i] + 1);
        int sx,sy,flag = 0;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                if(mp[i][j] == '.' && !flag)
                    sx = i,sy = j,flag = 1;
        haha e = bfs(sx,sy);
        haha ans = bfs(e.x,e.y);
        printf("Maximum rope length is %d.\n",ans.step);
    }

    return 0;
}


O : codeforces - 653E

规定根节点点1度数必须为k,之后给若干形如"u和v之间不会有边"的条件,问是否满足这n个点形成一棵树满足所有条件。


P : codeforces - 677D

问从左上角开始顺次经过1~p所有数字的最短路。


Q : codeforces - 776D

原题是门,我还是按灯来叙述吧…

给n个灯和m个开关,每个开关可能控制多个灯,每个灯有且仅有被两个开关控制。给定灯的开关的初始状态,问能否通过调节开关使所有灯全被打开,

注意到一个灯只会被两个开关控制。

如果这个灯是关着的,那么必须从中选一个。

如果这个灯是开着的,那么要么都选,要么都不选。

于是我们可以把控制每个灯的两个开关连边,那么就是图染色问题。

如果这个灯是关着的,那么这两个点的颜色是不同的。

否则,这两个点的颜色是相同的。

dfs一遍即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int SZ = 1000010;

int n,m;
vector<int> swi[SZ];
int head[SZ],nxt[SZ],to[SZ],cost[SZ],tot = 1;

void build(int f,int t,int v)
{
    to[++ tot] = t;
    cost[tot] = v;
    nxt[tot] = head[f];
    head[f] = tot;
}

int color[SZ],a[SZ];

bool dfs(int u,int c)
{
    color[u] = c;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i],d = cost[i],x;
        if(d == 0) x = c ^ 1;
        else x = c;
        if(color[v] == -1)
            { if(!dfs(v,x)) return false; }
        else if(color[v] != x)
            return false;
    }
    return true;
}

bool check()
{
    memset(color,-1,sizeof(color));
    for(int i = 1;i <= m;i ++)
        if(color[i] == -1)
            if(!dfs(i,0))
                return false;
    return true;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&a[i]);
    for(int i = 1;i <= m;i ++)
    {
        int k;
        scanf("%d",&k);
        for(int j = 1;j <= k;j ++)
        {
            int x;
            scanf("%d",&x);
            swi[x].push_back(i);
        }
    }
    for(int i = 1;i <= n;i ++)
    {
        build(swi[i][0],swi[i][1],a[i]);
        build(swi[i][1],swi[i][0],a[i]);
    }
    if(check()) puts("YES");
    else puts("NO");
    //for(int i = 1;i <= n;i ++)
    //    cout << color[i] << " "; puts("");
    return 0;
}

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

算法搜索模拟赛
最后由DQS修改于2017-08-06 02:42
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆