2020-2021:teams:too_low:0711-0717
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:too_low:0711-0717 [2020/07/17 23:22] member [陈源] |
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%%'' | ||
| 行 88: | 行 88: | ||
| ==== 胡琎 ==== | ==== 胡琎 ==== | ||
| + | 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.1594999368.txt.gz · 最后更改: 2020/07/17 23:22 由 member
