WORIA

https://codeforces.com/contest/1139 D. Steps to One   题意：给定一个数m，1≤m≤1000001 \leq m \leq 1000001≤m≤100000，有一个空数列，每一轮随机选一个 1 到 m 的数，加入数列，当数列的 gcd 为 1 时停止。问最终数列长度的数学期望。 数学期望+莫比乌斯反演+dp 首先加入一个数，可能为 1，2，···， m，则第一次操作后 gcd 可能为 1，2，···， m，所以只要求出 gcd 为 1，2，···， m 时还需要的长度的数学期望，求和求平均值。 设 f[i]f[i]f[i] 表示当前 gcd 为 iii 时还需要加入的数列长度的期望。 加入的下一个数可能为 1，2，···，m。所以 f[i]=1m∑j=1mf[gcd(i,j)]+1f[i]=\frac{1}{m}\sum_{j=1}^mf[gcd(i,j)]+1f[i]=m1​∑j=1m​f[gcd(i,j)]+1 。 直接枚举 j 复杂度不够，所以枚举 i 的因子，作为 gcd(i,j) ，变为 f[i]=1m∑x∣i(f[x]⋅c ...

https://codeforces.com/contest/1136 E. Nastya Hasn’t Written a Legend   题意：给定长为 nnn 的数列 aaa，长为 n−1n-1n−1 的数列 kkk，两种操作：询问 a[l]+⋯+a[r]a[l]+\cdots +a[r]a[l]+⋯+a[r]；a[i]+=xa[i]+=xa[i]+=x，若 a[i+1]<a[i]+k[i]a[i+1]<a[i]+k[i]a[i+1]<a[i]+k[i]，则 a[i+1]=a[i]+k[i]a[i+1]=a[i]+k[i]a[i+1]=a[i]+k[i]，并继续检查 a[i+2]⋯a[i+2]\cdotsa[i+2]⋯。 线段树+二分 令 g[i]=∑j=1ik[j]g[i]=\sum_{j=1}^i k[j]g[i]=∑j=1i​k[j]，u[i]=a[i]−g[i]u[i]=a[i]-g[i]u[i]=a[i]−g[i]。 则 ∑i=lra[i]=∑i=lru[i]+∑i=l−1r−1g[i]\sum_{i=l}^{r}a[i]=\sum_{i=l}^r ...

http://codeforces.com/contest/1137 A. Skyscrapers   题意：n*m的网格每格一个数，在一个交叉点的格子里，要尽量减小横向纵向的数字，保持大小关系不变。 要大小关系不变容易想到最小为行或列的不同数个数。 但是看样例2又发现还要折线方向不同。所以分四种。 12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const int N = 2e5 + 10;int n, m;int a[1010][1010];vector<int>r[1010], c[1010];int main() { scanf("%d%d", &n, &m); for (int i ...

https://codeforces.com/contest/1120 A. Diana and Liana   题意：m个数，k个一组，取前n组，要求删除一些数，使得取的n组中至少一组满足存在给定的需要的数。删除的数个数任意，但必须剩下至少n组。 枚举 遍历每个位置，考虑从它开始构造一组满足条件的数。找到它开始的最短的满足含有所有需要的数的区间。再考虑删除前面的数，使得这个位置成为一组的开头，且在n组内，再删除组内的数，直到个数为k。判断删除后剩下至少n组，则满足条件，输出。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 5e5 + 10;int m, k, n, s;int a[N], b[N], n ...

http://codeforces.com/contest/1109 D. Sasha and Interesting Fact from Graph Theory   题意：一棵树n个点，每条边权为1到m，问有多少棵树满足给定两点的距离为m。 组合数学+扩展 Cayley 定理 给定两点其实没什么用，所以不需要管。 两点的路径是一条链，所以枚举链的长度，链上所有边和为m，且每条边为1到m，所以隔板法求出有多少种分配方法。 确定了链之后，还剩下一些点，要把这些点插到链上，问有多少种插法。 就要用到扩展 Cayley 定理了。 Cayley 定理及证明见 https://www.cnblogs.com/lfri/p/10433011.html 扩展 Cayley 定理及证明见 https://kaloronahuang.com/oi/cayley-定理-扩展-cayley-定理/ Cayley 定理 ：nnn 个有标号的点能组成 nn−2n^{n-2}nn−2 棵不同的树。 扩展 Cayley 定理 ：nnn 个有标号的点组成包含 sss 棵树的森林，有 snn−s−1sn^{n-s-1 ...

https://codeforces.com/contest/1114 E. Arithmetic Progression   题意：交互题。有一个打乱了的等差数列，公差大于 0。你可以发起询问，两种：询问是否有大于 x 的数；询问第 i 个数。求出数列中最小的数和公差。询问不超过 60 次。 随机 首先通过第一种询问查出最大的数。还剩下 30 次。 也就是可以随机得到数列中的30个数，显然需要用到的是排列后的差，这些差都是公差的倍数。 关键点就是直接求出这些差的gcd，也就是说这里假定这些数的gcd就是公差。 出错的概率约为 1.86185⋅10 − 91.86185·10 ^{- 9}1.86185⋅10 − 9。 下面是搬运的官方题解： 为方便起见，假设原数列为 {0,1,2,⋯ ,n−1}\{0,1,2,\cdots,n-1\}{0,1,2,⋯,n−1}。 假设 我们可以选出 k 个元素。 令 SSS 为选出的 k 个元素组成的集合，即 S={s1,s2,⋯ ,sk}S=\{s_1,s_2,\cdots,s_k\}S={s1​,s2​,⋯,sk​}。 令 allallall ...

https://codeforces.com/contest/1106/problem/E 题意：1到 n 的时间轴上，给定 k 个区间，每个有 d 值和 w 值，当位于坐标 x 时，可以会选择包含 x 的区间中 w 值最大，若 w 相同，则选 d 值最大，若还相同，则随机选一个。获得区间的 w 值，并移动到 d 值去。可以选择 m 个点堵住，在被堵住的点处不能获得 w 和移动。问最少获得的 w 值之和。 扫描线+dp dp[i][j]dp[i][j]dp[i][j] 表示在坐标 i，总共堵了 j 个点，最小 w 值和。 有两种转移：不堵坐标 i，则获得 w 值，并移动到坐标 i 对应区间的 d 值去。堵坐标 i ，则什么都不加，并移动到 i+1 去。 由于需要知道移动到后面某个坐标的 dp 值，所以这里从后往前转移更好。先算出后面的dp值，再算前面的。 扫描线确定每个坐标应该选择的区间，并记录 w 值和 d 值。 注意 multiset erase key 会删除所有为 key 的元素，所以会导致某些不应该被删除的元素提前删除了。要只删除一个可以 erase(find())。 123 ...

https://codeforces.com/contest/1062/problem/E 题意：给定一棵树，多次询问，每次给出一个区间，要从区间中删去一个数，区间中剩下所有数的 lca 深度最大，每次询问后还原为原树。 RMQ+dfs序 树上的区间问题还是要考虑dfs序。 一个点集的 LCA 必定是这些点中 dfs 序最小的点与最大的点的 LCA。证明略 维护区间的 dfs 序最大值和最小值，RMQ查询。 要改变 LCA 必定要并且只要删掉 最大值或最小值，都尝试一下就好了。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117#include<bit ...

https://codeforces.com/contest/1305 B. Kuroni and Simple Strings   题意：括号序列，每次操作可以删去一个任意层的正确的括号序列，要求最终不存在正确的括号对，求最少操作。 大胆猜测答案只有0或1。然后就简单了，直接贪心从最左找左括号，最右找右括号。 123456789101112131415161718192021222324252627282930313233#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;int vis[N];char s[N];vector<int>vc;int main() { scanf("%s", s); int n = strlen(s); for (int i = 0; s[i]; i++) { if (s[i] == ')')co ...

http://codeforces.com/contest/1284 C. New Year and Permutation   题意：给定n，问1到n的所有排列的满足区间最大值减最小值等于区间长度-1的区间数量之和。 看到区间应该要想到枚举区间长度。 可以发现所需要的区间就是满足区间内所有数是连续的一段。 在固定长度下，先枚举区间的位置，以及区间内是哪一段数字，再把这些数字全排列，其他数字也全排列。 1234567891011121314151617#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 3e5 + 10;ll n, m, ans;ll fac[N];int main(){ scanf("%lld%lld", &n, &m); fac[0] = 1; for (int i = 1; i <= n; i++)fac[i] = fac[i - 1] * i%m; for (ll i = 1; i <= n; ...