? 优质资源分享 ?
学习路线指引(点击解锁) | 知识定位 | 人群定位 |
---|---|---|
? Python实战微信订餐小程序 ? | 进阶级 | 本课程是python flask+微信小程序的完美结合,从项目搭建到腾讯云部署上线,打造一个全栈订餐系统。 |
?Python量化交易实战? | 入门级 | 手把手带你打造一个易扩展、更安全、效率更高的量化交易系统 |
盖房子
n×nn×nn\times n 的矩形中选出一个边长为 k×kk×kk\times k 的子矩阵,使得中位数最小
中位数定义为子矩阵中第 ⌊k22⌋+1⌊k22⌋+1\lfloor\dfrac{k^2}{2}\rfloor+1 大的数,n≤800n≤800n\le 800
比较显然的二分,二分答案 midmidmid 。另 bi,j=[ai,j>mid]bi,j=[ai,j>mid]b_{i,j}=[a_{i,j}>mid] ,作二维前缀和
如果 bbb 存在子矩阵使得 s≤⌊k22⌋s≤⌊k22⌋s\le\lfloor\dfrac{k^2}{2}\rfloor ,则 midmidmid 可行且可以缩小,反之需要增大,O(n2logn2)O(n2logn2)O(n^2\log n^2)
复制代码
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
#include 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 val); for (int i = K, x, y, t; i > 1; if (chk(t[mid])) res = mid, R = mid - 1; else L = mid + 1; } printf("%d", t[res]); }
移动棋子
(2n+1)×(2n+1)(2n+1)×(2n+1)(2n+1)\times(2n+1) 的棋盘,行、列的编号都为 0,1,⋯,2n0,1,⋯,2n0,1,\cdots,2n ,棋盘上有 mmm 个棋子。
在 (0,n)(0,n)(0,n) 开始移动。设当前在 (i,j)(i,j)(i,j)
- 若 (i+1,j)(i+1,j)(i+1,j) 没有棋子且没有出界,可以移动到 (i+1,j)(i+1,j)(i+1,j)
- 若 (i+1,j−1)(i+1,j−1)(i+1,j-1) 没有棋子且没有出界,可以移动到 (i+1,j−1)(i+1,j−1)(i+1,j-1)
- 若 (i+1,j+1)(i+1,j+1)(i+1,j+1) 没有棋子且没有出界,可以移动到 (i+1,j+1)(i+1,j+1)(i+1,j+1)
求能到达第 2n2n2n 行的位置的数量,n≤109,m≤2×105n≤109,m≤2×105n\le 10^9,m\le 2\times 10^5
最终的答案可以转换为起点最后能否到达一些纵坐标。(一直往下走即可)
用 set
维护,排序后依次处理,设当前棋子在 (x,y)(x,y)(x,y)
- y−1y−1y-1 或 y+1y+1y+1 能到,且 yyy 不能到,则需要加入
set
- y−1y−1y-1 和 y+1y+1y+1 都不能到,且之前 yyy 能到,则需要从
set
中删除
答案为最终集合大小,O(mlogm)O(mlogm)O(m\log m)
注意同一行需要同时处理,暂存一下即可
复制代码
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
#include 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
清理花园
nnn 个数 aiaia_i ,初始可以删除最多 KKK 个数
一次操作为选出最大的 aiaia_i ,删除所有大于 max2max2\frac{max}{2} 的数。
求最小化操作次数的前提下,最少删除数的个数,n≤2×105n≤2×105n\le 2\times 10^5
排序,设 fi,jfi,jf_{i,j} 为前 iii 个用了 jjj 次操作最少删除,其中 1≤j≤log2a1≤j≤log2a1\le j\le\log_2 a
则 fi,j=min(fi−1,j+1,fk,j−1)fi,j=min(fi−1,j+1,fk,j−1)f_{i,j}=\min(f_{i-1,j}+1,f_{k,j-1}) ,kkk 表示高度不超过 ai2ai2\frac{a_i}{2} 的数的编号
转移为 O(1)O(1)O(1) ,状态数 O(nlogn)O(nlogn)O(n\log n) ,总 O(nlogn)O(nlogn)O(n\log n)
复制代码
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
#include 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
疫情延迟
nnn 点 mmm 边的有向图,一条边为 (u,v,w,k)(u,v,w,k)(u,v,w,k) ,其中 kkk 表示这一条边的年龄
要求删除一些边,使的从 1 到 nnn 的最短路 dis≥Tdis≥Tdis\ge T ,求删除边的最大年龄最小
n,m≤105n,m≤105n,m\le 10^5
又是二分,二分删除的最大年龄,则所有 k>midk>midk>mid 的边都可以走,算最短路
若 dis≥Tdis≥Tdis\ge T 则 midmidmid 可行且可以更小,否则需要增大,O(nlognlogm)O(nlognlogm)O(n\log n\log m)
复制代码
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
#include 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 A.d; } }; priority_queue 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 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 > 1; if (chk(b[mid])) res = min(res, b[mid]), R = mid - 1; else L = mid + 1; } printf("%d", res); }
总结
- 二分不要打挂,注意
check
- 注意情况考虑全
- nnn 在 10510510^5 级也不要放弃
DP
转载请注明:xuhss » 202206007 模拟赛 总结