位运算——异或运算

大家好，欢迎来到IT知识分享网。

按位异或运算(^)

了解异或运算的用法，我们来看看异或运算在算法题中的应用。

异或运算的应用

镜子田地

题目描述

农夫约翰在屋子外面放了一些旧镜子，他的奶牛们像往常一样调皮地偷走了它们！

奶牛们将镜子放置在了一个矩形田地中，该田地可被划分为$N\times M$个方格区域。

在每个方格区域中，奶牛在其某对对角之间放置一个双面镜，因此，共有两种放法，一种为/放置（镜子连接方格左下角和右上角），另一种为\放置（镜子连接方格左上角和右下角）。

一天晚上，奶牛贝茜将激光发射器带到了该田地中。

她站在田地外面，沿着田地的行或列水平或垂直照射光束，使光束反射一定数量的镜子。

由于镜子都是沿对角线摆放，因此经反射镜反射的水平光束最终将垂直传播，反之亦然。

贝茜想知道从田地之外射入的水平或垂直光束最多可以在田地中被反射多少次。

给定镜子田地的布局，请帮助贝茜计算这个数字。

输入格式

第一行包含$N$和$M$。

接下来$N$行，每行包含$M$个/或\字符，表示田地中镜子的具体摆放方式。

输出格式

输出田地之外的水平或垂直光束能够被反射的最大次数。

如果可以无限反射，则输出 −1。

数据范围
$1\le N,M\le 1000$
输入样例：

3 3 /\\ \\\ /\/ 

输出样例：

3 

样例解释

贝茜可以从上向下沿中间列上方发射激光。

共可以反射 3 次。

题目分析

代码如下

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int N = 1010; int n, m; char g[N][N]; int dx[4] = { 
     -1, 0, 1, 0}, dy[4] = { 
     0, 1, 0, -1}; int dfs(int x, int y, int d) { 
      if (x < 0 || x > n - 1 || y < 0 || y > m - 1) return 0; if (g[x][y] == '/') d ^= 1; else d ^= 3; return dfs(x + dx[d], y + dy[d], d) + 1; } int main() { 
      cin >> n >> m; for (int i = 0; i < n; i ++) cin >> g[i]; int res = 0; for (int i = 0; i < n; i ++) { 
      res = max(res, dfs(i, 0, 1)); res = max(res, dfs(i, m - 1, 3)); } for (int i = 0; i < m; i ++) { 
      res = max(res, dfs(0, i, 2)); res = max(res, dfs(n - 1, i, 0)); } cout << res << endl; return 0; } 

镜子

题目描述

输入格式

第一行包含三个整数$N,a,b$。
接下来$N$行，其中第$i$行描述第$i$号围栏的位置和朝向。首先包含两个整数$x_i,y_i$表示其中心点位置，然后包含一个字符/或\表示围栏朝向。
围栏编号从$1$开始。

输出格式

输出第一个能够通过改变其朝向使得约翰成功看到点$(a,b)$的围栏的顺序编号。
如果约翰不需要切换任何围栏的朝向就已经可以看到点$(a,b)$则输出$0$。
如果约翰无法通过切换单个围栏的朝向使自己看到点$(a,b)$则输出$-1$。

数据范围
$1\le N\le 200$,
$-106\le x_i,y_i,a,b\le 106$

输入样例：

5 6 2 3 0 / 0 2 / 1 2 / 3 2 \ 1 3 \ 

输出样例：

4 

样例解释

农场的平面图如下所示，其中$H$表示约翰的房子，$B$表示牛棚：

3 .\..... 2 //.\..B 1 ....... 0 H../... 0 

通过改变$(3,2)$处的围栏朝向，就可以使约翰看到点$(a,b)$，如下所示：

3 .\..... 2 //./--B 1 ...|... 0 H--/... 0 ``` 

题目分析

无

代码如下

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int N = 210, INF = 1e8; int n; struct Mirror { 
       int x, y; char c; }q[N]; //坐标系跟镜子田地不一样 int dx[4] = { 
      0, 1, 0, -1}, dy[4] = { 
      1, 0, -1, 0}; void rotate(char& c) { 
       if (c == '/') c = '\\'; else c = '/'; } bool check() { 
       int d = 1, k = 0; for (int i = 0; i < 2 * (n + 1); i ++) { 
       int id = -1, len = INF; for (int j = 1; j <= n + 1; j ++) { 
       // 遍历每个镜子需要保证当前镜子和遍历的镜子不同 if (k == j) continue; // 横竖水平 欧几里得距离 看是否能够反射到 if (q[k].x + abs(q[k].x - q[j].x) * dx[d] != q[j].x) continue; if (q[k].y + abs(q[k].y - q[j].y) * dy[d] != q[j].y) continue; int t = abs(q[k].x - q[j].x) + abs(q[k].y - q[j].y); //取最小的，因为不能跨镜子反射 if (t < len) id = j, len = t; } if (id == -1) return false; if (id == n + 1) return true; k = id; if (q[id].c == '/') d ^= 1; else d ^= 3; } return false; } int main() { 
       cin >> n; cin >> q[n + 1].x >> q[n + 1].y; for (int i = 1; i <= n; i ++) cin >> q[i].x >> q[i].y >> q[i].c; if (check()) puts("0"); else { 
       for (int i = 1; i <= n; i ++) { 
       rotate(q[i].c); if (check()) { 
       cout << i << endl; return 0; } rotate(q[i].c); } puts("-1"); } return 0; }