就说坑不坑，就说坑不坑。。。
1002 线段树，初始没看到初始时为2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 | /************************************************************************* > File Name: 1002.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年09月20日 星期六 12时11分42秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define LL long long #define pb push_back #define mp make_pair #define PI acos(-1.0) #define eps 1e-8 #define x first #define y second #define MAXN 1000005 #define LS(x) (x << 1) #define RS(x) (x << 1) | 1 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair<int, int> PII; typedef vector<int> vi; int N, M, a, b, c; char op[2]; struct Node { int color, lazy; } p[MAXN << 2]; void pushdown(int pos) { if (p[pos].lazy) { p[LS(pos)].lazy = p[RS(pos)].lazy = p[pos].lazy; p[LS(pos)].color = p[RS(pos)].color = p[pos].color; p[pos].lazy = 0; } } void pushup(int pos) { if (p[LS(pos)].lazy && p[RS(pos)].lazy) { if (p[LS(pos)].color == p[RS(pos)].color) { p[pos].color = p[LS(pos)].color; p[pos].lazy = 1; } } } void build(int l, int r, int pos) { p[pos].color = 1 << 2; p[pos].lazy = 0; if (l == r) { p[pos].lazy = 1; return ; } int mid = (l + r) >> 1; build(l, mid, LS(pos)); build(mid + 1, r, RS(pos)); } void update(int l, int r, int pos, int L, int R, int color) { if (l <= L && R <= r) { p[pos].lazy = 1; p[pos].color = color; return ; } pushdown(pos); int mid = (L + R) >> 1; if (mid >= l) { update(l, r, LS(pos), L, mid, color); } if (mid < r) { update(l, r, RS(pos), mid + 1, R, color); } pushup(pos); } int query(int l, int r, int pos, int L, int R) { if (l <= L && R <= r) { if (p[pos].lazy) { return p[pos].color; } } int mid = (L + R) >> 1; int ans = 0; pushdown(pos); if (mid >= l) { ans |= query(l, r, LS(pos), L, mid); } if (mid < r) { ans |= query(l, r, RS(pos), mid + 1, R); } pushup(pos); return ans; } void work() { build(1, N, 1); for (int i = 1; i <= M; i ++) { scanf("%s", op); if (op[0] == 'P') { scanf("%d %d %d", &a, &b, &c); update(a, b, 1, 1, N, 1 << c); } else { scanf("%d %d", &a, &b); int ans = query(a, b, 1, 1, N); int flag = 0; for (int i = 1; i <= 30; i ++) { if (ans & (1 << i)) { if (flag) printf(" "); flag = 1; printf("%d", i); } } printf("\n"); } } } int main() { while (scanf("%d %d", &N, &M) != EOF) { if (N == 0 && M == 0) break; work(); } return 0; } |
1003 简单的预处理操作就可以了。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 | /************************************************************************* > File Name: 1003.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年09月20日 星期六 13时06分05秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> // #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define LL long long #define pb push_back #define mp make_pair #define PI acos(-1.0) #define eps 1e-8 #define x first #define y second #define MAXN 105 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair<int, int> PII; typedef vector<int> vi; int N, Mat[MAXN][MAXN], sx1[MAXN][MAXN], sx2[MAXN][MAXN], sy1[MAXN][MAXN], sy2[MAXN][MAXN]; int lx1[MAXN][MAXN], lx2[MAXN][MAXN], ly1[MAXN][MAXN], ly2[MAXN][MAXN]; string line; void work() { for (int i = 1; i <= N; i ++) { cin >> line; for (int j = 0; j < line.length(); j ++) { Mat[i][j + 1] = (line[j] == '#' ? 0 : 1); } } memset(lx1, 0, sizeof(lx1)); memset(lx2, 0, sizeof(lx2)); memset(ly1, 0, sizeof(ly1)); memset(ly2, 0, sizeof(ly2)); memset(sx1, 0, sizeof(sx1)); memset(sx2, 0, sizeof(sx2)); memset(sy1, 0, sizeof(sy1)); memset(sy2, 0, sizeof(sy2)); for (int i = 1; i <= N; i ++) { for (int j = 1; j <= N; j ++) { if (Mat[i][j]) { lx1[i][j] = lx1[i][j - 1] + 1; } } for (int j = N; j >= 1; j --) { if (Mat[i][j]) { lx2[i][j] = lx2[i][j + 1] + 1; } } } for (int i = 1; i <= N; i ++) { for (int j = 1; j <= N; j ++) { if (Mat[i][j]) { ly1[i][j] = ly1[i - 1][j] + 1; } } } for (int i = N; i >= 1; i --) { for (int j = 1; j <= N; j ++) { if (Mat[i][j]) { ly2[i][j] = ly2[i + 1][j] + 1; } } } for (int i = 1; i <= N; i ++) { for (int j = 1; j <= N; j ++) { if (Mat[i][j]) { sx1[i][j] = sx1[i - 1][j - 1] + 1; } } for (int j = N; j >= 1; j --) { if (Mat[i][j]) { sy1[i][j] = sy1[i - 1][j + 1] + 1; } } } for (int i = N; i >= 1; i --) { for (int j = N; j >= 1; j --) { if (Mat[i][j]) { sx2[i][j] = sx2[i + 1][j + 1] + 1; } } for (int j = 1; j <= N; j ++) { if (Mat[i][j]) { sy2[i][j] = sy2[i + 1][j - 1] + 1; } } } int ans = 0; for (int i = 1; i <= N; i ++) { for (int j = 1; j <= N; j ++) { if (Mat[i][j]) { ans = Max(ans, lx1[i][j] + lx2[i][j] - 1); ans = Max(ans, ly1[i][j] + ly2[i][j] - 1); ans = Max(ans, sx1[i][j] + sx2[i][j] - 1); ans = Max(ans, sy2[i][j] + sy1[i][j] - 1); ans = Max(ans, lx1[i][j] + ly1[i][j] - 1); ans = Max(ans, lx1[i][j] + ly2[i][j] - 1); ans = Max(ans, lx2[i][j] + ly1[i][j] - 1); ans = Max(ans, lx2[i][j] + ly2[i][j] - 1); ans = Max(ans, sx1[i][j] + sy1[i][j] - 1); ans = Max(ans, sx1[i][j] + sy2[i][j] - 1); ans = Max(ans, sx2[i][j] + sy1[i][j] - 1); ans = Max(ans, sx2[i][j] + sy2[i][j] - 1); } } } cout << ans << endl; } int main() { while (scanf("%d", &N) != EOF) { if (N == 0) break; work(); } return 0; } |
1004 三维BFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 | /************************************************************************* > File Name: 1004.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2014年09月20日 星期六 12时49分22秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> // #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define LL long long #define pb push_back #define mp make_pair #define PI acos(-1.0) #define eps 1e-8 #define x first #define y second #define MAXN 105 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair<int, int> PII; typedef vector<int> vi; const int INF = 0x3fffffff; int N, M, snack; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; bool vis[10][MAXN][MAXN]; int len[10][MAXN][MAXN]; int Mat[10][MAXN][MAXN], a[MAXN][MAXN]; string line; struct Point { int x, y, z; Point () {} bool operator == (const Point &next) const { if (x == next.x && y == next.y && z == next.z) { return true; } return false; } } start, end; Point s[10]; void init(int state) { memset(Mat, 0, sizeof(Mat)); memset(vis, 0, sizeof(vis)); for (int i = 0; i <= M; i ++) { for (int j = 1; j <= N; j ++) { for (int k = 1; k <= N; k ++) { if (a[j][k] <= i + 1) { Mat[i][j][k] = a[j][k]; } else { Mat[i][j][k] = 0; } } } } for (int i = 0; i < snack; i ++) { if (state & (1 << i)) { for (int j = 0; j <= M; j ++) { Mat[j][s[i].x][s[i].y] = 0; } } } } int bfs() { queue <Point> Q; Q.push(start); vis[start.z][start.x][start.y] = true; len[start.z][start.x][start.y] = 0; while (!Q.empty()) { Point now = Q.front(); for (int i = 0; i < 4; i ++) { Point next = now; next.x += dir[i][0]; next.y += dir[i][1]; if (next.x >= 1 && next.x <= N && next.y >= 1 && next.y <= N && Mat[next.z][next.x][next.y] >= 0 && !vis[next.z][next.x][next.y]) { vis[next.z][next.x][next.y] = true; len[next.z][next.x][next.y] = len[now.z][now.x][now.y] + 1; if (next == end) { return len[next.z][next.x][next.y]; } if (Mat[next.z][next.x][next.y] == next.z + 1) { next.z ++; if (!vis[next.z][next.x][next.y]) { len[next.z][next.x][next.y] = len[next.z - 1][next.x][next.y]; vis[next.z][next.x][next.y] = true; if (next == end) { return len[next.z][next.x][next.y]; } Q.push(next); } } else { Q.push(next); } } } Q.pop(); } return -1; } void work() { snack = 0; memset(a, 0, sizeof(a)); for (int i = 1; i <= N; i ++) { cin >> line; for (int j = 0; j < N; j ++) { if (line[j] == 'S') { s[snack].x = i, s[snack].y = j + 1; snack ++; a[i][j + 1] = -1; } else if (line[j] == 'K') { start.x = i, start.y = j + 1, start.z = 0; a[i][j + 1] = 0; } else if (line[j] == 'T') { end.x = i, end.y = j + 1, end.z = M; a[i][j + 1] = 0; } else if (line[j] == '#') { a[i][j + 1] = -1; } else if (line[j] == '.') { a[i][j + 1] = 0; } else { a[i][j + 1] = line[j] - '0'; } } } int ans = INF; for (int i = 0; i < (1 << snack); i ++) { int num = 0; for (int j = 0; j < snack; j ++) { if (i & (1 << j)) { num ++; } } init(i); int now = bfs(); if (now == -1) { continue; } ans = Min(ans, now + num); } if (ans == INF) { printf("impossible\n"); return ; } else { printf("%d\n", ans); } } int main() { while (scanf("%d %d", &N, &M) != EOF) { if (N == 0 && M == 0) break; work(); } return 0; } |
坑！