uvalive专题
【UVALive】6709 Mosaic 二维线段树
传送门：【UVALive】6709 Mosaic 题目大意： 每次选择矩阵中的一个点，求以他为中心，边长为D（D一定是奇数）的矩阵中的最小值min和最大值max，输出ans =（min+max）/ 2（向下取整）。然后将该点的值修改为ans。 题目分析： 赤果果的二维线段树单点修改、区间查询。 又一次学习了线段树，发现原来所有的更新操作全部放在二维中即可。 很不错，一定要经常看看，温
【UVALive】3887 Slim Span 枚举+最小生成树
传送门：【UVALive】3887 Slim Span 题目大意：给出一个n(2 <= n <= 100)个结点的无向图，找一棵苗条度（最大边减最小边的值）最小的生成树。图中不含自环或重边。 题目分析：枚举最小边求生成树即可。模板用用萌萌哒~ 代码如下： #include <cstdio>#include <cstring>#include <algorit
【UVALive】5713 Qin Shi Huang's National Road System 最小生成树
传送门：【UVALive】5713 Qin Shi Huang's National Road System 题目大意：秦朝有n个城市，需要修建一些道路使得任意两个城市之间都可以连通。道士徐福声称他可以用法术修路，不花钱，也不用劳动力，但只能修一条路，因此需要慎重选择用法术修哪一条路。秦始皇不仅希望其他道路的总长度B尽量短（这样可以节省劳动力），还希望法术连接的两个城市的人口之和A尽量大，因此下
【UVALive】3661 Animal Run 平面图最小割 最短路
传送门：【UVALive】3661 Animal Run 题目大意：给你一个n*m个点的网格图，其中动物园在左上角，动物们的目的地在右下角，现在你需要派出一些工作人员拦截某些边使得没有一只动物能到达右下角，已知每个单元网格中存在左上角到右下角的对角线，网格中的边以及对角线都是双向的，每条道路有个权值，表示拦截这条边所需要的工作人员数。你的任务是派尽量少的工作人员使得达到目的。 题目分析
【UVALive】2965 Jurassic Remains 中途相遇法
传送门：【UVALive】2965 Jurassic Remains 题目分析：本题用了一个很不错的思想——中途相遇法。 因为题目的数据很小，我们很容易想到暴力，但是2^24次方的枚举依旧复杂度太大，因此我们可以这么做：将一半的串枚举异或能得到的所有的值，插入到map中，然后再枚举异或另一半的串能得到的所有的值，然后查找map中的与这个值相同的有没有，更新一下能得到的最大数量即可。 成
【UVALive】6163 Myth Busters 类24点
传送门：【UVALive】6163 Myth Busters 题目分析： 可以使用括号，还有加减乘除，问能否用四个0~9的数凑出10。。。我了个去。。渣渣不会写拿来当模拟写了，写的人都要吐了。。。。 先处理出所有两个数和起来的情况，然后用两个数和起来的情况再加上一个数处理出所有三个数和起来的情况，最后用两个两个数或者一个三个数加一个数的继续推出四个数的，最后按照不降序保存。 这个能一
UVALive 4255 Guess
题意： 给你半个矩阵 如果(i,j)的位置是'-' 则说明sum[i...j]<0 如果是'+' 说明sum>0 如果是'0' 说明sum=0 给出一种满足这个矩阵的序列 序列元素绝对值在10以内 思路： 很容易想到的是将sum[i...j]转化为sum[j]-sum[i-1] 即用前缀和来表示 那么题中的矩阵就可以转化成前缀和之间的大小比较 也就是说 我们可以通过
UVALIVE 5000 Underwater Snipers（二分+贪心）
二分答案 贪心判断 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <iostream>#include <iomanip>#include <cstring>#include <climits>#include <comple
UVALIVE 4887 Soccer UVELIVE 4882
2015 UESTC Winter Training #6 训练赛的两道搜索模拟题 uvalive 4882 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <iostream>#include <iomanip>#include
HDU 5150 UVALive 5061 (LCA标记)
这两题都是在树上求某一些路径上的点权的变化 两道题的思路相同 HDU 5150： 每一种颜色我们分开考虑他们对所有节点的贡献，对于颜色同为c的两个节点u和v(假设u!=v)，那么在lca(u,v)的时候我们需要-1，因为在lca(u,v)一直到根的路径上，颜色c只能影响一次。基于此，我们对每种颜色的所有节点按照dfs序排好序，首先每个节点+1，然后对dfs序相邻的两个节点（注意颜色要相同）求
UVAlive 6426 Count【读入】
You have: • A matrix of natural numbers, with the property that all rows and all columns are sorted in ascending order (i.e. A[i,j]≥A[i−1,j] A[i,j] ≥ A[i−1,j] and A[i,j]≥A[i,j−1] A[i,j] ≥ A[i,j −1]
UVALive - 3027Corporative Network（带权并查集）
题目： UVALive - 3027Corporative Network（带权并查集） 题目大意：有n和节点，初始时每个节点的父节点都不存在，然后有下面两种操作：I 操作 I a，b 将a的父节点变成b。E操作 E a，查询a到它的父节点的距离。 解题思路：带权并查集。注意这里距离的变化是a -> b，那么a到根节点的距离就是a到b的距离的绝对值 % 1000 + b到它的根节点
UVALive - 3644X-Plosives（并查集）
题目：UVALive - 3644X-Plosives（并查集） 题目大意：给出K个简单的化合物，正好包含K种元素，那么将它们装车的时候，已经拿到的化合物再来的时候就应该拒绝装车，安全起见，然后给你装车的化合物列表，问你需要拒绝装车的次数。 解题思路：并查集。将已经装过的化合物记录下来，那么如果下次的化合物如果已经在集合中了，就说明需要拒绝装车。 代码： #inclu
UVALive 5783 Everyone out of the Pool
地址：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3794 When you rent a table at a pool hall, the proprietor gives you a 4-by-4 tray of 16 bal
CSU 1623 Inspectors（二分图最大权匹配 KM算法）（UVAlive 6879）
题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1623 选用一些边 覆盖所有的点 使得这些边的权值和最小 比赛时的想法是用一般图最大权匹配 样例也过了 但是提交总是WA 看kuangbin模版中写的是点的个数必须是偶数。。是不是有可能是这个原因 改用二分图最大权匹配之后就过了。。。。 #include <cstdio>
UVALive 6493 - Round Robin
题目链接：题目链接 就是初学编程的经典例子： N个小孩围成一个圈，给出一个数T，每次数到一个小孩，该小孩就得一分； 数到T的小孩退出。。。 但这里不同的是结束条件不再是只剩最后一个小孩，而是当剩余所有小孩的分数都相同时结束，并输出剩余的小孩数，和他们的得分 组队做题，我在这道题上坑了很久。。。 原因不是我不知道怎么做，而是想着优化模拟，比如N=5，T=17时，第一次可以判断每个小孩肯定
UVALive 6499 - sort me
题目是PDF文档格式的，所以直接贴题目链接吧： 题目链接 一般我们对字符串排序是根据ABC……XYZ的字母序进行排序，现在题目给出新的字母序，和待排序的字符串； 要求根据这些新的字母序题意是给出新的排序后的字符串 我想一般人的想法肯定是类比ABC……XYZ序列，再排序吧 我的想法就是为每一个待排序的字符串关联一个字符串，在这个关联字符串中保存当前字符串对应的ABC……XYZ序
【UVAlive】康托展开的思想
题目链接：点击打开链接 题目大意：就是给你一个n 求0~n之间的数 的k-进制和（-k）进制相同的数目 题目分析：要是的k和（-k）进制的数相同，那么就是在转化为k（-k）进制之后，在奇数位上 为全零。 对于n在转化为长度为len的k进制数后 从最高位开始“递归”看 即康托展开的思想。 #inclu
UVALive 4513 Stammering Aliens (hash+二分 or 后缀数组)
大白书上的一道例题，后缀数组的模板题吧，今天想练练hash，结果就wa+Tle了一脸。 还真没见过不卡自然取模，而卡自行取模的题，今天算是见到了。。取了好几个x，还是发生了碰撞？！ 题意： 让你根据所给字符串，找出至少出现m次的最长字符串，输出最长的长度和起始位置的最大值。 思路： 字符串hash+二分。（等学会了后缀数组再来套下模板） 二分len，然后判断长度是否合法。 判断
UVALive - 2191 Potentiometers
题意：S操作将x改为y，M操作求[x,y]的和 思路：稍加改动一下树状数组就行了，当然线段树也可以 #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 400005;int n,t[MAXN];int lowbi
UVALive - 3942 Remember the Word （Trie）
题意：给你一个有S个不同单词组成的字典和一个长字符串，把这个字符串分解成若干个单词的连接，有多少种方法 思路：转化为Trie树的形式储存，用d(i)表示字符从i开始的字符串的分解方案，每次搜索到一个单词末的时候就可以累加了 #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>const
UVALive - 3644 X-Plosives
题意：每个化合物都是有两种元素组成的，如果车上存在k个简单化合物时，如果它和已装车的化合物形成易燃物的话，你就应该拒绝装车，否则装车，输出没有装车的个数 思路：简单的并查集应用 #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const in
UVALive - 3135 Argus
题意：有一系列的事件，它每Period秒钟就会产生编号为qNum的事件，你的任务是模拟出前k个事件，如果多个事件同时发生，先处理qNum小的事件 思路：用优先队列模拟 #include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace s
uvalive 2088 - Entropy(huffman编码）
题目连接：2088 - Entropy 题目大意：给出一个字符串， 包括A~Z和_， 现在要根据字符出现的频率为他们进行编码，要求编码后字节最小， 然后输出字符均为8字节表示时的总字节数， 以及最小的编码方式所需的总字节数，并输出两者的比率， 保留一位小数。 解题思路：huffman编码。 #include <stdio.h>#include <string.h>#
uvalive 2949 - Elevator Stopping Plan(贪心+二分）
题目连接：2949 - Elevator Stopping Plan 题目大意：某个抠门的公司只有一个电梯， 现在有n 个人从1楼， 他们有各自想要到达的楼层， 然后电梯每上一楼需要4 秒， 每在一个楼层开门需要10 秒， 然后然爬楼梯的话需要20一楼。问， 如何用最短的时间让所有人都到达各自想要到的楼层。 解题思路：因为人可以爬楼梯， 所以可以在某个楼层下楼之后走楼梯到达想要到的
uvalive 2519 - Radar Installation(区间选点问题）
题目连接：2519 - Radar Installation 题目大意：给出n和半径r， 然后给出n个坐标， 现在要求在x轴选出最少的点， 以这些点为圆心， 半径为r画圆， 要求将所有点均在画的圆内。 解题思路：区间选点问题，就是变形了一下。 #include <stdio.h>#include <string.h>#include <math.h>#includ