ACM/ICPC 2018亞洲區預選賽北京賽站網路賽

來自專欄 Code++4 人贊了文章

當時一看到最後一題0AC，再定睛一看，「Rikka with Polygon」，禿然明白了什麼……然後點開一看，果然……2333如果我沒猜錯的話這題是個多邊形的布爾運算？

A. Saving Tang Monk II

題面好評！這道題是一個比較明顯的bfs，策略如下：

遇到了#，檢查身上有沒有氧氣瓶，有的話就可以通過，時間+2
遇到了B，只要還裝得下，就裝一個，時間+1
遇到了P，不花時間
遇到了T，輸出答案
遇到了空格，時間+1

有一個特殊情況就是S也算作空格。

又考慮到在這道題裏如果使用std::queue的話「最小值」很難確定，因此可以採取類似於Dijkstra的優化的方法，使用std::priority_queue來進行搜索，這樣可以保證你走到這一點走的是最短路

#include <cstdio>#include <cstring>#include <vector>#include <queue>#define N 110using namespace std;const int dirx[4] = {0, 0, -1, 1};const int diry[4] = {-1, 1, 0, 0};int n, m;char mp[N][N];int vis[N][N][6];struct Node { int x, y, o2, d; Node() {} Node(const int& x, const int& y, const int& o2, const int& d) : x(x), y(y), o2(o2), d(d) {}};struct cmp { bool operator ()(const Node& n1, const Node& n2) const { return n1.d > n2.d; } };inline int bfs(pair<int, int> s){ priority_queue<Node, vector<Node>, cmp> q; memset(vis, 0, sizeof(vis)); int sx = s.first, sy = s.second; q.push(Node(sx, sy, 0, 0)); for (; !q.empty();) { Node u = q.top(); q.pop(); int x = u.x, y = u.y; if (vis[x][y][u.o2]) continue; vis[x][y][u.o2] = 1; for (int i = 0; i < 4; ++i) { int nx = x + dirx[i], ny = y + diry[i]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) { if (mp[nx][ny] == # && u.o2) q.push(Node(nx, ny, u.o2 - 1, u.d + 2)); if (mp[nx][ny] == B) q.push(Node(nx, ny, (u.o2 == 5 ? u.o2 : (u.o2 + 1)), u.d + 1)); if (mp[nx][ny] == P) q.push(Node(nx, ny, u.o2, u.d)); if (mp[nx][ny] == . || mp[nx][ny] == S) q.push(Node(nx, ny, u.o2, u.d + 1)); if (mp[nx][ny] == T) return u.d + 1; } } } return -1;}int main(){ //freopen("test.in", "r", stdin); for (;;) { scanf("%d%d", &n, &m); getchar(); if (!n) break; pair<int, int> s(0, 0); for (int i = 1; i <= n; ++i) scanf("%s", mp[i] + 1); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (mp[i][j] == S) s = make_pair(i, j); printf("%d ", bfs(s)); } return 0;}

（數組開小了，爆了十一發才FA♂現……）

B. Tomb Raider

有點♂fantasies，佔坑待補

D. 80 Days

因為一定是要走過n的長度的，因此我們把環複製一份然後就直接劃成一段一段就行了。有一個小小的優化是尺取法，一旦你發現走不了了，就把開頭的城市往後移

#include <bits/stdc++.h>#define N 1000010using namespace std;int T, n, c, a[N], b[N], e[N << 1];int main(){ scanf("%d", &T); while (T--) { scanf("%d%d", &n, &c); for (int i = 1; i <= n; ++i) scanf("%d", a + i); for (int i = 1; i <= n; ++i) scanf("%d", b + i); for (int i = 1; i <= n; ++i) e[i] = e[i + n] = a[i] - b[i]; int l = 1, r = 1; long long sum = 0; for (; l <= n && r - l + 1 <= n { sum += 1LL * e[r++]; while (sum + c < 0) sum -= e[l++]; } printf("%d ", l > n ? -1 : l); } return 0;}