cake专题
CF629D Babaei and Birthday Cake
题意：给出N个半径，和高的圆柱，要求后面的体积比前面大的可以堆在前一个的上面，求最大的体积和。 dp[i]=max（dp[j]）+v[i](j<i&&v[i]>v[j]); 离散化，线段树维护区间最大值 import java.io.BufferedInputStream;import java.io.BufferedOutputStream;import
经典题hdu 1722 Cake
Cake Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2648 Accepted Submission(s): 1275 Problem Description 一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕.问最少要
【递归+二叉树思想+搜索】 Alice and the Cake题解
Alice and the Cake题解 AC记录：记录-洛谷 题面翻译（大概就是题目大意） 执行恰好 n − 1 n-1 n−1 次操作，每次操作可以选择当前所有蛋糕中满足其重量 w ⩾ 2 w\geqslant 2 w⩾2 的一块，然后将其分为质量分别为 ⌊ w 2 ⌋ \lfloor\dfrac w2\rfloor ⌊2w⌋ 和 ⌈ w 2 ⌉ \lceil\dfrac
hdu-2134-Cuts the cake
#include<stdio.h> #include<math.h> #define m 3.14 int main() { int n; double x,y=0; while(scanf("%d",&n)&&n!=0) { x=sqrt(m*n*n/(3*m)); y=sqrt(2*m*x*x/m); printf("%.3lf
POJ - 1020 Anniversary Cake
题意：有一块边长为BoxSize的正方形的大蛋糕，现在给出n块不同尺寸的正方形的小蛋糕的边长，问是否能把大蛋糕按恰好切割为这n块小蛋糕，要求每块小蛋糕必须为整块。 思路：有技巧性的DFS，这里有一篇写的很好的：点击打开链接 #include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using
【HDU 5448】Marisa’s Cake
题意：给你一个包含n个点的凸包，所有可能出现凸包的面积和。 分析：首先比较暴力的方法就是n^2枚举一条边，求它对答案的贡献。但是点的个数有10^5，因此我们考虑从某一个点出发的所有有向面积。 若我们当前考虑的是第i个点，那么它与第i+1个点形成的这条边所能产生的凸包个数为(2^(n - 2) - 1)个，与第i + 2个点形成的这条边的个数为(2 ^ (n - 3) - 1)个……又因为叉积满
hdu 4454 Stealing a Cake(三分)
题目链接：hdu 4454 Stealing a Cake 题目大意：给定一个起始点s，一个圆形，一个矩形。现在从起点开始，移动到圆形再移动到矩形，求最短距离。 解题思路：在圆周上三分即可。即对角度[0,2*pi]三分，计算点和矩形的距离可以选点和矩形四条边的距离最短值。 #include <cstdio>#include <cstring>#include <cmath>#in
hdu 5448 Marisa’s Cake（几何+凸包）
题目链接：hdu 5448 Marisa’s Cake 解题思路 这题和zoj 3871 Convex Hull有点像，不过点数比较大，不能接受 o(n2) o(n^2)的算法。但是题目给定的是一个凸包，所以可以通过化简，在 o(n) o(n)的复杂度内计算出答案。 首先，对于一个三角形ABC SABC=fA×fB+fB×fC+fC×fA(fi表示点i和原点组成的向量） S_{
zoj 3905 Cake(状压dp)
题目链接：zoj 3905 Cake 代码 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 805;struct State {int a, b;State (int a = 0, int b = 0): a(a), b(b) {}bool operat
UVA10167 Birthday Cake【暴力】
Lucy and Lily are twins. Today is their birthday. Mother buys a birthday cake for them. Now we put the cake onto a Descartes coordinate. Its center is at (0, 0), and the cake’s length of radius is 100
Codeforces 1282 E The Cake Is a Lie —— 拓扑
This way 题意： 现在有一个正n边型的蛋糕，每次都会在蛋糕的点上切下一个三角形，现在给你每个三角形的三个点的下标，问你这个蛋糕下标排列的顺序以及按照什么顺序切下这些三角形的。 题解： 由于最外面的边只会出现一次，切割边会出现两次，所以我们计算每条边出现的次数，然后做一个dfs就可以求出下标排列的顺序。 我们可以发现每次切下一个三角形的时候一定有一个点在接下来只出现一次，于是我们只需
Bessie‘s Birthday Cake (Hard Version)
题目链接 CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) C2. Bessie’s Birthday Cake (Hard Version) 思路： 其实可以先做一下easy version。 先不选点，已有的点我们肯定能加多少边就加多少，而且手玩后发现一个规律，就是不管我们怎么加边，总的加边数量和产生的三角形个数是固定的，只和点的
uva 10167 Birthday Cake
原题： Lucy and Lily are twins.Today is their birthday.Mother buys a birthday cake for them. Now we put the cake onto a Descartes coordinate. Its center is at (0,0), and the cake’s length of radius is
Codejam之Alphabet Cake
问题描述 需要为party准备一个蛋糕，R行 C列的格子形状。助理已经把每个孩子的名字首字母写在了蛋糕的单元里，每个孩子的名字首字母都是唯一的，没有重复。每个单元至多有1个首字母。 切分蛋糕时，每个孩子的蛋糕都是矩形的，只包含自己的名字首字母，且不包含其他孩子的名字首字母。 输入：第一行的数字T，有T个测试用例。 每个测试用例开始是R和C，接着R行，每行有C个字符，表示开始的蛋糕状况。？号
HDOJnbsp;nbsp;1722nbsp;nbsp;nbsp;nbsp;Cake
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1722 题目分析：假设Q>P；先分Q份，取出P份（已分好），再将剩下的（Q-P）份看做一块蛋糕，要分给（Q-P）与P人，一直这样往下分，直到（Q-P)等于1时将蛋糕分为P快就可以，然后将所有的加在一起 #include <stdio.h> #include <math.h> int gcd(in
【GCD（最大公约数）】HDU1722-Cake
【题目】 Cake Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3489 Accepted Submission(s): 1815 Problem Description 一次生日P
zoj 3537 Cake(区间DP+最优三角形剖分)待续
1、http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4472 2、题目大意; 给出一个多边形，将这个多边形用不相交的线段分割成一个一个的三角形，如果不能进行分割输出I can't cut.，每条分割线的代价是|xi + xj| * |yi + yj| % p，求将该多边形分割成三角形的最小代价是多少？ 首先判断一下该多边形
CodeForces 629A-Far Relative’s Birthday Cake（枚举/暴力）
题目描述： Door's family is going celebrate Famil Doors's birthday party. They love Famil Door so they are planning to make his birthday cake weird! The cake is a n×n n×n n×n square consisting of equal s
uva-10167 - Birthday Cake
题意：给你一系列的点，让你找出一条直线AX+BY=0，使直线把这一系列的点分为两个部分。 由于A，B的范围在-500～500之间，所以直接枚举就可以了。 反思：由于没仔细看题意，If there are many solutions, you can only print one of them.这句话让我吃亏了。 调试的程序和Sample Output 不一样，然后就纠结了老久。。。。