A：加数

知识点：while循环、函数

思路：由于 N 的范围很小，所以可以直接模拟题目的过程，每次 N←⌊N/2⌋，然后将 N 的位数累加到答案上。

求一个数 X 的位数可以利用函数来进行，每次去掉个位数，就统计一次长度，直到该数为0为止。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,len,ans;
int f(int n){
    int s=0;
    while(n){
        n/=10;
        s++;
    }
    return s;
}
int main() {
    cin>>n;
    while(n){
        ans+=f(n);
        n/=2;
    }
    cout<<ans;
    return 0;
}

B：宝石串

知识点：前缀和、循环嵌套

思路：题目大意是尽量截取一段最长的稳定宝石(稳定宝石需要绿宝石和红宝石数量一致)。故可以采用前缀和的思想，若是遇到了红宝石a[++k]=1,遇到了绿宝石a[++k]=-1,累加其前缀和s[k]=s[k-1]+a[k]。再利用循环嵌套来进行区间枚举，区间从j到i，若是发现前缀和之差为0，比较最大值，直接中断即可，最后输出答案。

参考代码：

#include<bits/stdc++.h>
using namespace std;
string str;
int a[100001],s[100001],k,ans;
int main(){
    cin>>str;
    for(int i=0;i<str.size();i++){
        if(str[i]=='R') a[++k]=1;
        else a[++k]=-1;
        s[k]=s[k-1]+a[k];
    }
    for(int i=1;i<=str.size();i++){
        for(int j=1;j<i;j++){
            if(s[i]-s[j-1]==0){
                ans=max(ans,i-j+1);
                break; 
            } 
        }
    }
    cout<<ans;
    return 0;
}

C：最小的回文代价

知识点：区间动态规划

思路：题目给定长度为m的字符串，其中有n种字符，每种字符有两个值，分别是插入这个字符的代价，删除这个字符的代价，求原字符串变为回文串的最小代价。

可以设置dp[i] [j]表示区间i到区间j成为回文串的最小代价，那么对于dp[i] [j]有三种情况：

①、dp[i + 1] [j] 表示区间 i +1到区间 j 已经是回文串了的最小代价，那么对于 s[i] 这个字母，我们有两种操作，删除与添加，对应有两种代价，dp[i + 1] [j] + ins[s[i]] 或 dp[i + 1] [j] + del[s[i]] ，取这两种代价的最小值.

②、dp[i] [j - 1] 表示区间 i 到区间 j - 1 已经是回文串了的最小代价，那么对于 s[j] 这个字母，同样有两种操作，dp[i] [j - 1] + ins[s[j]] 或 dp[i] [j - 1] + del[s[j]] ，取最小值.

③、若是 s[i] == s[j] ，dp[i + 1] [j - 1] 表示区间i+1到区间 j - 1 已经是回文串的最小代价，那么对于这种情况，我们考虑 dp[i] [j] 与 dp[i + 1] [j - 1] 的大小.

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,dp[2001][2001];//dp[i][j]:区间i,j回文的最小代价
int ins[2001],del[2001];//添加和删除的代价
string s;
char c;
int main() {
    cin>>n>>m>>s;
    s=" "+s;
    for(int i=1; i<=n; i++) {
        cin>>c;
        cin>>ins[c]>>del[c];
    }
    memset(dp,0x3f3f3f3f,sizeof dp);
    for(int i=1; i<=m; i++)dp[i][i]=0;
    for(int len=1; len<=m; len++) {
        for(int l=1; l+len<=m; l++) {
            int r=l+len;
            if(s[l]==s[r]){
                if(r-l==1)dp[l][r]=0;
                else dp[l][r]=dp[l+1][r-1];
            }
            dp[l][r]=min(dp[l][r],dp[l+1][r]+min(del[s[l]],ins[s[l]]));
            dp[l][r]=min(dp[l][r],dp[l][r-1]+min(del[s[r]],ins[s[r]]));
        }
    }
    cout<<dp[1][m];
    return 0;
}

D：高手去散步

知识点：深度优先搜索、回溯

思路：题目要求不可以去同一个观景点一次以上，也就是不可以重复走任何一个节点。

故此题可以利用深度优先遍历来进行权值的累加：①、访问顶点p；②标记顶点p；③深度优先遍历顶点p的所有未被访问的邻接点u；④去除标记顶点p

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,s,ans;
bool vis[21];
struct node{
    int v,w;
};
vector<node> v[21];
void dfs(int p){
    for(int i=0;i<v[p].size();i++){
        int u=v[p][i].v,w=v[p][i].w;
        if(!vis[u]){
            vis[u]=1; 
            s+=w;
            dfs(u);
            s-=w;
        }
    }
    ans=max(ans,s);
    vis[p]=0;
} 
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof vis);
        vis[i]=1;
        dfs(i);//从i号点开始搜索 
    }
    cout<<ans; 
    return 0;
}