Z_L_G - 个人主页动态

05-19 16:21

A 时间比较 题意  两个时间比大小  思路  签到，硬做  代码 #include<bits/stdc++.h> using namespace std; int main(){ int a,b,c,d; cin >> a >> b >> c >> d; if(a<c) cout << "No\n"; else if(a>c) cout << "Yes\n"; else{ if(b>d) cout << "Yes\n"; else cout << "No\n"; } ...

0 点赞评论收藏

05-19 10:45

北京航空航天大学算法工程师

算法入门-树上子链

题意  一颗有n个结点的树，每个结点具有权值，求解最长（权值最大）的一条子链  思路  对于某一个结点来思考，他能构成的最长子链无非下列集中情况之一  包含他的最长链+最长的包含他一个儿子的最长链 所有结点均为负值，最长子链自身的权值 他自己的一条最长链（另一条全负）   因此我们维护一个dp数组，dp[i]表示包含结点i的最长子链，u是i的儿子，最终的为了避免dp[i]和dp[u]包含同一条子链，我们选择先更新res后更新dp[i]，由因为存在全负的可能性，所以每次遍历一颗子树时，ans的初值应该取到dp[i]  代码 #include<bits/stdc++.h> #defin...

0 点赞评论收藏

05-17 14:27

已编辑

北京航空航天大学算法工程师

NKmounth-Round-116(赛时ABC，补DF)

比赛链接 A 简单游戏(语法) 题意  给定三个数，和一个序号，问序号位置的数是不是最大的  思路  遍历整个数组，找不到比他大的就Y，找不到就N  代码 #include<bits/stdc++.h> using namespace std; int main(){ int a[5]={0},idx; for(int i=1;i<=3;i++){ cin >> a[i]; } cin >> idx; for(int i=1;i<3;i++){ if(a[i]>a[idx]){ cout << "No" << end...

0 点赞评论收藏

06-04 19:41

已编辑

北京航空航天大学算法工程师

算法入门-二叉苹果树(边权转点权)(补：两种做法)

题意  对于一个有n个结点的二叉树，根的编号一定为1，每条边有权值 求保留q条边时，最多能获得多少权值 tip:分析样例可以知道，这棵树的根是必须保留的，“剪枝行为”一定是保留根含有根的子树  思路（法一）  由于输入是无规律的输入每一条边，所以应当先建立起二叉树，从根开始深搜建树 由于边权是较难处理的，我们发现可以把所有边权变为该条边所连的儿子的权值，把边权转换为点权，同时边转化为点，会多一个点，所以最终保留q条边会变为保留q+1个点 建完这棵树后，可以进行动态规划，对每个结点考虑剩下多少个边，进行枚举   表示i包含j个点(边) 树形dp，dfs深搜即可，每次深搜记录当前结点和剩余结点数，...

0 点赞评论收藏

05-16 11:09

北京航空航天大学算法工程师

最小支配集-最小点覆盖-最小边覆盖

最小点覆盖 (Minimum Vertex Cover, MVC)  用最少数量的顶点覆盖图中所有的边。  最小边覆盖 (Minimum Edge Cover, MEC)  用最少数量的边覆盖图中所有的顶点。  最小支配集 (Minimum Dominating Set, MDS)  用最少数量的顶点支配图中所有的顶点。  注意  注意区分最小点覆盖和最小支配集，两者一个考虑点一个考虑边 对于A-B-C-D-E-F，最小点覆盖是3，最小支配集是2

0 点赞评论收藏

05-16 10:58

已编辑

北京航空航天大学算法工程师

算法入门-(USACO 2008 Jan G)Cell Phone Network(最小支配集)

最小支配集  选择一个点，可以覆盖相邻的点，覆盖所有点所需最小选点  题意  给定一颗n个结点的树，求最小支配集  思路  考虑每一个点，他可能被支配的方式有：被父亲支配，选自己，被儿子支配，维护一个二维dp数组记录点和状态：   自己： 父亲： 儿子： 对于自己和父亲，状态方程很显然可以推出，对于被儿子支配的情况，所有儿子不能依靠父亲，只能靠自己或者靠儿子的儿子，但是，总归有一个儿子需要靠自己，不然就无法覆盖父亲，所以，维护，如果最终结果大于0,说明全都靠的儿子的儿子，需要补上一个靠儿子和自己的差值inc 对于inc，如果小于0，说明一定有一个被选了，不用再依靠inc，所以每次inc>...

0 点赞评论收藏

05-16 10:56

已编辑

北京航空航天大学算法工程师

算法入门-Strategic game(最小点覆盖)

最小点覆盖  选择一个点，覆盖所有相邻边，最少选几个点能覆盖所有边  题意  给定一棵n个结点的树，选定一个结点后即可覆盖他的所有邻边，求覆盖所有邻边的最少选定结点数  思路  动态规划 对于每一个结点，由于覆盖边，所以自己考虑选和不选两种情况，且父亲没选，自己就一定得选，父亲选了，自己就可选可不选，注意区分最小点覆盖，最小边覆盖，最小支配集      代码 #include<bits/stdc++.h> using namespace std; /** * dp[i][0/1];表示自己不选，自己选 * dp[i][1]=sum(min(dp[u][0],dp[u][1])+1;...

0 点赞评论收藏

05-14 23:26

北京航空航天大学算法工程师

算法入门-小G有一个大树

题意  对于一棵树，我们希望找到一个点，使得删除这个点之后，最大子树的结点数最小 以边的形式输入，输出被删除的点的编号和删除后最大子树的结点数  思路  考虑用无根树描述，对于树的某一个结点，删掉后，整棵树变为两部分  这个结点的父亲所属的树 这个结点的若干子树   故另表示删除这个点后最大子树结点数，表示这个点除了父亲以外的子树的总结点数，则就是祖先部分的结点数 得到,u是i的每一个儿子， 所求答案为所有中最小的一个  代码 #include<bits/stdc++.h> #define maxn 1024 using namespace std; int n; int tol[...

0 点赞评论收藏

05-14 23:25

北京航空航天大学算法工程师

算法入门-没有上司的舞会

题意  给定一颗n个结点的树，结点编号1~n，每个结点有权值，一个点选择以后，它的父亲就不可以被选，输出能选出的最大权值  思路  对于每个点，都有选和不选两种情况，当一个点选的时候，所有的儿子都不能选，当一个点不选的时候，每个儿子取选和不选的最大值即可，维护一个二维dp数组，状态转移方程如下  注意到，由于涉及父子关系，所以考虑用有根树来维护，因为输入的时候每个除了根以外的结点都只出现一次，根不出现，所以用编号和不断减去结点编号，最终剩余的就是根 当然，本题也可以使用无根树来维护  代码 #include<bits/stdc++.h> //有根树 using namespace ...

0 点赞评论收藏

05-12 15:07

已编辑

北京航空航天大学算法工程师

Prac-周赛Round92(ABCD+补EF)

比赛地址 A 小红的签到题 题意  输入一个大于等于三的整数n 输出一个长为n的由"_"分为两段的字符串  思路  直接硬输出即可  代码 #include<bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; cout << "a_"; for(int i=2;i<n;i++){ cout << 'a'; } cout << endl; return 0; }  B 小红的模拟题 题意  读入一张n*m的地图，其中有且仅有一个陷阱，输出一条从(1,1)...

0 点赞评论收藏

05-10 11:44

北京航空航天大学算法工程师

算法入门-宝藏猎人

题意  共有0~30000编号的岛，有n个宝藏，你每次只能往编号大的方向走，走的步长只能是上一次走的步长+p（p=-1,0,1），第一步走了d，求最多能拿到多少宝藏  思路  本题应该使用dfs+剪枝是更好写的 dp  对于0~30000这个范围，从1开始走，最大的偏移量不超过300 即相较于第一步d，最后一步的步长一定在d-300~d+300之间 对于每一步，都有可能从任何一个偏移量的步数走来，需要维护一个二维dp数组  上一步走了j走到第i座岛屿能拿到的最多宝藏，是从上上步走了j+1，j，j-1走到i-j的最大宝藏数+i处的宝藏数 由于数组不方便开负的，所以要把所有的偏移量加上一个base...

0 点赞评论收藏

05-10 10:07

北京航空航天大学算法工程师

算法入门-[NOIP2005]过河

题意  给定桥的长度L，每一步可以走S~T中任意距离，桥上共有M颗石子，求走过桥最少踩多少石子 0<= L <=1e9, 1<=S<=T<=10, 1<=M<=100  思路  一个类似于走楼梯的动态规划，很显然的可以得到转移方程:其中，S<=j<=T，0<=i<=L 但是，由于L的范围很大，不可能开下这么大的dp数组，所以需要对长度进行压缩 参考NOIP2017|小凯的疑惑，数字a，b不能表示的最大数是 因为最大步长为10，所以所有超过71的数都可以等价的压缩成72 完成路径压缩后即可正常处理，对于L由于不要求恰好过桥，所以i...

0 点赞评论收藏

05-06 21:12

北京航空航天大学算法工程师

算法入门-拦截导弹

题意  有若干导弹，拦截系统只能拦高度降序的一组导弹，问一套系统最多拦截多少导弹，拦截全部导弹需要几套系统  思路   对于第一个问题，直接对整个序列跑一个最长递减子序列(LDS Longest-Decreasing-Subsequence)   对于第二个问题，正解是跑一个最长递增子序列(LIS)   对于第二个问题，证明如下 记程度n 首先，至少需要n套系统，是显然可以得到的 需要证明的是，至多也只需要n套系统，由Dilworth定理可得，一个序列的最少不上升子序列数目就是其LDS长度   AC代码 #include<bits/stdc++.h> using namespace...

0 点赞评论收藏

05-06 20:41

北京航空航天大学算法工程师

算法入门-简单瞎搞题(分组背包+bitset优化)

题意  有n个区间，从每个区间中取一个值求 的种数  思路  分组背包，考虑前i组能不能凑出j，，其中k属于a[i] 双层枚举i,j,对于每一个j枚举区间，O(100*1000000*100)=O(1e10),过不了一点   for(int i=1;i<=n;i++){ for(int j=1;j<1e6;j++){ for(int k=a[i].first;k<=a[i].second;k++){ dp[i][j]=dp[i-1][j-k*k] } } }   使用bitset优化  bitset   定义：bitset<大小>   方法： count():返回...

0 点赞评论收藏

05-06 15:30

北京航空航天大学算法工程师

算法入门-[NOIP2004]合唱队形

题意  共有n个人，每个人有身高，移除若干人，使得序列为{纯升序||纯降序||先升序后降序}，求最少的移除人数  思路  方法1：对于整个序列正着求一个最长上升子序列，反着求一个最长上升子序列，枚举每个位置两个序列和，最大的减一即为序列最长长度。 方法2：维护一个二维dp数组，第二维记录当前元素属于升序列还是降序列，对于每个位置，如果他的值大于前面的某个值，则维护升序列，如果他的值小于，则维护降序列，特别的，维护降序列的时候，要比较作为降序列的开始还是衔接在前一个降序列，取两种情况中的最优解。 初值：对于每一个元素，至少都可以自己作为一个序列，所以所有初值为1。  PS  对于第二种方法，不需...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：