====== 2020/07/11 – 2020/07/17 周报 ======
===== 团队训练 =====
* 2020.07.12 [[2020niuke1|2020牛客暑期多校训练营（第一场）]] ''%%pro: 5/5/10%%'' ''%%rk: 30/1216%%''
* 2020.07.13 [[2020niuke2|2020牛客暑期多校训练营（第二场）]] ''%%pro: 5/6/11%%'' ''%%rk: 83/1162%%''
===== 李英龙 =====
==== 专题 ====
无
==== 比赛 ====
* [[https://blog.csdn.net/dragonylee/article/details/107402229|Atcoder AIsing Programming Contest 2020]] ''%%pro: 4/6/6%%'' ''%%rk: 765/7353%%'' **FINISHED**
* [[https://blog.csdn.net/dragonylee/article/details/107409181|Codeforces Round #655 (Div. 2)]] ''%%pro: 4/6%%'' ''%%rk: NaN%%''
==== 题目 ====
无
===== 陈源 =====
==== 专题 ====
无
==== 比赛 ====
* [[http://112.74.186.118/doku.php?id=2020-2021:teams:too_low:cf665cy|Codeforces Round #655 (Div. 2)]] ''%%pro: 4/6%%'' ''%%rk: NAN%%''
==== 题目 ====
无
===== 胡琎 =====
==== 专题 ====
无
==== 比赛 ====
* [[https://blog.csdn.net/weixin_43936456/article/details/107410018 | Atcoder AIsing Programming Contest 2020]] ''%%pro: 4/6%%'' ''%%rk: 935/7353%%''
==== 题目 ====
* [[https://blog.csdn.net/weixin_43936456/article/details/107412053 | 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，问最小代价是多少。
比如 [[https://atcoder.jp/contests/agc044/tasks/agc044_a|这一题]] 和 [[https://ac.nowcoder.com/acm/contest/6218/B|这一题]] 就是这种类型的题目，想知道这类型题目的一般思路。
==== 陈源 ====
复习后缀数组
=== CF643F ===
给定一个括号串，问有多少种不同的合法括号子串，n<=5e5
题解：将左括号看作1，右括号看作-1，处理出一个前缀和。下面求每个位置开头的合法子串个数，即对于每一个i，求出多少$i=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。
[[https://codeforces.com/contest/1371/problem/E2 | 链接]]
思路：
存在x使f(x) > 0可以推算出x的上界。而最后得到的f(x)一定由几个阶乘相乘得到。对于一个满足P[i] + x + i>= a[i]的排列P，可以求出1-n在排列p中的“松弛区间”，x的变化会使松弛区间出现偏移，使最大的阶乘项发生变化。根据最大的阶乘项小于p可推算x的下界。x在这两个上下界之间是连续的。
复杂度为O（n）。
实际上推算的过程非常困难，找规律+二分查找上下界似乎更好想些