NOIP2018提高组金牌训练营——搜索专题

1416 两点

福克斯在玩一款手机解迷游戏，这个游戏叫做”两点”。基础级别的时候是在一个n×m单元上玩的。像这样：

每一个单元有包含一个有色点。我们将用不同的大写字母来表示不同的颜色。

这个游戏的关键是要找出一个包含同一颜色的环。看上图中4个蓝点，形成了一个环。一般的，我们将一个序列 d₁,d₂,...,d_k 看成一个环，当且仅当它符合下列条件时：

1.    这k个点不一样，即当 i≠j时， d_i 和 d_j不同。

2.    k至少是4。

3.    所有的点是同一种颜色。

4.    对于所有的 1≤i≤k-1: d_i 和 d_i+1 是相邻的。还有 d_k 和 d₁ 也应该相邻。单元 x 和单元 y 是相邻的当且仅当他们有公共边。

当给出一幅格点时，请确定里面是否有环。

Input

单组测试数据。

第一行包含两个整数n和m (2≤n,m≤50):板子的行和列。

接下来n行，每行包含一个有m个字母的串，表示当前行每一个点的颜色。每一个字母都是大写字母。

Output

如果有环输出Yes，否则输出No。

Input示例

3 4

AAAA

ABCA

AAAA

3 4

AAAA

ABCA

AADA

Output示例

Yes

No

---

复习了一下判环的问题
如果是有向图，就用拓扑排序
如果是无向图。如果访问到了已经访问过的点，且这个节点非前驱结点，那就有环

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int MAXN =  + ;

struct Edge{ int to, next; };

int dir[][] = {, , , -, , , -, };

char s[MAXN][MAXN];

int vis[MAXN][MAXN], n, m; 

bool dfs(int x, int y, int px, int py)

{

    vis[x][y] = ;

    REP(i, , )

    {

        int xx = x + dir[i][], yy = y + dir[i][];

        if(!( <= xx && x <= n &&  <= y && y <= m) || s[x][y] != s[xx][yy]) continue;

        if(xx == px && yy == py) continue;

        if(vis[xx][yy] || !dfs(xx, yy, x, y)) return false;

    }

    return true;

}

int main()

{

    while(~scanf("%d%d", &n, &m))

    {

        _for(i, , n) scanf("%s", s[i] + );

        bool ok = false;

        _for(i, , n)

        {

            _for(j, , m)

                if(!vis[i][j] && !dfs(i, j, -, -))

                {

                    ok = true;

                    break;

                }

            if(ok) break;

        }

        printf("%s\n", ok ? "Yes" : "No");

    }

    return ;

}

1267 4个数和为0

给出N个整数，你来判断一下是否能够选出4个数，他们的和为0，可以则输出"Yes"，否则输出"No"。

Input

第1行，1个数N，N为数组的长度(4 <= N <= 1000)

第2 - N + 1行：A[i]（-10^9 <= A[i] <= 10^9)

Output

如果可以选出4个数，使得他们的和为0，则输出"Yes"，否则输出"No"。

Input示例

5

-1

1

-5

2

4

Output示例

Yes

---

用中途相遇法
四个数分成两个数的和

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 1e3 + ;

struct node

{

    int k1, k2, w;

    bool operator < (const node& rhs) const

    {

        return w < rhs.w;

    }

};

vector<node> v;

int a[MAXN], n;

inline bool judge(int i, int j)

{

    return v[i].k1 != v[j].k1 && v[i].k1 != v[j].k2 && v[i].k2 != v[j].k1 && v[i].k2 != v[j].k2;

} 

int main()

{

    scanf("%d", &n);

    _for(i, , n) scanf("%d", &a[i]);

    _for(i, , n)

        _for(j, i + , n)

            v.push_back(node{i, j, a[i] + a[j]});

    sort(v.begin(), v.end());

    int l = , r = v.size() - , ok = ;

    while(l < r)

    {

        if(v[l].w > ) break;

        if(v[l].w + v[r].w ==  && judge(l, r))

        {

            ok = ;

            puts("Yes");

            break;

        }

        if(abs(v[l].w) > abs(v[r].w)) l++;

        else r--;

    }

    if(!ok) puts("No");

    return ;

} 

之前写过一道类似的题
https://vjudge.net/problem/UVA-1152这里练习了哈希表

#include<cstdio>

#include<vector>

#include<cmath>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int Hash_size = 1e5 + ;

const int MAXN = 4e3 + ;

int a[][MAXN], n;

vector<int> v[Hash_size];

inline int Hash(int a, int b) { return abs(a + b) % Hash_size; }

int main()

{

    int T, kase = ;

    scanf("%d", &T);

    while(T--)

    {

        if(kase) puts(""); kase = ;

        REP(i, , Hash_size) v[i].clear();

        scanf("%d", &n);

        _for(i, , n)

            _for(j, , )

                scanf("%d", &a[j][i]);

        _for(i, , n)

            _for(j, , n)

                v[Hash(a[][i], a[][j])].push_back(a[][i] + a[][j]);

        int ans = ;

        _for(i, , n)

            _for(j, , n)

            {

                int key = -(a[][i] + a[][j]), id = Hash(a[][i], a[][j]);

                REP(i, , v[id].size())

                    if(v[id][i] == key)

                        ans++;

            }

        printf("%d\n", ans);

    }

    return ;

} 

NOIP2018提高组金牌训练营——搜索专题的相关教程结束。