A：木材运输的最小成本

知识点：数学

思路：两根木材，三辆车，每辆车只能装一根木材，所以至多切一次。

设被切割的木材长为n，那么$n<=k$时无需切割，否则设分成两段$x$和$n-x$，其中$n-k<=x<=k$。

题目要求最小化：$x(n-x)=-x^2+nx$

由这个式子看出最小值在$x=k$(或者对称的$x=n-k$)处取到，代入得：$k(n-k)$

整合一下，无论n是否大于k，把答案增加$max(k(n-k),0)$

由于题目保证存在能被运输的方案，$n$和$m$一定有一个$<=k$,我们只需要考虑二者的较大值$max(n,m)$

所以最终答案为$max(k(max(n, m)-k), 0)$

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
long long minCuttingCost(int n, int m, int k) {
    long long ans=0;
    ans=max(1ll*k*(max(n,m)-k),1ll*0);
    return ans;
}
int main() {
    cin>>n>>m>>k;
    cout<<minCuttingCost(n,m,k);
    return 0;
}

B：哥德巴赫猜想

知识点：质数筛

思路：使用埃氏筛找出所有质数，再使用双指针法找到当前数是否为两个质数的和，

代码：

#include <bits/stdc++.h>
using namespace std;
int a[100005];
vector <int> b;
int t,n;
int main(){
    for(int i=2;i*i<=100000;i++){//埃氏筛找出所有质数
        if (a[i]==1) continue;
        for(int j=i*i;j<=100000;j+=i){
            a[j]=1;
        }
    }
    for(int i=2;i<=100000;i++){//将所有质数装入b数组
        if (a[i]==0){
            b.push_back(i);
        }
    }
    cin>>t;
    while(t--){
        cin>>n;
        int l=0;//左指针
        int r=b.size()-1;//右指针
        bool flag=0;//标记是否找到
        while(l<=r){//双指针查找和为n的数
            if (b[l]+b[r]==n){
                flag=1;
                break;
            }else if (b[l]+b[r]<n){
                l++;
            }else{
                r--;
            }
        }
        if (flag==1){
            cout<<"Yes\n";
        }else{
            cout<<"No\n";
        }
    }
    return 0;
}

C：移除相邻字符

知识点：栈

思路：注意相邻字符消除后，原本不相邻的字符会变成相邻，可以继续消除。

由于每次都是消除最左边的字符，我们从左到右遍历 s，同时用栈记录字符：

如果栈不为空，且 s[i] 与栈顶是「连续」的，那么立刻消除，弹出栈顶。否则把 s[i] 入栈。

最后答案就是栈中剩余字符，即栈底到栈顶。

参考代码：

#include<bits/stdc++.h>
using namespace std;
string s,ans;
bool pd(char a,char b){
    int x=abs(a-b);
    return x==1||x==25;
}
int main(){
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(ans.size()&&pd(ans.back(),s[i])){
            ans.pop_back();
        }else{
            ans+=s[i];
        }
    }
    cout<<ans;
    return 0;
}

D：相似基因

知识点：动态规划

思路：

【状态定义】：f[i] [j]表示a串的前i个碱基和b串的前j个碱基的相似度。

【状态转移】：最后一对碱基只有以下3种可能：非空碱基和非空碱基。非空碱基和空碱基。空碱基和非空碱基。去掉最后一对碱基，转化成规模更小的同样的问题，就是转移式的意义。易得如下转移式：

dp[i] [j]=max(dp[i-1] [j-1]+g[mp[a[i]]] [mp[b[j]]]，max(dp[i-1] [j]+g[mp[a[i]]] [4]，dp[i] [j-1]+g[4] [mp[b[j]]]))

【边界判断与初始化】：当计算基因a的前i个碱基与基因b的前0个碱基的相似度时，等于基因a的前i−1个碱基与基因b的前0个碱基的相似度加上a的第i个碱基与空碱基的相似度，

即dp[i] [0]=dp[i-1] [0]+g[mp[a[i]]] [4];(1<=i<=n)

当计算基因a的前0个碱基与基因b的前i个碱基的相似度时，等于基因a的前0个碱基与基因b的前i−1个碱基的相似度加上b的第i个碱基与空碱基的相似度，

即dp[0] [i]=dp[0] [i-1]+g[4] [mp[b[i]]];(1<=i<=m)

基因a的前0个碱基与基因b的前0个碱基的相似度为0，

即f[0] [0]=0

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[101][101];
string a,b;
int g[][5]= {
    {5, -1, -2, -1, -3},
    {-1, 5, -3, -2, -4},
    {-2, -3, 5, -2, -2},
    {-1, -2, -2, 5, -1},
    {-3, -4, -2, -1, 0}
};
int mp[256];
int main() {
    mp['A']=0;mp['C']=1;mp['G']=2;mp['T']=3;
    cin>>n>>a>>m>>b;
    a=" "+a;
    b=" "+b;
    for(int i=1; i<=n; i++) 
        dp[i][0]=dp[i-1][0]+g[mp[a[i]]][4];
    for(int j=1; j<=m; j++) 
        dp[0][j]=dp[0][j-1]+g[4][mp[b[j]]];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            dp[i][j]=max(dp[i-1][j-1]+g[mp[a[i]]][mp[b[j]]],
                         max(dp[i-1][j]+g[mp[a[i]]][4],
                             dp[i][j-1]+g[4][mp[b[j]]]));
        }
    }
    cout<<dp[n][m];
    return 0;
}
``