[赛记] csp-s模拟8 csp-s模拟9

HZOI大作战 15pts

赛时暴力跳父亲15pts；

正解：发现在树上对于向上找大于这个数的操作具有随意划分性，所以考虑倍增，设 $ f_{i, j} $ 表示从 $ i $ 这个点向上跳 $ 2^j $ 个比它大的数能跳到哪里，于是我们只需处理出向上跳一个（也就是 $ f_{i, 0} $）的，然后 $ ST $ 表预处理即可；

具体地，对于一个点 $ a_i $：

如果 $ a_{fa_{i}} > a_i $，就 $ f_{i, 0} = fa_{i} $；

如果 $ a_{fa_{i}} = a_i $，就 $ f_{i, 0} = f_{fa_i, 0} $；

否则用倍增找出第一个比它大的赋值即可；

对于查询，思路基本一样；

时间复杂度： $ \Theta(n \log n) $；

点击查看代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n, q;
int a[500005];
struct sss{int t, ne;
}e[2000005];
int h[2000005], cnt;
void add(int u, int v) {e[++cnt].t = v;e[cnt].ne = h[u];h[u] = cnt;
}
int f[500005][21], dep[500005];
void dfs(int x, int fa) {if (a[x] < a[fa]) f[x][0] = fa;else if (a[x] == a[fa]) f[x][0] = f[fa][0];else if (a[x] > a[fa]) {int y = fa;for (int i = 19; i >= 0; i--) {if (a[f[y][i]] <= a[x] && f[y][i] != 0) y = f[y][i];}f[x][0] = f[y][0];}for (int j = 1; j <= 19; j++) {f[x][j] = f[f[x][j - 1]][j - 1];}dep[x] = dep[fa] + 1;for (int i = h[x]; i; i = e[i].ne) {int u = e[i].t;if (u == fa) continue;dfs(u, x);}
}
int w(int u, int v, int c) {int ans = 0;if (c < a[u]) {ans++;} else if (c > a[u]) {for (int i = 19; i >= 0; i--) {if (a[f[u][i]] <= c && f[u][i] != 0) u = f[u][i];}}for (int i = 19; i >= 0; i--) {if (dep[f[u][i]] >= dep[v]) {u = f[u][i];ans += pow(2, i);}}return ans;
}
int main() {freopen("accepted.in", "r", stdin);freopen("accepted.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> q;for (int i = 1; i <= n; i++) {cin >> a[i];}int x, y;for (int i = 1; i <= n - 1; i++) {cin >> x >> y;add(x, y);add(y, x);}dfs(1, 0);int u, v, c;for (int i = 1; i <= q; i++) {cin >> u >> v >> c;cout << w(u, v, c) << '\n';}return 0;
}

邻面合并 70pts

赛时错解70pts；

正解：看见 $ m \leq 8 $，考虑状压；

设 $ f_{i, j} $ 表示考虑到第 $ i $ 行，当前行的连接状态是 $ j $ 时的最小划分数；

这里的连接状态是指，对于 $ j $ 的一个二进制位 $ j_x $（ $ x $ 从 $ 0 $ 开始计数 ），若 $ j_x = 1 $ 则代表 $ a_{i, x + 1} $ 与 $ a_{i, x + 2} $ 连接，否则不连接；

转移直接转（lxyt说），但我分了很多情况，最后好像还是不对，但过了。。。

时间复杂度：$ \Theta(n \times 2^{2x - 2}) $；

代码仅供参考；

点击查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m;
int a[105][105];
int f[105][(1 << 9)];
bool ck(int i, int j) {for (int x = 0; x <= m - 2; x++) {if (a[i][x + 1] + a[i][x + 2] < 2 && ((j >> x) & 1)) return false;}return true;
}
int main() {freopen("merging.in", "r", stdin);freopen("merging.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];}}memset(f, 0x3f, sizeof(f));for (int j = 0; j < (1 << (m - 1)); j++) {f[0][j] = 0;}for (int i = 1; i <= n; i++) {for (int j = 0; j < (1 << (m - 1)); j++) {if (!ck(i, j)) continue;for (int k = 0; k < (1 << (m - 1)); k++) {if (!ck(i - 1, k)) continue;int res = f[i - 1][k];int ej = -1;int ek = -1;int x = 1;bool vis = false;while(x <= m) {ej = m;ek = m;if (!a[i][x]) {x++;vis = false;continue;}if (!a[i][x - 1] && ((k >> (x - 2)) & 1)) vis = true;for (int t = x; t <= m; t++) {if (!((j >> (t - 1)) & 1)) {ej = t;break;}}if (((k >> (x - 2)) & 1)) {ek = ej + 1;} else {for (int t = x; t <= m; t++) {if (i == 1) {ek = ej + 1;break;}if (!((k >> (t - 1)) & 1)) {if (!a[i - 1][t]) ek = ej + 1;else ek = t;break;}}}if (ej != ek || vis) res++;x = ej + 1;}f[i][j] = min(f[i][j], res);}}}int ans = 0x3f3f3f3f;for (int i = 0; i < (1 << (m - 1)); i++) {ans = min(ans, f[n][i]);}cout << ans;return 0;
}

光线追踪 30pts；

赛时最暴力的暴力30pts；

正解：可以发现每次插入的矩形只有左边和下边的边能够产生贡献；

所以用斜率当下标建一棵线段树，然后区间插入+单点查询即可解决；

难点：想到用斜率当下标建一棵线段树（可以用 $ double $ 类型当下标，但最好还是离线将所有要用到的斜率离散化一下）；

注意特判斜率等于零和不存在的情况；

时间复杂度：设一共有 $ k $ 个不同的斜率，则时间复杂度为： $ \Theta(q \log k) $；

点击查看代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int q;
double a[1000005];
int cnt;
int qx[500005], qy[500005], hx[500005], hy[500005], x[500005], y[500005], s[500005];
pair<int, int> pcm(pair<int, int> a, pair<int, int> b) {if (a.first < b.first) return a;if (a.first > b.first) return b;if (a.first == b.first) {if (a.second > b.second) return a;else return b;}
}
namespace SEG{inline int ls(int x) {return x << 1;}inline int rs(int x) {return x << 1 | 1;}struct sss{int l, r;pair<int, int> mi, lz;}tr[2][5000005];inline void push_down(int s, int id) {if (tr[s][id].lz.first != 2e9) {tr[s][ls(id)].lz = pcm(tr[s][ls(id)].lz, tr[s][id].lz);tr[s][rs(id)].lz = pcm(tr[s][rs(id)].lz, tr[s][id].lz);tr[s][ls(id)].mi = pcm(tr[s][ls(id)].mi, tr[s][id].lz);tr[s][rs(id)].mi = pcm(tr[s][rs(id)].mi, tr[s][id].lz);tr[s][id].lz = {2e9, 0};}}void bt(int s, int id, int l, int r) {tr[s][id].l = l;tr[s][id].r = r;tr[s][id].mi = {2e9, 0};tr[s][id].lz = {2e9, 0};if (l == r) return;int mid = (l + r) >> 1;bt(s, ls(id), l, mid);bt(s, rs(id), mid + 1, r);}void add(int s, int id, int l, int r, pair<int, int> d) {if (tr[s][id].l >= l && tr[s][id].r <= r) {tr[s][id].mi = pcm(tr[s][id].mi, d);tr[s][id].lz = pcm(tr[s][id].lz, d);return;}push_down(s, id);int mid = (tr[s][id].l + tr[s][id].r) >> 1;if (l <= mid) add(s, ls(id), l, r, d);if (r > mid) add(s, rs(id), l, r, d);}pair<int, int> ask(int s, int id, int pos) {if (tr[s][id].l == tr[s][id].r) return tr[s][id].mi;push_down(s, id);int mid = (tr[s][id].l + tr[s][id].r) >> 1;if (pos <= mid) return ask(s, ls(id), pos);else return ask(s, rs(id), pos);}
}
pair<int, int> px, py;
int main() {freopen("raytracing.in", "r", stdin);freopen("raytracing.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> q;px = {2e9, 0};py = {2e9, 0};for (int i = 1; i <= q; i++) {cin >> s[i];if (s[i] == 1) {cin >> qx[i] >> qy[i] >> hx[i] >> hy[i];if (qy[i] && hx[i]) a[++cnt] = 1.00 * qy[i] / hx[i];if (qy[i] && qx[i]) a[++cnt] = 1.00 * qy[i] / qx[i];if (hy[i] && qx[i]) a[++cnt] = 1.00 * hy[i] / qx[i];}if (s[i] == 2) {cin >> x[i] >> y[i];if (x[i] == 0 || y[i] == 0) continue;a[++cnt] = 1.00 * y[i] / x[i];}}a[++cnt] = 0.0;a[++cnt] = 1000000000.00;sort(a + 1, a + 1 + cnt);cnt = unique(a + 1, a + 1 + cnt) - a - 1;SEG::bt(0, 1, 1, cnt);SEG::bt(1, 1, 1, cnt);for (int i = 1; i <= q; i++) {if (s[i] == 1) {if (qx[i] == 0) {py = pcm(py, {qy[i], i});SEG::add(0, 1, lower_bound(a + 1, a + 1 + cnt, 1.00 * qy[i] / hx[i]) - a, lower_bound(a + 1, a + 1 + cnt, 1000000000.00) - a, {qy[i], i});continue;}if (qy[i] == 0) {px = pcm(px, {qx[i], i});SEG::add(1, 1, lower_bound(a + 1, a + 1 + cnt, 0.0) - a, lower_bound(a + 1, a + 1 + cnt, 1.00 * hy[i] / qx[i]) - a, {qx[i], i});continue;}SEG::add(0, 1, lower_bound(a + 1, a + 1 + cnt, 1.00 * qy[i] / hx[i]) - a, lower_bound(a + 1, a + 1 + cnt, 1.00 * qy[i] / qx[i]) - a, {qy[i], i});SEG::add(1, 1, lower_bound(a + 1, a + 1 + cnt, 1.00 * qy[i] / qx[i]) - a, lower_bound(a + 1, a + 1 + cnt, 1.00 * hy[i] / qx[i]) - a, {qx[i], i});}if (s[i] == 2) {if (x[i] == 0) {cout << py.second << '\n';continue;}if (y[i] == 0) {cout << px.second << '\n';continue;}double k = 1.00 * y[i] / x[i];int pos = lower_bound(a + 1, a + 1 + cnt, k) - a;pair<int, int> yy = SEG::ask(0, 1, pos);pair<int, int> xx = SEG::ask(1, 1, pos);double nowx = 1.00 * yy.first / k;if (nowx < 1.00 * xx.first) {cout << yy.second << '\n';} else if (nowx > 1.00 * xx.first) {cout << xx.second << '\n';} else {cout << max(yy.second, xx.second) << '\n';}}}return 0;
}