//法一：中点扩散
//法二：动态规划
//法三：hash+二分
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=1e6+10;
const int base=131;
ull hr[2*N],hl[2*N],p[2*N];//超过ull自动取余
char s[N*2];
ull get_hash(ull h[],int l,int r)//获取某段长度字符串的hash值
{
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
int t=1;
while(scanf("%s",s+1),strcmp(s+1,"END"))
{
int res=0;
int n=strlen(s+1);
for(int i=2*n;i>0;i-=2)
{
s[i]=s[i/2];
s[i-1]='z'+1;//添加#(未出现字符)
}
n*=2,p[0]=1;
for(int i=1,j=n;i<=n;i++,j--)
{
hl[i]=hl[i-1]*base+s[i]-'a'+1;//处理hash值
hr[i]=hr[i-1]*base+s[j]-'a'+1;
p[i]=p[i-1]*base;
}
for(int i=1;i<n;i++)
{
int l=0,r=min(i-1,n-i),mid;//二分寻找以str[i]为中心的最长回文子串的长度
while(r>l)
{
mid=l+r+1>>1;
if(get_hash(hl,i-mid,i-1)==get_hash(hr,n-(mid+i)+1,n-(i+1)+1))
l=mid;
else r=mid-1;
}
if(s[i-l]=='z'+1)
res=max(res,l);
else res=max(res,l+1);
}
printf("Case %d: %d\n",t++,res);
}
return 0;
}
//法四：Manacher算法
Manacher算法详解 - BT-7274 - 博客园 (cnblogs.com)
#include<bits/stdc++.h>
using namespace std;
int manacher(string str)
{
if(!str.length()) return 0;
int l=(int)(str.length()*2+1);
char *s=new char[l];//记录回文子串
int *p=new int[l];//记录每个位置最大回文半径
int r,c,index,mx;
r=c=-1;
index=mx=0;
for(int i=0;i<l;i++) s[i]=i&1?str[index++]:'#';
for(int i=0;i<l;i++)
{
p[i]=r>i?min(r - i, p[2 * c - i]):1;
while(i+p[i]<l&&i-p[i]>-1)
{
if(s[i+p[i]]==s[i-p[i]]) p[i]++;
else break;
}
if(i+p[i]>r)
{
r=i+p[i];
c=i;
}
mx=max(mx,p[i]);
}
delete[] s;
delete[] p;
return mx-1;
}
int main()
{
string str;
cin>>str;
cout<<manacher(str)<<endl;
return 0;
}
用双层循环会超时，所以改用动态规划的思想。（核心是通过一次遍历找出符合条件的最大值和最小值，一次循环保证卖一定在买后面）。
#include <iostream>
using namespace std;
int p[1000010];
int dp[1000010];
int main() {
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int m;
scanf("%d",&m);
p[i]=m;
}
int min=p[0];
dp[0]=0;
for(int i=1;i<n;i++)
{
if(p[i]<min)
min=p[i];
dp[i]=max(dp[i-1],p[i]-min);
}
cout<<dp[n-1]<<endl;
}
// 64 位输出请用 printf("%lld")
#include<iostream>
using namespace std;
int ans = 0;//记录路径条数
int n, m, x, y;
bool index[24][24] = { 0 };//将所有坐标初始化为0(在递归时0是有作用的）
void dfs(int x, int y)
{
if (x == n && y == m)
{
ans++;
return;
}
if (index[x][y] == 1 || x > n || y > m)
{
return;
}
dfs(x + 1, y);//下
dfs(x, y + 1);//右
}
int main()
{
cin >> n >> m >> x >> y;//B点和马的坐标
x += 2, y += 2, n += 2, m += 2;//这一步很重要，因为下面index最小为x-2，若保持没有负数加2即可
index[x][y] = 1;
index[x - 2][y - 1] = 1;
index[x - 2][y + 1] = 1;
index[x + 2][y - 1] = 1;
index[x + 2][y + 1] = 1;
index[x - 1][y + 2] = 1;
index[x - 1][y - 2] = 1;
index[x + 1][y + 2] = 1;
index[x + 1][y - 2] = 1;//标记马以及初始坐标
dfs(2,2);//原点平移到(2,2)
cout << ans;
return 0;
}
#include<iostream>
using namespace std;
int n, m, x, y;
bool index[24][24] = { 0 };//将所有坐标初始化为0(在递归时0是有作用的）
long long int f[24][24] = {0};
int main()
{
cin >> n >> m >> x >> y;//B点和马的坐标
x += 2, y += 2, n += 2, m += 2;//这一步很重要，因为下面index最小为x-2，若保持没有负数加2即可
index[x][y] = 1;
index[x - 2][y - 1] = 1;
index[x - 2][y + 1] = 1;
index[x + 2][y - 1] = 1;
index[x + 2][y + 1] = 1;
index[x - 1][y + 2] = 1;
index[x - 1][y - 2] = 1;
index[x + 1][y + 2] = 1;
index[x + 1][y - 2] = 1;//标记马以及初始坐标
f[2][2] = 1;
for (int x = 2; x <= n; x++)
{
for (int y = 2; y <= m; y++)
{
if (index[x][y] == 1 || x == 2 && y == 2)continue;
f[x][y] = f[x - 1][y] + f[x][y - 1];
}
}
cout << f[n][m];
return 0;
}
