AcWing 5572. 魔法植物
原题链接
困难
作者:
ordinary_
,
2024-04-22 13:13:42
,
所有人可见
,
阅读 6
题目描述
给你x、y,求最大的n使得用1~n所有数能分别用x,y减去,不能一个数同时用x、y减。
思路
- 1~n(n + 1)/2一定可以被数字1~n凑出。
证明:数学推理
假设1-n可以组成1-n*(n+1)/2所有数,则1-n+1可以组成1-(n+1)*(n+2)/2所有数。因为,(n+1)*(n+2)/2-n*(n+1)/2=n+1。把组成1~n*(n+1)/2的倒数n+1个数都所有数加上n+1就等于1~(n+1)*(n+2)/2倒数n+1个数。前提是n*(n+1)/2>=n+1 ==> n >= 2
又因为n==1的时候也成立,所以,对于所有的n都有 1~n(n + 1)/2一定可以被数字1~n凑出。
- 题目中假设答案为n则n*(n+1)/2<=x+y (由上面的理论可以推出只要满足这个不等式的n就一定可以凑出x或者y,一定满足答案的条件)。所以,求出满足n*(n+1)/2<=x+y的最大n就是答案
- 求满足条件的方案数。
思路:枚举m可以取的所有值就是答案
要考虑的问题:枚举是的x、y必须满足n*(n+1)/2-y<=x
C++ 代码
blablabla