蓝桥杯vip试题以及答案解析

《蓝桥杯vip试题以及答案解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、//首先声明这并不是本人原创，只不不过本人想总结出来方便大家，全为C++代码。1.结点选择问题描述有一棵n个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？解题思路：这题模型是树形动态规划入门题目，dp[i][0]表示该节点不被选择，dp[i][1]表示该结点被选择。转移方程为:dp[u][1]+=dp[v][0];//选择了u结点，则与它邻接的结点不选；dp[u][0]+=max(dp[v][0]，dp[v][1]);不选择u结点，则与它

2、邻接的结点选择结果最大的；应该特别注意：该题结点数量较大，应该选用邻接表存储边的关系1.#include  2.#include  3.#define max(a,b) ((a)>(b)?(a):(b))  4.#define maxn 100010  5.bool vis[maxn];  6.int dp[maxn][2];  7.int father[maxn];  8.int head[maxn];  9.int n;  10.int cnt;  11.struct Edge  

3、12.{  13.    int to,next;  14.}edge[2*maxn];  15.void add(int u,int v)  16.{  17.    edge[cnt].to=v;  18.    edge[cnt].next=head[u];  19.    head[u]=cnt++;  20.}  21.void treedp(int u)  22.{  23.    vis[u]=1;  24.    for(int i=head[u];i!=-1;i=edge[i].next)  25. 

4、   {  26.        int v=edge[i].to;  27.        if(!vis[v])  1.        {  2.            treedp(v);  3.            dp[u][1]+=dp[v][0];  4.            dp[u][0]+=max(dp[v][1],dp[v][0]);  5.        }  6.    }  7.}  8.void init()  9.{  10.    cnt=0;  11.    memset(dp,

5、0,sizeof(dp));  12.    memset(father,0,sizeof(father));  13.    memset(vis,0,sizeof(vis));  14.    memset(head,-1,sizeof(head));  15.}  16.int main()  17.{  18.    init();  19.    scanf("%d",&n);  20.    for(int i=1;i<=n;i++)  21.    scanf("%d",&dp[i][1]);  22. 

6、   int root=0;  23.    int begin=1;  24.    for(int i=0;i

7、

8、begin)  32.        {  33.            r

9、oot=a;  34.        }  35.    }  36.      37.    while(father[root])  38.    root=father[root];  39.    treedp(root);  40.    int ans;  41.    ans=max(dp[root][0],dp[root][1]);  42.    printf("%d",ans);  43.}  2.K好数 问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数

10、是K好数。求L位K进制数中K好数的数目。例如K=4，L=2的时候，所有K好数为11、13、20、22、30、31、33共7个。由于这个数目很大，请你输出它对1000000007取模后的值。解题思路：dp[i][j]表示第i位为j的时候的个I好数个数；因此有转移方程：dp[i][j]=dp[i-1][m]+dp[i][j];m为上一