优购物官方网站手机版,wordpress上传本地视频教程,做网站用花生壳哪个版本,网站开发前端php 后端python题目描述 给出一个圈和若干段#xff0c;问#xff1a;对于所有的 $i$ #xff0c;选择第 $i$ 段的情况下#xff0c;最少需要选择多少段#xff08;包括第 $i$ 段#xff09;能够覆盖整个圈#xff1f;输入 第1行#xff0c;包含2个正整数N,M#xff0c;分别表示边防…题目描述 给出一个圈和若干段问对于所有的 $i$ 选择第 $i$ 段的情况下最少需要选择多少段包括第 $i$ 段能够覆盖整个圈 输入 第1行包含2个正整数N,M分别表示边防战士数量和边防站数量。 随后n行每行包含2个正整数。其中第i行包含的两个正整数Ci、Di分别表示i号边防战士常驻的两个边防站编号 Ci号边防站沿顺时针方向至Di号边防站力他的奔袭区间。数据保证整个边境线都是可被覆盖的。 输出 输出数据仅1行需要包含n个正整数。其中第j个正整数表示j号边防战士必须参加的前提下至少需要 多少名边防战士才能顺利地完成国旗计划 样例输入 4 8 2 5 4 7 6 1 7 3 样例输出 3 3 4 3 题解 倍增 如果将选择的区间按照右端点正方向顺序考虑的话那么如果选择了某个区间下一个区间的选择一定是所有左端点小于等于该区间右端点中右端点最靠后的那一个。 因此首先断环成链然后选择区间 $[l,r]$ 后下一个选择就应该是左端点在 $[1,r]$ 范围内右端点最靠后的。 所以对于每一个区间 $[l,r]$ 在 $l$ 位置上加入 $r$ 然后求前缀最大值即可得到每个位置选上一个区间后最远能够覆盖到哪。 我们要求的是覆盖整个圈因此可以考虑倍增算法预处理出 $f[i][j]$ 表示从 $j$ 位置选择 $2^i$ 段区间最远能够覆盖到哪。那么上面的全椎最大值就是 $f[0][j]$ 。 根据递推式 $f[i][j]f[i-1][f[i-1][j]]$ 预处理出 $f$ 数组然后倍增求解。从大到小枚举 $i$ 如果加入一段不能覆盖整个圈则加入否则不加入。最后加上2本身无限逼近后剩余的一段即为答案。 注意一下区间跨越 $m$ 的处理 详见代码。 时间复杂度 $O(n\log n)$ #include cstdio
#include cstring
#include algorithm
#define N 200010
#define pos(x) lower_bound(v 1 , v m 1 , x) - v
using namespace std;
int a[N] , b[N] , v[N 1] , f[20][N 2];
int main()
{int n , m 0 , i , j , t , ans;scanf(%d%*d , n);for(i 1 ; i n ; i ) scanf(%d%d , a[i] , b[i]) , v[m] a[i] , v[m] b[i];sort(v 1 , v m 1);for(i 1 ; i n ; i ){a[i] pos(a[i]) , b[i] pos(b[i]);if(a[i] b[i]){f[0][a[i]] max(f[0][a[i]] , b[i]);f[0][a[i] m] max(f[0][a[i] m] , b[i] m);}else{f[0][1] max(f[0][1] , b[i]);f[0][a[i]] max(f[0][a[i]] , b[i] m);f[0][a[i] m] max(f[0][a[i] m] , m 1);}}for(i 1 ; i m 1 ; i ) f[0][i] max(f[0][i] , f[0][i - 1]);for(t 1 ; (1 t) m 1 ; t )for(i 1 ; i m 1 ; i )f[t][i] f[t - 1][f[t - 1][i]];for(i 1 ; i n ; i ){ans 0;if(a[i] b[i]) a[i] m;for(j t - 1 ; ~j ; j -- )if(f[j][b[i]] a[i])ans (1 j) , b[i] f[j][b[i]];printf(%d , ans 2);if(i n) printf( );}return 0;
}转载于:https://www.cnblogs.com/GXZlegend/p/8029235.html
