板刷计划:ARC060

传送门:https://atcoder.jp/contests/arc060/tasks

前言:D把我卡死了。 E,F都挺简单的.

略.

给你两个数 n , s. 让你找到一个b进制使得 n在b进制下数位和 = s.有多解，输出最小的b

题目思路：

形式化定义为:

$x_0+x_1*b+...+x_n*b^n=n\\x_0+x_1+...+x_n=s$

观察到一点：

要使得 n 表示出的最高次幂大小大于等于 2 的话， $b^2*x_2+b*x_1+x_0=n \rightarrow b ^2 <= n\rightarrow b <= \sqrt{n}$

所以这种情况，我们只需要暴力枚举 b到根号n. 若存在，就是最小答案

当最高次幂 = 1 时, $x0+b*x_1=n\\x_0+x1=s$

两式合并得到: $x_1(b-1)=n-s$

这时，我们只需要枚举 n - s 内的因数(x1). 得到 b - 1. 然后根据上面两个式子判断合法性即可。

这里要注意一点: 为了防止溢出问题。判断 x * x <= n 可以变成 x <= n / x.

题目大意:在线段上给你一些点。你站在一个点上，每一步只能走不超过<= L 的距离。每一步一定要从一个点到另一个点上。保证每个相邻的点的距离 <= L . 现在Q次询问，每次询问你从点 A 到点B 至少需要多少步。

题目思路:倍增

用二分初始化dp[i][0].logn时间解决询问即可。r

联系倍增求LCA的原理(深度相同时,不相等就跳的原理)。查询[x,y]时，注意我们是移动到 < y 的最大位置。如果dp[pos][i] < y就跳到dp[pos][i].最后ans再++。

这题个人认为难度仅次于C.

题目大意:给你一个字符串。让你用最少的切分次数使得切出来的字符串不含循环节。以及切分方案数.

题目思路：

容易观察到，答案要么是0次（不含循环节），要么是1次(含有循环节)，要么是 n - 1 次(全等字符串)。

其他两个很容易。对于1次的：我们很容易构造出一种划分方式使得剩下的两个部分都不是循环节。

对于方案数，枚举分割点，利用next数组判两部分循环节(正着求一遍next,反着求一遍next即可)