NOIP2018提高组金牌训练营——搜索专题
1416 两点
福克斯在玩一款手机解迷游戏，这个游戏叫做”两点”。基础级别的时候是在一个n×m单元上玩的。像这样：
每一个单元有包含一个有色点。我们将用不同的大写字母来表示不同的颜色。
这个游戏的关键是要找出一个包含同一颜色的环。看上图中4个蓝点，形成了一个环。一般的，我们将一个序列 d,d,...,d 看成一个环，当且仅当它符合下列条件时：
1. 这k个点不一样，即当 i≠j时， d 和 d不同。
2. k至少是4。
3. 所有的点是同一种颜色。
4. 对于所有的 1≤i≤k-1: d 和 d 是相邻的。还有 d 和 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 ;
}