admin管理员组

文章数量:1026989

COW(暴力枚举) + 玄神的字符串(思维题) + Duplicate Strings(字符串思维题)

'只要坚持就会成功--2022.1.22'

1.COW，这道题的大概意思就是求出一个字符串中一共有多少个COW，不要求连续。

思路: 暴力枚举，枚举每一个包含O，看这个O和前后的C，W结合能组成多少个COW，最终求和即可;

题目链接: COW

AC代码: 

#include<bits/stdc++.h>using namespace std;int main()
{long long  n, onum = 0, snum = 0, res = 0, unum = 0;string a;cin >> n;cin >> a;for(int i = 0; i < a.size(); i ++){if(a[i] == 'W')unum ++; //先求出字符串中共有多少个最后的字母W，方便后边求每一个O的后边有多少个W;}for(int i = 0; i < a.size(); i ++){if(a[i] == 'C')onum ++;if(a[i] == 'W')unum --;if(a[i] == 'O')res += onum * unum;//相乘累加求出即可;}cout << res << endl;return 0;
}

 2.玄神的字符串:链接：题目链接
来源：牛客网

玄神有一条珍藏多年的神奇字符串。因为某种原因，该字符串只由数字0和数字1组成。但是最近，他开始对字符串感到厌烦，所以他想将这个字符串删除。他可以任意进行以下三种操作，每种操作的次数不限：
1）选择字符串中的一个0和一个1，将他们删除，代价为a；
2）选择字符串中两个位置不同的0或者两个位置不同的1，将他们删除，代价为b；
3）将字符串中的一个0变成1或将字符串中的一个1变成0，代价为c。
聪明的你能不能帮帮玄神，求出将这条神奇字符串删除成空字符串（不含任何字符的字符串）的最小代价为多少？

输入描述:

第一行包括一个仅由数字0和数字1构成的字符串s，s的长度不超过500005000050000,保证s的长度为偶数
第二行包括三个整数a、b、c，分别代表上述三种操作的代价。保证1 ≤ a,b,c ≤ 10000;

输出描述:

输出包括一个整数，表示删除该字符串的最小代价

这道题就是根据题意将只有0 1 的字符串删除，并求出最小代价 

思路: 先求出0 和 1 的数量，再分情况讨论，看a和b的大小关系，再据此求出具体结果

1. a <= b 就可以这样操作: 先将0 和 1 中的最小的那个删除完，这是min(cnt0, cnt1) * a的代价，然后将剩下的用b操作和a + c操作，这两个中代价小的那个删除完，这个代价是min(a + c, b) * abs(cnt0 - cnt1) / 2;(这其中有个小的细节，第一个操作结束后，剩下的字符串的长度一定是偶数，因为开始字符串的长度是偶数，所以如果1的数量是奇数的话，0的数量也是奇数，那么大的减小的，奇数减奇数，结果是偶数，而如果一开始都是偶数的话，那么结果还是偶数，所以可以这样做)

2.剩下的情况，就是b > a的情况，先分别把0 和 1 的最大偶数个数删除，代价是cnt0 / 2 * b + cnt1 / 2 * b，如果字符串已经删除完毕，则结束，如果字符串未删除结束，那么一定就剩下一个0 和 一个 1(参照1的注解)就再用b + c，以及a操作，中的代价小的那个操作删除字符串即可，代价:(cnt0 % 2) * min(b + c, a)；

 AC代码:

#include<bits/stdc++.h>using namespace std;string s;
int a, b, c;
int cnt0, cnt1;
int  ans;
int main()
{cin >> s;cin >> a >> b >> c;int n = s.size();for(int i = 0; i < n; i ++){if(s[i] == '0')cnt0 ++;else cnt1 ++;}if(a <= b){ans += min(cnt0, cnt1) * a;cout << min(a + c, b) * abs(cnt0 - cnt1) / 2 + ans;}else{ans += cnt0 / 2 * b + cnt1 / 2 * b;cout << ans + (cnt0 % 2) * min(b + c, a);//由于优先级的关系，前边那个括号一定要加上，debug不容易hh}return 0;
}

 3.Duplicate Strings: 输入字符串，后续可能进行多次两个不同的操作，1.将前边的字符串复制多次接到后边，2.查询某个字母出现了几次(字符串都是小写字母);

思路: 做题太少，一开始只会暴力hh，然后出了莫名其妙的错误，然后听了小伙伴说可以 转化一下，开个数组记录每个小写字母出现过的次数，如果复制，则将这些字母出现的次数相乘对应数量即可。

题目链接:  Duplicate Strings

AC代码:

#include<bits/stdc++.h>using namespace std;
long long  a[26];
int n, q;
string s;
const int mod = 1e9 + 7; 
int main()
{cin >> n >> q;cin >> s;for(int i = 0; i < n; i ++){a[s[i] - 'a'] ++;}while(q --){int op;cin >> op;if(op == 1){int k;cin >> k;for(int i = 0; i < 26; i ++){a[i] = a[i] * (k + 1) % mod;}}else{char zimu;cin >> zimu;printf("%lld\n", a[zimu - 'a']);}}return 0;
}

COW(暴力枚举) + 玄神的字符串(思维题) + Duplicate Strings(字符串思维题)

'只要坚持就会成功--2022.1.22'

1.COW，这道题的大概意思就是求出一个字符串中一共有多少个COW，不要求连续。

思路: 暴力枚举，枚举每一个包含O，看这个O和前后的C，W结合能组成多少个COW，最终求和即可;

题目链接: COW

AC代码: 

#include<bits/stdc++.h>using namespace std;int main()
{long long  n, onum = 0, snum = 0, res = 0, unum = 0;string a;cin >> n;cin >> a;for(int i = 0; i < a.size(); i ++){if(a[i] == 'W')unum ++; //先求出字符串中共有多少个最后的字母W，方便后边求每一个O的后边有多少个W;}for(int i = 0; i < a.size(); i ++){if(a[i] == 'C')onum ++;if(a[i] == 'W')unum --;if(a[i] == 'O')res += onum * unum;//相乘累加求出即可;}cout << res << endl;return 0;
}

 2.玄神的字符串:链接：题目链接
来源：牛客网

玄神有一条珍藏多年的神奇字符串。因为某种原因，该字符串只由数字0和数字1组成。但是最近，他开始对字符串感到厌烦，所以他想将这个字符串删除。他可以任意进行以下三种操作，每种操作的次数不限：
1）选择字符串中的一个0和一个1，将他们删除，代价为a；
2）选择字符串中两个位置不同的0或者两个位置不同的1，将他们删除，代价为b；
3）将字符串中的一个0变成1或将字符串中的一个1变成0，代价为c。
聪明的你能不能帮帮玄神，求出将这条神奇字符串删除成空字符串（不含任何字符的字符串）的最小代价为多少？

输入描述:

第一行包括一个仅由数字0和数字1构成的字符串s，s的长度不超过500005000050000,保证s的长度为偶数
第二行包括三个整数a、b、c，分别代表上述三种操作的代价。保证1 ≤ a,b,c ≤ 10000;

输出描述:

输出包括一个整数，表示删除该字符串的最小代价

这道题就是根据题意将只有0 1 的字符串删除，并求出最小代价 

思路: 先求出0 和 1 的数量，再分情况讨论，看a和b的大小关系，再据此求出具体结果

1. a <= b 就可以这样操作: 先将0 和 1 中的最小的那个删除完，这是min(cnt0, cnt1) * a的代价，然后将剩下的用b操作和a + c操作，这两个中代价小的那个删除完，这个代价是min(a + c, b) * abs(cnt0 - cnt1) / 2;(这其中有个小的细节，第一个操作结束后，剩下的字符串的长度一定是偶数，因为开始字符串的长度是偶数，所以如果1的数量是奇数的话，0的数量也是奇数，那么大的减小的，奇数减奇数，结果是偶数，而如果一开始都是偶数的话，那么结果还是偶数，所以可以这样做)

2.剩下的情况，就是b > a的情况，先分别把0 和 1 的最大偶数个数删除，代价是cnt0 / 2 * b + cnt1 / 2 * b，如果字符串已经删除完毕，则结束，如果字符串未删除结束，那么一定就剩下一个0 和 一个 1(参照1的注解)就再用b + c，以及a操作，中的代价小的那个操作删除字符串即可，代价:(cnt0 % 2) * min(b + c, a)；

 AC代码:

#include<bits/stdc++.h>using namespace std;string s;
int a, b, c;
int cnt0, cnt1;
int  ans;
int main()
{cin >> s;cin >> a >> b >> c;int n = s.size();for(int i = 0; i < n; i ++){if(s[i] == '0')cnt0 ++;else cnt1 ++;}if(a <= b){ans += min(cnt0, cnt1) * a;cout << min(a + c, b) * abs(cnt0 - cnt1) / 2 + ans;}else{ans += cnt0 / 2 * b + cnt1 / 2 * b;cout << ans + (cnt0 % 2) * min(b + c, a);//由于优先级的关系，前边那个括号一定要加上，debug不容易hh}return 0;
}

 3.Duplicate Strings: 输入字符串，后续可能进行多次两个不同的操作，1.将前边的字符串复制多次接到后边，2.查询某个字母出现了几次(字符串都是小写字母);

思路: 做题太少，一开始只会暴力hh，然后出了莫名其妙的错误，然后听了小伙伴说可以 转化一下，开个数组记录每个小写字母出现过的次数，如果复制，则将这些字母出现的次数相乘对应数量即可。

题目链接:  Duplicate Strings

AC代码:

#include<bits/stdc++.h>using namespace std;
long long  a[26];
int n, q;
string s;
const int mod = 1e9 + 7; 
int main()
{cin >> n >> q;cin >> s;for(int i = 0; i < n; i ++){a[s[i] - 'a'] ++;}while(q --){int op;cin >> op;if(op == 1){int k;cin >> k;for(int i = 0; i < 26; i ++){a[i] = a[i] * (k + 1) % mod;}}else{char zimu;cin >> zimu;printf("%lld\n", a[zimu - 'a']);}}return 0;
}

本文标签： COW(暴力枚举)玄神的字符串(思维题)Duplicate Strings(字符串思维题)