[ICPC2016 WF]String Theory
题目链接:https://codeforces.com/gym/101242
题目描述
1-quotation 指一个以单引号开头并以另一个单引号结尾,而且中间没有单引号的字符串。例如 ‘this is a string
‘ 是一个1-quotation。对于 k>1,k-quotation 以 k 个单引号开头,以另外 k 个单引号结尾,并且中间嵌套了一个字符串。嵌套在其中的字符串是一系列(k-1)-quotation,它们可能紧接前面,分开,或者跟在若干非引号字符后面。例如”All ‘work’ and no ‘play”’是一个2-quotation。给出一个字符串的描述,请计算它最大可能的嵌套级
(即最大的k使该字符串是一个k-quotation)。
Solution
= =看错题面了一开始
首先要有一个转化的思维。
题目说 k-quotation 里可能嵌套 一些 (k-1) -quotation,实际上只用考虑一个就好。因为
3,2,1,1,2,2,1,1,2,3
可以转化为
3,2,1,1,(1,1),(1,1),1,1,2,3
也就是说,k-quotation 当 k\neq1,2 时,内部可以看成直接嵌套了一个 (k-1)-quotation
然后 k=2 时,内部嵌套了许多 1-quotation ,即使可能可以构建成 3,2,1,1,2,2,1,1,2,3 的引号序列,也都可以通过这个思想将它理解为 3,2,1,1,(1,1),(1,1),1,1,2,3 。
另外就是注意细节。。
贴一个来自这里的证明,讲得很清楚:
代码:
#include<bits/stdc++.h>
const int N = 105;
int n,b[N],a[N];
int solve(int l,int r,int k){
if(a[l]==0) l++;
if(a[r]==0) r--;
if(k!=1){
if(a[l]>=k&&a[r]>=k){
if(l==r) if(a[l]<2*k) return 0;
a[l]-=k,a[r]-=k;
return solve(l,r,k-1);
}
else return 0;
}
else{
int ans=0;
for(int i=l;i<=r;++i)
ans+=a[i];
return ((ans&1)^1)&&ans!=0;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&b[i]);
for(int p=std::min(b[1],b[n]);p>=2;--p){
for(int i=1;i<=n;++i) a[i]=b[i];
if(solve(1,n,p)){
printf("%d",p);
return 0;
}
}
if(n==1&&b[1]==2) puts("1");
else if(n==2&&b[1]==1&&b[2]==1) puts("1");
else puts("no quotation");
return 0;
}
0 条评论