uva1025 动态规划
这道题的边界是dp(T,N)=0,状态dp(i,j)表示在时间i、第j个车站最少等待时间，有三个决策：1、等1分钟2、如果有向左的车，向左3、若果有向右的车，向右 转移方程就是dp(i,j)=min(dp(i+1,j),dp(i+t[j],j+1),dp(i+t[j-1],j-1))AC代码：#in...
UVA821 floyd最短路+暴力
题意：给n条边，求每两个点之间的平均距离；思路：数据是100条边，用floyd得到每两点之间的最短距离，然后遍历相加除以边的数目；#include<iostream>#include<cstdio>#include<cstring>#include<cstd...
UVa 1646 (递推 JAVA大数) Edge Case
题意：有n个点围成一圈，这n个点的匹配就是没有公共点的边集(这些边只能连接一圈中相邻的两点)，求所有匹配的个数。额，我不会分析。。=_=||算了几个数，找找规律发现它满足斐波那契数列的递推关系，f(n)=f(n-1)+f(n-2)自从会用了Java的BigInteger，就懒得写C的高精度了。imp...
uva 11019 Matrix Matcher
题意:给出一个n*m的字符矩阵T,你的任务是找出给定的x*y的字符矩阵P在T中出现了多少次.思路：要想整个矩阵匹配，至少各行都得匹配。所以先把P的每行看做一个模式串构造出AC自动机，然后在T中的各行逐一匹配，找到P中每一行的所有匹配点。只要在匹配时做一些附加操作，就可以把匹配出来的单一的行拼成矩形。...
UVA11019 Matrix Matcher【hash傻逼题】【AC自动机好题】
LINK1LINK2题目大意让你在一个大小为\(n*m\)的矩阵中找大小是\(x*y\)的矩阵的出现次数思路1：Hashhash思路及其傻逼你把一维情况扩展一下一维是一个bas，那你二维就用两个bas好了对一个在\((i,j)\)的字符，令他的hash值是\(c_{i,j}*bas1^i*bas2^...
UVa 400 Unix Is
题意：给出n个字符串，按照字典序排列，再按照规则输出。===学习的紫书，题目意思很清楚，求列数和行数最开始看的时候木有看懂啊啊啊列数：即为（60-M）/(M+2)+1;即为先将最后那一列减去，算普通的有多少列，算完了再加上最后一列行数：可以用紫书里面的（n-1）/cols+1,也可用ceil函数再将...
POJ1015 && UVA - 323 ~Jury Compromise（dp路径）
InFrobnia,afar-awaycountry,theverdictsincourttrialsaredeterminedbyajuryconsistingofmembersofthegeneralpublic.Everytimeatrialissettobegin,ajuryhastobes...
uva 10534
一开始WA了 参考了一下 求正反两个方向的最长上升子序列 并分别记录在两个数组中 最后求最大值#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingname...
uva 11275 3D Triangles
题意：三维空间中，给出两个三角形的左边，问是否相交。面积法判断点在三角形内：#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<iostream&...
uva1471 二叉搜索树
此题紫书上面有详细分析，关键是运用Set优化实现O(nlgn)复杂度AC代码：#include<cstdio>#include<set>#include<algorithm>usingnamespacestd;constintmaxn=2e5+5;intnum[m...
UVA 11021 C - Tribles(概率DP)
记忆化就可以搞定，比赛里都没做出来，真的是态度有问题啊。。。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;doublep[...
UVA1607-Gates（思维+二分）
ProblemUVA1607-GatesAccept:111 Submit: 767TimeLimit:3000mSecProblemDescriptionInputThefirstlineoftheinputcontainsexactlyonepositiveintegerdequaltothen...
斜率优化dp(POJ1180 Uva1451)
学这个斜率优化dp却找到这个真心容易出错的题目，其中要从n倒过来到1的确实没有想到，另外斜率优化dp的算法一开始看网上各种大牛博客自以为懂了，最后才发现是错了。不过觉得看那些博客中都是用文字来描述，还是应该用画图来表示更容易让人明白，不过时间不太够，且网上该题解法到处都是，就不累赘了。代码才20几行...
uva 725 division（水题）——yhx
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABVMAAAOHCAIAAAClwESxAAAgAElEQVR4nOydybGturJFcQEPfgQu4AMmYAMu4AEe0PtNLMACHMABPKD1HOA1Zqx8OqpIUayCPUfjxj1s...
简单几何(向量旋转+凸包+多边形面积) UVA 10652 Board Wrapping
题目传送门题意：告诉若干个矩形的信息，问他们在凸多边形中所占的面积比例分析：训练指南P272，矩形面积长*宽，只要计算出所有的点，用凸包后再求多边形面积。已知矩形的中心，向量在原点参考点再旋转，角度要转换成弧度制。/******************************************...
UVa 11059 最大乘积
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2000题意：找出乘积最大的连续子序列。思路：这道题目我挺无语的，一直超时，也不知道...
UVA1291----Dance Dance Revolution----3维DP
本文出自：http://blog.csdn.net/dr5459题目地址：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4037题目...
习题9-8 Uva1632
题意：给你n个宝藏，然后给出他们的位置a[i]以及存在时间tim[i],如果能全部拿完，求出最短时间；否则输出Nosolution思路：对于一段区间[i,j]，你取完之后肯定是在最左端或者最右端，因为如果最后你停在中间位置，你始终会先到左右，所以并不能是最优解。所以我们dp[i][j][0]表示拿完...
uva11806
【题意】n行m列网格放k个石子。有多少种方法？要求第一行，第一列，最后一行，最后一列必须有石子。【题解】利用容斥原理。可以转到求“第一行、第一列、最后一行、最后一列没有石子”的方案数。枚举各个集合的组合时可以借助二进制进行枚举#include<iostream>#include<c...
UVA 11481 - Arrange the Numbers 数学
Considerthissequence{1,2,3,...,N},asainitialsequenceoffirstNnaturalnumbers.Youcanearrangethissequenceinmanyways.TherewillbeN!differentarrangements.Youha...