A. 「JOISC 2014」巴士走读
summarization
有 \(n\) 个点和 \(m\) 辆巴士，每个巴士在 \(X_i\) 时从 \(A_i\) 出发，\(Y_i\) 时到达 \(B_i\)，若要乘坐一辆巴士，在 \(\le X_i\) 时到达 \(A_i\) 即可。给定 \(Q\) 个询问 \(L_i\)，询问若要到达 \(n\) 号点的时间 \(\le L_i\)，最晚何时从 \(1\) 号点出发。
solution
考虑预处理出一些 \(l_i,r_i\)，表示 \(l_i\) 时从 \(1\) 号点出发，\(r_i\) 时可以到达 \(n\) 号点，则在回答第 \(x\) 个询问时只需要找到满足 \(r_i\le L_x\) 的最大的 \(l_i\) 即可。
由于到达 \(n\) 号点的时间只可能是 \(B_i=n\) 的巴士的 \(Y_i\)， 所以考虑枚举所有 \(B_i=n\) 的边，确定到达 \(n\) 号点的时间，然后在反向图上跑 Dijkstra，一条边能走的条件是点 \(B_i\) 的时间 \(\ge Y_i\)，则到达 \(A_i\) 的时间为 \(X_i\)。
但是这样肯定超时，考虑优化。
先将 \(A_i,B_i\) 相同的边按 \(Y_i\) 升序排序，访问时优先访问 \(Y_i\) 小的。不难发现如果一条边在之前的 Dijkstra 中经过，则这条边就不用访问了。
这是因为在先后两次 Dij 中，到达 \(n\) 的时间是变大的。而当在两次 Dij 中访问到 \(B_i\) 时，这个点此时的时间是不变的。而此时先的 Dij 若能访问这条边则已经访问了，且先的 Dij 对答案的贡献比后的 Dij 要大，所以后的 Dij 就不需要访问了。
所以所有的边只需要被访问一次，时间复杂度得到保证。
code
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
CI N = 1e5, M = 3e5; int n, m, cur[M + 5], dis[N + 5]; struct node {int A, X, Y;}; vector <node> G[N + 5]; vector <pii> ans; bool vis[N + 5];
priority_queue <pii> q;
bool cmp (node a, node b) {return a.Y < b.Y;}
void Dij (node a) {
RI i, j; Mt (vis, 0); vis[n] = 1; if (dis[a.A] >= a.X) return ; dis[a.A] = a.X; q.push (mk(a.X, a.A)); W (! q.empty ()) {
pii p = q.top (); q.pop (); if (vis[p.se]) continue; vis[p.se] = 1; int sz = G[p.se].size ();
for (i = cur[p.se]; i < sz; ++ i) {
cur[p.se] = i; if (p.fi < G[p.se][i].Y) break; int to = G[p.se][i].A; if (dis[to] < G[p.se][i].X) dis[to] = G[p.se][i].X, q.push (mk (dis[to], to));
}
} ans.pb (mk (a.Y, dis[1]));
}
int main () {
RI i, j; for (Read (n, m), i = 1; i <= m; ++ i) {int a, b, x, y; Read (a, b, x, y); G[b].pb ((node){a, x, y});} for (i = 1; i <= n; ++ i) sort (G[i].begin (), G[i].end (), cmp);
Mt (dis, -1); ans.pb (mk (0, -1)); for (i = 0; i < G[n].size (); ++ i) Dij (G[n][i]); int Q; Read (Q);
W (Q --) {int x; Read (x); printf ("%d\n", (--upper_bound (ans.begin (), ans.end (), mk (x, 0x7fffffff))) -> se);}
return 0;
}
B. 「JOISC 2014」有趣的家庭菜园
summarization
给定一个序列，每次操作只能交换相邻的两个数，问最少几次操作后可以将序列变为单峰。
solution
若将操作前序列中的数组从左到右标号 \(1\sim n\)，则所有操作后交换的次数就是此时标号的逆序对个数。所以我们将最大的放在中间，然后将其他的数由大到小依次放在已有数字的左边或右边，哪边逆序对小就放在哪边，最后逆序对的个数就是最少的操作，注意相同数字放置的细节。
code
#define pb push_back
CI N = 3e5; struct node {int num, id;} a[N + 5]; int n, b[N + 5]; vector <int> v;
bool cmp (node x, node y) {return x.num > y.num;}
int lowbit (int x) {return x & -x;}
void add (int id, int x) {for (; id; id -= lowbit (id)) b[id] += x;}
int ask (int id) {int sum = 0; for (; id <= n; id += lowbit (id)) sum += b[id]; return sum;}
int main () {
RI i, j; for (Read (n), i = 1; i <= n; ++ i) {int x; Read (x); a[i].num = x; a[i].id = i;} sort (a + 1, a + n + 1, cmp);
int lst = 0x7fffffff, now = 0; ll ans = 0; for (i = 1; i <= n; ++ i) {
if (lst != a[i].num) {for (auto x : v) add (x, 1), ++ now; v.clear ();} ans += min (ask (a[i].id), now - ask (a[i].id)); v.pb (a[i].id); lst = a[i].num;
} printf ("%lld\n", ans);
return 0;
}
C. 「JOISC 2014」历史研究
summarization
给出一个序列和若干个询问 \(l_i,r_i\)，需要求出在 \(l_i\sim r_i\) 之间的数中相同的数乘以相同的数的个数的乘积的最大值。（比如 7 8 9 8 7，则要求的值就是 \(\max(7\times2,8\times2,9\times1)=16\)）
solution
emmm，回滚莫队板子题，不在赘述。
code
#define int ll
CI N = 1e5; int n, q, a[N + 5], b[N + 5], Tng[N + 5], ans[N + 5];
int bk, bn, bl[N + 5], br[N + 5], bi[N + 5];
struct node {
int l, r, id;
friend bool operator < (node x, node y) {
return bi[x.l] == bi[y.l] ? x.r < y.r : x.l < y.l;
}
}qn[N + 5];
int query (int l, int r) {
RI i, j; int now = 0; for (i = l; i <= r; ++ i) ++ Tng[a[i]], now = max (now, Tng[a[i]] * b[a[i]]); for (i = l; i <= r; ++ i) -- Tng[a[i]]; return now;
}
main () {
RI i, j; for (Read (n, q), i = 1; i <= n; ++ i) Read (a[i]), b[i] = a[i]; sort (b + 1, b + n + 1); int tot = unique (b + 1, b + n + 1) - b - 1;
for (i = 1; i <= n; ++ i) a[i] = lower_bound (b + 1, b + tot + 1, a[i]) - b; bk = sqrt (n); bn = ceil (n * 1.0 / bk);
for (i = 1; i <= bn; ++ i) bl[i] = (i - 1) * bk + 1, br[i] = i * bk; br[bn] = n; for (i = 1; i <= n; ++ i) bi[i] = (i - 1) / bk + 1;
int qq = 0; for (i = 1; i <= q; ++ i) {
int X, Y; Read (X, Y); if (bi[X] == bi[Y]) ans[i] = query (X, Y); else ++ qq, qn[qq].l = X, qn[qq].r = Y, qn[qq].id = i;
} sort (qn + 1, qn + qq + 1);
int L, R, mx, lst; bool flag = 0; for (i = 1; i <= qq; ++ i) {
if (bi[qn[i].l] != bi[qn[i - 1].l]) flag = 1; if (flag) {
Mt (Tng, 0); R = br[bi[qn[i].l]]; mx = 0; lst = 0; flag = 0;
}
W (R < qn[i].r) {++ R; ++ Tng[a[R]]; mx = lst = max (lst, Tng[a[R]] * b[a[R]]);} L = br[bi[qn[i].l]] + 1;
W (L > qn[i].l) {-- L; ++ Tng[a[L]]; mx = max (mx, Tng[a[L]] * b[a[L]]);} ans[qn[i].id] = mx; mx = lst; L = br[bi[qn[i].l]] + 1;
W (L > qn[i].l) {-- L; -- Tng[a[L]];}
} for (i = 1; i <= q; ++ i) printf ("%lld\n", ans[i]);
return 0;
}
D. 「JOISC 2014」水壶
summarization
emmm，我概括不来了，看原题吧（精简了一下）：
IOI 市被分成 \(H\) 行，每行包含 \(W\) 块区域。每个区域都是建筑物、原野、墙壁之一。
IOI 市有 \(P\) 个区域是建筑物，坐标分别为 \((A_1, B_1), (A_2, B_2), \ldots, (A_P, B_P)\)。
JOI 君只能进入建筑物与原野，而且每次只能走到相邻的区域中，且不能移动到市外。
JOI 君在原野上每走过一个区域都需要 1 升水。大小为 \(x\) 的水壶最多可以装 \(x\) 升水，建筑物里有自来水可以将水壶装满。
JOI 君决定携带尽量小的水壶移动，问最少需要多大的水壶。
现在给出 IOI 市的地图和 \(Q\) 个询问，第 \(i\) 个询问包含两个整数 \(S_i, T_i\)，对于每个询问，请输出：要从建筑物 \(S_i\) 移动到 \(T_i\)，至少需要多大的水壶？