2020-2021:teams:alchemist:weekly_digest_12
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_12 [2020/08/28 14:14] maxdumbledore 创建 |
2020-2021:teams:alchemist:weekly_digest_12 [2020/08/28 17:26] (当前版本) hardict [龙鹏宇 Hardict] |
||
|---|---|---|---|
| 行 7: | 行 7: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| - | 学习了一点计算几何 | + | 暂无 |
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | 一场atcoder,一场cf global round | + | 一场cf edu, 好惨好惨 |
| - | rating小涨 | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| 暂无 | 暂无 | ||
| 行 22: | 行 21: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | cf div2 | + | cf div2 涨回原rating |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 35: | 行 34: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | 打了atcoder，rating小涨。 | + | cf edu, 算错了复杂度浪费了半个小时。 |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 48: | 行 47: | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| - | 补题，学点新东西 | + | 补题 |
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| 行 54: | 行 53: | ||
| ===== 陈铭煊 Max.D. ===== | ===== 陈铭煊 Max.D. ===== | ||
| - | ===来源：=== | ||
| - | [[https://codeforces.com/contest/1392/problem/F|Codeforces Global Round 10 F. Omkar and Landslide]] | ||
| - | ===标签：=== | + | === 来源： === |
| - | 思维题 | + | |
| - | ===题意：=== | + | |
| - | 给出一个$n(1\le n \le 10^6)$长的严格递增序列$h$，每一次找到满足所有$h_{i+1}-h_i\ge 2$的下标$i(1\le i< n)$，进行操作$h_i=h_i+1,h_{i+1}=h_{i+1}-1$，得到新的$h'$。然后再重复操作若干次，直到无法操作为止，求出最终的序列。 | ||
| + | [[https://codeforces.com/contest/1393/problem/E2|Codeforces Round 662(Div. 2) E2 Twilight and Ancient Scroll (harder version)]] | ||
| + | === 标签： === | ||
| - | ===题解：=== | ||
| - | 题意很简单，不过感觉真是想不到。 | ||
| - | 首先发现，每一次操作$1$的转移，顺序是没有什么关系的，或者说可以看做每一次随便挑选一对可变的$h_i,h_{i+1}$进行变换（这里变换是指让两者值最多相差$1$），然后再挑选一直到不能变为止。暂时不会证明，不过手动几个例子是很容易看出来的。 | + | 字符串处理，动态规划，哈希，双指针 |
| - | 接下来我们安排一种变换轮次，每一次从左往右将新的$h_i$加入到轮次中来，到左边$1\sim i$序列无法变换，再加入下一个。对于每一个新加入的$h_i$，我们首先对$h_{i-1},h_i$进行一次变换，然后让序列$1\sim i-1$“消化”这个增加的$1$，接下来再变换$h_{i-1},h_i$... | + | === 题意： === |
| - | 很显然，考虑$1\sim i-1$中有唯一一对相邻相等元素$h_k,h_{k+1}$，消化的过程中，会消除了这对元素，产生了一对新的$h_{k+1},h_{k+2}$；考虑没有相邻相等元素，那么消化的过程中会在最左边产生一对新的相邻相等元素。 | ||
| - | 通过归纳，我们知道，因为一开始是没有相邻相等元素的，所以最后的相邻相等元素不会超过$1$对。 | + | 给出$n$个非空字符串，每个长$L_i$，现在让你在每个字符串中选择删除一个字符，或者是不删除，使得得到的字符串组按顺序字典序不减，求符合要求的操作的个数，答案对$1000000007$取模。 |
| - | 剩下的，就只用靠数学方法求解了。 | + | $1\le n\le 10^5,\sum L_i\le 10^6$ |
| + | |||
| + | === 题解： === | ||
| + | |||
| + | |||
| + | 我们容易想到设置$dp$状态为$dp[i][j]$表示到了第$i$个字符串删除第$j(0\le j \le L_i)$个字符，满足前$i$个不减的种类数（其中，$j=L_i$代表不删除）。这个时候我们会发现即使用一些预处理来快速比较相邻两个删除后的字符串，由于更新时要枚举位置，所以效率不会比$O(n*\sum L_i)$更优。 | ||
| + | |||
| + | 这时候有个很精彩的技巧，我们如果能够预处理出每个字符串删除之后得到的字符串的一个字典序数组，那么$dp$更新时等价于做一个区间加操作——对于前状态的字符串，用双指针找到第一个比其大的后状态，接着后面的所有状态都可以加上这个前状态的值。 | ||
| + | |||
| + | 怎么预处理呢？通过双指针求出一个$nxt$数组，$nxt[i]$代表第$i$个字符之后第一个出现不同的位置。那么对于两个删除点$p,q$，我们就可以通过对$nxt$和其大小的讨论，对状态字符串进行排序。 | ||
| + | |||
| + | <code cpp> | ||
| + | for (int i = 0; i < res.size(); i++) | ||
| + | res[i] = i; | ||
| + | sort(res.begin(), res.end(), [&](int x, int y) { | ||
| + | bool f = true; | ||
| + | if (x > y) | ||
| + | swap(x, y), f = false; | ||
| + | if (nxt[x] <= y) { | ||
| + | f ^= s[nxt[x]] > s[x]; | ||
| + | } else | ||
| + | f = !f; | ||
| + | return f; | ||
| + | }); | ||
| + | </code> | ||
| + | 剩下还有一个问题，怎么快速比较前后两个状态字符串大小呢？这里用哈希求出公共前缀更方便，当然用后缀数组也可以。 | ||
| + | |||
| + | 因此总的效率为$O((n+\log\sum L_i)*\log \sum L_i)$ | ||
| + | |||
| + | === 评论： === | ||
| - | ===评论：=== | ||
| - | 赛场上其实想的很多，但没总结出这个最多一对的性质，其实打表已经比较明显了，以后还是注意好好观察。 | ||
| + | 离散的动态规划我们可以将状态排序使之紧凑，很好的思路。 | ||
| ===== 龙鹏宇 Hardict ===== | ===== 龙鹏宇 Hardict ===== | ||
| 行 86: | 行 107: | ||
| === 来源： === | === 来源： === | ||
| - | [[http://acm.hdu.edu.cn/showproblem.php?pid=6061|HDU 6061]] | + | [[https://codeforces.com/gym/102465/problem/J|SWERC 2018 J]] |
| === 标签： === | === 标签： === | ||
| - | 多项式卷积,NTT | + | hash碰撞，随机算法 |
| === 题意： === | === 题意： === | ||
| - | 先给定一个$f(x)=\sum_{i=0}^{n}c_{i}x^{i}$,然后求解$g(x)=f(x-\sum_{i}a_{i})=\sum_{i=0}^{n}b_{i}x^{i}$ | + | 给定一个随机数生成器，以及$4$个种子$S_i$，知道算法可以求得其运行$C_i$次会生成数$x_i$(这个需要一步一步求)，我们截取$x_i$二进制前$N$位，计算$w=x_1 \oplus x_2 \oplus x_3 \oplus x_4$，题目要求选取合适的$C_i$使$w=0$ |
| - | + | ||
| - | 输出$b_{i}$ | + | |
| === 题解： === | === 题解： === | ||
| - | $A=-sum{a[i]}$并取模变成求解$f(x+A)$少去正负计算 | ||
| - | 然后按$f(x+A)$每一项进行一个展开(会成一个三角表) | + | 下述$x_i$默认只保留二进制前$N$位 |
| - | 目标多项式系数$b_j=\sum_{i \geq j} c_i A^{i-j} C_i^j$ | + | 先考虑两个数情况，对于$x_1$与$x_2$，我们实际是要寻找$x_1=x_2$情况，对于给定种子$S_i$我们可以根据随机序列定义$Hash:h(S_i,x_1)=c_k$，即给定种子下生成值与次数的关系 |
| - | 化解后有$j!A^jb_j=\sum_{i=j}^{n} \frac{c_{i}i!A^i}{(i-j)!}$ | + | 那么$x_1=x_2$可以理解为对$x_1$的$Hash$在${x_2}$中寻找一次$原像碰撞$ |
| - | 整体上$g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j=0}^{n-i}\frac{c_{i+j}(i+j)!A^{i+j}}{j!}$ | + | 将设我们对$x_1$进行哈希了$D$次，我们可以利用//生日攻击//知道$D=2^{\frac{N}{2}}$最优（或者利用期望耗费为$D+\frac{2^N}{D}$分析） |
| - | 这里令$k=n-(i+j),g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j+k=n-i}\frac{c_{n-k}(n-k)!A^{n-k}}{j!} | + | 于是对于原题我们得到一种想法：对${x_1}$构建大小为$2^{\frac{N}{2}}$的哈希表，$x_3,x_4$随便生成，遍历${x_2}$寻找碰撞$x_1=x_2 \oplus x_3 \oplus x_4$，复杂度为$O(2^{\frac{N}{2}})$，会$TLE$ |
| - | =\sum_{k=0}^{n}\frac{x^{k}}{A^{k}k!}\sum_{n+k=i+j}\frac{c_{i}(i)!A^{i}}{(n-j)!}$ | + | |
| - | 将$\frac{1}{j!}$当作一个翻转(两者都可),求$\sum_{i}c_{i}i!A^{i}x^{i}$与$\sum_{i}\frac{1}{(n-i)!}x^{i}$的卷积,然后取结果$n+i$项系数即可 | + | 现在考虑利用$x_3,x_4$，可以考虑将$(x_1,x_2),(x_3,x_4)$看作两个整体，要求$x_1 \oplus x_2;\quad x_3 \oplus x_4$分别将前$M$比特位碰撞为0，再在对于两个整体在后$N-M$位中寻找 |
| + | 哈希，复杂度为$O(4*2^{\frac{M}{2}}$) | ||
| + | |||
| + | $M$作为参数进行选取，理论$\frac{N}{2}$即可，但实际可能没有碰撞，调参后选取$\frac{2N}{3}+4$通过 | ||
| 行 121: | 行 141: | ||
| === 来源： === | === 来源： === | ||
| - | [[https://atcoder.jp/contests/abc175/tasks/abc175_d|D - Moving Piece]] | + | [[http://codeforces.com/contest/1380/problem/D|D. Berserk And Fireball]] |
| === 标签： === | === 标签： === | ||
| 行 129: | 行 149: | ||
| === 题意： === | === 题意： === | ||
| - | 给定步数和诸多环，求在某个环上走的最大收益。 | + | 给定一个两个排列，长度分别为n和m。 |
| + | |||
| + | 有两种操作，花费x的代价消除恰好k个连续的人(操作1)或者花费y的代价消除相邻的两个人中力量较小的人(操作2)，消除以后两边会合并。 | ||
| + | |||
| + | 问最小花费多少代价可以使得第一个排列变成第二个排列，有无解情况。 | ||
| === 题解： === | === 题解： === | ||
| - | 枚举每个点作为起点然后分类讨论，如果步数不够一圈就模拟一下找一个最大值。 | + | 首先第二个排列一定要满足是第一个排列的子序列。 |
| + | |||
| + | 然后考虑如何消除子序列相邻两个位置间的人，设要留下的数字是a和b，那么这之间如果有比a和b都大的数字，那么我们至少要进行一次操作1。 | ||
| + | |||
| + | 分两种情况，如果$y * k \leq x$那么肯定尽量一个一个消除更优，如果都比a或者b小那么直接一个一个消除即可。否则我们考虑最大的数，可以用它先把其它的数消除到只剩k个然后一波带走，如果人数本身不够k个那么显然无解。 | ||
| - | 如果够一圈则在模拟走一圈内的最大值和走多圈和余下步数的最大值取个最大值即可。 | + | 如果$y * k > x$也就是说尽量一段一段的消除，从前往后贪心即可，遇到比a或者b小的数就先留着，遇到比a和b都大的数就以它为起点删除长度为k的一段，如果长度不够看去拿开始留着的数凑就行了，凑不够就无解。最后剩下的数先尽量整段消除再一个一个消除即可。 |
| === 评论： === | === 评论： === | ||
| - | 分类没有处理好WA了很多发，这种简单题也要注意细节。 | + | 还是分类讨论没有处理好WA了一发。 |
2020-2021/teams/alchemist/weekly_digest_12.1598595240.txt.gz · 最后更改: 2020/08/28 14:14 由 maxdumbledore
