zzqwtc

未归档

题解(3)

/ 注册

全部文章 / 未归档（共54篇）

贪心问题选做

区间问题区间选点给定 N N N个闭区间 [ a i , b i ] [ai,bi] [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。位于区间端点上的点也算作区间内。输入格式第一行包含整数N，表示区间数。接下来 N ...

2021-01-25

0 619

Codeforces - 1463C. Busy Robot （思维）

Busy Robot 题意机器人初始在一数轴上的原点某时刻接受命令并朝命令方向前进每秒前进1距离在未到达当前命令的终点时忽略当前时刻的其他命令若机器人在 [ t i , t i + 1 ] [t_i,t_{i+1}] [ti,ti+1] 时间内移动到 x i x_i xi...

2021-01-25

0 568

离散化部分

离散化 ①：要求保序排序、判重、二分 vector<int>alls; int find(int x){ //二分 int l = 0, r = alls.size(); while(l < r){ int mid = l+...

2021-01-25

0 495

线段树部分

线段树基本操作 query() int query(int u, int l, int r) { //查询操作 if (tr[u].l >= l && tr[u].r <= r)return tr[u].v; //树中节点已经被完全包含在[l,r]中 i...

2021-01-25

0 470

组合数部分

组合数定义 C a b = a ! b ! ( a − b ) ! C^{b}_{a} = \frac{a!}{b!(a-b)!} Cab=b!(a−b)!a! 带模数数据范围(a 、b较小) 1 ≤ n ≤ 10000 1≤n≤10000 1≤n≤10000, 1 ≤ b ≤ ...

2021-01-25

0 416

FloodFill和最短路

FloodFill AcWing1097. 池塘计数农夫约翰有一片 N ∗ M N∗M N∗M 的矩形土地。最近，由于降雨的原因，部分土地被水淹没了。现在用一个字符矩阵来表示他的土地。每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。现在，约翰想知道他...

2021-01-25

0 458

多源BFS-双端队列广搜

多源BFS AcWing173. 矩阵距离给定一个N行M列的01矩阵A， A [ i ] [ j ] A[i][j] A[i][j] 与 A [ k ] [ l ] A[k][l] A[k][l] 之间的曼哈顿距离定义为： d i s t ( A [ i ] [ j ] , A [ k ...

2021-01-25

0 477

双向广搜和A-star

两种算法解决从起点到终点状态过多的问题（BFS剪枝）双向广搜双向广搜实际是 B F S BFS BFS的一种剪枝形式实现方式是 <mark>同时从起点和终点搜索到相遇为止</mark> AcWing190. 字串变换已知有两个字串 A A A, B B B...

2021-01-25

0 581

DFS之连通性和搜索顺序

连通性 Acwing 1112. 迷宫一天 E x t e n s e Extense Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由 n∗n 的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当 E x t e n s e Exten...

2021-01-25

0 367

DFS之剪枝

常用的几种剪枝策略 1.优化搜索顺序大部分情况下我们应该优先搜索分支较少的节点例如分组问题可以先从花费较大的元素搜索可以减少状态分支 2.排除等效冗余如果不考虑顺序的话尽量用组合的方式搜索即与组内元素顺序无关 3.可行性剪枝在搜索过程中已经检测到不合法可以提前退出...

2021-01-25

0 557