国旗计划:原题链接题意: 输入:第一行给你一个n和m,n代表边防战士的人数,m代表总共有几个站点,接下来有n行,每行给你两个站点C和D,战士行走的区间为[C,D],区间会重叠,但不会完全覆盖。 输出:输出每个战士,在以他自身的区间为起点的前提下,至少需要多少人可以使战士之间行走的区间形成一个环。做题思路: 初步入手本题,可以想到如果要判断成环,最好的办法是将环拆分成链,即当右边的点小于左边的点时,说明该点跨过了环,因此将右边的点加上站点总数,即可生成假设在一条链上的两点间的距离。初始输入代码: cin >>n>>m; for (int i=1;i<=n;i++) { cin >>w[i].l>>w[i].r; //破环成链 if (w[i].r<w[i].l)w[i].r+=m; } 在生成完链后,题目要求也变成了找到覆盖3-10的这个区间,问题是该怎么求解,找到最少的人数去覆盖这个区间,这里可以先试用贪心的思想进行思考,因为战士之间的区间是不会完全覆盖的,所以只要每次是下一个选中区间的起点是当前区间中,最靠近选择区间末的区间,即可完成最少人数成环这一条件。 以此为依据,在原先来链的基础上,再copy(复制)一份每个区间都加上一个环时的情况,用以判断当区间跨过环时,存在2-5的区间,但无法求解的情况,同时,因为题目只规定了战士不会被完全覆盖,但其顺序可能是被打乱的,所以为了满足区间查找的单调性,对数组进行sort排序。改进后输入代码: //输入+处理 cin >>n>>m; for (int i=1;i<=n;i++) { //记录id,在输出结果时,是原序输出 w[i].id=i; cin >>w[i].l>>w[i].r; //破环成链 if (w[i].r<w[i].l)w[i].r+=m; } //起点排序 sort(w+1,w+n+1); //复制一份 n2=n*2; for (int i=n+1;i<=n2;i++) { w[i]=w[i-n]; w[i].l+=m; w[i].r+=m; } 接下来是查找区间,但注意,如果直接查找区间会导致是o(n^2)的时间复杂度,也就是超时,因此需要优化区间查找,为此,来到本次题解的重中之中,倍增(st)。 在使用倍增前,先了解倍增的使用条件:必须要有单调性,很显然,这个条件已经满足。 其次是倍增的原理:同二分一样,二分的作用是不断缩减数组,以此来找到需要的数,而倍增则是不断增大。它的运算原理可以参考二进制定理:2^n=2^(n-1)+2^(n-2)+...+2^0+1。 因此其运行规则为:先走2^n步,倘若大于等于数值则说明步数过多,倘若小于,将将步数加上2^n,加至最后,加起来的总步数会是要求步数-1的值。st的代码://贪心选择区间+st生成静态数据void st(){ //自建图: int next=1; //链上共n2条 for (int i=1;i<=n2;i++) { //找到每个区间离右端点最近的左端点所在的区间 while (next <= n2 && w[next].l<= w[i].r)next++; //记录区间 go[i][0]=next-1; } //倍增:i = 1,2,4,8,16..共 logn 次 for (int i=1;(1 << i)<=n;i++) { //枚举每条线段 for (int s=1;s<=n2;s++) { //若走2^3步,2^3= 2^2+2^2 //先从 s 到走2^2步到中转站 //再从中转站走2^2到终点 go[s][i]=go[go[s][i-1]][i-1]; } }} 构建完图后,即可运用图表进行求解每位士兵的最少人数,即st的调用。//st的使用 void getRes(int x){ //len为终点长度,该长度代表能否成环 //now为初始的节点 //ans记录人数,因为放入了自身的初始节点,所以人数至少为1 int len=w[x].l+m,now=x,ans=1; //i初始为log2(n),20是为了方便计算 for (int i=20;i>=0;i--) { //从大到小开始查找 int to=go[now][i]; //当to存在,长度在len内 if (to && w[to].r<len) { ans=ans+(1<<i); //累加跳过的区域 now=to;//从新位置开始 } } //记录时使用id记录人数,毕竟sort过了,但输出要使用原序列 //ans+1因为ans是小于len的,还无法成环, //但因为st性质,他的下一步必定大于len,此时可以成环 res[w[x].id]=ans+1;} 最后直接输出存入的数值,即可得出答案,这里直接放ac代码:#include <bits/stdc++.h>using namespace std;const int maxn = 4e5 + 10;int n, n2, m;struct Index{ int id,l,r;//编号+区间 //以起始点小的排序 bool operator<(const Index &b) const { return l< b.l;}};Index w[maxn*2];//破环成链,因此空间需要开两份int go[maxn][25];//倍增记录自建图int res[maxn];//记录结果//贪心选择区间+st生成静态数据void st(){ //自建图: int next=1; //在链上选择共n2条 for (int i=1;i<=n2;i++) { //每个区间的下一个右端点最大的区间 while (next <= n2 && w[next].l<= w[i].r)next++; //区间i的下一个区间 go[i][0]=next-1; } //倍增:i = 1,2,4,8,16..共 logn 次 for (int i=1;(1 << i)<=n;i++) { //枚举每条线段 for (int s=1;s<=n2;s++) { //若走 2^3 步,2^3= 2^2+2^2 //先从 s 到走2^2步到中转站 //再从中转站走2^2到终点 go[s][i]=go[go[s][i-1]][i-1]; } }}//st的使用 void getRes(int x){ //len为终点长度,该长度代表能否成环 //now为初始的节点 //ans记录人数,因为放入了自身的初始节点,所以人数至少为1 int len=w[x].l+m,now=x,ans=1; //i初始为log2(n),20是为了方便计算 for (int i=20;i>=0;i--) { //从大到小开始查找 int to=go[now][i]; //当to存在,长度在len内 if (to && w[to].r<len) { ans=ans+(1<<i); //累加跳过的区域 now=to;//从新位置开始 } } //记录时使用id记录人数,毕竟sort过了,但输出要使用原序列 //ans+1因为ans是小于len的,还无法成环, //但因为st性质,他的下一步必定大于len,此时可以成环 res[w[x].id]=ans+1;}int main(){ //输入+初步处理 cin >>n>>m; for (int i=1;i<=n;i++) { w[i].id=i; cin >>w[i].l>>w[i].r; //破环成链 if (w[i].r<w[i].l)w[i].r+=m; } //起点排序 sort(w+1,w+n+1); //复制一份 n2=n*2; for (int i=n+1;i<=n2;i++) { w[i]=w[i-n]; w[i].l+=m; w[i].r+=m; } //倍增(st)开始 st(); //循环得出每个节点的最少成环人数 for (int i=1;i<=n;i++)getRes(i); //输出答案 for (int i=1;i<=n;i++)cout <<res[i]<<" "; cout <<"\n"; return 0;}