第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-987 强力党逗志芃
前言
这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。
关于数学的疑问
蓝桥杯中涉及到的数学说多不多，说少也不少，这里罗列了一下能用到的，其中红色的是【大学C组】会使用到的
1、简单数学(基础运算)
2、位运算
3、线性代数
4、离散数学(组合数学)
5、初等数论(整数的性质)
6、概率论
7、几何
虽然看到了线性代数、离散数学、初等数论，但是对于C组来说不会考的太复杂，会基础就好。
算法训练 强力党逗志芃
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
逗志芃励志要成为强力党，所以他将身上所以的技能点都洗掉了重新学技能。现在我们可以了解到，每个技能都有一个前提技能，只有学完了前提技能才能学习当前的技能（有一个最根本的技能不需要前提技能）。学习每个技能要消耗一个技能点，然后可以获得这个技能的威力值。由于逗志芃要陪妹子，所以他希望你教他如何点技能使得威力值最大从而成为强力党。
输入格式
第一行两个数n，m表示有n个技能和m个技能点。第二行有n个数，第i个数表示第i个技能的威力值。
之后的n-1行，每行两个数x,y，表示y技能的前提技能是x，也就是说先学第x个技能才能学弟y个技能。
输出格式
一个数，最大的威力值。
样例输入
3 2
1 10 20
1 2
1 3
样例输出
21
数据规模和约定
0<n,m<=200, 技能的威力值不超过200
题解：
C语言
#include <stdio.h> #include <stdlib.h> int n,m; int score[250]={0}; long long dp[250][250]={0}; int mp[250][250]={0}; long long max(long x,long y); void f(int cur); int main() { scanf("%d%d",&n,&m); m=m+1; int i; for(i=1;i<=n;i++) { scanf("%d",&score[i]); mp[0][i]=1; } for(i=0;i<n-1;i++) { int c,d; scanf("%d%d",&c,&d); mp[c][d]=1; mp[0][d]=0; } f(0); printf("%lld",dp[0][m]); return 0; } long long max(long x,long y) { if(x>=y) return x; else return y; } void f(int cur) { int i,j,k; for(i=1;i<=n;i++) { if(mp[cur][i]==1) { f(i); for(j=m-1;j>=0;j--) { for(k=0;k<=j;k++) { dp[cur][j]=max(dp[cur][j],dp[cur][j-k]+dp[i][k]); } } } } for(j=m;j>=0;j--) { if(j==0) dp[cur][0]=0; else dp[cur][j]=dp[cur][j-1]+score[cur]; } }
C++语言
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int N = 210; int n,m; int q[N]; int h[N],e[N],ne[N],idx; int dp[N][N];//以i为根节点，总花费的点数不超过j的最大方案 bool st[N];//是否有前驱 int res = 0;//伤害的最大的值 void add(int x,int y) { e[idx] = y,ne[idx] = h[x],h[x] = idx++; } void dfs(int u) { for(int i = h[u];i != -1; i = ne[i])//循环物品组 { int son = e[i]; dfs(son); for(int j = m - 1; j >= 0; j--)//循环剩余的点数 for(int k = 0; k <= j; k++)//循环决策 dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[son][k]); } //将当前的节点1 for(int i = m; i >= 1; i--) dp[u][i] = dp[u][i - 1] + q[u]; dp[u][0] = 0; } int main() { cin >> n >> m; memset(h, -1 ,sizeof h); for(int i = 1; i <= n; i++)//读取每个节点的值 cin>>q[i]; for(int i = 1; i < n; i++)//读取节点之间的关系 { int x,y; cin >> x >> y; add(x,y);//x为y的父节点 st[y] = true; } int root;//寻找根节点 for(int i = 1; i <= n; i++) if(st[i] == false){ root = i; break; } dfs(root); cout << dp[root][m] << endl; return 0; }
Java语言
在扫描输入内容上会有不同的方法，但是与Scanner的用法是相同的。只是相对的录入速度快于Scanner这样在整体运算的过程中可以适当节约时间。
import java.io.*; import java.util.ArrayList; import java.util.List; public class Main { static int[][] dp; static TreeNode[] treeNodes = new TreeNode[201]; static int n; static int m; static void dfs(int index){ if (m >= 1) { if (treeNodes[index].child.size() == 0 || 1 == m) { for (int i = 1; i <= m; i++){ dp[index][i] = treeNodes[index].w; } }else{ for (int k = 0; k < treeNodes[index].child.size(); k++){ dfs(treeNodes[index].child.get(k)); for (int i = m - 1; i > 0; i--){ for (int j = 1; j <= i; j++) { dp[index][i] = Math.max(dp[index][i], dp[index][i - j] + dp[treeNodes[index].child.get(k)][j]); } } } for(int i = m; i >= 1; i--) { dp[index][i] = dp[index][i - 1] + treeNodes[index].w; } } } } public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); in.nextToken(); n = (int) in.nval; in.nextToken(); m = (int) in.nval; dp = new int[201][201]; for (int i = 1; i <= n; i++){ treeNodes[i] = new TreeNode(); in.nextToken(); treeNodes[i].w = (int) in.nval; } for(int i = 0; i < n - 1; i++){ in.nextToken(); int x = (int) in.nval; in.nextToken(); int y = (int) in.nval; treeNodes[x].child.add(y); } dfs(1); out.println(dp[1][m]); out.flush(); out.close(); } static class TreeNode{ int w; List<Integer> child = new ArrayList<>(); } }
Python语言
相对简洁，但是需要对Python的一些语法很了解，特别是列表推导式的熟悉。
n,q=map(int,input().split()) we=list(map(int,input().split())) we.insert(0,0) gen=[0 for i in range(n)] dp=[[0 for i in range(n+1)]for j in range(n+1)] sum=[0 for i in range(n+1)] def dfs(u,father): for i in range(len(edge[u])): v=edge[u][i][0] w=edge[u][i][1] if v==father: continue dfs(v,u) sum[u]+=sum[v]+1 for j in range(min(q,sum[u]),-1,-1): for k in range(min(sum[v],j-1),-1,-1): dp[u][j]=max(dp[u][j],dp[u][j-1-k]+dp[v][k]+w) edge=[[]for i in range(n+1)] for _ in range(n-1): a,b=map(int,input().split()) gen[b-1]=1 edge[a].append((b,we[b])) edge[b].append((a,we[b])) for i in range(n): if gen[i]==0: w=we[i+1] dfs(i+1,0) break print(dp[1][q-1]+w)
总结
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
