CF 1562 D.Two Hundred Twenty One (思维+二分+字符串)

CF 1562 D.Two Hundred Twenty One (思维+二分+字符串)

链接

题意：

分析：

首先我们看D1是让我求出最少去除多少个数，

我们知道去除几个数后，需要看看去除那个位置，那么我们按照上面的思考， 收我们我们用数存储，这样使得我们知道每个位置的值，然后我们需要二分查找位置，使得满足条件。

ll n,m;string str;void check(ll l,ll r){ ll cha =v[r]-v[l-1]; ll x=l-1; ll y=r; while(y-x>1){ ll mid=(x+y)/2; if(abs(v[mid]-v[l-1]) < abs(v[mid]-v[r])){ x=mid; } else { y=mid; } } printf("%lld\n",y);}void solve(){ v.clear(); cin>>n>>m; cin>>str; str=" "+str; ll sum=0; v.push_back(0); for(int i=1;i<=n;i++){ if(i%2){ if(str[i]=='+') sum++; else sum--; }else{ if(str[i]=='+') sum--; else sum++; } v.push_back(sum); } while(m--){ ll l,r; cin>>l>>r; ll cha=v[r]-v[l-1]; if(cha==0){puts("0");} else if(cha%2){ puts("1"); check(l,r); }else { puts("2"); printf("%lld ",l); check(++l,r); } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。