蓝桥杯分类模拟题.doc

《蓝桥杯分类模拟题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#本资料非原创，为了方便大家复习，特此整理。在此感谢提供试题的作者专题一：动态规划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   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  12.{  

3、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.    {  2

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

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

6、ot=0;  24.    int begin=1;  25.    for(int i=0;i

7、

8、begin)  33.        {  34.            root=a;  35

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

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