2022 ICPC Jinan DG and 2022 ICPC Nanjing
2022 Jinan
D
需要考虑的地方是 ? 类型的提交，对于每种这样的提交，我们可以算出它可产生的最小罚时和最大罚时。于是我们单独考虑这样的提交，二进制枚举那些提交过了，判断一下可不可能合法。枚举出那些 ? 罚时是能够通过的后，就开始构造了，思路就是枚举每个 ? 类型的提交时都尽可能让它的罚时大。具体看代码就好了：
constexpr int N = 1000;struct Submit {int id; // 题号char type; // 类型int a, b;
};
struct Froz {int id;int a, b; // 封榜后的提交数和总提交数int mn, mx;Froz(int _id, int _a, int _b) : id(_id), a(_a), b(_b) {mn = (b - a) * 20 + 240; // 封榜后立刻过过mx = (b - 1) * 20 + 299; // 直到最后一刻才过}
};int M;bool solve() {// 题数和罚时int n = 0, p = 0;std::cin >> n >> p;int cntn = 0, cntp = 0;std::vector<Froz> pending;std::vector<Submit> all(M);for (int i = 0; i < M; ++i) {all[i].id = i;char t;std::cin >> t;all[i].type = t;if (t == '-') {std::cin >> all[i].b;}else if (t == '?'){std::cin >> all[i].a >> all[i].b;pending.push_back(Froz(i, all[i].a, all[i].b));}else if (t == '+'){scanf("%d/%d", &all[i].a, &all[i].b);cntn += 1;cntp += all[i].b + (all[i].a - 1) * 20;}}int m = n - cntn; // 封榜后的过题数if (m < 0) {std::cout << "No\n";return true;}int t = pending.size();if (m > t) {std::cout << "No\n";return true;}int u;int mn, mx;for (u = 0; u < (1 << t); ++u) {if (std::__popcount(u) != m) {continue;}mn = 0, mx = 0;for (int i = 0; i < t; ++i) {if (u >> i & 1) {mn += pending[i].mn;mx += pending[i].mx;}}if (cntp + mn <= p && p <= cntp + mx) {break;}}if (u == (1 << t)) {std::cout << "No\n";return true;}for (int i = 0; i < t; ++i) {if (!(u >> i & 1)) {continue;}int id = pending[i].id;all[id].type = '+';all[id].a = (pending[i].b - pending[i].a + 1);all[id].b = 240;mn -= pending[i].mn;cntp += pending[i].mn;while (all[id].a < pending[i].b) {if (cntp + 20 + mn <= p) {cntp += 20;all[id].a += 1;}else {break;}}while (all[id].b < 299) {if (cntp + 1 + mn <= p) {cntp += 1;all[id].b += 1;}else {break;}}}std::cout << "Yes\n";for (int i = 0; i < M; ++i) {if (all[i].type == '+') {std::cout << "+ " << all[i].a << '/' << all[i].b << '\n';}else if (all[i].type == '.') {std::cout << ".\n";}else {std::cout << "- " << all[i].b << '\n';}}return true;
}int main () {// IOS;int T = 1;std::cin >> T;std::cin >> M;while (T--) {solve();// std::cout << (solve() ? "YES" : "NO") << '\n';}return 0;
}
G
分析一下这个排序算法，发现瓶颈在于 PARTITION 函数中的双指针找数，就是在特定区间找一个小于等于或大于等于一个阈值的数，直接线段树维护区间最值然后线段树上二分就好了:
constexpr int N = 5e5, Inf = 1e9;struct info {int mn, mx;info() : mn(Inf), mx(-Inf) {};info(int val) : mn(val), mx(val) {};info (const info l, const info r) {mn = std::min(l.mn, r.mn);mx = std::max(l.mx, r.mx);}info operator+ (const info &r) {return info(*this, r);}
} tr[N << 2];int n;
int a[N + 5];
int ans;void push_up(int cur) {tr[cur] = tr[cur << 1] + tr[cur << 1 | 1];
}
void build(int cur, int l, int r) {if (l == r) {tr[cur] = info(a[l]);return;}int m = l + r >> 1;build(cur << 1, l, m);build(cur << 1 | 1, m + 1, r);push_up(cur);
}
void upd(int cur, int l, int r, int pos) {if (l == r) {tr[cur] = info(a[pos]);return;}int m = l + r >> 1;if (pos <= m) {upd(cur << 1, l, m, pos);}else {upd(cur << 1 | 1, m + 1, r, pos);}push_up(cur);
}
// 在 [sl, sr] 中找最左边的大于等于 val 的位置
int findLnoLS(int cur, int l, int r, int sl, int sr, int val) {if (r < sl || l > sr) {return Inf;}if (sl <= l && r <= sr) {if (tr[cur].mx < val) {return Inf;}while (l < r) {int m = l + r >> 1;cur <<= 1;if (tr[cur].mx >= val) {r = m;}else {l = m + 1;cur |= 1;}}return l;}int m = l + r >> 1;return std::min(findLnoLS(cur << 1, l, m, sl, sr, val), findLnoLS(cur << 1 | 1, m + 1, r, sl, sr, val));
}
// 在 [sl, sr] 中找最右边的小于等于 val 的位置
int findRnoGR(int cur, int l, int r, int sl, int sr, int val) {if (r < sl || l > sr) {return -Inf;}if (sl <= l && r <= sr) {if (tr[cur].mn > val) {return -Inf;}while (l < r) {int m = l + r >> 1;cur <<= 1;if (tr[cur | 1].mn <= val) {l = m + 1;cur |= 1;}else {r = m;}}return l;}int m = l + r >> 1;return std::max(findRnoGR(cur << 1, l, m, sl, sr, val), findRnoGR(cur << 1 | 1, m + 1, r, sl, sr, val));
}
void swap(int x, int y) {std::swap(a[x], a[y]);upd(1, 1, n, x);upd(1, 1, n, y);return;
}int find(int l, int r) {int val = a[l + r >> 1];int i = l - 1, j = r + 1;while (true) {i = findLnoLS(1, 1, n, i + 1, n, val);j = findRnoGR(1, 1, n, 1, j - 1, val);if (i >= j) {return j;}else {swap(i, j);ans += 1;}}
}void qsort(int l, int r) {if (l >= 0 && r >= 0 && l < r) {int m = find(l, r);qsort(l, m);qsort(m + 1, r);}
}void init(int n) {ans = 0;build(1, 1, n);
}bool solve() {;std::cin >> n;for (int i = 1; i <= n; ++i) {std::cin >> a[i];}init(n);qsort(1, n);std::cout << ans << '\n';return true;
}
2022 Nanjing
A
在没有洞的情况下，模拟这个过程，最后可以直到那块区域中的袋鼠留在了最后，对于最后可能留下来的袋鼠，我们跟踪最坐上角的一只，看他会经过那些格子，用 set 记录一下。对于其他袋鼠，经过的格子相当于是第一只袋鼠经过的格子向下向右平移后得来的，用二维前缀和维护出每个格子被多少只不同的袋鼠经过过，然后合法的格子就是被 \(lx\times ly - k\) 只袋鼠经过的格子的数量，其中 \(lx\) \(ly\) 是最后可能留下来的袋鼠所占区域的长宽：
int dx['Z' + 1], dy['Z' + 1];int pre[N + 5][N + 5];void init(int n, int m) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {pre[i][j] = 0;}}
}void add(int mnx, int mny, int mxx, int mxy) {pre[mnx][mny] += 1;pre[mxx + 1][mxy + 1] += 1;pre[mnx][mxy + 1] -= 1;pre[mxx + 1][mny] -= 1;
}int solve() {int n = 0, m = 0, k = 0;std::string s;std::cin >> n >> m >> k >> s;init(n, m);int mnx = 1, mny = 1;int mxx = n, mxy = m;int Dx = 0, Dy = 0;for (auto &c : s) {mnx = std::max(1, mnx + dx[c]);mny = std::max(1, mny + dy[c]);mxx = std::min(n, mxx + dx[c]);mxy = std::min(m, mxy + dy[c]);Dx += dx[c];Dy += dy[c];if (mxx <= 0 || mxy <= 0 || mnx > n || mny > m) {if (k == 0) {return n * m;}else {return 0;}}}mnx -= Dx, mny -= Dy, mxx -= Dx, mxy -= Dy;int lx = mxx - mnx, ly = mxy - mny;std::set<std::pair<int, int>> S;S.insert({ mnx, mny });for (auto &c : s) {mnx += dx[c];mny += dy[c];S.insert({ mnx, mny });}for (auto &[x, y] : S) {add(x, y, x + lx, y + ly);}for (int j = 1; j <= m; ++j) {for (int i = 1; i <= n; ++i) {pre[i][j] += pre[i - 1][j];}}for (int i = 1; i <= n; ++i) {for(int j = 1; j <= m; ++j) {pre[i][j] += pre[i][j - 1];// std::cout << pre[i][j] << ' ';}// std::cout << '\n';}k = (lx + 1) * (ly + 1) - k;int ans = 0;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if (pre[i][j] == k) {ans += 1;}}}return ans;
}int main () {IOS;int T = 1;std::cin >> T;dx['U'] = -1, dy['U'] = 0;dx['D'] = 1, dy['D'] = 0;dx['L'] = 0, dy['L'] = -1;dx['R'] = 0, dy['R'] = 1;while (T--) {std::cout << solve() << '\n';}return 0;
}
D
直接二分答案\(lim\)，问题在于如何检查
想知道一个序列的第 \(k\) 大的数能不能大于等于 \(lim\)，只需要知道这个序列中大于等于 \(lim\) 的数有没有等于或超过 \(k\) 个。与其考虑选择一个区间会让多少个数不小于 \(lim\)，不如直接判断对于一个数，有哪些区间能够使他不少于 \(lim\)，这样对所有数扫一遍后，我们就知道了每个区间能使多少个数不少于 \(lim\)，看有没有一个大于等于 \(k\) 就好了。具体的，对于原本就不小于的 \(lim\) 的数，我们认为所有区间都能让它不小于 \(lim\)；对于最大（\(a_i + c + (m - 1)d\)）还小于 \(lim\) 的数，我们认为所有区间都不能让它不小于 \(lim\)；其他的，我们首先判断判断是否满足 \(lim \leq a_i + c\)，此时只要包含 \(i\) 的区间都满足条件，否则就要算一下满足条件的区间有哪些：
constexpr int N = 2e5;int n, k, m;
i64 c, d;
i64 a[N + 5];
int pre[N + 5];bool chk(i64 lim) {int L = 1, R = n - m + 1;for (int i = L; i <= R + 1; ++i) {pre[i] = 0;}for (int i = 1; i <= n; ++i) {if (a[i] >= lim) {pre[1] += 1;continue;}if (a[i] + c + (m - 1) * d < lim) {continue;}int l = std::max(L, i - m + 1);int r = R;if (a[i] + c >= lim) {r = std::min(r, i);}else {r = std::min(r, i - (int)((lim - c - a[i] - 1) / d + 1));}if (l <= r) {pre[l] += 1;pre[r + 1] -= 1;}}for (int i = L; i <= R + 1; ++i) {pre[i] += pre[i - 1];if (pre[i] >= k) {return true;}}return false;
}void solve() {std::cin >> n >> k >> m >> c >> d;for (int i = 1; i <= n; ++i) {std::cin >> a[i];}i64 l = 0, r = Inf;while (l <= r) {i64 mid = (l + r >> 1);if (chk(mid)) {l = mid + 1;}else {r = mid - 1;}}std::cout << r << '\n';return;
}
M
比较 ez 的计算几何，看代码就好了：
using node = std::array<i64, 2>;node operator- (const node &u, const node &v) {return { u[0] - v[0], u[1] - v[1] };
}i64 operator^ (const node &u, const node &v) {return u[0] * v[1] - u[1] * v[0];
}int solve() {int n = 0;std::cin >> n;std::vector p(n + 2, node{});for (int i = 1; i <= n; ++i) {std::cin >> p[i][0] >> p[i][1];}p[0] = p[n];p[n + 1] = p[1];std::vector<int> Y;for (int i = n; i >= 1; --i) {if (p[i][1] != p[1][1]) {Y.push_back(p[i][1]);break;}}int ans = 0;for (int i = 1; i <= n; ++i) {if (Y.back() != p[i][1]) {Y.push_back(p[i][1]);}i64 cross = ((p[i - 1] - p[i]) ^ (p[i + 1] - p[i]));if (cross >= 0) {continue;}int a = Y[Y.size() - 2];int b = Y.back();int c = p[i + 1][1];if (a > b && c > b) {ans += 1;}}return ans;
}