Loading... ## 分治算法 （持续更新） > 最小值最大，二分 --- ### problem 1 #### [愤怒的牛](https://www.luogu.org/problemnew/show/P2678) n个点，取出m个点使得相邻的点的最小距离最大 $n\leq 10^5, m\leq n$ - 最小距离最大 - 如果太大了，会选不出m个点 - 限制的最小距离越大，选出的点越少 - 符合二分性质 #### 题解 - 二分最小距离k，然后贪心验证。 - 首先第一个点必须取，然后后面的点超过k就取。 - 最后看能不能取完m个点。 - 复杂度$O(nlog_2n)$ - 代码如下： ```cpp #include<bits/stdc++.h> using namespace std; int n, m, d, a[50010]; bool judge(int x){ int tot = 0; int i = 0; int now = 0; while (i < n+1){ i++; if (a[i] - a[now] < x) tot++; else now = i; } if (tot > m) return false; else return true; } int main(){ cin>>d>>n>>m; for(int i = 1; i <= n; i++){ cin>>a[i]; } a[n + 1] = d; int l = 1,r = d,res = 0; while(l <= r){ int mid=(l + r) / 2; if(judge(mid)){ res = mid; l = mid + 1; } else{ r = mid - 1; } } cout<<res; return 0; } ``` --- ### problem 2 #### [Slicing](https://www.luogu.org/problemnew/show/P3017) 给定$n\times m$的数字矩阵，要求横着切$A - 1$刀，对每块再竖着切$B-1$刀。 使得最小子矩阵最大。 $n,m\leq 500$ #### 题解 - 二分，然后贪心切 - 每次扫一行，看这行和上次切割的行之间能否满足二分条件k，如果能就横切+1，最后看可行条能否到n。 - 代码如下： ```cpp #include<bits/stdc++.h> using namespace std; int r, c, aa, bb; int a[509][509], sum[509][509]; int ans; bool check(int x){ int num = 0, now = 0; for(int i = 1; i <= r; i++){ int s = 0, cnt = 0; for(int j = 1; j <= c; j++){ if(s + sum[i][j] - sum[i][j-1] - sum[now][j] + sum[now][j-1] < x) s += sum[i][j] - sum[i][j-1] - sum[now][j] + sum[now][j-1]; else{ cnt++; s = 0; } } if(cnt >= bb){ num++; now = i; } } if(num >= aa) return 1; else return 0; } int main(){ scanf("%d%d%d%d", &r, &c, &aa, &bb); for(int i = 1; i <= r; i++){ for(int j = 1; j <= c; j++){ scanf("%d", &a[i][j]); sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j]; } } int ll = 0, rr = sum[r][c]; while(ll <= rr){ int mid = (ll + rr) / 2; if(check(mid)){ ll = mid + 1; } else rr = mid - 1; } printf("%d\n", ll - 1); return 0; } ``` --- ### problem 4 #### [花盆](https://www.luogu.org/problemnew/show/P2698) 给出n个点坐标，根据x轴选定区间$[L,R]$，使得其中的点的y值的最大和最小之差>=D。求$min\{R-L\}$ $n\leq 10^5$ #### 题解 二分枚举区间大小，然后通过单调队列求出每个区间最大值和最小值，最后得出答案即可。 ```cpp #include<bits/stdc++.h> using namespace std; int n, d; struct node{ int x, y; }a[100009]; bool cmp(const node &a, const node &b){ return a.x < b.x; } int qmin[100009], qmini[100009], qmax[100009], qmaxi[100009]; int headmin, tailmin, headmax, tailmax; bool check(int x){ headmin = headmax = 1; tailmin = tailmax = 0; for(int i = 1; i <= n; i++){ while(headmin <= tailmin && qmin[tailmin] >= a[i].y) tailmin--; qmin[++tailmin] = a[i].y; qmini[tailmin] = a[i].x; while(headmin <= tailmin && qmini[headmin] < qmini[tailmin] - x) headmin++; while(headmax <= tailmax && qmax[tailmax] <= a[i].y) tailmax--; qmax[++tailmax] = a[i].y; qmaxi[tailmax] = a[i].x; while(headmax <= tailmax && qmaxi[headmax] < qmaxi[tailmax] - x) headmax++; int cz = qmax[headmax] - qmin[headmin]; if(cz >= d) return true; } return false; } int main(){ scanf("%d%d", &n, &d); for(int i = 1; i <= n; i++){ scanf("%d%d", &a[i].x, &a[i].y); } sort(a + 1, a + n + 1, cmp); int l = 1, r = a[n].x + 5; while(l < r){ int mid = (l + r) / 2; if(check(mid)){ r = mid; } else l = mid + 1; } if(l > a[n].x) printf("%d\n", -1); else printf("%d\n", l); return 0; } ``` --- ### problem 5 #### [组题](https://www.luogu.org/problemnew/show/UVA1451) - 给出一个长度为n的序列，求一段长度大于等于k的字串。 - 使得它们的平均值最大。 - $n\leq 10^5, k\leq n$ #### 题解 - 分数规划，二分答案（平均值） - 让每个数减去平均值，检测是否有一个长度大于等于k的字串，使其和为非负。 - 平均值问题转化为求和问题。 - 把区间和转化为前缀和相减的形式。 - 枚举右端点i，判定的就是$sum[i]-min\{sum[j]\}(0\leq j\leq i-k)$是否大于等于0。 - 代码如下： ```cpp #include<bits/stdc++.h> using namespace std; int T, n, len; double a[100009], a1[100009], sum[100009]; const double jd = 1e-5; bool check(double x, bool op){ int ansl, ansr; double ans = -0x3f3f3f3f; for(int i = 1; i <= n; i++) a1[i] = a[i] - x; for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a1[i]; double minx = 0x3f3f3f3f, l; for(int i = len; i <= n; i++){ if(sum[i - len] <= minx) l = i - len + 1; minx = min(minx, sum[i - len]); if(sum[i] - minx > ans + jd){ ans = sum[i] - minx; ansl = l; ansr = i; } } if(op == 1) printf("%d %d\n", ansl, ansr); return ans >= 0; } int main(){ scanf("%d", &T); while(T--){ scanf("%d%d", &n, &len); string s; cin>>s; for(int i = 1; i <= n; i++){ a[i] = s[i - 1] - '0'; } double l = 0, r = 1; while(l < r - jd){ double mid = (l + r) / 2; if(check(mid, 0)) l = mid; else r = mid; } check(l + jd, 1); } return 0; } ``` --- ### problem 6 #### 猜数 - 给一个长度为n的数列，但不知道这个数列。 - 有q条限制条件$l_i,r_i,x_i$，表示$(l,r)$所有数的最小值为x。 - 问从第几个限制条件开始出现矛盾，无矛盾输出0。 - $n\leq 10^6,q\leq 25000$ - 例如：$(3,5)$最小值为2，$(1,7)$最小值为4，矛盾。 #### 题解 - 会矛盾的情况就是出现了包含关系，并且被包含的区间最小值更小。 - 先对区间按x排序 - 处理某个区间时，发现已经被之前的某个区间$(l,r)$包含了。矛盾。 --- ### problem 7 #### Tree - 给一个无向带权连通图，每条边是黑色或者白色。求一颗最小权的恰好有need条白色边的生成树。 - 题目保证有解，$n,m\leq 10^5$ #### 分析及题解 - 生成树权值变化时，白边数目可能变大或者变小。 - 不能直接二分。 ### problem 8 #### [电话线](https://www.luogu.org/problemnew/show/P1948) - 给出n个点m条边的DAG - 可以选择k条边，使其权值变为0 - 需要让1-n的最长路径最短 - $n,m\leq 50000$ --- ### problem 9 #### [Dynamite](https://www.luogu.org/problemnew/show/P3523) - 给出一颗n个节点的树，上面有k个关键节点。 - 树上选m个点，求最小化关键节点到选择点的最大距离。 - $n\leq 10^5$ #### 分析 - 二分一个数L表示答案 - 问题转化为一个判定问题，判定能否用m个点覆盖（范围为L）整个树上的关键点。 - 树形DP，考虑子树情况： 1. 子树内关键点都覆盖完了，并且子树内有选择点的贡献可以向上。 2. 子树内有不被覆盖的点，没有节点可以继续贡献。 3. 子树内都被覆盖，但没有对上面的贡献 --- ## 搜索算法 ### problem 1 #### 装箱 - n个物品，每个物品大小为$w_i$。箱子大小为m，求最少箱子数目，能装下所有物品。 #### 分析，题解 - 搜索每一个物品，装入到之前能装的箱子中，或者开一个新的箱子，$dfs(x)$代表搜到了第几个物品。 - 物品从大到小排序，再依次搜索。 - 当前搜到了最优解已经为$m$，那么当前步数$>=m$可以直接return，因为不会最优。 - 进一步剪枝。 - 考虑没有搜的物品的总和减去没有被填满的空间/m就是至少要新开的箱子的空间。然后新箱子数+已有箱子数>=m就可以剪掉。 - 排序和预估下界都是常见剪枝技巧。 - 另外一种方法： - 先贪心一遍，求出较优解，然后进行搜索-最优性剪枝。 --- ### problem 2 #### 天平 - 有n个砝码$(n\leq 1000)$，重量为$w[i]$. - 从中选择一些砝码，使得这些砝码总重量最大，但不超过c。 - $w[i]$按照递增顺序给出并且保证$w[i]>=w[i-1]+w[i-2]$ #### 分析题解 - 因为$w[i]>=w[i-1]+w[i-2]$,所以n实际上是45左右（斐波那契）。 - dfs(int k, int tot)//搜到第k个数，当前总和是tot。 - 剪枝： 1. 优化选砝码（不跳过），并且优先选择重量大的砝码，尽早更新ans。 2. 如果当前tot + 剩下砝码的总重（前缀和） < ans，return。可行性剪枝。 - 折半搜索：n=40的一类子集问题， 1. $40=2\times 20$ 2. $n=20$类问题，二进制枚举即可。 3. 把40拆成两个20算。 4. 要求$n=40$时，有多少个子集的权值和大于等于L。 5. 物品分成前一半和后一半1 2 3 4|5 6 7 8 6. $2^{20}\{A\},2^{20}\{B\}$ 7. 合并左右两子集，得到完整的子集和。 8. 具体。。。没有懂，百度吧。。。 --- ### problem 3 #### 虫食算 如果这个算式是$N$进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的$0$到$N-1$这$N$个不同的数字：但是这$N$个字母并不一定顺序地代表$0$到$N-1$。输入数据保证$N$个字母分别至少出现一次。 ``` BADC +CBDA —————— DCCC ``` 上面的算式是一个4进制的算式。很显然，我们只要让$ABCDABCD$分别代表$01230123$，便可以让这个式子成立了。你的任务是，对于给定的$N$进制加法算式，求出$N$个不同的字母分别代表的数字，使得该加法算式成立。输入数据保证有且仅有一组解。 #### 分析&题解 - 从右往左依次尝试填充数字 - 剪枝 1. 在尝试放新的数字的时候，从n-1道0放会快很多。 2. 每次搜的时候，看自己左边的列如果三行都确定了的话，就检查是否合法。 --- ### problem 4 #### [循环赛](https://www.luogu.org/problemnew/show/P3154) - n个队伍进行循环赛，胜者得3分，平得1分，负得0分，现在给出各队分数，求可能的胜负情况数。 - $n\leq 8$ #### [分析](https://www.luogu.org/problemnew/solution/P3154) ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n; int a[9], tmp[9]; int totwin, totfl; bool cmp(const int &a, const int &b){ return a > b; } map<ll, ll> mapx; ll dfs(ll x, ll y){ ll sum = 0; if(x >= n) return 1; if(y > n){ if(tmp[x] != a[x]) return 0; int f[9]; for(int i = x + 1; i <= n; i++){ f[i] = a[i] - tmp[i]; } ll hash = 0; sort(f + x + 1, f + n + 1); for(int i = x + 1; i <= n; i++){ hash = hash * 27 + f[i]; } if(mapx[hash] != 0) return mapx[hash]; else return mapx[hash] = dfs(x + 1, x + 2); } if(tmp[x] + 3 <= a[x] && totwin){ tmp[x] += 3; totwin--; sum += dfs(x, y + 1); tmp[x] -= 3; totwin++; } if(tmp[y] + 3 <= a[y] && totwin){ tmp[y] += 3; totwin--; sum += dfs(x, y + 1); tmp[y] -= 3; totwin++; } if(tmp[x] + 1 <= a[x] && tmp[y] + 1 <= a[y] && totfl){ tmp[x]++, tmp[y]++, totfl--; sum += dfs(x, y + 1); tmp[x]--, tmp[y]--, totfl++; } return sum; } int main(){ int s = 0; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); s += a[i]; } sort(a + 1, a + n + 1, cmp); totwin = s - n * n + n; totfl = (n * n - n) / 2 - totwin; ll ans = dfs(1, 2); printf("%lld\n", ans); return 0; } ``` --- ## 迭代加深搜索 ### problem 1 #### [埃及分数](https://www.luogu.org/problemnew/show/UVA12558) 太难了吧。。。 --- ### problem 2 > P.S.其实刚刚打洛谷月赛去了，还是回来听听。 #### 骑士精神 在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士， 且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。 给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘： 为了体现出骑士精神，他们必须以最少的步数完成任务。  #### 分析&题解 最小步数这类，适合用迭代加深搜索。 用空格走代替骑士。 搜索时记录上一步防止来回走。 不需要每次判断是否都在位置，可以计算出不在对应位置的骑士有多少个。而且每次复原一个骑士至少需要一步。 --- ## 启发式搜索（A*） - $f[x]=g[x]+h[x]$ ### problem 1 #### k短路问题 - 给出一个图，和s，t，求s到t的第k短路。 - 考虑用搜索的遍历，搜出1-k短路。 #### [分析](https://www.luogu.org/problemnew/show/P2483) - $f[x] = g[x] + h[x]$ - $g[x]$就是遍历过程中，s走到x的距离。 - $h[x]$就是x到t的最短距离 - 预处理建反向图，求出t为起点的最短路。也就能得到每个点的$h[x]$ - 算法流程： 1. 维护一个优先队列，因为我们要取的是$f[x]$最优的点。 2. 最开始加入s到队列中。 3. 从队列中弹出$f[x]$最小的点。 4. 把和x相邻的点y，$g[y]=g[x]+w(x,y)$，$f[y]=g[y]+h[y]$，然后放入优先队列。 5. 如果弹出的点就是t，那我们就找到了一个解，并且tot++。 6. 当tot为k，即找到了第k小的路径。 Last modification：January 27, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏