1026. 字符串消除
对代码能力有一定的要求，建议使用C++
主要思路：适当拆解功能，一个solve函数用于遍历每一个可以插入的地方和插入的字符ABC，生成新字符串ss，一个count函数计算一个字符串消除到不能再消除时一共减去了多少个字符
count函数里，我的思路大致是这样：
1、先将flag设为true，用于表示是否继续消除
2、每次while(flag)循环开始，先把flag设为false，如果在循环过程中进行了消除，则把flag改为true
3、这样就能达成的效果是：只要一次循环里进行了消除，就必然会再进行至少一次循环。如果一次循环里没有消除，那么下一次循环里也不会发生消除，flag变为false，退出循环
4、怎么进行消除呢？我的方法是先新建一个空字符串news，在消除过程中采用双指针的做法，一开始l=0,r=1，只要s[l] == s[r]，一直右指针右移r++，并且标记tempflag为true，跳出while (s[l] == s[r])后，如果tempflag为true，说明刚刚那一段是重复的，将原字符串s中[l,r)的部分修改为#，说明已经被消除
5、最后遍历原字符串s，将不是#的部分加在空字符串news上，最后将news赋值给s
参考代码如下，复杂度O(N^3)（遍历s进行插入是O(N)，消除的平均复杂度是O(N^2)），金牌学长还提出可以使用区间dp的做法，但复杂度并没有更优，只是说常数会小一点（有空就写写看（咕咕））
#include <bits/stdc++.h>
using namespace std;
int count(string& s) {
// cout << "pp " << s << endl;
bool flag = true;
int ans = 0;
while (flag) {
int n = s.size();
flag = false;
string news = "";
int l = 0,r = l + 1;
while (l < s.size()) {
bool tempflag = false;
while (s[l] == s[r]) {
tempflag = true;
r++;
}
if (tempflag) {
flag = true;
for (int j = l;j < r;j++){
s[j] = '#';
ans++;
}
}
l = r;
r = l + 1;
}
for (char ch:s) {
if (ch != '#') {
news += ch;
}
}
s = news;
}
return ans;
}
void solve() {
string s;
cin >> s;
string toadd = "ABC";
int ans = 0;
for (char ch:toadd) {
for (int i = 0;i <= s.size();i++) {
string ss = s;
ss.insert(i,string(1,ch));
ans = max(ans,count(ss));
}
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
for (int cas = 0;cas < t;cas++) {
printf("case #%d:\n",cas);
solve();
}
return 0;
}1027. 反转字符串
发现打ACM的同学使用reverse秒了（）
手写一个循环也可以，有兴趣的话还可以挑战O(1)空间
总的时间复杂度都是O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
string str;
while (getline(cin,str)) {
string ans = "";
for (int i = str.size() - 1;i >= 0; i--) {
ans += str[i];
}
cout << ans << endl;
}
return 0;
}1028. 字符串模式匹配简单匹配
可以使用课上讲的暴力匹配算法、STL大法、KMP、字符串哈希等
暴力匹配和STL都是O(N^2)，KMP和字符串哈希O(N)
暴力匹配：
#include <bits/stdc++.h>
using namespace std;
void bf(string& s, string& t) {
int lens = s.length(), lent = t.length();
int i = 0, j = 0;
while (i < lens) {
if (s[i] == t[j]) {
i++;
j++;
if (j == lent) {
cout << i - j << endl;
return;
}
} else {
if (j > 0) {
i = i - j + 1;
j = 0;
} else {
i++;
}
}
}
cout << -1 << endl;
}
int main() {
string s, t;
cin >> s >> t;
bf(s, t);
return 0;
}KMP
#include <bits/stdc++.h>
using namespace std;
int Next[10005] = {0};
void getnext(string& T) {
int n = T.length();
int j = 0;
for (int i = 1; i < n; ++i) {
while (j > 0 && T[i] != T[j]) {
j = Next[j - 1];
}
if (T[i] == T[j]) {
++j;
}
Next[i] = j;
}
}
int match(string& s, string& t) {
int j = 0;
int sn = s.length();
int tn = t.length();
for (int i = 0; i < sn; ++i) {
while (j > 0 && t[j] != s[i]) {
j = Next[j - 1];
}
if (t[j] == s[i]) {
++j;
}
if (j == tn) {
return i - tn + 1;
}
}
return -1;
}
int main() {
string s, t;
cin >> s >> t;
getnext(t);
cout << match(s, t) << endl;
return 0;
}字符串哈希
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353, seed = 233;
const int N = 10005;
string s;
int h[N] = {0}, qp[N] = {0};
void init_hash(const string& s) {
qp[0] = 1;
h[0] = s[0] % MOD;
for (int i = 1; i < s.size(); ++i) {
h[i] = (1ll * h[i - 1] * seed % MOD + s[i]) % MOD;
qp[i] = 1ll * qp[i - 1] * seed % MOD;
}
}
int get_hash(int l, int r) {
if (l == 0) return h[r];
return (h[r] + MOD - 1ll * h[l - 1] * qp[r - l + 1] % MOD) % MOD;
}
int compute_hash(const string& s0) {
int hs = s0[0] % MOD;
for (int i = 1; i < s0.size(); ++i) {
hs = (1ll * hs * seed % MOD + s0[i]) % MOD;
}
return hs;
}
int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// cout.tie(nullptr);
string s, s0;
cin >> s >> s0;
init_hash(s);
int hs = compute_hash(s0);
int len = s0.size();
for (int i = 0; i <= s.size() - len; i++) {
int temp_hash = get_hash(i, i + len - 1);
if (temp_hash == hs) {
printf("%d\n",i);
return 0;
}
}
printf("%d\n",-1);
return 0;
}1029. 稀疏矩阵三元组转化
结构体排序模板题
#include <bits/stdc++.h>
using namespace std;
struct Triple {
int row;
int col;
int value;
};
vector <Triple> Triples;
bool cmp(const Triple &t1,const Triple &t2) {
if (t1.row != t2.row) {
return t1.row < t2.row;
}else {
return t1.col < t2.col;
}
}
int main() {
int n,m,c;
cin >> n >> m >> c;
int tr,tc,tv;
for (int i = 0; i < c; i++) {
cin >> tr >> tc >> tv;
Triple triple;
triple.row = tc;
triple.col = tr;
triple.value = tv;
Triples.push_back(triple);
}
sort(Triples.begin(),Triples.end(),cmp);
for (int i = 0; i < c; i++) {
cout << Triples[i].row << " " << Triples[i].col << " " << Triples[i].value << "\n";
}
return 0;
}1030. 三元组稀疏矩阵相加
注意相加的逻辑：维护双指针，指向两个三元组的“头部”，哪边小就把哪边放进答案并且指针加一，如果一样就把值相加，把新的三元组放进答案
时间复杂度O(N1+N2)
#include <bits/stdc++.h>
using namespace std;
struct Triple {
int col;
int row;
int value;
};
int main() {
int n,m,num;
int x,y,v;
cin >> n >> m >> num;
vector<Triple> triples1;
while (num--) {
cin >> x >> y >> v;
Triple triple;
triple.col = x;
triple.row = y;
triple.value = v;
triples1.push_back(triple);
}
cin >> n >> m >> num;
vector<Triple> triples2;
while (num--) {
cin >> x >> y >> v;
Triple triple;
triple.col = x;
triple.row = y;
triple.value = v;
triples2.push_back(triple);
}
int i = 0,j = 0;
int len1 = triples1.size();
int len2 = triples2.size();
// cout << len1 << " " << len2 << endl;
vector<Triple> ans;
while (i < len1 && j < len2) {
Triple triple1 = triples1[i];
Triple triple2 = triples2[j];
if (triple1.col < triple2.col || (triple1.col == triple2.col && triple1.row < triple2.row)) {
ans.push_back(triple1);
i++;
} else if (triple1.col > triple2.col || (triple1.col == triple2.col && triple1.row > triple2.row)) {
ans.push_back(triple2);
j++;
} else {
Triple new_triple;
new_triple.col = triple1.col;
new_triple.row = triple1.row;
new_triple.value = triple1.value + triple2.value;
ans.push_back(new_triple);
i++;
j++;
}
}
while (i < len1) {
ans.push_back(triples1[i]);
i++;
}
while (j < len2) {
ans.push_back(triples2[j]);
j++;
}
// cout << ans.size() << endl;
for (auto t:ans) {
printf("%d %d %d\n",t.col,t.row,t.value);
}
return 0;
}