2020-2021:teams:too_low:0711-0717

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:too_low:0711-0717 [2020/07/17 15:28]
dragonylee
+++ 2020-2021:teams:too_low:0711-0717 [2020/08/02 11:25] (当前版本)
dragonylee
@@ 行 18: / 行 18: @@
 ==== 比赛 ====
-  * [[https://blog.csdn.net/dragonylee/article/details/107402229|Atcoder AIsing Programming Contest 2020]] ''%%pro: 4/5/6%%'' ''%%rk: 765/7353%%''
+  * [[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%%''
+  * [[https://blog.csdn.net/dragonylee/article/details/107409181|Codeforces Round #655 (Div. 2)]] ''%%pro: 4/6%%'' ''%%rk: NaN%%''
@@ 行 36: / 行 36: @@
 ==== 比赛 ====
-无
+  * [[http://112.74.186.118/doku.php?id=2020-2021:teams:too_low:cf665cy|Codeforces Round #655 (Div. 2)]] ''%%pro: 4/6%%'' ''%%rk: NAN%%''
 ==== 题目 ====
@@ 行 52: / 行 51: @@
 ==== 比赛 ====
-无
+  * [[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]]
 <html><br/></html>
@@ 行 73: / 行 71: @@
 最后目标是要把 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<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。
+[[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）。
+实际上推算的过程非常困难，找规律+二分查找上下界似乎更好想些
-无

2020-2021/teams/too_low/0711-0717.1594970933.txt.gz · 最后更改: 2020/07/17 15:28 由 dragonylee