202206007 模拟赛总结

技术分享 2年前 (2022-06-10) 0 999+

盖房子

(ntimes n) 的矩形中选出一个边长为 (ktimes k) 的子矩阵，使得中位数最小

中位数定义为子矩阵中第 (lfloordfrac{k^2}{2}rfloor+1) 大的数，(nle 800)

比较显然的二分，二分答案 (mid) 。另 (b_{i,j}=[a_{i,j}>mid]) ，作二维前缀和

如果 (b) 存在子矩阵使得 (slelfloordfrac{k^2}{2}rfloor) ，则 (mid) 可行且可以缩小，反之需要增大，(O(n^2log n^2))

#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 805; int n, K, a[N][N], s[N][N], t[N * N], le, L, R, mid, res; inline bool chk(int val) {     memset(s, 0, sizeof(s));     for (int i = 1; i <= n; i++)         for (int j = 1; j <= n; j++) s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (a[i][j] > val);     for (int i = K, x, y, t; i <= n; i++)         for (int j = K; j <= n; j++) {             x = i - K + 1, y = j - K + 1;             t = s[i][j] - s[x - 1][j] - s[i][y - 1] + s[x - 1][y - 1];             if (t <= K * K / 2)                 return true;         }     return false; } int main() {     scanf("%d%d", &n, &K);     for (int i = 1; i <= n; i++)         for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]), t[++le] = a[i][j];     sort(t + 1, t + le + 1);     le = unique(t + 1, t + le + 1) - t - 1;     L = 1, R = le;     while (L <= R) {         mid = L + R >> 1;         if (chk(t[mid]))             res = mid, R = mid - 1;         else             L = mid + 1;     }     printf("%d", t[res]); }

移动棋子

((2n+1)times(2n+1)) 的棋盘，行、列的编号都为 (0,1,cdots,2n) ，棋盘上有 (m) 个棋子。

在 ((0,n)) 开始移动。设当前在 ((i,j))

若 ((i+1,j)) 没有棋子且没有出界，可以移动到 ((i+1,j))
若 ((i+1,j-1)) 没有棋子且没有出界，可以移动到 ((i+1,j-1))
若 ((i+1,j+1)) 没有棋子且没有出界，可以移动到 ((i+1,j+1))

求能到达第 (2n) 行的位置的数量，(nle 10^9,mle 2times 10^5)

最终的答案可以转换为起点最后能否到达一些纵坐标。（一直往下走即可）

用 set 维护，排序后依次处理，设当前棋子在 ((x,y))

(y-1) 或 (y+1) 能到，且 (y) 不能到，则需要加入 set
(y-1) 和 (y+1) 都不能到，且之前 (y) 能到，则需要从 set 中删除

答案为最终集合大小，(O(mlog m))

注意同一行需要同时处理，暂存一下即可

#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 4e5 + 5; int n, m, res, b[N], c[N], t1, t2; struct P { int x, y; } a[N]; set<int> s; inline int f(int x) { return s.find(x) != s.end(); } int main() {     scanf("%d%d", &n, &m);     for (int i = 1; i <= m; i++) scanf("%d%d", &a[i].x, &a[i].y);     sort(a + 1, a + m + 1, [](P A, P B) { return A.x ^ B.x ? A.x < B.x : A.y < B.y; });     s.insert(n);     for (int i = 1, y; i <= m + 1; i++) {         if (a[i].x ^ a[i - 1].x) {             while (t1) s.insert(b[t1--]);             while (t2) s.erase(c[t2--]);         }         if (i > m) break;         y = a[i].y;         if ((f(y - 1) || f(y + 1)) && !f(y)) b[++t1] = y;         if ((!f(y - 1) && !f(y + 1)) && f(y)) c[++t2] = y;     }     res = s.size();     printf("%d", res); }

清理花园

(n) 个数 (a_i) ，初始可以删除最多 (K) 个数

一次操作为选出最大的 (a_i) ，删除所有大于 (frac{max}{2}) 的数。

求最小化操作次数的前提下，最少删除数的个数，(nle 2times 10^5)

排序，设 (f_{i,j}) 为前 (i) 个用了 (j) 次操作最少删除，其中 (1le jlelog_2 a)

则 (f_{i,j}=min(f_{i-1,j}+1,f_{k,j-1})) ，(k) 表示高度不超过 (frac{a_i}{2}) 的数的编号

转移为 (O(1)) ，状态数 (O(nlog n)) ，总 (O(nlog n))

#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 2e5 + 5, INF = 0x3f3f3f3f; int n, K, a[N], f[N][35], mx; int main() {     scanf("%d%d", &n, &K);     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);     sort(a + 1, a + n + 1);     memset(f, 0x3f, sizeof(f));     f[0][0] = 0;     for (int i = 1, k; i <= n; i++) {         k = upper_bound(a + 1, a + n + 1, a[i] / 2) - a - 1;         mx = log2(a[i]) + 1;         f[i][0] = f[i - 1][0] + 1;         for (int j = 1; j <= mx; j++)             f[i][j] = min(f[i - 1][j] + 1, f[k][j - 1]);     }     for (int i = 0; i <= mx; i++)         if (f[n][i] < INF && f[n][i] <= K)             return printf("%d %d", i, f[n][i]), 0; }

疫情延迟

(n) 点 (m) 边的有向图，一条边为 ((u,v,w,k)) ，其中 (k) 表示这一条边的年龄

要求删除一些边，使的从 1 到 (n) 的最短路 (disge T) ，求删除边的最大年龄最小

(n,mle 10^5)

又是二分，二分删除的最大年龄，则所有 (k>mid) 的边都可以走，算最短路

若 (disge T) 则 (mid) 可行且可以更小，否则需要增大，(O(nlog nlog m))

#include <bits/stdc++.h> using namespace std; typedef unsigned long long uLL; typedef long double LD; typedef long long LL; typedef double db; const int N = 2e5 + 5, INF = 0x3f3f3f3f; int n, m, T, lst[N], Ecnt, L, R, b[N], le, mid, res, dis[N], vis[N]; struct Ed { int to, nxt, qz, cs; } e[N]; inline void Ae(int fr, int go, int vl, int k) {     e[++Ecnt] = (Ed){ go, lst[fr], vl, k }, lst[fr] = Ecnt; } struct P {     int x, d;     bool operator < (P A) const {         return d > A.d;     } }; priority_queue<P> Q; inline bool chk(int val) {     memset(dis, 0x3f, sizeof(dis));     memset(vis, 0, sizeof(vis));     dis[1] = 0;     Q.push((P){ 1, 0 });     while (!Q.empty()) {         int u = Q.top().x; Q.pop();         if (vis[u]) continue;         vis[u] = 1;         for (int i = lst[u], v; i; i = e[i].nxt)             if (dis[u] + e[i].qz < dis[v = e[i].to] && e[i].cs > val)                 dis[v] = dis[u] + e[i].qz, Q.push((P){ v, dis[v] });     }     return dis[n] >= T; } int main() {     scanf("%d%d%d", &n, &m, &T);     for (int i = 1, u, v, w, k; i <= m; i++)         scanf("%d%d%d%d", &u, &v, &w, &k), Ae(u, v, w, k), b[++le] = k;     if (chk(0)) return printf("-1 %d", dis[n]), 0;     sort(b + 1, b + le + 1);     le = unique(b + 1, b + le + 1) - b - 1;     L = 1, R = le, res = b[le] + 1;     while (L <= R) {         mid = L + R >> 1;         if (chk(b[mid]))             res = min(res, b[mid]), R = mid - 1;         else L = mid + 1;     }     printf("%d", res); }