蓝桥杯分类模拟题.docx

# 本资料非原创，为了方便大家复习，特此整理。在此感谢提供试题的作者 专题一：动态规划 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结点，则与它邻接的结点选择结果最大的； 应该特别注意：该题结点数量较大，应该选用邻接表存储边的关系 #includecstdio?? #includecstring?? #define?max(a,b)?((a)(b)?(a):(b))?? #define?maxn?100010?? bool?vis[maxn];?? int?dp[maxn][2];?? int?father[maxn];?? int?head[maxn];?? int?n;?? int?cnt;?? struct?Edge?? {?? ????int?to,next;?? }edge[2*maxn];?? void?add(int?u,int?v)?? {?? ????edge[cnt].to=v;?? ????edge[cnt].next=head[u];?? ????head[u]=cnt++;?? }?? void?treedp(int?u)?? {?? ????vis[u]=1;?? ????for(int?i=head[u];i!=-1;i=edge[i].next)?? ????{?? ????????int?v=edge[i].to;?? ????????if(!vis[v])?? ????????{?? ????????????treedp(v);?? ????????????dp[u][1]+=dp[v][0];?? ????????????dp[u][0]+=max(dp[v][1],dp[v][0]);?? ????????}?? ????}?? }?? void?init()?? {?? ????cnt=0;?? ????memset(dp,0,sizeof(dp));?? ????memset(father,0,sizeof(father));?? ????memset(vis,0,sizeof(vis));?? ????memset(head,-1,sizeof(head));?? }?? int?main()?? {?? ????init();?? ????scanf(%d,n);?? ????for(int?i=1;i=n;i++)?? ????scanf(%d,dp[i][1]);?? ????int?root=0;?? ????int?begin=1;?? ????for(int?i=0;in-1;i++)?? ????{?? ????????int?a,b;?? ????????scanf(%d%d,a,b);?? ????????add(a,b);?? ????????add(b,a);?? ????????father[b]=a;?? ????????if(root==b||begin)?? ????????{?? ????????????root=a;?? ????????}?? ????}?? ?????? ????while(father[root])?? ????root=father[root];?? ????treedp(root);?? ????int?ans;?? ????ans=max(dp[root][0],dp[root][1]);?? ????printf(%d\n,ans);?? }?? 2.K好数 ? 问题描述 如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是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为上一位的值，满足的条件应为m-j的绝对值不为1.即不相邻； 应当注意的是：最后在求和的时候不能简单的统计dp[l][m] 0=mk;因为首位如果是0的话，其实不足L位了，所以0mk,也许有人会疑问这是不统计L位的0，不是第一位呀