当前位置: 代码迷 >> 综合 >> A. As Simple as One and Two(cf)思维
  详细解决方案

A. As Simple as One and Two(cf)思维

热度:65   发布时间:2023-11-23 05:55:22.0

原题链接: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;
}

  相关解决方案