呃,主要是把之前没有参加的Educational Codeforces Round补一补。QAQ。。。
Educational Codeforces Round 1-2017.8.22
C:【题意】给定$n$个向量,求夹角最小的两个。
【题解】用$atan2(x,y)$可以求出向量与$x$轴的夹角,排序即可。卡精度!!
E:【题意】给定一个$n\times m$的巧克力,划分一个巧克力的代价为长度的平方,求划分出$K$个小巧克力块的最小代价。
【题解】定义状态$f[i][j][k]$如题意,暴力转移,$O(n^3K^2)$的暴力可过。
Educational Codeforces Round 3-2017.8.23
E:【题意】给定一个无向图,求必须包含某个点的最小生成树。$n<=200000$
【题解】这题可以倍增或者并查集按秩合并。其中并查集按秩合并常数较小。
Educational Codeforces Round 4-2017.8.24
E:【题意】给定一个置换,求这个置换的平方根。$n<=10^6$
【题解】显然,我们需要将置换分解为若干个循环的乘积。如果一个循环的长度为奇数,那么它一定存在平方根。以一个$5$边形为例,它的平方根类似于一个五角星;如果一个循环的长度为偶数,单独的一个循环不存在平方根,如果有两个相同长度的循环,我们可以将这两个循环合并,得到他的平方根。
Educational Codeforces Round 5-2017.8.25
E:【题意】给定$n,m$,求$n\%1+n\%2+n\%3+…+n\%m$的值。$n,m<=10^{13}$。
【题解】一道数论好题。一开始无从下手,考虑打表。以$n=100,m=100$为例,发现前$10$项毫无规律,从$100$项到第$51$余数以公差为$1$递增,从$50$到$34$项,余数以公差为$2$递增。可以得到规律在第$\large \lfloor \frac n r \rfloor$到第$\large \lfloor \frac n {r+1} \rfloor$以公差为$r$递增,首项为$n \%r$。于是利用等差数列求和公式即可。对于前面的$sqrt(n)$项暴力计算即可。
Educational Codeforces Round 6-2017.8.26
D:【题意】给定两个长度分别为$n,m$的序列,要求至多交换两对不同位置数,使得$|Sa-Sb|$最小,这里的$Sa,Sb$分别表示两个序列的和。
【题解】对于不交换或只交换一对,直接暴力即可。如果交换两对,可以这么做:将所有对列举出来$(Ai,Bj)$。求出它们差,放在一个数组中。考虑首先排序,左指针从左往右扫,同时,右指针单调往左移。当右指针满足一定会使结果大于当前答案时,左移。每一次移动后,只要在可能的答案区间里扫一下即可。可能无法计算复杂度?
E:【题意】给定一颗树,每个节点有一个颜色$c(c<=60)$。每一次可以修改一个子树的颜色,或者询问一个子树存在多少不同的颜色。
【题解】注意到颜色数很小,所以可以直接压成一个$long\ long$,求出$DFS$序,并用线段树维护区间出现了哪些颜色。
Educational Codeforces Round 24
D:【题意】给定n个数${c1,c2…}$和A,用$cntX(i)$表示${c1,c2,…,ci}$中等于X的数。询问是否存在B,使得对于任意i,都有$cntB(i)>=cntA(i)$。
【题解】考虑一个个枚举B,首先判定$cntB(n)$是否不小于$cntA(n)$ 。发现答案的条件等价于:一个个比较A和B所在的位置,对于所有第i次出现的A,都满足第i个出现的B在前面。假设A的个数为m,则每次判断为$O(m)$,而满足前提的B的个数为$O(n/m)$ ,复杂度$O(n)$ 。
E:【题意】给定$n$个数${a1,a2…}$和$k$,问存在多少有序数对$(x,y)$满足:删除前$x$个数和后$y$个数,剩下数的乘积是$k$的倍数。
【题解】将k质因数分解(最多有10个不同的质因子),只要每个质因子的个数达到$k$拥有的就可以了。直接暴力枚举左端区间,发现右区间有单调性,直接维护一个滑动窗口就好了(比赛时写了二分233…)。
F:【题意】很好玩的题。 有q组询问,每组询问给出数n。问n个节点最多能连多少条边,使得桥的数量不少于总边数的一半。
【题解】有个很显然的结论:n个节点构成的图中桥不超过n-1个。因为无向图可以看一些树连一些边构成的,而n节点数恰好只有n-1个桥,连上的边一定不会成为桥。考虑这样构造:中间构造一个“K-完全图“,剩余的节点就往“完全图“上连单一的边,不难发现这样是存在k个桥时,边数最多的方案。
实际上,内部的图最多只有$min(n-k, \frac{k(k-1)}{2}) $ 条边,于是总边数为$f(k)=n-k+min(n-k, \frac{k(k-1)}{2}) $ 发现这个函数$f(k)$ 是个单峰函数,用三分法求解(最值两边有严格单调性)即可。
三分法的正确姿势。 ${Lmid=(2l+r)/3}~~~{Rmid=(l+2r)/3}$ ,当L和R差小于3后,暴力找出最值。
(坑)G:网络流难题。
Educational Codeforces Round 26