HDU 4928 Series2

本文主要是介绍HDU 4928 Series2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

0序列为 a1、a2、a3……an 根据运算规则ai=ai+1-ai计算i序列  如果序列单调则为合理序列  问从0开始到第几序列是合理的  如果一直合理就是nice  如果一开始就不合理就是ugly

思路：

照着题解做 - -b  负责度证明很是精妙  具体见官方题解

这里有一点需要补充  就是压缩0的那个优化  压缩只能在串首和串尾进行  因为要保证答案不变

还有不是每次压缩之后留下一个0  而是要保证“对于i序列来讲  如果它被压缩了  那么在压缩处要留下一个0”  注意理解这句话  这就是为什么下面的代码中  令L--和R++的时候  判断条件不是“在这个回合内”压缩过  而是判断长度！！  这是关键！！

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 LL;
#define N 100010LL a[N];
int L,R,t,n,ans;int main()
{int i,small,big;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=1;i<=n;i++) scanf("%I64d",&a[i]);L=1;R=n;for(ans=0;ans<n;ans++){small=big=0;while(L<=R&&!a[L]) L++;if(L>1) L--;while(R>=L&&!a[R]) R--;if(R<n-ans) R++;if(L>=R) break;for(i=L;i<R;i++){if(a[i]<a[i+1]) small=1;if(a[i]>a[i+1]) big=1;}if(small&&big){if(!ans) puts("ugly series");else printf("%d\n",ans-1);ans=-1;break;}for(i=L;i<R;i++)a[i]=a[i+1]-a[i];R--;}if(ans!=-1) puts("nice series");}return 0;
}

这篇关于HDU 4928 Series2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---