链接
A题
这个题先将大写变小写然后将重复元素去除，判断是不是等于meow就可以
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 100008;
void solve() {
int n;
cin >> n;
string s;
string res;
cin >> s;
for (int i = 0; i < n; i++) {
if (s[i] >= 'A' && s[i] <= 'Z') {
s[i] = s[i] + 32; //先转小写
}
//特别判断一下i为0的时候因为这时候s为空我们直接加上第一个字母就可以了
//然后判断一下每次要加入的元素和s最后面的元素是不是相同的如果不是的话，就直接加入
if (i == 0 || (s[i] != res[res.size() - 1])) {
res = res + s[i];
}
}
if (res == "meow") { //最后判断一下
yes;
} else {
no;
}
}
signed main () {
int t;
cin >> t;
while (t) {
solve();
t--;
}
return 0;
}
B题
这个题比较有意思我们分别拿两个st数组来存字符串的大小写字母的个数，对于同一个大小写之母来说(st1[1]-st2[i])/2向下取整这样可以得到这个字母可以通过k来减少多少次
最后打印出结果数量
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 100008;
void solve() {
int st1[30];
int st2[30];//两个st数组
int n, k;
cin >> n >> k;
string s;
cin >> s;
memset(st1, 0, sizeof st1);
memset(st2, 0, sizeof st2); //初始化一下
for (int i = 0; i < n; i++) {
if (s[i] >= 'a' && s[i] <= 'z') {
st1[s[i] - 'a']++; //小写存st1
} else {
st2[s[i] - 'A']++; //大写存st2
}
}
int cnt = 0;
int ans = 0;
for (int i = 0; i < 29; i++) {
ans = ans + min(st1[i], st2[i]); //先得到原本不需要操作就存在有多少对
cnt = cnt + abs(st1[i] - st2[i]) / 2; //cnt用来记录可以通过k来操作的有多少对
}
if (k >= cnt) { //k大于cnt的话让cnt全部被操作完
ans = ans + cnt;
} else {
//这种情况只能操作k次
ans = ans + k;
}
cout << ans << '\n';
}
signed main () {
int t;
cin >> t;
while (t) {
solve();
t--;
}
return 0;
}
C1题
C2题
原本c1用了一个非常笨的方法，每次都对数组排序一遍，这个题用优先队列和multiset比较好写
思路就是先对不为0的元素入队，然后每次遇到0直接取出最大的元素，使用然后将该元素删除
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 200008;
int a[N];
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i]; //读入数据
}
multiset<int> cnt;//定义multiset可以储存重复的元素
int ans = 0;
for (int i = 0; i < n; i++) {
if (a[i] != 0) {
cnt.insert(a[i]);//数据不为0加入multiset，因为这个容器会自动的将最大元素排序到最后
} else {
if (cnt.empty() == true) { //如果原本没有元素直接加上0
ans = ans + 0;
} else {
auto it = cnt.end();
it--;//否则的话取出最后一个元素
ans = ans + *it; //让ans加上这个元素
cnt.erase(it);//将这个元素删除
}
}
}
cout << ans << '\n'; //打印结果
}
signed main () {
int t;
cin >> t;
while (t) {
solve();
t--;
}
return 0;
}
D题
不会做看了题解才会做，就是每次都判断第一个和第三个是不是一样的如果是一样的删除就只剩一种情况。如果是不一样的就是两种情况，最后打印结果
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
const int N = 30015;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
int ans = n - 1; //如果所给的单词全部不同的话，那么总数量是n-1种
for (int i = 1; i + 1 < n; i++) {
//如果第一个单词和第三个单词相同那么，删除的时候就会重复一个这样让答案减去一个
if (s[i - 1] == s[i + 1]) {
ans--;
}
}
cout << ans << '\n';//打印结果
}
signed main () {
int t;
cin >> t;
while (t) {
solve();
t--;
}
return 0;
}