首页 > 代码库 > CodeForces 487D Conveyor Belts
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 20 int 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; else to[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; else to[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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。