UVaLive 7374 Racing Gems (DP，LIS)
题意：以辆赛车可以从x轴上任意点出发，他的水平速度允许他向每向上移动v个单位，就能向左或向右移动v/r个单位（也就是它的辐射范围是个等腰三角形）现在赛车从x轴出发，问它在到达终点前能吃到的最多钻石。析：那个v是怎么变那个是不变的。比例考虑每个钻石的向下辐射范围，并且将其投影到x轴上的两个点，（辐射范...
UVALive 4426 Blast the Enemy! --求多边形重心
题意：求一个不规则简单多边形的重心。解法：多边形的重心就是所有三角形的重心对面积的加权平均数.关于求多边形重心的文章： 求多边形重心用叉积搞一搞就行了。代码：#include <iostream>#include <cstdio>#include <cstring>...
UVALive 2889（回文数字）
题意：给定i，输出第i个回文数字。分析：1,2,3,4，……，9------------------------------------------------------------------------------------------9个11,12,13,14，……，19---------...
UVALive 5135 Mining Your Own Business 双连通分量 2011final
题意：n条隧道由一些点连接而成，其中每条隧道链接两个连接点。任意两个连接点之间最多只有一条隧道。任务就是在这些连接点中，安装尽量少的太平井和逃生装置，使得不管哪个连接点倒塌，工人都能从其他太平井逃脱，求最少安装数量和方案。思路：其实本题就相当于在一张无向图中，涂尽量少的黑点，使得任意删除哪个点，每个...
训练指南 UVALive - 5135 （双连通分量）
layout: posttitle: 训练指南 UVALive - 5135 （双连通分量）author: "luowentaoaa"catalog: truemathjax: truetags:- 双连通分量- 图论- 训练指南Mining Your Own Busin...
UVALive 5135 Mining Your Own Business 双连通分量
据说这是一道Word Final的题，Orz。。。原题链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3136题...
UVALive - 5031 Graph and Queries (并查集+平衡树/线段树)
给定一个图，支持三种操作:1.删除一条边2.查询与x结点相连的第k大的结点3.修改x结点的权值解法：离线倒序操作，平衡树or线段树维护连通块中的所有结点信息，加个合并操作就行了。感觉线段树要好写很多。平衡树(Treap)版: #include<bits/stdc++.h> typedef...
UVAlive 5031 Graph and Queries(treap)
题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3032 题意：初始时给出一个图，每个点有一个权值,三种操作...
UVaLive 5031 Graph and Queries (Treap)
题意：初始时给出一个图，每个点有一个权值,三种操作：（1）删除某个边；（2）修改每个点的权值；（3）询问与节点x在一个连通分量中所有点的第K大的权值。 析：首先是要先离线，然后再倒着做，第一个操作就成了加边操作，很容易实现，第二操作，就是分成两个操作，先把x结点删掉，然后再插入一个新结点， 最后一个...
【UVALive】5031 Graph and Queries treap实现名次树
传送门：【UVALive】5031 Graph and Queries 题目分析：第一道treap~yeah 代码如下： #include <cstdio>#include <cstdlib>#include <cstring>#include <a...
UVaLive 5009 Error Curves (三分)
题意：给定 n 条二次曲线， fi(x) = aix^2 + bix + c 定义 F(x) =max{Si(x)}，求 F(x) 在 0 ~ 1000 上的最小值。 析：从题目给定的曲线上进行分析，很容易知道，最后的所形成的图形一定是下凸的，而这个图形就一定有一个最小值，而下凸函数可以用三分来求解...
UVaLive 11525 Permutation (线段树)
题意：有一个由1到k组成的序列，最小是1 2 … k，最大是 k k-1 … 1，给出n的计算方式，n = s0 * (k - 1)! + s1 * (k - 2)! +… + sk-1 * 0!，给出s1…sk，输出序列里第n大的序列。析：我们先看第一数，如果第一个数是2，那么它前面至少有(k-1...
UVALive-5731
UVALive-5731题意一颗 n - 1 条边的有向树，要求整棵树成为强连通图，一次操作即构建一条路（一笔画），限制：新建的路上的所有边必须与原有的边逆向，即构建的路必须在原有的边和点上，操作构建的路可以存在公共边或公共点，一次操作构建的路只能有同一点或边一次分析要成为强连通图，那么在建边的时候...
UVALive 7146 （贪心+少许数据结构基础）2014acm/icpc区域赛上海站
这是2014年上海区域赛的一道水题。请原谅我现在才发出来，因为我是在太懒了。当然，主要原因是我刚刚做出来。其实去年我就已经看到这道题了，因为我参加的就是那一场。但是当时我们爆零，伤心的我就再也没有看过那一场的题了。昨天我的队友的高中同学建议我们一起来打一打这场比赛吧，然后我才再次回顾这场比赛。结果一...
UVALive - 5116
dfs n以内所有素数的乘积map或set删多余的，有点思维在里面，就写写
UVALive-3263 That Nice Euler Circuit （几何欧拉定理）
https://vjudge.net/problem/UVALive-3263 平面上有一个n个端点的一笔画，第n个端点总是和第一个端点重合，因此图示一条闭合曲线。 组成一笔画的线段可以相交，但不会部分重叠，求这些线段将平面分为几部分 包括封闭区域和无限大区域 欧拉定理：平面图的顶点数V，边...
UVALive 7299 Boggle（深搜的姿势）
一开始确实是我的锅，我把题意理解错了，以为是一个q周围没有q的时候才可以当时qu，其实是只要碰到q，他就是qu，所以我们也可以通过预处理的方式，把字典中的不满足qu连在一起的直接去掉。后来的各种TIE我就表示不能理解了……我换了好多个姿势，改了各种各样的形式，最后改的快跟学长一模一样了，还是TLE…...
【字符串匹配】UVALive 4670 模板题
给一个文本T，和n个模板字符串，都是由小写字母组成，问这些字符串那些在字符串中出现的次数最多，输出最多的次数以及相应的字符串。AC自动机的模板题，递归输出的时候改成累加次数统计数组cnt即可。大白书认为会有重复出现的模板，但是在实际测试中，不判断重复也能通过。#include<bits/std...
UVALive 3486/zoj 2615 Cells（栈模拟dfs）
这道题在LA是挂掉了，不过还好，zoj上也有这道题。 题意：好大一颗树，询问父子关系。。考虑最坏的情况，30w层，2000w个点，询问100w次，貌似连dfs一遍都会TLE。 安心啦，这肯定是一道正常人能做的题目。不过是需要几个小技巧。 1、2000w个点不一定都要保存下来，事实上，虽然题目给了25...
UVALive 5004 Balanced Number && hdu-3967 Zero's Number（数位dp）
非常相似的两题，都是枚举分界点。 hdu 3967 ： 题意:求A到B之间有多少个数，满足这个数分为两半之后（非零）的和能被k整除； dp[i][j][rest][k][f], i表示当前位数，cut表示分界点，rest表示余数，f == 0 表示有前导零 UVALive5003：...