本文主要是介绍CodeForces 487D Conveyor Belts，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
n*m（10^5*10）的棋盘 每个格子有个箭头表示行走方向 有q(10^5)个操作 更改操作即改变某个位置的箭头 更改最多10^4次 查询操作即询问从(x,y)位置开始走最后走到哪 或者 死循环
思路：
我们发现n大m小 联想到可能3进制状压什么的 如果不更新明显dp一下就好 更新少 联想到分块搞
因为分块有个很好的性质 “走出这一块，就不归我这一块管了” 也就是更新只影响一块
假设分块大小为sqrt(n) 那么更新的复杂度就是 O(sqrt(n)*m) 查询的复杂度就是 O(sqrt(n))
代码借鉴了Nero爷的写法 更新一块时候采用递归来写
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long LL;
#define N 100010
#define M 20int n, m, q, size, amt;
char maz[N][M];
int to[N][M][2], vis[N][M];void find(int x, int y, int up) {vis[x][y] = 1;if (maz[x][y] == '^') {if (x == up)to[x][y][0] = x - 1, to[x][y][1] = y;elseto[x][y][0] = to[x - 1][y][0], to[x][y][1] = to[x - 1][y][1];} else if (maz[x][y] == '<') {if (y == 1)to[x][y][0] = x, to[x][y][1] = 0;else if (maz[x][y - 1] == '>')to[x][y][0] = -1, to[x][y][1] = -1;elseto[x][y][0] = to[x][y - 1][0], to[x][y][1] = to[x][y - 1][1];} else {if (y == m)to[x][y][0] = x, to[x][y][1] = m + 1;else if (maz[x][y + 1] == '<')to[x][y][0] = -1, to[x][y][1] = -1;else {find(x, y + 1, up);to[x][y][0] = to[x][y + 1][0];to[x][y][1] = to[x][y + 1][1];}}
}void update(int block) {int up = block * size + 1, down = (block + 1) * size;for (int i = up; i <= n && i <= down; i++) {for (int j = 1; j <= m; j++)vis[i][j] = 0;}for (int i = up; i <= n && i <= down; i++) {for (int j = 1; j <= m; j++)if (!vis[i][j])find(i, j, up);}
}void query(int x, int y) {int tmpx, tmpy;while (x > 0 && y > 0 && y <= m) {tmpx = to[x][y][0];tmpy = to[x][y][1];x = tmpx;y = tmpy;}printf("%d %d\n", x, y);
}int main() {scanf("%d%d%d", &n, &m, &q);for (int i = 1; i <= n; i++) {scanf("%s", maz[i] + 1);}size = sqrt(0.5 + n);amt = n / size;if (amt * size < n)amt++;for (int i = 0; i < amt; i++)update(i);while (q--) {char op[5], c[5];int x, y;scanf("%s%d%d", op, &x, &y);if (op[0] == 'A')query(x, y);else {scanf("%s", c);maz[x][y] = c[0];update((x - 1) / size);}}return 0;
}
这篇关于CodeForces 487D Conveyor Belts的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
