Z_L_G - 个人主页动态

06-27 13:28

题意  多组数据 每组数据给出一个图中点的个数n，链接任意一条边需要的代价是这个边所连的两个联通块的大小的差值，使这n个点联通所需的最小代价是多少  思路  贪心的思考，想让价值最小，每一步合并的两个块得大小接近 最终都会合成一个联通图，逆序思考   深搜即可  代码 #include<bits/stdc++.h> using namespace std; /** * 1 0 * 2 0 * 3 1 * 4 0 * 5 2 * 6 2 * 7 2 * 8 0 100 * 9 2 101 * 10 4 110 * 11 4 * 12 4 */ long long dfs(long l...

0 点赞评论收藏

06-27 13:27

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

算法入门-花店橱窗

题意  花店有f朵花，v个盆，每个花放每个盆有不同的美观度，求如何摆放能使美观度最大 特别的，给花编上号，花必须按照顺序摆放，编号小的的花不能放在编号大的花的后面  思路  由于必须按照顺序摆放，所以新的一盆花可放的盆一定是上一盆花放的盆的后面   初始化:对于最开始，每朵花放在自己编号的盆里，其它位置都放极小值即可 对于输出路径，使用记录到(i,j)这个点是谁转移来的，然后dfs回溯即可  代码 #include<bits/stdc++.h> using namespace std; /** * 所有的花束在放入花瓶时必须保持其标识数的顺序，即： * 杜鹃花必须放在秋海棠左边的花...

0 点赞评论收藏

06-27 13:26

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

算法入门-免费馅饼

题意  在一个W*H的长方形平面内，有若干块饼下坠，每块饼会有{下坠时间，下坠位置，下坠速度，价值}四个信息 人最初站在中间，可以移动(-2,-1,0,1,2)，请输出最多获得的价值以及开始后每一秒的操作  思路  这题有很多坑点 显然是一个动态规划，状态转移方程 坑点1:由于起点强制锁定在中间，但从中间开始发散着dp不好描述，又从第一秒开始往后接饼和从最后一秒往前接饼效果是一样的，所以不妨从最后一秒开始倒推dp过程，即规划的过程从i=maxt到i=0 坑点2:计算时间的时候，虽然高度是H但是只用下落(H-1)的高度，所以下落时间是 坑点3:题干中描述，只有在每一秒末落下的饼才会被接到，也就是...

0 点赞评论收藏

06-27 12:21

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

逆天顺序

同值路径必须先往左再往右按照：-2,-1,0,1,2的顺序，不然会卡60%

0 点赞评论收藏

06-24 23:36

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

算法入门-舔狗舔到最后一无所有

题意  每天可以从三家店中选一家，不能连续三天选同一家，t次询问，每次询问连续选n天有多少种不同的选择方案  思路  简单动态规划，显然第i天的可选择方案数取决于第i-1和第i-2天 对于任意一个店，第i天可以选它的情况是  第i-1天选另外两家，不用考虑第i-2天  第i-1天选它，第i-2天只能选另外两家    综上,  AC代码 #include<bits/stdc++.h> using namespace std; const int mod = 1e9+7; vector<long long> dp(101010); int main(){ ios::sync...

0 点赞评论收藏

06-23 20:20

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

算法入门-方块与收纳盒

题意  走楼梯，斐波那契换了个描述  思路  水题，  代码 #include<bits/stdc++.h> using namespace std; /** * dp[i]=dp[i-1]+dp[i-2] */ vector<long long> dp(100); int main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); dp[1]=1,dp[2]=2; for(int i=3;i<=80;i++) dp[i]=dp[i-1]+dp[i-2]; int t; cin >> t; ...

0 点赞评论收藏

06-23 17:26

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

算法入门-第k大数

题意  给定若干组数组，每组数组给出长度n和询问k 输出第k大的数  思路  水题，直接硬模拟+排序即可 注意输入量很大，需要使用快读  inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if (ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = (x<<1) + (x<<3) + (ch^48); ch = getc...

0 点赞评论收藏

06-23 16:57

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

算法入门-NOIP2009分数线划定

题意  n个人参加考试录取m个人，分数线划在m*150%的地方 输出有多少人录取，录取分数线，录取的人  思路  水题，直接硬模拟+排序即可 注意如果从0开始存储m乘完要减一名  代码 #include<bits/stdc++.h> using namespace std; #define pii pair<int,int> int cmp(pii a,pii b){ if(a.second==b.second) return a.first<b.first; else return a.second>b.second; } int main(){ int ...

0 点赞评论收藏

05-19 16:21

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

ABC406(赛时AB，补CD)

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 点赞评论收藏

创作者周榜

关注他的用户也关注了：