容斥 + 组合数学 ---Codeforces Round #317 A. Lengthening Sticks
2024-10-18 21:20:36
Lengthening Sticks
Problem's Link: http://codeforces.com/contest/571/problem/A
Mean:
给出a,b,c,l,要求a+x,b+y,c+z构成三角形,x+y+z<=l,成立的x,y,z有多少种。
analyse:
这题在推公式的时候细心一点就没问题了。
基本的思路是容斥:ans=所有的组合情况-不满足条件的情况。
1.求所有的组合情况
方法是找规律:
首先只考虑l全部都用掉的情况。
l=1:3
l=2:6
l=3:10
l=4:15
......
到这可能你会发现,其实l=i时,结果就是1+2+...+(i+1),即:C(i+2,2),也就是三角数。
然而i可以取0~l中的任何一个,那也很简单,一路累加上去就可。
2.不满足条件的情况:
三角形满足的条件是什么?任意两边之和大于第三边,那么不满足的必要条件就是第三边小于等于其它两边之和。
分别枚举a,b,c做第三边的情况,再考虑将剩下的l拆分三份分配给a,b,c依旧不满足的情况即可。
Time complexity: O(N)
Source code:
;
;
);
;
;;
;
}
/*
;
);
;
;;
;
}
/*
*/
最新文章
- eclipse 设置jsp页面为HTML5
- JQuery快速入门
- VelocityTracker简介
- django-ajax之post方式
- Branch and Bound:分支限界算法
- Swift中元组(Tuples),结构体(Struct),枚举(Enums)之间的区别
- 正确openvSwitch不同种类port认识
- linux服务器操作系统,在相同环境下,哪个做lamp服务器更稳定点?哪个版本更稳定?
- Java多线程:线程与进程
- linux 大冒险
- sklearn中的损失函数
- centos 安装部署zabbix
- 【转】怎么给javascript + div编辑框光标位置插入表情文字等?
- MySqlHelper的封装
- 20165231 2017-2018-2 《Java程序设计》第7周学习总结
- css清除浏览器默认样式
- 测试开发之Django——No3.Django中的试图(views)
- dataGridView1.DataSource,解决查询结果不从第一行显示,而是不断往表下面扩展问题
- Python中将字典转换为有序列表、无序列表的方法
- C语言近程型(near)和远程型(far)的区别是什么?
热门文章
- 使用Bootstrap3和Ladda UI实现的多种按钮“加载中”效果体验
- UNIX网络编程读书笔记:基本SCTP套接口编程
- UNIX网络编程读书笔记:TCP输出、UDP输出和SCTP输出
- request.getHeader不区分大小写
- 右键菜单 GenericMenu
- poj 1125 (floyed 最短路径)
- QtGui.QCalendarWidget
- vue + 百度地图api
- 浅析CentOS和RedHat Linux的区别(转)
- LINUX下动态链接库的使用-dlopen dlsym dlclose dlerror