P1320 压缩技术（续集版）——题解

解题思路

把所有行连接成一个字符串，从期望字符 0 开始计数。当前字符与期望字符相同时累计；不同时输出上一段长度，切换期望字符，并把当前段长度设为 1。最后别忘了输出末段。

复杂度分析

时间复杂度 $O(N^2)$，空间复杂度 $O(N^2)$；也可边读边处理到 $O(N)$ 空间。

易错点

若第一个字符是 1，必须输出一个长度为 0 的首段。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    vector<string> g; string s;
    while(cin>>s) g.push_back(s);
    int n=g.size();
    string all;
    for(auto &x:g) all+=x;
    cout<<n;
    char want='0'; int cnt=0;
    for(char c:all){
        if(c==want) cnt++;
        else{cout<<' '<<cnt;cnt=1;want=(want=='0'?'1':'0');}
    }
    cout<<' '<<cnt<<'\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); vector g; string s; while(cin>>s) g.push_back(s); int n=g.size(); string all; for(auto &x:g) all+=x; cout<<n; char want='0'; int cnt=0; for(char c:all){ if(cwant) cnt++; else{cout<<' '<<cnt;cnt=1;want=(want'0'?'1':'0');} } cout<<' '<<cnt<<'\n'; return 0; }