_zlWang-CSDN博客

原创暂不更新博客了，欢迎大家摘抄

友链:https://blog.csdn.net/tigerisland45https://blog.csdn.net/Miranda_ymz

2019-08-14 21:27:31 625

原创 CCF认证历年真题满分代码（更新至2018年12月）

目标是集齐所有CCF认证试题的满分代码！每次考试出题一般规律：第一题：水题（稍微有些编程经验就可以写）第二题：小模拟（处理比较简单的问题，掌握C++STL很有帮助）第三题：大模拟（处理复杂的问题，一般涉及文本处理，需要熟练掌握C++STL并且细心）第四题：算法题（难度一般，重点考图论算法和动态规划）第五题：算法题（难度很高，涉及算法面很多，而且数据量很大，需要对算法极致优化...

2018-02-21 21:56:18 99929 30

原创 CCF认证 2018-12 数据中心

题目说的挺玄乎，还对树分了层，其实就是一个裸的最小生成树求出最小生成树后，所用的最大的那条边的长度就是答案#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;t...

2019-02-12 13:14:57 6944 6

原创 CCF认证 2018-12 CIDR合并

题目挺长，但是说的挺清楚，最后还直接给出了算法，直接按照给出的算法就能得出答案我们只需要处理输入和输出，将格式转化为自己熟悉的格式方便接下来的处理即可这次的第三题对时间卡的挺紧，在同级合并那里我用了链表优化，不然会超时还有一开始我用string保存ip，结果最后一组数据过不去之后改用了整型保存，再用特定的方法处理，比string快很多#include<iostream&...

2019-02-12 13:12:31 6587

原创 CCF认证 2018-12 小明放学

用一个变量保存当前时间，过一遍所有路口利用当前时间和 t 的差值以及对r+y+g的取模，计算当前路口的状态要用long long 型变量#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using...

2019-02-12 13:05:53 8626

原创 CCF认证 2018-12 小明上学

第一题水题#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;typedef long long ll;int main(){ int r,y,g,n,...

2019-02-12 13:01:41 15471 1

原创 CCF认证 2018-03 棋局评估

状态压缩+博弈+搜索我先把棋局按照3进制压缩为一个整数，用这个整数作为参数去搜索，比较简便两个人都要按最优策略来，就是博弈，这道题就简单的标记下当前是哪个人走是Alice就递归的选择接下来能得到的最大分数，Bob就是最小分数#include<iostream>#include<cstdio>#include<cstring>#includ...

2019-02-10 11:11:10 1993

原创 CCF认证 2018-03 URL映射

文本处理题，题意阐述有点歧义，不是很清楚，能满分是一下一下试出来的，所以代码很乱匹配时除非出现了<path>，否则元素个数和结尾的'/'都必须相同，否则就算做不匹配且<path>不能匹配空串知道了这些再按题意一步一步来就可以满分了#include<iostream>#include<cstdio>#include<cstr...

2019-02-10 11:06:43 1724

原创 CCF认证 2018-03 碰撞的小球

小模拟题，模拟下小球的移动，并检查碰撞，如果有两个小球在相同位置或者移动到了边界，则改变速度方向#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;typedef ...

2019-02-10 11:01:18 1942 6

原创 CCF认证 2018-03 跳一跳

简单的小水题#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;typedef long long ll;int main(){ int a,b=2;...

2019-02-10 10:59:02 2143

原创 CCF认证 2018-09 元素选择器

总结了下，这道题就是个大坑题两个方面很坑，一是题意不明确，让人有误解，二是数据水，也导致让人更加不懂题意了解释下题意，我最后得出的结果是：这题应该是让人构造一棵树，按照输入的文本前面的点来划分层级对于每行来说，他的父节点应该是向上查找第一个点数小于自己的行例如样例，应该是这样一颗树(按照标签)： html ...

2018-11-26 17:49:14 3042 5

原创 CCF认证 2018-09 买菜

暴力求解法#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;typedef long long ll;const i...

2018-11-26 10:34:37 2832 6

原创 CCF认证 2018-09 卖菜

简单模拟，按照题目要求所说处理即可，注意一下首尾特殊处理#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;typede...

2018-11-26 10:02:10 3305 1

原创 HDU-3507 Print Article

第一次写斜率DP的题，参考了很多东西经过这题对斜率dp的理解是：斜率dp是dp的优化方法，目的是将不能得到最优解的状态舍弃，将可能得到最优解的状态保留将dp方程的转化为不等式，通过数形结合的方法把每个状态的答案反应为坐标系上的斜率通过单调的下标来维护一个斜率单调的可行解队列，像是维护一个凸图形参考的题解:https://www.cnblogs.com/kuangbin/arch...

2018-11-15 12:05:12 185

原创 CCF认证 2018-09 再卖菜

可以用dfs记忆化搜索+剪枝更稳的方法是用差分约束，因为会有三元一次的不等式，所以把不等式全部改为前缀和的不等式s[i]代表前i项的和，如a1+a2+a3>=b可改为s3-s0>=b，a1+a2+a3<=c改为s0-s3>=-c以此类推，就全部转化为s[x]-s[y]>=z的形式，然后按照差分约束建图用spfa求解，一开始就把所有点入队，求最长路，便可...

2018-11-02 11:35:43 5119 3

原创 SPOJ-HIGH Highways

一道生成树计数模板题#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;typedef long long ll;co...

2018-10-31 21:31:58 221

原创 HDU-4408 Minimum Spanning Tree

参考博客：https://www.cnblogs.com/jcf94/p/4071098.html#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#inclu...

2018-10-31 21:03:10 242

原创 HDU-4305 Lightning

参考博客：https://blog.csdn.net/alpc_wt/article/details/47057517#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue&...

2018-10-31 20:12:12 261 2

原创 URAL-1627 Join

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;typedef long long ll;const int N=10...

2018-10-31 13:59:12 165

原创 SPOJ-DETER3 Find The Determinant III

求矩阵行列式的模板题因为需要取模，并且有除法，可以在除法完成之后再取模#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace st...

2018-10-31 09:33:53 266

原创 UVA-10766 Organising the Organisation

生成树计数模板题发现这个的模板有很多种，有的套上来时WA，有的能AC因为自己不懂怎么求行列式，看不出有什么问题，赶紧补习一下#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include&lt...

2018-10-30 21:12:53 229

原创 HDU-4009 Transfer water

把每个房子看作点，水渠看作边，按照题目规则给点之间建边另外新建一个点作为水源点，和每个房子之间连边，权值为height*x从水源点求最小树形图就是答案，因为每个点都与源点连边，所以这题一定有解#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>...

2018-10-30 19:37:01 231

原创 HDU-2121 Ice_cream’s world II

最小树形图问题，但是没有给定根，需要自己选根可以加一个虚根，连向其他所有点，权值为sum=其他所有边权值之和+1从虚根形成最小树形图，得到的答案ans需减去sum如果ans==-1||ans>=sum说明不能形成树形图中途需要记录最后连向虚根的边，这个边原本连向的另一个点就是选好的根#include<iostream>#include<cstdio&...

2018-10-30 18:59:07 135

原创朱刘算法模板（最小树形图）

前向星存储结构题为UVA-11183 Teen Girl Squad#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std...

2018-10-30 13:01:15 223

原创 POJ-3164 Command Network

最小树形图模板题，用朱刘算法注意自环和重边的处理#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;typedef ...

2018-10-30 11:40:59 154

原创 UVA-10462 Is There A Second Way Left?

给出图，要求是否有生成树，是否有次小生成树，输出次小生成树花费因为给出的图有重边，所以不能用prim求次小，改用kruskal先用kruskal求出最小生成树，并记录所用边接下来枚举删去所用边，再生成一次最小生成树，其中最小的就是次小生成树#include<iostream>#include<cstdio>#include<cstring>...

2018-10-29 22:20:44 142

原创 UVA-10600 ACM Contest and Blackout

次小生成树模板题#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;typedef long long ll;cons...

2018-10-29 21:22:02 115

原创 HDU-4081 Qin Shi Huang's National Road System

意思就是先求出最小生成树，接下来要选一条边作为magic路径要让这条magic路径(u,v)的值最大 = (p[u]+p[v]) / 最小生成树的花费(减去magic路径后)先用次小生成树算法求出Max数组，接下来枚举每条边作为magic路径如果这条边被用到了，它的值就是(p[u]+p[v]) / 最小生成树的花费-cost[u][v]如果没被用到，值就是(p[u]+p[v]) /...

2018-10-29 20:27:02 115

原创 HDU-4687 Boke and Tsukkomi

一般图匹配问题，带花树算法要求给出的边中那些是冗余的，就是不再任何一个最大匹配里把每条边的点都去掉，检查匹配值是否小于最大匹配值-1，如果是的话就是冗余边#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath&...

2018-10-22 21:05:18 182

原创 URAL-1099 Work Scheduling

一般图匹配问题，用带花树算法这个直接套模板即可，光是模板也够长了，这次就先知道这个算法了，以后再深究#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>usi...

2018-10-22 20:12:48 284

原创 HDU-3488 Tour

将每个城市拆为入点，出点，然后求一次二分图最小权匹配就是答案坑点是题目有重边#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace...

2018-10-21 15:55:52 120

原创 HDU-2255 奔小康赚大钱

二分图最大权匹配模板题，用了KM算法，也可用最小费用最大流#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;typed...

2018-10-21 15:08:15 135

原创 POJ-3189 Steady Cow Assignment

网络流+二分+枚举区间#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;typedef long long ll;c...

2018-10-21 14:29:46 129

原创 POJ-2112 Optimal Milking

floyd+网络流+二分#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;typedef long long ll;...

2018-10-21 14:05:09 238

原创 POJ-2289 Jamie's Contact Groups

二分图多重匹配+二分对于每个组设置匹配上限，然后用二分图多重匹配看能否全部匹配好直到找到最小的上限，这就是最大的组的最小值，这个过程可以用二分来优化#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>...

2018-10-21 12:20:14 489

原创 HDU-3829 Cat VS Dog

如果有人喜欢的动物是另一个人不喜欢的动物，就是有冲突，那么在这俩人之间连一条边喜欢猫的必定讨厌狗，喜欢狗的必定讨厌猫，那么把喜欢猫和喜欢狗的分开，就是一个二分图那么要让更多的人高兴，就是找这个二分图的最大独立集（任意两点之间没有边，就是没有冲突）二分图最大独立集 = | V | - 最大匹配#include<iostream>#include<cstdio&g...

2018-10-21 10:22:29 106

原创 POJ-2594 Treasure Exploration

最小路径覆盖问题，最小路径覆盖 = |V| - 最大匹配数但是有一个问题，如果路径可以相交，需要经过处理：如何处理#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue...

2018-10-21 09:02:55 154

原创 HDU-1151 Air Raid

给出一个有向无环图，问最小路径覆盖是多少最小路径覆盖=点数-最大匹配数这个最大匹配就是，将每个点拆为入点，出点，然后形成二分图求最大匹配#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#incl...

2018-10-20 20:02:35 160

原创 HDU-1054 Strategic Game

题目意思是，给你一棵树，问这个树的最小点覆盖数是多少（就是用最少的点覆盖所有边）有个定理，二分图的最大匹配数就是最小点覆盖数，而树也可以转化为二分图对树进行一次深搜，标记深度，深度为奇数的分为一组，深度为偶数的分为一组然后求最大匹配即可#include<iostream>#include<cstdio>#include<cstring>#...

2018-10-20 17:20:19 135

原创 POJ-3020 Antenna Placement

思路和这道题一样：https://blog.csdn.net/wl16wzl/article/details/83214275在求出最大覆盖之后，还剩下一些单独的点，每个都单独分配一个即可#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#in...

2018-10-20 16:34:09 154

空空如也

空空如也