题目连接:uva 11971 - Polygon
题目大意:给定一个长度为N的线段,要求切K刀,分成K+1个线段,问能组成K+1边形的概率。
解题思路:K条线段能组成K边形的条件为任意一条边小于其他所有边的和,因为是求概率,所以和N无关。
根据高中线性规划的知识,以二维为例:
所以有ans=2K−K−12K
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 60;
ll gcd (ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
int main () {
ll f[maxn];
f[0] = 1;
for (int i = 1; i <= 50; i++)
f[i] = f[i-1] * 2;
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
int N, K;
scanf("%d%d", &N, &K);
printf("Case #%d: ", kcas);
if (K == 1)
printf("0/1\n");
else {
ll member = f[K] - K - 1;
ll d = gcd(member, f[K]);
printf("%lld/%lld\n", member / d, f[K] / d);
}
}
return 0;
}
分享到:
相关推荐
前端开源库-point-in-polygon点在多边形中,用光线交点计数算法确定点是否在多边形中。
npm install --save circle-to-polygon 或者 yarn add circle-to-polygon 用法 例子 const circleToPolygon = require ( "circle-to-polygon" ) ; const coordinates = [ - 27.4575887 , - 58.99029 ] ; //[lon, ...
前端项目-d3-polygon,二维多边形的运算。
mapbox-gl-draw-cut-polygon-mode 自定义模式,用于切割多边形检查用于分割多边形。安装npm install mapbox-gl-draw-cut-polygon-mode mapbox-gl-draw-passing-mode 或使用CDN: < script src =" ...
例子var pointInPolygon = require ( 'point-in-polygon' ) ;var polygon = [ [ 1 , 1 ] , [ 1 , 2 ] , [ 2 , 2 ] , [ 2 , 1 ] ] ;console . log ( pointInPolygon ( [ 1.5 , 1.5 ] , polygon ) ) ; // trueconsole ...
matlab开发-Polygon2Voxel。将三角形网格转换为体素体积
pytorch-polygon-rnn-源码.rar
var classifyPoint = require ( "robust-point-in-polygon" ) var polygon = [ [ 1 , 1 ] , [ 1 , 2 ] , [ 2 , 2 ] , [ 2 , 1 ] ] console . log ( classifyPoint ( polygon , [ 1.5 , 1.5 ] ) , classifyPoint ( ...
正在安装如果使用NPM,则npm install d3-polygon 。 否则,请下载。 您也可以作为或一部分直接从加载。 支持AMD,CommonJS和香草环境。 在香草中,将导出d3全局变量:< script src =" ...
例子: ( ) ( )快速开始import { ConicPolygonGeometry } from 'three-conic-polygon-geometry';或者const { ConicPolygonGeometry } = require('three-conic-polygon-geometry');甚至[removed][removed]然后...
2D Polygon Collision Detection, 多边形碰撞检测,两个多边形是否可以靠近,
var lineToPolygon = require('turf-line-to-polygon'); var lineFeature = { "type": "Feature", "properties": {}, "geometry": { "type": "LineString", "coordinates": [ [ 0,0 ], [ 0,1 ], [ 1,1 ], [ 1,...
有效的多边形示例自相交多边形示例如何使用此套件安装npm install intersecting-polygon-detector用const isPolygonIntersecting = require ( 'intersecting-polygon-detector' ) ;// orimport * as ...
安装npm install 2d-plolygon-contains-polygon 用 var a = [ [ 0 , 0 ] , [ 100 , 0 ] , [ 100 , 100 ] , [ 0 , 100 ]] ;var b = [ [ 20 , 20 ] , [ 80 , 20 ] , [ 80 , 80 ] , [ 20 , 80 ]] ;console . log ( ...
geojson-clip-polygon 围绕草皮的小包装线相交,可将一个geojson多边形安全地剪切到另一个
网格切片多边形用平面切片网格并返回生成的多边形安装npm install mesh-slice-polygon 用下面的代码是提取 var createSlicer = require ( './mesh-slice-polygon' ) ;var slicer = createSlicer ( ) ;var stl = ...
An improved method for calculating the no-fit polygon Hamish T. Dean∗,Yiliu Tu, John F. Raffensperger 200 Armagh Street, P.O. Box 13-761, Christchurch, New Zealand
蓝色六边形svg动画404页面源码,HTML+CSS+JS+CSS,记事本打开源码文件可以进行内容文字之类的修改,双击html文件可以本地运行效果,也可以上传到服务器里面,重定向这个界面
gmaps-simple-polygon
POLYGON Apocalypse Pack包含超过1800个详细的预制件包含在此包装中。Unity绝对庞大的低聚资产模型包,适合使用在梦想游戏的开发上,只要你需要低聚模型,比如建筑、车辆、角色、道具、武器、特效,他都应有尽有。