cf689A 思路：一个老式的电话键盘。。。。给出一个拨号的移动路径。。。问这个路径是否唯一。 思路：如果唯一就说明。。。不能平移。。。否则不唯一。。 平移可以上下左右。。所以先写4个常亮数组。。。标记平移后的结果。。。设置不合法位就可以了。。。 /* *********************************************** Author :111qqz Created Time :2016年07月18日 星期一 12时56分28秒 File Name :code/2016whust/E.cpp ************************************************ */ …

cf682C题目链接 题意：给一棵树。。有点权和边权。。。如果一个点v的子树中存在某点u,满足dis(u,v)>a[u]，那么点v就非常sad... dis(u,v)表示点u到v的距离。。。a[u]是u的点权。。现在问最少要删除多少个叶子节点才能使得没有点节点感到sad.. 思路：dfs一下。。。需要注意的是边权有负数。。。所以类似于区间的最大连续区间和。。。我们也也可以维护在树上的最大连续和。。。只需要如果当前为负就变成0即可。。。 /* *********************************************** Author :111qqz Created Time :2016年07月18 …

cf682B题目链接 题意：给出n个数。。每个数可以任意减小到一个正整数。。。问进行恰当的操作后。。。最小的没有出现的正整数的最大可能取值。。 思路：傻逼题。。。直接离散化。。。。注意不能超过初始。。。 /* *********************************************** Author :111qqz Created Time :2016年07月18日 星期一 12时43分41秒 File Name :code/2016whus/B.cpp ************************************************ */ #include <cstdio> …

cf682A题目链接 题意：两个数组，分别为1..n和1..m。。。从两个数组中各取一个，问和能被5整除的方案数。。。 思路：傻逼题。。。统计%5。。。然后乘法原理。。 /* *********************************************** Author :111qqz Created Time :2016年07月18日 星期一 12时32分22秒 File Name :code/2016whust/A.cpp ************************************************ */ #include <cstdio> #include …

hdu 4123 题目链接 题意：一棵树，定义d[i]为点i到树上某点的最大距离。。。给出若干查询，每个查询一个x,问最多能有多少点满足这些点中，最大的d与最小的d的差小于等于x.要求这些点的编号必须是连续的。 思路：可以三遍bfs处理出所有点的d... 由于不能排序。。。所以就是尺取+rmq.... 然而神Tm TLE..... 这复杂度还TLe... 结果最后发现是。。。log运算的常数太大被卡。。。 所以做法是先预处理一下。。。嗯。。。。 珍爱生命，远离log! 珍爱生命，远离log! 珍爱生命，远离log! /* *********************************************** Author …

题目链接 题意:一棵树。。然后初始两个推雪机在点s,问如何选择路径使得处理完所有边上的积雪所耗费的汽油最少（走过一条有雪的边和一条没雪的边耗费的汽油一样） 思路：很容易想到，我们应该尽可能不走已经被清理过雪了的边，因为这样很浪费。。。这样不难想到应该是和树的直径有关。但是初始的位置是给定的。。。怎么办？突然发现由于是给了两个推雪机。。所以其实相当于。。。只有一个推雪机&我们可以从任意位置开始推雪。。。第二个问题是。。。对于不在直径上的边。。我们怎么算cost?解决办法是读边的时候进行记录。。。然后求直径的时候记录路径。。。对于一条边。。。只要有一个点不在直径上。。。那么这条边的代价就是2倍。。。 1A蛤蛤蛤 /* …

hdu3873题目链接 题意：n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。 思路：。。一开始写了spfa。。。然后一脸懵逼。。。因为我第一次访问某个点的时候无法保证距离是最短的。。。所以还是上dij吧。。。 然后dij写得比较少。。。不是很熟练。。参考了这篇题解参考题解 思路倒是不难想，我在写spfa的时候也是这样想法，然后试图记录路径递归来搞。。。。。然而并不可以2333 也是第一次遇到带限制条件的最短路。。。还是多积累吧。。。 哦对了。。。权值比较大。。。要记得开long long /* …

poj 2031 题意：三维空间中n个球要相连。。。通路的代价是距离。。。如果球相交（切）或者包含那么不用建通路就能联系。。。问联系所有球的最小代价。。。 思路：裸的最小生成树。。。。先预处理球和球表面的距离。。。距离是负数的处理成0.。。然后mst搞之。。。不算CE的话是1A.... /* *********************************************** Author :111qqz Created Time :2016年07月14日 星期四 15时44分53秒 File Name :code/poj/2031.cpp …

poj1789题目链接 题意：其实题目不难理解。。。直接按照定义去搞就行了。。。 思路：由于距离在分母上。。所以要quality最大。。。就是要分母最小。。。 然后由于题目中说每一种类型的type只能由其他一种派生出来。。。我们可以把这个派生关系看做一条边。。。把每种类型看成点。。 这样就构成了一棵树。。。先o(nn7)预处理出权值。。。然后最小生成树即可。。。 这种给了坐标距离作为权值的图一定是稠密图。。。图小用kruskal糊弄一下就过去了。。。图大的话还是乖乖的用prim吧。。。 然而仍然 TLE???wtf?? 最后发现。。因为我习惯用string...但是又怕卡cin...所以做法是scanf读入字符数组然后再赋值 …

Poj2349题目链接 题意：给出n个点坐标。。。然后可以建s个卫星基站。。。有卫星基站的地方之间可以互相免费通信。。现在要建一些无线电通讯线路（不同于卫星基站，是另一种通信方式），两个点之间线路的代价是他们的距离。。。问最小距离是多少。。。使得任意两个点之间都可以直接或者间接联系。。。 思路：mst即可。。。s个卫星基站可以减少s-1条最大的边。。。多组数据。。m忘记清0.。。re一发。。。2a /* *********************************************** Author :111qqz Created Time :2016年07月13日 星期三 16时35分42秒 File Name …