• 2020.07.12 2020牛客暑期多校训练营（第一场） pro: 5/5/10 rk: 30/1216
• 2020.07.13 2020牛客暑期多校训练营（第二场） pro: 5/6/11 rk: 83/1162

无

• Atcoder AIsing Programming Contest 2020 pro: 4/6/6 rk: 765/7353 FINISHED
• Codeforces Round #655 (Div. 2) pro: 4/6 rk: NaN

无

无

• Codeforces Round #655 (Div. 2) pro: 4/6 rk: NAN

无

无

• Atcoder AIsing Programming Contest 2020 pro: 4/6 rk: 935/7353

• TopCoder ABBA

给出两个数 A 和 B（$1\le A, B \le 10^{16}$），可以对 A 进行若干次操作，每次操作类型如下：

• 加 1，代价为 X；
• 减 1，代价为 Y；
• 乘 $C_i$，代价为 $Z_i$ ；（$2\le C_i \le 10$）
• 平方，代价为 Q ；

最后目标是要把 A 变为 B，问最小代价是多少。

比如 这一题 和 这一题 就是这种类型的题目，想知道这类型题目的一般思路。

复习后缀数组

给定一个括号串，问有多少种不同的合法括号子串，n⇐5e5

题解：将左括号看作1，右括号看作-1，处理出一个前缀和。下面求每个位置开头的合法子串个数，即对于每一个i，求出多少$i<j<n,s.t. s_j=s_{i-1},i < = k< =j,s_k>=s_{i-1}$

​ 先处理出每种前缀和的所有位置，并通过RMQ维护区间最小值，然后在之前处理出的位置数组中二分判断最大可选的j在哪个位置。

​ 求出height，然后j的范围就是$sa_i + height_i + 1 < = j< =n$ ​ 复杂度$O(nlogn)$

Tag：组合数学

Asterism 来源：codeforces

题意数学化表述：

给定一个长度为n的数列a，对于n的任意全排列P构成的集合A，计f(x) = 集合A中满足P[i] + x + i>= a[i]的元素P的个数。

给定质数p，2≤p≤n≤10^5。求所有不满足p | f(x) 的x。

链接

思路： 存在x使f(x) > 0可以推算出x的上界。而最后得到的f(x)一定由几个阶乘相乘得到。对于一个满足P[i] + x + i>= a[i]的排列P，可以求出1-n在排列p中的“松弛区间”，x的变化会使松弛区间出现偏移，使最大的阶乘项发生变化。根据最大的阶乘项小于p可推算x的下界。x在这两个上下界之间是连续的。

复杂度为O（n）。

实际上推算的过程非常困难，找规律+二分查找上下界似乎更好想些