数学专题 by kuangbin

从放暑假前周sir给我讲了一个用polya计数法和burnside定理做的题目(pku2409)后,突然觉得组合数学挺有意思,然后从那时起到现在几乎都在做这类的题目。
做到现在感觉这类题目的一些基本知识点都差不多有所了解了,水题也刷了不少,但还有很多难题自己实在是做不动,所以准备把这类题目先放一放,然后把前段时间做的水题整理一下(供以后的初学者参考,大牛就不要看了哈,都是水题)。剩下的比较难的题目就慢慢来吧,以后做出来再不上,这个小结会不断地更新。也希望大家有好的题目可以推荐一下,分享一下哈。
感谢:周sir,J_factory和福州大学神牛aekdycoin,大连理工大学神牛czyuan。
不扯了,进入主题:
1.burnside定理,polya计数法
这个专题我单独写了个小结,大家可以简单参考一下:polya 计数法,burnside定理小结
2.置换,置换的运算
置换的概念还是比较好理解的,《组合数学》里面有讲。对于置换的幂运算大家可以参考一下潘震皓的那篇《置换群快速幂运算研究与探讨》,写的很好。
*简单题:(应该理解概念就可以了)
pku3270 Cow Sorting
http://acm.pku.edu.cn/JudgeOnline/problem?id=3270
pku1026 Cipher
http://acm.pku.edu.cn/JudgeOnline/problem?id=1026
*置换幂运算:
pku1721 CARDS
http://162.105.81.212/JudgeOnline/problem?id=1721
pku3128 Leonardo’s Notebook
http://162.105.81.212/JudgeOnline/problem?id=3128
*推荐:(不错的应用)
pku3590 The shuffle Problem
http://162.105.81.212/JudgeOnline/problem?id=3590
3.素数,整数分解,欧拉函数
素数是可能数论里最永恒,最经典的问题了(我们的队名就叫PrimeMusic^-^)。素数的判断,筛法求素数,大素数的判断···还有很多其他问题都会用到素数。
*最水最水的:(心情不爽时用来解闷吧)
pku1365 Prime Land
pku2034 Anti-prime Sequences
pku2739 Sum of Consecutive Prime Numbers
pku3518 Prime Gap
pku3126 Prime Path
pku1595 Prime Cuts
pku3641 Pseudoprime numbers
pku2191 Mersenne Composite Numbers
pku1730 Perfect Pth Powers
pku2262 Goldbach’s Conjecture
pku2909 Goldbach’s Conjecture
*筛法:
pku2689 Prime Distance(很好的一个应用)
http://162.105.81.212/JudgeOnline/problem?id=2689
*反素数:
zoj2562 More Divisors
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2562
*素数判断,整数分解:
这两题都要用到miller_rabin的素数判断和pollard_rho的整数分解,算法书上都会有,应该是属于模板题吧,不过最好看懂自己敲一遍。
pku1811 Prime Test
http://acm.pku.edu.cn/JudgeOnline/problem?id=1811
pku2429 GCD & LCM Inverse
http://acm.pku.edu.cn/JudgeOnline/problem?id=2429
*欧拉函数:
数论里很多地方都能用到欧拉函数,很重要的。
pku1284 Primitive Roots (很水)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1284
pku2407 Relatives (很水)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2407
pku2773 Happy 2006
http://162.105.81.212/JudgeOnline/problem?id=2773
pku2478 Farey Sequence (快速求欧拉函数)
http://162.105.81.212/JudgeOnline/problem?id=2478
pku3090 Visible Lattice Points (法雷级数)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3090
*推荐:(欧拉函数,费马小定理)
pku3358 Period of an Infinite Binary Expansion
http://acm.pku.edu.cn/JudgeOnline/problem?id=3358
*整数分解
这个也很重要的耶,包括大数的表示方法。
pku2992 Divisors
http://acm.pku.edu.cn/JudgeOnline/problem?id=2992
fzu1753 Another Easy Problem
http://acm.fzu.edu.cn/problem.php?pid=1753
hit2813 Garden visiting
http://acm-hit.sunner.cn/judge/show.php?Proid=2813
pku3101 Astronomy (分数的最小公倍数)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3101
4.扩展欧几里得,线性同余,中国剩余定理
这应该是数论里比较重要的一个部分吧,这类的题目也挺多,具体的内容最好先看看数论书,我也整理过一些,可以参考参考:
http://hi.baidu.com/%B1%BF%D0%A1%BA%A2%5Fshw/blog/item/0676025d56a87d4afbf2c093.html
*简单题:
pku1006 Biorhythms
http://acm.pku.edu.cn/JudgeOnline/problem?id=1006
pku1061 青蛙的约会
http://acm.pku.edu.cn/JudgeOnline/problem?id=1061
pku2891 Strange Way to Express Integers
http://acm.pku.edu.cn/JudgeOnline/problem?id=2891
pku2115 C Looooops
http://acm.pku.edu.cn/JudgeOnline/problem?id=2115
pku2142 The Balance
http://162.105.81.212/JudgeOnline/problem?id=2142
*强烈推荐:
sgu106 The equation
http://acm.sgu.ru/problem.php?contest=0&problem=106
pku3708 Recurrent Function (经典)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3708
5.约瑟夫环问题
这个问题还是比较有意思的,不是很难。
*简单题:
pku3517 And Then There Was One
http://acm.pku.edu.cn/JudgeOnline/problem?id=3517
pku1781 In Danger
http://acm.pku.edu.cn/JudgeOnline/problem?id=1781
pku1012 Joseph
http://162.105.81.212/JudgeOnline/problem?id=1012
pku2244 Eeny Meeny Moo
http://162.105.81.212/JudgeOnline/problem?id=2244
*推荐:
pku2886 Who Gets the Most Candies?
http://162.105.81.212/JudgeOnline/problem?id=2886
6.高斯消元法解方程
其实解方程并不是很难,就是按线性代数中学的那种方法,把系数矩阵化成上三角矩阵或数量矩阵,不过有些题目要判断是否有解,或枚举所有解。不过这类题目我认为比较难的还是怎么去建立这个方程组,这个理解了,就没什么大问题了。
*简单题:
pku1222 EXTENDED LIGHTS OUT
http://162.105.81.212/JudgeOnline/problem?id=1222
pku1681 Painter’s Problem
http://162.105.81.212/JudgeOnline/problem?id=1681
pku1830 开关问题
http://162.105.81.212/JudgeOnline/problem?id=1830
*推荐:
pku2947 Widget Factory
http://162.105.81.212/JudgeOnline/problem?id=2947
pku2065 SETI
http://162.105.81.212/JudgeOnline/problem?id=2065
*强烈推荐:
pku1753 Flip Game
http://162.105.81.212/JudgeOnline/problem?id=1753
pku3185 The Water Bowls
http://162.105.81.212/JudgeOnline/problem?id=3185
*变态题:
pku1487 Single-Player Games
http://162.105.81.212/JudgeOnline/problem?id=1487
7.矩阵
用矩阵来解决问题确实很常见,但我现在用到还不是很好,很多难题我还不会做。建议大家可以去看Matrix67的那篇关于矩阵的十个问题,确实很经典,但不太好看懂。
*简单:
pku3070 Fibonacci
http://162.105.81.212/JudgeOnline/problem?id=3070
pku3233 Matrix Power Series
http://162.105.81.212/JudgeOnline/problem?id=3233
pku3735 Training little cats
http://162.105.81.212/JudgeOnline/problem?id=3735
8.高次同余方程
有关这个问题我应该是没什么发言权了,A^B%C=D,我现在只会求D和B,唉,很想知道A该怎么求。就先推荐几道题目吧,这里涉及到了一个baby-step,giant-step算法。
fzu1759 Super A^B mod C
http://acm.fzu.edu.cn/problem.php?pid=1759
pku3243 Clever Y
http://162.105.81.212/JudgeOnline/problem?id=3243
pku2417 Discrete Logging
http://162.105.81.212/JudgeOnline/problem?id=2417
hdu2815 Mod Tree
http://acm.hdu.edu.cn/showproblem.php?pid=2815
9.容斥原理,鸽巢原理
很有用的两个定理,但好像单独考这两个定理的不是很多。
*鸽巢原理:
pku2365 Find a multiple
http://162.105.81.212/JudgeOnline/problem?id=2356
pku3370 Halloween treats
http://162.105.81.212/JudgeOnline/problem?id=3370
*容斥原理:
hdu1695 GCD
http://acm.hdu.edu.cn/showproblem.php?pid=1695
hdu2461 Rectangles
http://acm.hdu.edu.cn/showproblem.php?pid=2461
10.找规律,推公式
这类题目的设计一般都非常巧妙,真的是很难想出来,但只要找到规律或推出公式,就不是很难了。我很多都是在参考别人思路的情况下做的,能自己想出来真的很不容易。
*个人感觉都挺不错的:
pku3372 Candy Distribution
http://162.105.81.212/JudgeOnline/problem?id=3372
pku3244 Difference between Triplets
http://162.105.81.212/JudgeOnline/problem?id=3244
pku1809 Regetni
http://162.105.81.212/JudgeOnline/problem?id=1809
pku1831 不定方程组
http://162.105.81.212/JudgeOnline/problem?id=1831
pku1737 Connected Graph
http://162.105.81.212/JudgeOnline/problem?id=1737
pku2480 Longge’s problem
http://162.105.81.212/JudgeOnline/problem?id=2480
pku1792 Hexagonal Routes
http://acm.pku.edu.cn/JudgeOnline/problem?id=1792
11.排列组合,区间计数,计数序列
这些题目可能需要一些组合数学知识,基本上高中的知识就够了。区间计数问题一般不难,但写的时候需要仔细一些,各种情况要考虑到位。至于像卡特兰数,差分序列,斯特灵数···都还挺有意思,可以去看看《组合数学》。
*简单题:
pku1850 Code
http://162.105.81.212/JudgeOnline/problem?id=1850
pku1150 The Last Non-zero Digit
http://162.105.81.212/JudgeOnline/problem?id=1150
pku1715 Hexadecimal Numbers
http://162.105.81.212/JudgeOnline/problem?id=1715
pku2282 The Counting Problem
http://162.105.81.212/JudgeOnline/problem?id=2282
pku3286 How many 0’s?
http://162.105.81.212/JudgeOnline/problem?id=3286
*推荐:
pku3252 Round Numbers
http://162.105.81.212/JudgeOnline/problem?id=3252
*计数序列:
pku1430 Binary Stirling Numbers
http://162.105.81.212/JudgeOnline/problem?id=1430
pku2515 Birthday Cake
http://acm.pku.edu.cn/JudgeOnline/problem?id=2515
pku1707 Sum of powers
http://acm.pku.edu.cn/JudgeOnline/problem?id=1707
12.二分法
二分的思想还是很重要的,这里就简单推荐几个纯粹的二分题。
*简单:
pku3273 Monthly Expense
http://162.105.81.212/JudgeOnline/problem?id=3273
pku3258 River Hopscotch
http://162.105.81.212/JudgeOnline/problem?id=3258
pku1905 Expanding Rods
http://162.105.81.212/JudgeOnline/problem?id=1905
pku3122 Pie
http://162.105.81.212/JudgeOnline/problem?id=3122
*推荐:
pku1845 Sumdiv
http://acm.pku.edu.cn/JudgeOnline/problem?id=1845
13.稳定婚姻问题
无意中接触到这个算法,还蛮有意思的,《组合数学》中有详细的介绍。
pku3487 The Stable Marriage Problem
http://acm.pku.edu.cn/JudgeOnline/problem?id=3487
zoj1576 Marriage is Stable
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1576
14.数位类统计问题
在航点月赛中第一次接触到这类问题,scau大牛little龙推荐我看了一篇论文,09年刘聪的《浅谈数位类统计问题》,这篇论文相当精彩,也相当详细,每道题都有详细的分析和作者的参考代码。所以我也没什么可说的了,这些题的代码我博客里也就不贴了,大家直接去看论文吧。
简单:
ural1057 Amount of degrees
http://acm.timus.ru/problem.aspx?space=1&num=1057
spoj1182 Sorted bit squence
https://www.spoj.pl/problems/SORTBIT/
hdu3271 SNIBB
http://acm.hdu.edu.cn/showproblem.php?pid=3271
较难:
spoj2319 Sequence
https://www.spoj.pl/problems/BIGSEQ/
sgu390 Tickets
http://acm.sgu.ru/problem.php?contest=0&problem=390
以上分类的题目在我的博客里都可以找到详细的解题报告和参考代码,由于比较麻烦就没加链接,需要的可以用我的站内搜索找到。
本小结会不断更新,转载请注明出处。
严重声明:本文只适合ACM初学者,路过的大牛如有相同类型的比较好的题目可以推荐一些啊。
来自: http://hi.baidu.com/%B1%BF%D0%A1%BA%A2%5Fshw/blog/item/5305e12c7289973e359bf768.html

http://apps.hi.baidu.com/share/detail/15350489

view plaincopy to clipboardprint?
·········10········20········30········40········50········60········70········80········90········100·······110·······120·······130·······140·······150
对数学类题目小结中的题目的简单解题报告:
偶然在网上看到某牛人发的数学题目小结,于是拷了回来做,下面每道题目后面注释的是我写的简单解题报告(有些只是注意事项),而且并非所有都有做,所以希望大家理解,目前正在更新中。
原文连接在这里:http://hi.baidu.com/%B1%BF%D0%A1%BA%A2_shw/blog/item/5305e12c7289973e359bf768.html
这里题目之前有‘ #’ 的表示已过,‘ ?’ 表示做了但还没过。
/******************************************************************************************/
1.burnside 定理,polya 计数法
这个大家可以看brudildi 的《组合数学》,那本书的这一章写的很详细也很容易理解。最好能完全看懂了,理解了再去做题,不要只记个公式。
* 简单题:(直接用套公式就可以了)
# pku2409 Let it Bead // 翻转时注意珠子为奇偶的情况。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2409
# pku2154 Color//LTC 的题目,看《具体数学》p141 ,有个化简的公式。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2154
# pku1286 Necklace of Beads // 和2409 一样
http://acm.pku.edu.cn/JudgeOnline/problem?id=1286
* 强烈推荐:(这题很不错哦,很巧妙)
# pku2888 Magic Bracelet // 见月赛解题报告.A[i][j] 为可达矩阵. 而且注意约数的个数范围。其中矩阵的幂可以预先求出所有matrix[2^i] 出来,然后根据二进制来 求。
http://162.105.81.212/JudgeOnline/problem?id=2888
2. 置换,置换的运算
置换的概念还是比较好理解的,《组合数学》里面有讲。对于置换的幂运算大家可以参考一下潘震皓的那篇《置换群快速幂运算研究与探讨》,写的很好。
* 简单题:(应该理解概念就可以了)
# pku3270 Cow Sorting // 列出置换,然后对于每一个置换循环,不断用环中的最小的那个和其他的进行换位,可以得到最优。另外还有一种情况就是用整个置换最小的那个和该环进行换位,对于每个环求出这两个的最小值加起来就可以了。
http://acm.pku.edu.cn/JudgeOnline/problem?id=3270
# pku1026 Cipher // 先找出所有置换循环,然后对于每一位来计算k% 循环长度后对应于哪个位置,O(n) 复杂度。注意读写方面的东西。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1026
* 置换幂运算:
# pku1721 CARDS // 详细见05 集训队论文《置换群快速幂运算研究与探讨》。
http://162.105.81.212/JudgeOnline/problem?id=1721
# pku3128 Leonardo’s Notebook// 摘自:http://blog.csdn.net/J_Factory/archive/2008/08/28 /2845330.aspx
题目意思是:一个置换是否可以由另一个置换的平方得来的。一个置换的平方,原来偶数长的循环会被分裂成两段长度相等的循环,而奇数长的循环不会被分裂。题目只是问是否存在,所以只要看所给置换中偶数长的循环是否成对,否则就不能由一个置换的平方得来。
补充:因为如果所给置换的循环是偶数,则肯定是由分裂过来的,那么一定是成对的,否则如果是奇数,那么有可能是原来是奇数,也有可能是原来的偶数分裂成两个奇数循环。
http://162.105.81.212/JudgeOnline/problem?id=3128
* 推荐:(不错的应用)
# pku3590 The shuffle Problem // 把n 分解成若干个数,使得他们的lcm 最大。在所取的数都是素数幂的时候是最大的,所以可以用递归来枚举所有的分解情况,而且由于要输出序最小的,所以对于剩下的数可以直接单独都作为一个循环,这样就可以使得序最小了。此外,这道题目需要注意求最大的lcm 的时候不能用dp 来做,因为这个具有后效 性,局部最优不一定使得全局最优。
http://162.105.81.212/JudgeOnline/problem?id=3590
3. 素数,整数分解,欧拉函数
素数是可能数论里最永恒,最经典的问题了(我们的队名就叫PrimeMusic^-^ )。素数的判断,筛法求素数,大素数的判断··· 还有很多其他问题都会用到素数。
* 最水最水的:(心情不爽时用来解闷吧)
# pku1365 Prime Land
# pku2034 Anti-prime Sequences// 直接搜索,用DL 优化会快很多。
# pku2739 Sum of Consecutive Prime Numbers
pku3518 Prime Gap
pku3126 Prime Path
pku1595 Prime Cuts
pku3641 Pseudoprime numbers
pku2191 Mersenne Composite Numbers
pku1730 Perfect Pth Powers
pku2262 Goldbach’s Conjecture
pku2909 Goldbach’s Conjecture
* 筛法:
# pku2689 Prime Distance (很好的一个应用)// 先找出sqrt(2^32) 内的所有素数,然后类似筛选法筛选掉[l,u] 范围内的数
http://162.105.81.212/JudgeOnline/problem?id=2689
* 反素数:
# zoj2562 More Divisors //waing… 后记:素数表少打了一个19 ~晕死啊~。。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2562
* 素数判断,整数分解:
这两题都要用到miller_rabin 的素数判断和pollard_rho 的整数分解,算法书上都会有,应该是属于模板题吧,不过最好看懂自己敲一 遍。
# pku1811 Prime Test // 学习miller 和pollard 的题目。
http://acm.pku.edu.cn/JudgeOnline/problem?id=1811
# pku2429 GCD & LCM Inverse // 分解lcm/gcd 为互质的p,q ,要用到Miller Rabin 和Pollard rho 算法,基本上做出来之后都是模板题了。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2429
* 欧拉函数:
数论里很多地方都能用到欧拉函数,很重要的。
# pku1284 Primitive Roots (很水)// 定理:对于奇素数m, 原根个数为phi(phi(m)), 由于phi(m)=m-1, 所以为phi(m-1)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1284
# pku2407 Relatives (很水)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2407
# pku2773 Happy 2006 //n 之后的互质的数都是n 之前的加上n 的倍数的。
http://162.105.81.212/JudgeOnline/problem?id=2773
# pku2478 Farey Sequence (快速求欧拉函数)// 求前n 个欧拉函数的和,用学习指导里面的n*(1+lnln(n)) 的算法就可以了,非常快。
http://162.105.81.212/JudgeOnline/problem?id=2478
# pku3090 Visible Lattice Points (法雷级数)
http://acm.pku.edu.cn/JudgeOnline/problem?id=3090
* 推荐:(欧拉函数,费马小定理)
# pku3358 Period of an Infinite Binary Expansion// 转化为高次同余方程。
http://acm.pku.edu.cn/JudgeOnline/problem?id=3358
* 整数分解
这个也很重要的耶,包括大数的表示方法。
# pku2992 Divisors// 注意预处理,有很多组数据.
http://acm.pku.edu.cn/JudgeOnline/problem?id=2992
? fzu1753 Another Easy Problem// 记得n! 有多少个p 的幂是怎么求的。
http://acm.fzu.edu.cn/problem.php?pid=1753
hit2813 Garden visiting
http://acm-hit.sunner.cn/judge/show.php?Proid=2813
? pku3101 Astronomy (分数的最小公倍数)// 高精度gcd ,超时中。
http://acm.pku.edu.cn/JudgeOnline/problem?id=3101
4. 扩展欧几里得,线性同余,中国剩余定理
这应该是数论里比较重要的一个部分吧,这类的题目也挺多,具体的内容最好先看看数论书,我也整理过一些,可以参考参考:
http://hi.baidu.com/%B1%BF%D0%A1%BA%A2%5Fshw/blog/item/0676025d56a87d4afbf2c093.html
* 简单题:
# pku1006 Biorhythms // 注意最后结果为0 或负数的情况
http://acm.pku.edu.cn/JudgeOnline/problem?id=1006
# pku1061 青蛙的约会
http://acm.pku.edu.cn/JudgeOnline/problem?id=1061
# pku2891 Strange Way to Express Integers //x==a1(mod m1),x==a2(mod m2), 两个方程可以求出x ,然后重新令a1 为求出的解x,m1=lcm(m1,m2) ,然后继续和后面的进行求解。注意数据运算过程中可能溢出的问题。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2891
# pku2115 C Looooops
http://acm.pku.edu.cn/JudgeOnline/problem?id=2115
# pku2142 The Balance // 枚举,x=x0+b/d*t ,直到x>min(x+y)
http://162.105.81.212/JudgeOnline/problem?id=2142
* 强烈推荐:
# sgu106 The equation // 求ax+by=c 的时候,考虑a,b 为零的特殊情况,此外,若a,b 不是非负数,那么扩展欧几里德会有问题,于是我们可以把求x,y 变为求 x’=-x,y’=-y ,此时a,b, 就可以变为非负数来处理,同时x’,y’ 的范围也要相应取反。而且在取得区间时候,要注意区间边缘要进行相应的取 整。后记:要用cin,cout 才能AC ,用printf 会wa 。。。极度无奈中,偶然才发现的~_ ~!
http://acm.sgu.ru/problem.php?contest=0&problem=106
# pku3708 Recurrent Function (经典)// 具体数学第一章。对于每一位求出循环节m1 ,还有该位从m 达到k 最少要经过r1 次标号变化,于是就可以得到x==r1 (mod m1) ,然后同样的方法求其他的位,接着就可以两两方程这样解中国剩余定理。
http://acm.pku.edu.cn/JudgeOnline/problem?id=3708
5. 约瑟夫环问题
这个问题还是比较有意思的,不是很难。
* 简单题:
# pku3517 And Then There Was One
http://acm.pku.edu.cn/JudgeOnline/problem?id=3517
# pku1781 In Danger
http://acm.pku.edu.cn/JudgeOnline/problem?id=1781
# pku1012 Joseph // 考虑剩下k+1 个人,那么上一个出局的人肯定是坏人,所以考虑接下来一定要最后一个坏人出局,所以m==0 或1(mod k+1) 。然后枚举m ,再验证。
http://162.105.81.212/JudgeOnline/problem?id=1012
# pku2244 Eeny Meeny Moo
http://162.105.81.212/JudgeOnline/problem?id=2244
* 推荐:
# pku2886 Who Gets the Most Candies?// 线段树+ 反素数。
http://162.105.81.212/JudgeOnline/problem?id=2886
6. 高斯消元法解方程
其实解方程并不是很难,就是按线性代数中学的那种方法,把系数矩阵化成上三角矩阵或数量矩阵,不过有些题目要判断是否有解,或枚举所有解。不过这类题目我认为比较难的还是怎么去建立这个方程组,这个理解了,就没什么大问题了。
* 简单题:
# pku1222 EXTENDED LIGHTS OUT // 解异或运算的方程。n*m 个方程和未知数。
http://162.105.81.212/JudgeOnline/problem?id=1222
# pku1681 Painter’s Problem
http://162.105.81.212/JudgeOnline/problem?id=1681
# pku1830 开关问题 // 以上三题做法都一样。
http://162.105.81.212/JudgeOnline/problem?id=1830
* 推荐:
# pku2947 Widget Factory // 最好要化成严格的阶梯型,方便判解。而且模某个数的时候解方程要用到扩展欧几里德算法。
http://162.105.81.212/JudgeOnline/problem?id=2947
# pku2065 SETI// 与上题一样。
http://162.105.81.212/JudgeOnline/problem?id=2065
* 强烈推荐:
# pku1753 Flip Game // 数据范围比较小,枚举可过。如果用高斯消元做,那么对于多解的时候也是需要枚举的,而且这种类型不具有太大的扩展性,这里高斯消元不见的比枚举要优越。
http://162.105.81.212/JudgeOnline/problem?id=1753
# pku3185 The Water Bowls // 同样如果对于无数解的时候,就需要对解进行枚举。其实这道题目可以先枚举第一位是否需要翻转,然后其他的就已经确定了,不过需要注意如果第一位翻转的时候,答案别忘了加上去,我因为这个搞了好久~~~郁闷。
http://162.105.81.212/JudgeOnline/problem?id=3185
// 同类题目,我自己加上去的。
pku1395
pku2055
ural1561
pku3254
* 变态题:
pku1487 Single-Player Games
http://162.105.81.212/JudgeOnline/problem?id=1487
7. 矩阵
用矩阵来解决问题确实很常见,但我现在用到还不是很好,很多难题我还不会做。建议大家可以去看Matrix67 的那篇关于矩阵的十个问题,确实很经典, 但不太好看懂。
* 简单:
pku3070 Fibonacci
http://162.105.81.212/JudgeOnline/problem?id=3070
pku3233 Matrix Power Series
http://162.105.81.212/JudgeOnline/problem?id=3233
pku3735 Training little cats
http://162.105.81.212/JudgeOnline/problem?id=3735
8. 高次同余方程
有关这个问题我应该是没什么发言权了,A^B%C=D ,我现在只会求D 和B ,唉,很想知道A 该怎么求。就先推荐几道题目吧,这里涉及到了一个baby- step ,giant-step 算法。
# fzu1759 Super A^B mod C //a^b%c=a^(b%phi(c))%c , 注意a==c 的情况,
http://acm.fzu.edu.cn/problem.php?pid=1759
# pku3243 Clever Y // 和上面差不多,不过c 不一定是素数,所以方法就是解出a^m*x+c*y=gcd(a^m,c) 的所有解来判断,若无解则不管,因为c 不是素数可能 a^m 没有逆。
http://162.105.81.212/JudgeOnline/problem?id=3243
# pku2417 Discrete Logging //hash ,最直接的离散对数
http://162.105.81.212/JudgeOnline/problem?id=2417
? hdu2815 Mod Tree // 超时中,时限好像挺紧的。
http://acm.hdu.edu.cn/showproblem.php?pid=2815
# sgu261 求A wa test 23.. 后记:原来是hash 有错误,因为用了vector 后是从0 开始的,而我判断hash 链表结束的是0 ,如果恰好最后一个是在vector 的0 位 置,那么就会忽略掉这个数据,所以就会出现找不到那个数的情况。另外进行最后答案输出的时候,vector 的size ()是返回unsigned int 的,如果size( )是0 ,那么size()-1 就是2^32-1 了,所以这里就需要特别注意。
? http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3538 //handling… 还没有找出更好的方法解决当a 和p 不互质情况下的解法。
http://202.120.80.191/problem.php?problemid=2700
9. 容斥原理,鸽巢原理
很有用的两个定理,但好像单独考这两个定理的不是很多。
* 鸽巢原理:
# pku2356 Find a multiple // 同下。
http://162.105.81.212/JudgeOnline/problem?id=2356
# pku3370 Halloween treats////n 个数,寻找c 个(c<=n) ,使得他们的和为c 的倍数。由抽屉原理,前n 个数的 mod c 肯定有重复的,那么一定存在一个区间使得他们的和是c 的倍数。 http://162.105.81.212/JudgeOnline/problem?id=3370 * 容斥原理: # hdu1695 GCD // 求gcd(x,y)=k 的个数,相当于求gcd(x/k,y/k)=1 的个数,其中x/k 在[a/k,b/k],y/k 在[c/k,d/k] 之间。所 以就是求在一定区间内,x ,y 互质的对数。假设b=times)
{
len=a/(times*10);
for(i=0;i<10;i++)aa[i]+=len*times; if(len>0)aa[0]-=times;
tmp=(a/times)%10;
if(a>=times*10)start=0;else start=1;
for(i=start;im,由于n有n个等价类,一个类包含不可表示出的数是m-1,总是是(n-1)*(m-1)/2
pku 2888 Magic Bracelet(带约束的着色问题)
这题还是要用到波利亚定理,唯一的不同是计算矩阵的幂模,再求矩阵的迹。具体的推导就不知道是怎么来的。关于矩阵是指允许相邻的两种颜色之间有边,这就形成了个无向图。矩阵的n幂模,和快速幂乘的原理是一样的。
pku 2917 Diophantus of Alexandria(不定方程,因数分解)
模拟下后发现,满足1/x+1/y=1/z的x,y是z的约数,并且x,y互素。统计x,y的对数再加1(x=z,y=z是特殊的一对)。
后来看到讨论里有公式,(x-z)(y-z)=z^2,计算小于z,并是z^2的约数就是答案了。
pku2992 Divisors (组合数,因子个数)
计算C(n,k)的因子个数,由于n很小,最大为431,所以可以把1~431的所有数先因式分解,再来统计n*(n-1)…(n-k+1)/k*(k-1)…1的素因子个数。
pku 3370 Halloween treats(鸽巢原理)
给定m个整数a1,a2,a3,..,am,存在整数k和l,0<=k a=k*(2^p-1)+r,先算个打概的k,得到的r>2^p-1,继续减2^p-1。这样比直接模运算要快。

pku 3372 Candy Distribution(二次剩余系)
根据题目的意思可以得到方程 1+n(n+1)/2 =a (mod N),显然这是一个二次模方程。要看N的二次完全剩余系是否都有解。
结论是N要是2^x,x>=0,结论的证明还不知道。
pku 3516 Hide That Number(高精度)
题目是说给出一个数y,找到 x*11= y (mod 10^length(y)),如果y很小,直接求出逆来就能得到答案了,可是y很大,构造的方法没有想到,最后还是暴力做的。每次在y的前面加个数学(1,2..9),或是加上10这两个数字,看新得到的数字是11的倍数。若是,就可以得到答案了。由于y很大,普通的高精度会超时,要增加进制。
pku 3847 The Stable Marriage Problem(稳定婚姻)
稳定婚姻问题。用到了延迟认可算法。用最优方提出匹配,而被匹配者,不会立即接受,而是在提出要求者的集合中去掉,比当前着差的元素,知道没有人提出匹配,被匹配者才确定下匹配关系。值得一提的是,稳定婚姻的存在性不能被保证。
pku 3358 Period of an Infinite Binary Expansion(数论,欧拉定理)
这个题目是求两个数相除p/q,结果的小数部分用二进制表示,当q不是2的幂时,这个二进制是个无线循环的01串。
下面是个模拟小数部分按二进制表示,可以发现二进制传一定会有循环,因为p=p%q,既然是循环,又是模运行,这和p模q的阶有关,p%q的阶一定是q的欧拉函数的因子。这样转换成一个模方程:p*2^n = x(mod q),当然p和q要互素,2和q互素。在计算前把q中的2去掉,p,q同除最大公因数。然后从1开始枚举,所以的欧拉数的因子。
#include
#define pr printf
int main()
{
int i,p,q;
while(scanf(“%d%d”,&p,&q)==2){
pr(“0.”);
for(i=1;i<=100;i++) { p*=2; pr("%d",p/q); p=p%q; } pr("/n"); } } /* 5 192 0.000001101010101010101010101010101010101010101010101010101010101010101010101010 1010101010101010101010 */ pku 3590 The shuffle Problem(置换,数的分解) 题目求一个排列通过置换之后再回到原来的那个排列,对于给定的排列求出一个满足置换次数最多的一个置换。一个置换可以分解成多个循环,每次置换元素之和在同一个循环中的元素发生转换,同一个循环中循环节是元素的个数,所以这个题是要把一个数分成多个数的和,让这些数的最小公倍数最大。要保证lcd最大应该分解出来的每个数两两互素。由于数比较小,23是能最大的素数,所以直接枚举可以满足。 pku 3641 Pseudoprime numbers(费马定理,快速幂乘) 简单题,先看p是否是素数,若是直接输出no。否则计算(a^p)%p,若结果是a输出yes,否则输出no。 2008哈尔滨赛区网络预选1007 The Luckiest number(欧拉定理运用) 题目说要找个数t,它的数字全是8,对于给定的n,t要是n的整数倍,求最小的t。 赛后才发现这题并不拿,可能是我太菜了。这题问题可以转换成8*(10^x-1)/9 = 0 (mod n ),这样就可以看出还有因子5和16的n是没有解的。并且n是偶数时,其解是n除去2因子的解。最后就是求解 10^x = 1 (mod 9*n) n是一个奇数,所以(10,n)=1,这样就可以根据欧拉定理 ,满足等式的解只能是 euler(9*n)的因子。枚举欧拉数的因子,最小的那个就是要求的解。由于n可以到2000000000,快速幂乘要支持64位运算。 2008 成都网络预选 1005 Farey Sequence Again(Farey Sequence ,构造) 与其说是数学题,还不如说是个模拟题。Farey Sequence序列规律性很强,暴力模拟后发现有很多规律。要用到的一个性质是 Fn中连续的3个元素,a1/b1 ,a2/b2,a3/b3。若a1+a3

uva 6692 Lucky Number

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4704

题目大意是说,定义一个数的lucky number是距离i最远的j且满足(a[i]<a[j] i<j)。

问对所有数最大的lucky number是什么。

不必线段树。

我们可以先处理出a[i]的最远点。倒着扫一遍即可。

然后可以处理出大于等于a[i]的最远位置。

codeforces #332 div 2 C. Day at the Beach

C. Day at the Beach
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

One day Squidward, Spongebob and Patrick decided to go to the beach. Unfortunately, the weather was bad, so the friends were unable to ride waves. However, they decided to spent their time building sand castles.

At the end of the day there were n castles built by friends. Castles are numbered from 1 to n, and the height of the i-th castle is equal to hi. When friends were about to leave, Squidward noticed, that castles are not ordered by their height, and this looks ugly. Now friends are going to reorder the castles in a way to obtain that condition hi ≤ hi + 1 holds for all i from 1 to n - 1.

Squidward suggested the following process of sorting castles:

  • Castles are split into blocks — groups of consecutive castles. Therefore the block from i to j will include castlesi, i + 1, …, j. A block may consist of a single castle.
  • The partitioning is chosen in such a way that every castle is a part of exactly one block.
  • Each block is sorted independently from other blocks, that is the sequence hi, hi + 1, …, hj becomes sorted.
  • The partitioning should satisfy the condition that after each block is sorted, the sequence hi becomes sorted too. This may always be achieved by saying that the whole sequence is a single block.

Even Patrick understands that increasing the number of blocks in partitioning will ease the sorting process. Now friends ask you to count the maximum possible number of blocks in a partitioning that satisfies all the above requirements.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of castles Spongebob, Patrick and Squidward made from sand during the day.

The next line contains n integers hi (1 ≤ hi ≤ 109). The i-th of these integers corresponds to the height of the i-th castle.

Output

Print the maximum possible number of blocks in a valid partitioning.

Sample test(s)
input

output

input

output

Note

In 

 

 

View Code

 

 

codeforces #332 div 2 B. Spongebob and Joke

B. Spongebob and Joke
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

While Patrick was gone shopping, Spongebob decided to play a little trick on his friend. The naughty Sponge browsed through Patrick’s personal stuff and found a sequence a1, a2, …, am of length m, consisting of integers from 1 to n, not necessarily distinct. Then he picked some sequence f1, f2, …, fn of length n and for each number ai got number bi = fai. To finish the prank he erased the initial sequence ai.

It’s hard to express how sad Patrick was when he returned home from shopping! We will just say that Spongebob immediately got really sorry about what he has done and he is now trying to restore the original sequence. Help him do this or determine that this is impossible.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the lengths of sequences fi and bi respectively.

The second line contains n integers, determining sequence f1, f2, …, fn (1 ≤ fi ≤ n).

The last line contains m integers, determining sequence b1, b2, …, bm (1 ≤ bi ≤ n).

Output

Print “Possible” if there is exactly one sequence ai, such that bi = fai for all i from 1 to m. Then print m integersa1, a2, …, am.

If there are multiple suitable sequences ai, print “Ambiguity”.

If Spongebob has made a mistake in his calculations and no suitable sequence ai exists, print “Impossible”.

Sample test(s)
input

output

input

output

input

output

Note

In the first sample 3 is replaced by 1 and vice versa, while 2 never changes. The answer exists and is unique.

In the second sample all numbers are replaced by 1, so it is impossible to unambiguously restore the original sequence.

In the third sample fi ≠ 3 for all i, so no sequence ai transforms into such bi and we can say for sure that Spongebob has made a mistake.

 

理解题意。。

需要注意的是。。。只有当在f中重复出现的那个在b中也出现了。。答案才是任意。。不然五影响。。。

 

View Code

 

codeforces #332 div 2 A. Patrick and Shopping

View Code

 

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Today Patrick waits for a visit from his friend Spongebob. To prepare for the visit, Patrick needs to buy some goodies in two stores located near his house. There is a d1 meter long road between his house and the first shop and a d2 meter long road between his house and the second shop. Also, there is a road of length d3 directly connecting these two shops to each other. Help Patrick calculate the minimum distance that he needs to walk in order to go to both shops and return to his house.

Patrick always starts at his house. He should visit both shops moving only along the three existing roads and return back to his house. He doesn’t mind visiting the same shop or passing the same road multiple times. The only goal is to minimize the total distance traveled.

Input

The first line of the input contains three integers d1, d2, d3 (1 ≤ d1, d2, d3 ≤ 108) — the lengths of the paths.

  • d1 is the length of the path connecting Patrick’s house and the first shop;
  • d2 is the length of the path connecting Patrick’s house and the second shop;
  • d3 is the length of the path connecting both shops.
Output

Print the minimum distance that Patrick will have to walk in order to visit both shops and return to his house.

Sample test(s)
input

output

input

output

Note

The first sample is shown on the picture in the problem statement. One of the optimal routes is: house  first shop  second shop  house.

In the second sample one of the optimal routes is: house  first shop  house  second shop  house.

 

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Today Patrick waits for a visit from his friend Spongebob. To prepare for the visit, Patrick needs to buy some goodies in two stores located near his house. There is a d1 meter long road between his house and the first shop and a d2 meter long road between his house and the second shop. Also, there is a road of length d3 directly connecting these two shops to each other. Help Patrick calculate the minimum distance that he needs to walk in order to go to both shops and return to his house.

Patrick always starts at his house. He should visit both shops moving only along the three existing roads and return back to his house. He doesn’t mind visiting the same shop or passing the same road multiple times. The only goal is to minimize the total distance traveled.

Input

The first line of the input contains three integers d1, d2, d3 (1 ≤ d1, d2, d3 ≤ 108) — the lengths of the paths.

  • d1 is the length of the path connecting Patrick’s house and the first shop;
  • d2 is the length of the path connecting Patrick’s house and the second shop;
  • d3 is the length of the path connecting both shops.
Output

Print the minimum distance that Patrick will have to walk in order to visit both shops and return to his house.

Sample test(s)
input

output

input

output

Note

The first sample is shown on the picture in the problem statement. One of the optimal routes is: house  first shop  second shop  house.

In the second sample one of the optimal routes is: house  first shop  house  second shop  house.

 

水题。

 

 

2015亚洲区域赛北京站总结

 

 

 

 

热身赛的时候发现没有codeblocks瞬间爆炸…我从暑假开始用的vim还好…不过两个队友平常用codeblocks的。。

还好有热身赛。。然后cch晚上强行学emacs。。。最后现场赛的时候我用vim写。。队友用emacs写2333

键盘有些别扭。。。上面是日文还是注音。。。看不懂==

总按错。。。

 

然后竟然有201个队。。。  才90个牌子。。。尼玛竟然不按比例来。。。55%的打铁率是闹哪样。。。

当得知这个消息的时候。。我们的内心真的是崩溃的。。。没有常用的cb其实已经够不爽的了(可以现学其他,但是总归是不熟练呀)

本来就觉得自己没底。。。这样更感觉要打铁了。。。

当时我们已经相互安慰了好么。。。。尽力就好尽力就好2333

 

 

比赛开始以后先是zcy和cch读题。。。我先配了一发vim环境。。。写了几个常用的。。。然后把编译和运行设置成了快捷键。。

弄好了之后cch发现j可以写。。。然后就写了j..

然后我看了G。。。发现是个水。。几乎是原题? 白书上那个是三个矩形。。。这个是四选三。。。

不过抱着看到熟悉的题更要细心的精神。。。我又仔细读了遍题。。。发现确实水,貌似G才是签到?(然而并不是

 

这时候cch写完了J不过在调。。。

 

然后我就在草稿纸上把G仔细列了下。。。好像一共(8+12)*4种情况的样子。。。

这时候CCH交了一发J。。。竟然WA了。。。然后我表示把代码打出来吧我要写G。。。

然后大概写到一半…?  cch表示找到写错的地方了。。。于是改J。。

又WA。。。有点方啊。。。然后在机器上debug一会。。。还是有问题。。。

我表示让我先过了G再说吧。。。

然后我大概花了10分钟写完了G。。。交。。卧槽竟然交成了gcc,幸好CE不算罚时。

再交,A了。。

然后CCH发现J题意理解错了(J我没读。。。不过后来发现好多人吐槽J题题意不清而且不好理解。。。朝鲜队WA了好多发)

然后改,再交,终于A了。。。这时候大概过了一个小时? 不那么慌了。。。

然后继续开新题。。。我看了F。。计算几何。。。因为赛前一直在刷计算几何。。结果想了半小时的样子…?发现好难。。放弃了。。

这个时候CCH和 ZCY在讨论D?(我不确定2333) 然后我看了下通过题目。。发现K题有人过。。就去看K了。。。CCH去看了A。。。

这个时候ZCY写了一发D。。。写完之后发现好像想错了QAQ..

看了一会CCH说A就是个二维树状数组,可以搞。 然后他就开始写A。。。

好像因为树状数组的sum函数忘了 return 而WA了一发。。。? 再交,过了。。。   

这时候大概是十一点半。。通过三题。。排名大概在80+?

****************************************

大家一起吃午餐时间,kfc有点良心

****************************************

然后可以搞的题貌似是K和I。。。

于是我开始搞I。。。

一个构造题。。。

大概弄了二十分钟..? 搞出来了。

感觉剩下的题没有很好搞得…

决定剩下的时间就搞I。。四题应该能稳。。

然后我拿着草稿纸把我的构造方法和CCH讨论了下。。。他表示好像很有道理的样子2333

觉得I可以撸。。。。我问CCH你写我写,我细节题有点虚。。他说他写吧。。。毕竟CCH是我们队实力最强的。。这种时候还是求稳比较好。。。

然后中间好像调了好久。。。 不过反正不方!因为我们剩下的题并没有明显可以搞得。。。于是剩下的时间可以都用来搞I。。。

大概1:35的时候吧。。。I终于调对了(1到10的数据检验了下),交,过了,爽!

 

然后最后25分钟。。。大家一起搞K。。各种打表试图找规律。。。然并卵。。。因为那是道数位Dp2333  并不会。

 

当时大概预感到能拿Cu了。。。

不过说真的。。能不能拿Cu我都炒鸡开心。。。

因为并不是抱大腿了。。。我真的特别不喜欢那种抱大腿的感觉。。。

最后72名Cu..  虽然只是块Cu吧。。但是真的炒鸡开心。。。

因为基本上。。我们会的题都做出来了。。。我们想了的但是没有成型思路的题最后发现思路根本就不对。。。

还有几何那道题。。怎么处理交点我实在没想出。。。。。

杜宇飞讲题的时候说“你们都懂得的四道题我就不说了”hhh,我们就是做出了那四道。。。

 

其实原本打算北京之后就退役的。。。

但是这块Cu真的给我了很大的鼓舞。。不仅仅是ACM。。对于课程内的东西也是鼓舞。。。

这周要忙着应付考试。。。

下个期待大概是十二月份的华师校赛

主要是想见xy妹纸(逃

虽然认识没多久…不过感觉各种聊得来(捂脸

她们队在长春拿了Cu。。。

还好北京我们也Cu了。。。这样才不会被嫌弃QAQ。。。

 

总之。。111qqz要学的东西还有很多。。。

明年争取拿银!

fighting!

 

 

幻方….

c语言上机。。。。

c写的幻方。

View Code

 

codeforces #320 div 2 C. A Problem about Polyline(计算几何?数学)

C. A Problem about Polyline
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

There is a polyline going through points (0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – … - (2kx, 0) – (2kx + x, x) – ….

We know that the polyline passes through the point (a, b). Find minimum positive value x such that it is true or determine that there is no such x.

Input

Only one line containing two positive integers a and b (1 ≤ a, b ≤ 109).

Output

Output the only line containing the answer. Your answer will be considered correct if its relative or absolute error doesn’t exceed10 - 9. If there is no such x then output  - 1 as the answer.

Sample test(s)
input

output

input

output

input

output

Note

You can see following graphs for sample 1 and sample 3.

                                  

 

题意:
  有从原点开始,斜率分别为1和-1的折线周期下去,问是否存在x使得整点(a,b)在折线上,存在的话求最小的x,无解输出-1.
 
思路:由于斜率为1,所以x>=y.那么x
对于x>=y的情况:我们发现(a,b)点如果是落在斜率为1的折线上,那么该折线与x轴的交点为(a-b,0)
如果(a,b)点落在落在斜率为-1的折线上,那么该折线与x轴的交点为(a+b,0) 
分析可知,如果a+b为奇数,那么一定会落在斜率为-1的折线上,如果a-b为偶数,一定会落在斜率为1的折线上。
而(a+b)不为偶数和(a-b)补为偶数不可能同时成立。
因为碎玉x>=y的情况一定有解。
二分答案即可(其实还有一种比较偷懒(比较聪明?)的办法是…不去考虑是否一定有解。把二分的初始条件设置为-1就好)
不过证明无解也并不难想。
 
需要注意的是精度问题。。。eps要记得根据题目调整。。。比如这道题要求1E-9…
eps至少比要求的多两位才保险。。。。
因为忘记调整eps(因为一般题目要求都是1E-6。。。所以我eps写的是1E-8)而wa了好多次。。。。
 

View Code

 

 
 

cf #320 B. Finding Team Member(优先队列)

B. Finding Team Member
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There is a programing contest named SnakeUp, 2n people want to compete for it. In order to attend this contest, people need to form teams of exactly two people. You are given the strength of each possible combination of two people. All the values of the strengths are distinct.

Every contestant hopes that he can find a teammate so that their team’s strength is as high as possible. That is, a contestant will form a team with highest strength possible by choosing a teammate from ones who are willing to be a teammate with him/her. More formally, two people A and B may form a team if each of them is the best possible teammate (among the contestants that remain unpaired) for the other one.

Can you determine who will be each person’s teammate?

Input

There are 2n lines in the input.

The first line contains an integer n (1 ≤ n ≤ 400) — the number of teams to be formed.

The i-th line (i > 1) contains i - 1 numbers ai1, ai2, … , ai(i - 1). Here aij (1 ≤ aij ≤ 106, all aij are distinct) denotes the strength of a team consisting of person i and person j (people are numbered starting from 1.)

Output

Output a line containing 2n numbers. The i-th number should represent the number of teammate of i-th person.

Sample test(s)
input

output

input

output

Note

In the first sample, contestant 1 and 2 will be teammates and so do contestant 3 and 4, so the teammate of contestant 1, 2, 3, 4will be 2, 1, 4, 3 respectively.

 

 

对于这种要频繁求最大值的题,首先想到优先队列。。

要注意,一定要定义cmp函数。。。没有默认。

还有一点。。。优先队列的cmp函数的符号是相反的。。。就是如果要大的在前面。。。那么要定义成 a

 

View Code

 

 

poj 1113 Wall (凸包模板题)

Wall
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 32808   Accepted: 11137

Description

Once upon a time there was a greedy King who ordered his chief Architect to build a wall around the King’s castle. The King was so greedy, that he would not listen to his Architect’s proposals to build a beautiful brick wall with a perfect shape and nice tall towers. Instead, he ordered to build the wall around the whole castle using the least amount of stone and labor, but demanded that the wall should not come closer to the castle than a certain distance. If the King finds that the Architect has used more resources to build the wall than it was absolutely necessary to satisfy those requirements, then the Architect will loose his head. Moreover, he demanded Architect to introduce at once a plan of the wall listing the exact amount of resources that are needed to build the wall. 

Your task is to help poor Architect to save his head, by writing a program that will find the minimum possible length of the wall that he could build around the castle to satisfy King’s requirements. 

The task is somewhat simplified by the fact, that the King’s castle has a polygonal shape and is situated on a flat ground. The Architect has already established a Cartesian coordinate system and has precisely measured the coordinates of all castle’s vertices in feet.

Input

The first line of the input file contains two integer numbers N and L separated by a space. N (3 <= N <= 1000) is the number of vertices in the King's castle, and L (1 <= L <= 1000) is the minimal number of feet that King allows for the wall to come close to the castle.  Next N lines describe coordinates of castle’s vertices in a clockwise order. Each line contains two integer numbers Xi and Yi separated by a space (-10000 <= Xi, Yi <= 10000) that represent the coordinates of ith vertex. All vertices are different and the sides of the castle do not intersect anywhere except for vertices.

Output

Write to the output file the single number that represents the minimal possible length of the wall in feet that could be built around the castle to satisfy King’s requirements. You must present the integer number of feet to the King, because the floating numbers are not invented yet. However, you must round the result in such a way, that it is accurate to 8 inches (1 foot is equal to 12 inches), since the King will not tolerate larger error in the estimates.

Sample Input

Sample Output

Hint

结果四舍五入就可以了

Source

 
 
给定n个点,求围一圈围墙使得围墙到每个点的距离大于等于l,求围墙的最小周长。
这道题的关键点是,由于最后是绕着中间的n个点转了一周(2×pi)
每个点对应一定弧度,合起来正好是一个圆的周长。
也就是,最后的答案为凸包的周长加上半径为L的圆的周长。
 
第一次写凸包,感谢适牛的板子,真是炒鸡好用呀喵喵喵。
 
不过引用那里没搞明白QAQ,稍微改了下写法。。

View Code

 

hdu 3532 Max Angle(atan2的使用)

Max Angle

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 678    Accepted Submission(s): 238

Problem Description
Given many points in a plane, two players are playing an interesting game.

Player1 selects one point A as the vertex of an angle. Then player2 selects other two points B and C. A, B and C are different with each other. Now they get an angle B-A-C.

Player1 wants to make the angle as large as possible, while player2 wants to make the angle as small as possible.

Now you are supposed to find the max angle player1 can get, assuming play2 is c lever enough.

 

 

Input
There are many test cases. In each test case, the first line is an integer n (3 <= n <= 1001), which is the number of points on the plane. Then there are n lines. Each contains two floating number x, y, witch is the coordinate of one point. n <= 0 denotes the end of input.
 

 

Output
For each test case, output just one line, containing the max angle player1 can get in degree format. The result should be accurated up to 4 demicals.
 

 

Sample Input
3
0 0
2 0
0 5
-1
 

 

Sample Output
90.0000
 

 

Source
 

 

题意是说。先选一个点A,然后选两个点B,C。 使得每个A对应的最小角B-A-C最大。
 
我们可以枚举每个点,然后求得这个点和其他所有点所成的角度,排序后找到一组相邻的差值最小的,记录为mn
然后对于每个点得到的mn,记录最大的一个,就是答案。
 
角度怎么搞呢…
atan2(y,x)是个好东西。
atan2(y,x)表示点(0,0)到(x,y)的射线与x轴正向所成的角度,取值范围介于 -pi 到 pi 之间(不包括 -pi),
 
我们可以处理下把角度变成0到2*pi之间。
 

还要注意直线的角度不可能是钝角。所以如果答案为钝角记得取补。
 
1A,开心。