思维+结论题：CF1965C Folding Strip——TJ

· · 题解

题目传送门

博客观看更佳

主要思路

思维+结论题。我们不难发现，我们最后折叠出来的纸条是 \tt0101 交替才是最优的，只要不是 \tt0101 交替，就一定还有解。如何用计算机实现呢？其实，只要碰到一段连续的 \tt0 或 \tt1，马上翻转。翻转次数越多，最后这个串就越短，就更优。

我们维护当前方向，翻转一次就旋转方向，同时维护好我们能走到的最左端 l 和最右端 r，答案就为 r-l+1 了。

代码虽然只有 22 行（无压行，做过的最短的蓝题），但是需要我们去细细思考，才能得出结论。

AC code

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        string s;
        cin>>n>>s;
        s=" "+s;
        int l=2147483647,r=-2147483648,fx=1,id=0;
        for(int i=1;i<=n;i++){
            if(s[i]==s[i-1])fx*=-1;
            else id+=fx;
            l=min(l,id),r=max(r,id);
        }
        cout<<r-l+1<<'\n';
    }
    return 0;
}