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串的形式描述初始武器能杀死的怪物下...
POJ 2289 Jamie's Contact Groups / UVA 1345 Jamie's Contact Groups / ZOJ 2399 Jamie's Contact Groups / HDU 1699 Jamie's Contact Groups / SCU 1996 Jamie's Contact Groups (二分，二分图匹配)
POJ 2289 Jamie's Contact Groups / UVA 1345 Jamie's Contact Groups / ZOJ 2399 Jamie's Contact Groups / HDU 1699 Jamie's Contact Groups / SCU 1996 Jamie...
UVa 二叉树重建(先序+中序求后序)
题意是给出先序和中序，求出后序。先序遍历先访问根结点，通过根结点可以在中序中把序列分为左子树部分和右子树部分，我建了一个栈，因为后序遍历最后访问根结点，所以把每次访问的根结点放入栈中。因为后序遍历先是左子树然后是右子树，所以在递归的时候就先递归右子树，然后继续递归左子树。写完程序后有个错误，找了很久...
UVA12298 Super Poker II
怎么又是没人写题解的UVA好题，个人感觉应该是生成函数的大板子题了。直接做肯定爆炸，考虑来一发优化，我们记一个多项式，其中\(i\)次项的系数就表示对于\(i\)这个数有多少种表示方式。那么很明显，我们可以先筛素数，那么初始的多项式只有范围的的素数对应项系数才为\(1\)，否则都为\(0\)。然后考...
Again Prime? No Time. UVA - 10780（质因子分解）
m^k就是让m的每个质因子个数都增加了k倍求m的质因子 在n！中增加了多少倍就好了，因为m^k 表示每一个质因子增加相同的倍数k 所以我们需要找到增加倍数最小的那个。。短板效应 其它质因子多增加的倍数都合并一下 就是n！的另一个因数了其他的乘到一起 就是N了。。。因为n！的很大。。但n！是从1到...
uva 11806 容斥原理+dfs
In most professional sporting events, cheerleaders play a major role in entertaining the spectators. Their roles are substantial during breaks and pri...
UVA 11806 Cheerleaders （容斥原理
1.题意描述本题大致意思是讲：给定一个广场，把它分为M行N列的正方形小框。现在给定有K个拉拉队员，每一个拉拉队员需要站在小框内进行表演。但是表演过程中有如下要求：（1）每一个小框只能站立一个拉拉队员；（2）广场的第一行，最后一行，第一列，最后一列都至少站有一个拉拉队员；（3）站在广场的四个角落的拉拉...
UVA 11806 Cheerleaders (容斥原理)
题意一个n*m的区域内，放k个啦啦队员，第一行，最后一行，第一列，最后一列一定要放，一共有多少种方法。思路设A1表示第一行放，A2表示最后一行放，A3表示第一列放，A4表示最后一列放，则要求|A1∧A2∧A3∧A4|由容斥原理可知|∪Ai| = Σ|Ai| - Σ|Ai∧Aj| + …… (+-)|...
UVa 11806 Cheerleaders (数论容斥原理)
题意：给定一个n*m的棋盘，要放k个石子，要求第一行，最后一行，第一列，最后一列都有石子，问有多少种放法。析：容斥原理，集合A是第一行没有石子，集合B是最后一行没有石子，集合C是第一列没有石子，集合D是最后一列没有石子，如果某一行或某一列，没有，那么就相当于减少一行或者一列。代码如下：#pragma...
UVa 11806 Cheerleaders （容斥原理+二进制表示状态）
In most professional sporting events, cheerleaders play a major role in entertaining the spectators. Theirroles are substantial during breaks and prio...
UVa12633 Super Rooks on Chessboard（容斥 + FFT）
题目Sourcehttp://acm.hust.edu.cn/vjudge/problem/42145DescriptionLet’s assume there is a new chess piece named Super-rook. When placed at a cell of a che...
【递推】【组合数】【容斥原理】UVA - 11806 - Cheerleaders
http://www.cnblogs.com/khbcsu/p/4245943.html本题如果直接枚举的话难度很大并且会无从下手。那么我们是否可以采取逆向思考的方法来解决问题呢？我们可以用总的情况把不符合要求的减掉就行了。首先我们如果不考虑任何约束条件，我们可以得出如下结论： ...