鶸校鶸选手出的题，各位苣苣们tql。
给一份官方题解，相信大家一些题有更好的做法，这里就当抛砖引玉了~
--------------------------------------
A kotori和糖果
知识点：贪心/递归
显然当a和b最接近时为最优解。那么有：
f(2n)=2f(n)
f(2n+1)=f(n)+f(n+1)+1。
由于是多次询问，可通过打表防止超时。对于n为1e18的数据，可递归到1e6（打表范围）然后返回打表值。
大家给出的代码很多人用的map进行备忘录，也是可以的。
显然当a和b最接近时为最优解。那么有：
f(2n)=2f(n)
f(2n+1)=f(n)+f(n+1)+1。
由于是多次询问，可通过打表防止超时。对于n为1e18的数据，可递归到1e6（打表范围）然后返回打表值。
大家给出的代码很多人用的map进行备忘录，也是可以的。
B kotori和气球
知识点：乘法原理
第一个位置有m种选择，后面的位置由于不能和前一位置种类相同，因此都有m-1种选择。答案是m*(m-1)^(n-1)。
第一个位置有m种选择，后面的位置由于不能和前一位置种类相同，因此都有m-1种选择。答案是m*(m-1)^(n-1)。
C kotori和出道
知识点：递归求解
假设n是偶数，不妨设n=2k，第一轮筛掉的是2,4,6...，剩下的是1,3,5,...,2k-1。因此f(2k)=2f(k)-1;
若n为奇数，设n=2k+1，第一轮剩下的是1,3,5,...,2k+1，但马上1号就被筛掉，变成 3,5,...,2k+1，因此f(2k+1)=2f(k)+1;
计算出前几项可发现规律，f(2^m+p)=2p+1。（p<2^m）
可通过数学归纳法证明之。
假设n是偶数，不妨设n=2k，第一轮筛掉的是2,4,6...，剩下的是1,3,5,...,2k-1。因此f(2k)=2f(k)-1;
若n为奇数，设n=2k+1，第一轮剩下的是1,3,5,...,2k+1，但马上1号就被筛掉，变成 3,5,...,2k+1，因此f(2k+1)=2f(k)+1;
计算出前几项可发现规律，f(2^m+p)=2p+1。（p<2^m）
可通过数学归纳法证明之。
D kotori和迷宫
知识点：BFS
BFS求最短路即可。注意出口要当成墙壁来看待（因为遇到出口即退出）。
BFS求最短路即可。注意出口要当成墙壁来看待（因为遇到出口即退出）。
E kotori和素因子
知识点：DFS、回溯法
可以用一个结构体存每个数的所有不同素因子。然后用回溯法去找所有不重复的取法，用一个min来维护最小值即可。
可以用一个结构体存每个数的所有不同素因子。然后用回溯法去找所有不重复的取法，用一个min来维护最小值即可。
F kotori和n皇后
知识点：二分查找、排序
值得注意的是，只要某一次放下皇后会产生互相攻击，那么之后所有的操作都会互相攻击。因此可以二分查找第一次导致互相攻击的操作。判断是否互相攻击的方法是：分别按照x,y,x+y,x-y四种方式排序，每次排序后即可通过一次遍历来确定是否存在一行/一列/45度/135度的相互攻击的皇后。
总复杂度O(nlognlogn)
也可以用set/map存x,y,x+y和x-y，判断每次输入是否存在已有值。
值得注意的是，只要某一次放下皇后会产生互相攻击，那么之后所有的操作都会互相攻击。因此可以二分查找第一次导致互相攻击的操作。判断是否互相攻击的方法是：分别按照x,y,x+y,x-y四种方式排序，每次排序后即可通过一次遍历来确定是否存在一行/一列/45度/135度的相互攻击的皇后。
总复杂度O(nlognlogn)
也可以用set/map存x,y,x+y和x-y，判断每次输入是否存在已有值。
G kotori和抽卡（二）
知识点：概率、组合数
n次试验中概率为p的事件发生m次的概率为C(n,m)*p^n*(1-p)^(n-m)。注意本题组合数不能直接用n!/m!(n-m)!来求（因为会爆long long）。可以通过循环，乘一个数后除一个数；或递归（需要用数组维护中间计算结果）来完成。
n次试验中概率为p的事件发生m次的概率为C(n,m)*p^n*(1-p)^(n-m)。注意本题组合数不能直接用n!/m!(n-m)!来求（因为会爆long long）。可以通过循环，乘一个数后除一个数；或递归（需要用数组维护中间计算结果）来完成。
H andy和购物
知识点：贪心
分别对货物和折扣排序，最大的货物对应最小的折扣即可。
分别对货物和折扣排序，最大的货物对应最小的折扣即可。
I andy种树
知识点：前缀和/dp
每次区间[i,j]上进行+1，对应的是前缀和数组sum[i-1]--，sum[j]++。最后进行一次前缀和。
每次区间[i,j]上进行+1，对应的是前缀和数组sum[i-1]--，sum[j]++。最后进行一次前缀和。
J andy的树被砍了
知识点：前缀和、二分查找
先求前缀和，对应的是第i天砍的树的总长度。
对应第i天可以先加上前缀和数组中的sum[i-1]（相当于补上之前没砍过的）。然后二分查找第几天被砍完。
先求前缀和，对应的是第i天砍的树的总长度。
对应第i天可以先加上前缀和数组中的sum[i-1]（相当于补上之前没砍过的）。然后二分查找第几天被砍完。
全部评论
(0) 回帖