补一下最近做的模拟题:
题意:一个含n个数的序列,能否从中只删除一个数,使得剩余序列为有序序列。(不递增或不递减序列)
题解:分别判断删除一个数后是否为不递增或不递减序列,同时还需判断删除数的前后两项是否满足序列关系。例如,判断是否为不递减序列时,若a[i]<a[i-1],对于序列1 2 5 3 4 7,若删除i项3,比较其前后两项发现不符合序列关系,则考虑删除i-1项5,再比较5的前后两项判断是否符合序列关系。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=100005; 5 int a[N],n; 6 int jud1(){//判断是否为不递减序列 7 int i,f=0; 8 a[0]=0,a[n+1]=N; 9 for(i=2;i<=n;++i){ 10 if(a[i]<a[i-1]){ 11 if(f)return 0; 12 f=1; 13 if(a[i+1]>=a[i-1]||a[i]>=a[i-2])continue; 14 else return 0; 15 } 16 } 17 return 1; 18 } 19 int jud2(){//判断是否为不递增序列 20 int i,f=0; 21 a[0]=N,a[n+1]=0; 22 for(i=2;i<=n;++i){ 23 if(a[i]>a[i-1]){ 24 if(f)return 0; 25 f=1; 26 if(a[i+1]<=a[i-1]||a[i]<=a[i-2])continue; 27 else return 0; 28 } 29 } 30 return 1; 31 } 32 int main(){ 33 int t,i; 34 scanf("%d",&t); 35 while(t--){ 36 scanf("%d",&n); 37 for(i=1;i<=n;++i)scanf("%d",&a[i]); 38 if(jud1()||jud2())puts("YES"); 39 else puts("NO"); 40 } 41 return 0; 42 }
hdu5583Kingdom of Black and White
题意:给出一串01字符串,例如:0011000
2 2 3 =>2*2+2*2+3*3
最多只能改变一个数字(0->1或1->0),使得最后平方和最大
题解:暴力枚举求最大值。枚举 第i块字符数+1与第i+1块字符数-1 和 第i块字符数-1与第i+1块字符数+1的情况,注意第i+1块只有一个字符(第i,i+1,i+2会合成一块)与第i块只有一个字符时(第i-1,i,i+1会合成一块)的情况。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=100005; 5 typedef long long ll; 6 ll s[N]; 7 char a[N]; 8 int main(){ 9 int t,i,j,c=1; 10 ll ans,ma,k; 11 scanf("%d",&t); 12 while(t--){ 13 scanf("%s",a); 14 for(s[0]=0,ans=0,i=1,j=1,k=1;a[i]!='