?

【題目鏈接】?http://acm.hdu.edu.cn/showproblem.php?pid=5741

?

【題目大意】

　　一個01相間的串，以0開頭，給出的序列每個數(shù)字表示連續(xù)的0的個數(shù)或者1的個數(shù)，現(xiàn)在有m個詢問，求0的個數(shù)為a且1的個數(shù)為b的串是否存在。

?

【題解】

　　我們發(fā)現(xiàn)形如11001這樣子以1為開頭結(jié)尾的串是包含1001這樣子的串的，同理以0為開頭結(jié)尾的串也是包含了一些開頭結(jié)尾數(shù)字相同的子串。

　　可以發(fā)現(xiàn)，當(dāng)0的個數(shù)固定，1的個數(shù)是數(shù)軸上的一個區(qū)間，而且在0的個數(shù)相差1時，必定可以取到相同的1的個數(shù)，因此可行域在二維平面內(nèi)是一個實心的聯(lián)通圖，且上邊界和下邊界的點坐標單調(diào)非減。

　　那么我們首先計算出上下邊界的點，可以發(fā)現(xiàn)在0的個數(shù)固定的情況下，1的個數(shù)的上界一定是由1開始，1結(jié)尾的子串產(chǎn)生的，下界是由0開始，0結(jié)尾的子串產(chǎn)生的，那么保存這些點。

　　然而在圖形中兩個橫縱坐標都不相同的點就能夠確定一個矩形可行區(qū)域，因此，只要保留上下邊界坐標均單調(diào)遞增的點即可，二分查詢(a,b)是否在連通塊區(qū)域內(nèi)，就能夠判斷是否存在這樣子的子串

?

【代碼】

#include <cstdio> #include <utility> #include <climits> #include <algorithm> using namespace std; const int N=1010,M=N*N; typedef pair<int,int> PII; char ans[M]; int T,n,m,a,b,t[N],cntd,cntu,cnt; PII D[M],U[M]; int main(){scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d",&t[i]);cntd=cntu=cnt=0;for(int i=0;i<n;i++){int x=0,y=0;for(int j=i;j<n;j++){if(j%2)y+=t[j];else x+=t[j];if(i%2==0&&j%2==0)D[cntd++]=PII(x,y);if(i%2&&j%2)U[cntu++]=PII(x,y);}}sort(D,D+cntd);for(int i=0,j;i<cntd;i=j){for(j=i;j<cntd&&D[i].first==D[j].first;j++);while(cnt&&D[cnt-1].second>=D[i].second)cnt--;D[cnt++]=D[i]; }cntd=cnt;sort(U,U+cntu); cnt=0;for(int i=0,j;i<cntu;i=j){for(j=i;j<cntu&&U[i].first==U[j].first;j++);if(!n||U[cnt-1].second<U[j-1].second)U[cnt++]=U[j-1];}cntu=cnt;for(int i=0;i<m;i++){scanf("%d%d",&a,&b);int x=upper_bound(U,U+cntu,PII(a,INT_MAX))-U;int y=upper_bound(D,D+cntd,PII(a,INT_MIN))-D;ans[i]='0'+(y<cntd&&U[x-1].second>=b&&D[y].second<=b);}ans[m]=0; puts(ans);}return 0; }

?

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/forever97/p/hdu5741.html

總結(jié)

以上是生活随笔為你收集整理的HDU 5741 Helter Skelter（构造法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。