解题报告：Codeforces 279C Ladder

Codeforces 279C Ladder

本题与tbw这篇博客上的题有相似思路。tbw的本来我还不会，抄了题解才过，这道题好歹自己磕半天磕出来了。到tbw做那道题我突然想明白了，再一想诶跟这里不是一样的嘛，lol。然后就被他逼着过来写题解，痛得一批。

题意

对于一段序列，要求刚开始不能递减，之后不能递增。换言之，只能有一个波峰，不能有波谷，可以是一条平平的线。

俺的思路

来一个数组ndec[]，记录某一个点之后的下降点。

再来一个数组ninc[]，记录某一个点之后的上升点。

 +-----------------+              +-----------------+

 |                 |              |        * *      |

 |      *     * *  |              |*     *    *    *|

 |    *   * *     *|              |  * *       * *  |

 |* *              |              |                 |

 +-----------------+              +-----------------+

  1 2 3 4 5 6 7 8 9                1 2 3 4 5 6 7 8 9

          ^       ^                      ^ ^       ^

d 5 5 5 5 9 9 9 9 ?              i 4 4 4 5 9 9 9 9 ?

注意不管上升、下降是否连续，只要比前一点大就认为是上升点，比前一点小就认为是下降点。

并且一定要记录下一个，不要记自己。

fill0(ninc);

fill0(ndec);

forward(i,2,n){

	if(a[i]>a[i-1])ninc[i]=1;

	if(a[i]<a[i-1])ndec[i]=1;

}

ll tmpi = INF, tmpd = INF, flagi, flagd;

backward(i,n,1){

	flagi = ninc[i];

	ninc[i] = tmpi;

	if(flagi==1)tmpi=i;

	flagd = ndec[i];

	ndec[i] = tmpd;

	if(flagd==1)tmpd=i;

}

俺已经忘记这都是些什么鬼画符了……

之后怎么判断一个区间是否OK呢？

 +-----------------+              +-----------------+

 |                 |              |                 |

 |      *     * *  |              |      *     * *] |

 |   [*   *]*     *|              |   [*   * *     *|

 |* *              |              |* *              |

 +-----------------+              +-----------------+

  1 2 3 4 5 6 7 8 9                1 2 3 4 5 6 7 8 9

d         ^       ^              d         ^       ^

      *-->*                            *-->*

i     ^ ^     ^                  i     ^ ^     ^

          *-->*                            *-->*

      l   r   ^OK                      l       ^ r NO

我们找l点之后的一个下降点，即ndec[l]。那么从l到这玩意之前都是一段非降序列。

如果ndec[l]\(>\)r，说明l到r之间都是非降序列，是合法的。
如果ndec[l]\(\le\)r，说明前半段是非降，那么就要求从ndec[l]开始的后半段非增。直接再往后找一个上升点，即ninc[ndec[l]]。
- 如果ninc[ndec[l]]\(>\)r，类似上面所述，是OK的。
- 如果ninc[ndec[l]]\(\le\)r，说明上升之后开始下降、结果还没出区间又开始上升了，炸裂。

好像没提到全程非升的情况？比如有a[l+1]\(<\)a[l]，

那样ndec[l]\(=\)l+1，就合并到“前半段非降”的情况（前半段指\([l,l]\)）。

if(ndec[x]>y||ninc[ndec[x]]>y){

	cout<<"Yes"<<endl;

}

else{

	cout<<"No"<<endl;

}

查询直接干到\(O(1)\)。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

#define wlf(i,a,b) for(ll i=a;i<=b;++i)

#define tbw(i,a,b) for(ll i=a;i>=b;--i)

#define fill0(b) memset(b,0,sizeof(b))

#define fill1(b) memset(b,-1,sizeof(b))

#define fill3f(b) memset(b,0x3f,sizeof(b))

const ll INF = 0x3f3f3f3f3f3f3f3f;

const ll N = 1e5+10;

ll n,m,a[N],ninc[N],ndec[N];

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0);cout.tie(0);

	cin>>n>>m;

	wlf(i,1,n)cin>>a[i];

	fill0(ninc);

	wlf(i,2,n){

		if(a[i]>a[i-1])ninc[i]=1;

		if(a[i]<a[i-1])ndec[i]=1;

	}

	ll tmpi = INF, tmpd = INF, flagi, flagd;

	tbw(i,n,1){

		flagi = ninc[i];

		ninc[i] = tmpi;

		if(flagi==1)tmpi=i;

		flagd = ndec[i];

		ndec[i] = tmpd;

		if(flagd==1)tmpd=i;

	}

	while(m--){

		ll x,y;

		cin>>x>>y;

		if(ndec[x]>y||ninc[ndec[x]]>y){

			cout<<"Yes"<<endl;

		}

		else{

			cout<<"No"<<endl;

		}

	}

	return 0;

}

巴特西

解题报告：Codeforces 279C Ladder

Codeforces 279C Ladder

题意

俺的思路

代码

最新文章

热门文章