一、经此一役小红所向无敌
题目解析
对于这道题，光和对立现在要挑战大魔王小红，小红的血量的
10^999999999，光的攻击是a、血量是h，对立的攻击是b、血量是k；每一回合光先对小红发起攻击，然后独立再对小红发起攻击，然后小红发动幻术，让光和对立同时相互攻击；
当光和对立其中一个人死亡后，另一个就会悲痛欲绝，然后对小红发动大招，伤害是
自身攻击力*10，然后自杀（如果光和对立同时死亡，都无法放出大招）。最后我们要求出小红受到的伤害
算法思路
这道题，通过观察数据范围我们可以发现，光和对立是无法杀死小红的，我们只需要求出小红受到的伤害然后输出即可。
对于第一种解法，就是模拟整个过程：
首先小红受到来自光的
a点伤害，然后再受到来自对立的b点伤害；然后光和对立相互攻击：光受到a点伤害，对立受到b点伤害。直到光和对立有一人死亡（生命值<=0）；如果两人同时死亡就不会放大招，否则就判断是谁放大招，小红受到攻击*10的伤害。
但是，模拟整个过程呢，是会超时的（如果光和对立的攻击都为1，而生命值都为10^9，那我们要循环10^9次）。
解法二：直接计算
每一回合小红受到的伤害是固定的
a+b，光受到的伤害是固定的a，对立受到的伤害也是固定的b；那我们是不是只需要计算出一共需要多少个回合，那是不是就可以直接计算出小红受到的伤害？
那如何计算一共需要多少个回合：
- 我们需要的回合数就是光和对立能坚持多少个回合：
- 那需要的回合数
n = min(h/b,k/a)，光会受到n*a的伤害，对立会受到n*b的伤害，小红受到n*(a+b)点伤害。- 但是我们知道
/运算是可能存在余数的（就是经过n个回合以后，光和对立可能都还存活者，但再过一个回合一定有一个人死亡）我们就需要进行判断，如果光和对立都存活，就再执行一个回合（光受到a点伤害，对立受到b点伤害，小红受到a+b点伤害)。- 最后我们要进行判断，是否需要放大招；在上述过程中，一定是有一个人死亡的（也可能两个人同时死亡），我们就需要判断此时是否还有人存活，如果光存活，小红受到
b点伤害；如果对立存活，小红受到a点伤害。- 最后我们输出小红受到的总伤害即可。
这里注意数据范围，10^9还要进行+、*运算，所以使用long long来存储数据
代码实现
#include<iostream>
using namespace std;
int main()
{
long long a,h,b,k;
cin>>a>>h>>b>>k;
long long n = min(h/b,k/a);
h = h-b*n;
k = k-a*n;
if(h>0&& k>0)
{
h-=b;
k-=a;
n++;
}
long long ret = n*(a+b);
if(h>0)
ret+=10*a;
if(k>0)
ret+=10*b;
cout<<ret<<endl;
return 0;
}
二、连续子数组最大和
题目解析
这道题，给一个长度为
n的数组，让我们求出非空连续子数组中所有数的和是最大值，让后返回即可。
算法思路
这道题解法思路就是：动态规划—线性dp
这里我们先来分析一下：我们要求出连续子数组中所有数的和的最大值，我们要这个和尽可能大；
状态表示：
dp[i]表示以i位置为结尾的连续子数组的和的最大值那对于
i位置，如果前面[0,i-1]区间中以i-1位置为结尾的连续子数组的和最大值大于0，那我们让这个值再加上i位置的值就等于以i位置为结尾的连续子数组的和的最大值；否则以i位置为结尾的连续子数组的和的最大值就等于arr[i]。那我们区间
[0,i-1]中以i-1位置为结尾的最大连续子数组的和如何去求呢？（这个值在我们的dp[i-1]中存着）那状态转移方程：
dp[i] = min(dp[i-1] , 0) + arr[i]。
这里注意：我们dp[i]表示的是以i位置为结尾的连续子数组所有数和的最大值，但是题目要求我们返回的是整个数组中，连续子数组中所有数和的最大值，所以我们要找出来整个dp表中的最大值。
代码实现
#include <iostream>
#include <vector>
using namespace std;
const int N = 200002;
int dp[N+1] = {0};
int main() {
int n;
cin >> n;
vector<int> arr(n);
for(int i = 1;i<=n;i++)
{
cin>>arr[i];
}
int ret = -101;
for(int i = 1;i<=n;i++)
{
dp[i] = max(dp[i-1],0)+arr[i];
if(dp[i]>ret)
ret = dp[i];
}
cout << ret << endl;
return 0;
}
三、非对称之美
题目解析
这道题，给我们一个字符串，让我们找出这个字符串中最长的非回文字符串的长度。
算法思路
这道题，我们如果按照找到字符串中最长的回文字符串的方法来解决，那是不能很好的解决的；（时间复杂度是
O(n^2)，会超时）
那我们如何解决呢？
我们找不是回文字符串的子串不好找，难不难试着去找一下是回文的子串；或者判断一下整个字符串是不是应该回文字符串？
**如果整个字符串是一个回文字符串：**那我们去掉一个字符后剩下的字符串一定不是回文字符串。（那最长的不是回文的子串长度就为
str.size() -1。**如果整个字符串不是回文字符串：**那此时整个字符串的长度就是我们想要的结果。
**但是这里要注意特殊情况：**如果整个字符串中只有一个字符，那我们去掉一个字符以后它也不是回文字符串。
代码实现
#include <iostream>
using namespace std;
string str;
int func()
{
int n = str.size();
bool flag = true;
for(int i = 0;i<n;i++)
{
if(str[i] != str[0])
{
flag = false;
break;
}
}
if(flag)
return 0;
flag = true;
int l = 0,r = n - 1;
while(l < r)
{
if(str[l] != str[r])
{
flag = false;
break;
}
l++;
r--;
}
if(flag)
return n-1;
else
return n;
}
int main()
{
cin>>str;
cout<<func()<<endl;
return 0;
}