[C++知识库]A. As Simple as One and Two(cf）思维

原题链接：Problem - 1276A - Codeforces

题目大意：

给你一个字符串，只有小写字母，然后希望字符串里没有one/two这两个字符串，问你最小删除字母数。

这题tag是dp，但是其实就是思维 + 贪心，不要被tag迷惑了！

1.想想看，对于一个单独的one或two：

对one，如果有段序列：ooonee,删除o和e都没有删除n高效。我们要删除肯定是因为串里有one，所以n在中间肯定只有一个，那么我们删除n就是最佳的了，同理对two也是。

2.特殊情况：如果存在twone，删除o一定是最高效的。

因此有：

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))

int main(){
  int t;
  string s;
  for(scanf("%d", &t); t; t--){
    vector<int> v;
    cin >> s;
    int n = s.length();
    s = " " + s;
    for(int i = 1; i <= n - 2; i++){
      if(s.substr(i, 3) == "one") v.push_back(i + 1), i += 2;
      else if(s.substr(i, 3) == "two"){
        if(i + 4 <= n && s.substr(i, 5) == "twone") v.push_back(i + 2), i += 4;
        else v.push_back(i + 1), i += 2;
      }
    }
    cout << v.size() << endl;
    for(auto i : v) cout << i << " ";
    cout << endl;
  }
  return 0;
}