本文共 3876 字，大约阅读时间需要 12 分钟。

A

题目大意

就是将两个字符串A和B选择子串进行拼接，然后求通过这样的方法能得到的最长回文串的长度

题解

对字符串A和字符串B各自进行一次manacher，求出p数组

#include
   
    using namespace std;const int maxn=1e5+5;int n,len;char s[maxn],a_new[maxn*2],b_new[maxn*2];int lena[maxn*2],lenb[maxn*2];void init(char *s_new){
       cin>>s;    int j=1;    s_new[0]='$';    s_new[1]='#';    for(int i=0;i
    
     mx){
               id=i;            mx=i+p[i];        }    }}int query(){
       int ans=1;    for(int i=2;i<=len;i++){
           int tmp=max(lena[i],lenb[i-2]);        while(a_new[i-tmp]==b_new[i+tmp-2]) tmp++;        ans=max(ans,tmp);    }    return ans-1;}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    while(cin>>n){
           init(a_new);        init(b_new);        len=2*n+1;        Manacher(a_new,lena);        Manacher(b_new,lenb);        int ans=query();        cout<
     
      <
     
    
   

B

题目大意

最长回文子串长度Manacher模板

题解

注意我的模板代码里面n代表起初输入的字符串的长度

len代表的是经过变化后的字符串的长度

#include
   
    using namespace std;const int maxn=1e5+5;int n,len;char s[maxn],a_new[maxn*2];int lena[maxn*2];void init(char *s_new){
       int j=1;    s_new[0]='$';    s_new[1]='#';    for(int i=0;i
    
     mx){
               id=i;            mx=i+p[i];        }        ans=max(ans,p[i]-1);    }    return ans;}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    while(cin>>s){
           n=strlen(s);        init(a_new);        len=strlen(a_new);        cout<
     
      <
     
    
   

C

题目大意

dp,由题意推递推公式

题解

做法是先存下每个数的个数放在c中，消除一个数i,会获得 c[ i ] * i 的值（因为可以消除c[i]次），如果从0的位置开始向右消去，那么，消除数i时，i-1可能选择了消除，也可能没有

如果消除了i-1，那么i值就已经不存在，dp[i] = dp[i-1]，如果没有被消除，那么dp[i] = dp[i-2]+ c[i]*i。

#include
   
    using namespace std;const int maxn=1e5+10;typedef long long ll;ll a[maxn],dp[maxn];;int n;int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    while(cin>>n){
           for(int i=1;i<=n;i++){
               ll x;            cin>>x;            a[x]++;        }        dp[1]=a[1];        for(int i=2;i<=maxn;i++){
               dp[i]=max(dp[i-1],dp[i-2]+a[i]*i);        }        cout<
    
     <
    
   

D

题目大意

求让路灯覆盖整个路的最小半径

题解

我们要考虑三个点，首先是起点附近的第一个路灯，其次是终点附近的第一个路灯，它们两个距离要取最大值 然后就是其他路灯，其它路灯的覆盖范围是它们位置之差的一半，要想覆盖整个路的话，需要从这三者当中求得一个最大值

#include
   
    using namespace std;int n,m;typedef long long ll;const int maxn=1e3+10;ll a[maxn];int main(){
       while(cin>>n>>m){
           for(int i=0;i
    
     >a[i];        sort(a,a+n);        double ans=max(a[0]-0,m-a[n-1]);        for(int i=1;i
    
   

E

题目大意

给出一条丝带长度n，要求把丝带切成给定长度a、b、c中的一种或多种，问：最多能切成几条？（保证至少有一个解）

题解

按照题意就很明确是一个完全背包的题目，要将背包装满，然后又要最大化丝带个数（即最大价值）

#include
   
    using namespace std;const int maxn=1e4+10;int a[maxn],dp[maxn];int n;const int INF=0x3f3f3f3f;int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    cin>>n>>a[0]>>a[1]>>a[2];    for(int i=1;i<=n;i++)        dp[i]=-INF;    dp[0]=0;    for(int i=0;i<=2;i++){
           for(int j=a[i];j<=n;j++){
               dp[j]=max(dp[j],dp[j-a[i]]+1);        }    }    cout<
    
     <
    
   

另外附上完全背包，01背包，多重背包模板代码写的

#include
   
    using namespace std;const int maxn=1e4+10;int a[maxn],dp[maxn],c[maxn];int n;const int INF=0x3f3f3f3f;void CompletePack(int v,int w,int m){
       for(int j=v; j<=m; j++)        dp[j] = max(dp[j],dp[j-v]+w);}void ZeroOnePack(int v,int w,int m){
       for(int j=m; j>=v; j--)        dp[j] = max(dp[j],dp[j-v]+w);}void MultiPack(int v,int w,int m,int c){
       if(v*c > m) CompletePack(v,w,m);    else    {
           int k = 1;        while(k < c)        {
               ZeroOnePack(k*v,k*w,m);            c -= k;            k *= 2;        }        ZeroOnePack(c*v,c*w,m);    }}int main(){
       ios::sync_with_stdio(false);    cin.tie(0);    cin>>n>>a[0]>>a[1]>>a[2];    for(int i=0;i
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/101507953 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！