A：栈模拟or字符串处理
题目链接：吐泡泡
思路：栈模拟，或者用string自带的函数进行处理，用string处理的时候要注意顺序从左到右！！！
字符串处理：
#include<bits/stdc++.h>
using namespace std;
int main()
{
string str;
while (cin >> str)
{
while (str.find("oo") != string::npos || str.find("OO") != string::npos)
{
if (str.find("oo") < str.find("OO"))
str.replace(str.find("oo"), 2, "O");
else if(str.find("oo") > str.find("OO"))
str.replace(str.find("OO"), 2, "");
}
cout << str << endl;
}
return 0;
}
/*
ooOOoooO
oOOo
*/
B：01背包变形
题目链接：TaoTao要吃鸡
思路：01背包的变形。
坑点：数组要开大，开105会wa。
错误想法一：我们有可能想到，直接留1的空间装威力大的，剩下的空间进行01背包计算。但是这样是错误的，因为威力最大的可能花费很少的空间就可以装进去，比如0，那么这个时候我们的想法就不对了。那么装最重的物品呢，其实道理是一样的，如果最重的物品威力为0，我们就白白浪费这个1的空间了。
错误想法二：我们能不能，m+h-1跑01背包，并记录下来最优解我背包都装了哪些东西。但是这个想法一想就可以推翻，因为背包问题记录路径并不能实现，也可能是我太菜不会。
正确做法：于是，我们想到能不能把所有的物品都统一进行处理，但是我们给一次机会可以用1的空间拿一件任意重的物品，就可以了。
那么怎么表示这一次机会呢，dp多开一维大小为2数组就行了，0代表没用过这次机会，1代表用过这次机会了。很容易就能得出这个想法的状态转移方程了：
动态规划学的不是很好，不太会写状态转移方程，大家见谅，详情看代码吧。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, m, h, dp[2][MAXN];
struct Node
{
int w, v;//重量，价值
}a[MAXN];
int main()
{
while (~scanf("%d", &n) && n)
{
scanf("%d%d", &m, &h);
for (int i = 0; i < n; i++) scanf("%d%d", &a[i].w, &a[i].v);
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++)
{
for (int j = m + h; j >= 1; j--)
{
if (j >= a[i].w)
{
dp[0][j] = max(dp[0][j], dp[0][j - a[i].w] + a[i].v);
dp[1][j] = max(max(dp[1][j], dp[1][j - a[i].w] + a[i].v), dp[0][j - 1] + a[i].v);
}
else
{
dp[1][j] = max(dp[1][j], dp[0][j - 1] + a[i].v);
}
}
}
if(h > 0) printf("%d\n", dp[1][m + h]);
else printf("%d\n", dp[0][m]);
}
return 0;
}
/*
3 3 3
2 3
3 2
2 3
*/
D：LIS变形（单调非递减子序列）
题目链接：YB要打炉石
思路：单调递增子序列的变形。然而基本是模板，只需要添加一个等号。如果是N*logN的写法，需要把lower_bound换成upper_bound。
坑点：当时比赛的时候，多组输入输出会wa，现在没事了。后来他们修改了一下，然后重判了。当时wa的怀疑人生。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int n, a[MAXN], dp[MAXN];
int main()
{
scanf("%d", &n);
{
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
dp[0] = a[0];
int len = 1;
for(int i = 1; i < n; i++)
{
int pos = upper_bound(dp, dp + len, a[i]) - dp;
if(pos < len) dp[pos] = a[i];
else dp[len++] = a[i];
}
if (len < 30) printf("no\n");
else printf("yes\n");
}
return 0;
}
G：DP，（打表水过）
题目链接：送分了QAQ
思路：应该是数位dp，开始没写，但是见好多人都过了，于是打表水一发，结果直接AC。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int n, m, sum[MAXN];
int main()
{
sum[0] = 0;
for (int i = 1; i < MAXN; i++)
{
sum[i] = sum[i - 1];
string t = to_string(i);
if (t.find("38") != string::npos || t.find("4") != string::npos) sum[i]++;
}
while (~scanf("%d%d", &n, &m) && (n + m))
{
printf("%d\n", sum[m] - sum[n - 1]);
}
return 0;
}
/*
1 100
0 1000000
0 0
*/
H：斐波那契数列变形
题目链接：了断局
思路：斐波那契数列的变形。从第四项开始，当前项等于前三项之和想加。记得开long long
#include<bits/stdc++.h>
using namespace std;
long long f[55];
int main()
{
f[1] = 0; f[2] = 1; f[3] = 1;
for (int i = 4; i < 55; i++)
{
f[i] = f[i - 1] + f[i - 2] + f[i - 3];
}
int n;
while (~scanf("%d", &n))
{
cout << f[n] << endl;
}
return 0;
}