UVA大模拟代码（白书训练计划1）UVA 401,10010,10361,537,409,10878，10815，644，10115，424，10106，465，10494
白书一：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=64609#overview注意UVA没有PE之类的，如果PE了显示ＷＡ。UVA401：Palindromes#include <iostream>#include <...
UVa 409 Excuses, Excuses!
哈哈，虽然是一道字符串水题，可是拿到一个1A还是很开心的！题意就是给一些keywords（子串）和Excuse（母串），然后输出包含keywords最多的Excuse，如果相等的话，按任意顺序全部输出即可。解题时有几点需要注意：1、一个keyword可能在Excuse里重复多次。2、每个keywor...
UVa409_Excuses, Excuses!(小白书字符串专题)
解题报告题意：找包括单词最多的串。有多个按顺序输出思路：字典树爆。#include <cstdio>#include <cstring>#include <iostream>using namespace std;int k,e,num[100],cnt;stru...
uva 10370 - Above Average
#include <iostream> #include <cstdio> using namespace std; int main() { unsigned C, N, tot_gra, aver, abo_c, gra[]; float perc; ...
UVa 11181 条件概率
题意：n个人选r个人，每个人被选中的概率为pi，问最后每个人被选中的概率是多少。sol：就是个简单的概率题，范围还特别小，深搜秒出...然而公式什么的很多还是需要注意的... 条件概率的公式：P(A|B)*P(B)=P(AB) ——>这题就成了求裸的P(ai|pr)，即在pr发生的情况下...
UVa 1660 Cable TV Network (最大流，最小割)
题意：求一个无向图的点连通度。析：把每个点拆成两个，然后中间连接一个容量为1的边，然后固定一个源点，枚举每个汇点，最小割。代码如下：#pragma comment(linker, "/STACK:1024000000,1024000000")#include <cstdio>#inclu...
UVA 562 Dividing coins --01背包的变形
01背包的变形。先算出硬币面值的总和，然后此题变成求背包容量为V=sum/2时，能装的最多的硬币，然后将剩余的面值和它相减取一个绝对值就是最小的差值。代码：#include <iostream>#include <cstdio>#include <cstring>...
UVA 10313(完全背包变形)
Problem BPay the PriceInput: standard inputOutput: standard outputTime Limit: 2 secondsMemory Limit: 32 MBIn ancient days there was a country whose pe...
UVa 10780 (质因数分解) Again Prime? No Time.
求mk整除n!，求k的最大值。现将m分解质因数，比如对于素数p1分解出来的指数为k1，那么n!中能分解出多少个p1出来呢？考虑10!中2的个数c：1~10中有10/2个数是2的倍数，c += 5；1~10中有10/4个数是4的倍数，所以c += 2，其中有10/8 = 1个数是8的倍数，所以c +=...
UVA 10791 -唯一分解定理的应用
#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<math.h>#define ll long longusing namesp...
UVA 10574 - Counting Rectangles 计数
Given n points on the XY plane, count how many regular rectangles are formed. A rectangle is regular if and only if its sides are all parallel to the ...
UVa 270 & POJ 1118 - Lining Up
题目大意：给一些点，找出一条直线使尽可能多的点在这条直线上，求这条直线上点的个数。以每一个点为原点进行枚举，求其它点的斜率，斜率相同则说明在一条直线上。对斜率排序，找出斜率连续相等的最大长度。 #include <cstdio> #include <cmath> #inclu...
UVA - 11987 Almost Union-Find[并查集 删除]
UVA - 11987Almost Union-FindI hope you know the beautiful Union-Find structure. In this problem, you’re to implement something similar, but not identi...
UVA 11584 "Partitioning by Palindromes"（DP+Manacher）
传送门•题意•思路一定义 dp[i] 表示 0~i 的最少划分数；首先，用马拉车算法求解出回文半径数组；对于第 i 个字符 si，遍历 j (0 ≤ j < i)，判断以 j 为回文中心的最大回文串是否包含 si；如果包含，dp[ i ]=min{dp[ i ],dp[2*j-i-1]+1}；...
uva 1411 Ants
题意：一个平面上有n个黑色的点，n个白色的点，要求黑色的点与白色点之间一一配对，且线段之间不相交。思路：线段不相交并不好处理，想了很久想不出，所以看了蓝书的讲解。一个很明显的结论是，不相交的线段一定比相交的线段短，如图：一个较为直观的例子。由于点之间一一对应，所以肯定用二分图匹配，然后要使得所有线段...
Uva 10917
题目链接：http://vjudge.net/contest/143062#problem/A题意：一个人要从点1去到点2，中间还有很多点和很多条边。问你如果他每次走的边(a,b)都满足：a点到目标点的最短距离<b点到目标点的最短距离，那么他从点1出发到点2总共有多少条路径。分析：从家出发使用...
UVa465 - Overflow
题目地址：点击打开链接C++代码：#include <cstdlib>#include <cstdio>int main(){char s1[10000],s2[10000];double a,b,ans;char c;while(scanf("%s %c %s",s1,&a...
UVa11054 Gergovia的酒交易 Wine trading in Gergovia-递推
https://vjudge.net/problem/UVA-11054As you may know from the comic “Asterix and the Chieftain’s Shield”, Gergovia consists of one street, and every in...
UVA12995 Farey Sequence [欧拉函数，欧拉筛]
洛谷传送门Farey Sequence（格式太难调，题面就不放了）分析：实际上求分数个数就是个幌子，观察可以得到，所求的就是$\sum^n_{i=2}\phi (i)$，所以直接欧拉筛+前缀和即可。Code：#include<cstdio>#include<cstring>#...
【状压DP】【UVA11795】 Mega Man's Mission
传送门Description你要杀n个怪，每杀掉一个怪那个怪会掉落一种武器，这种武器可以杀死特定的怪。游戏初始你有一把武器，能杀死一些怪物。每次只能杀一只，求有多少种杀怪方法。Input多组数据，第一行是数组组数T，对于每组数据，有：第一行是怪物个数n第二行以0/1串的形式描述初始武器能杀死的怪物下...