近期考试的总结

此文从6.23日开始更新,更新至7.13

用于发表一些认为有价值的题的简要的题解和考试时的感想

由于写博客对于我来说太浪费时间,于是变成随缘更新了

6.23

  今天垫底了(不$\text{Fake}$),主要是第一题即使一眼$0/1$分数规划,但是纠结在了怎么计算方案而忽略了本题最重要的性质。将大部分的时间都浪费在了写第一题,以为是一个很高深的题目。

T1

  本场考试最容易的题,显然可以想到$0/1$分数规划,$\text{check}$的话可以直接扫描一遍找出是否存在某一个值满足$t[i]-k\times s[i]\le 0$($t[i]$为时间,$s[i]$为安全程度,$k$为比值)。

  在这个基础上仔细思考一下不难发现答案就是$min(\frac{t[i]}{s[i]})$(证明见附录),所以只要找出有多少个相同的$min(\frac{t[i]}{s[i]})$(设有$tot$个)则方案数就是$2^{tot}-1$(模数差评)。

6.24

T1

  依然是本场考试最愚蠢的题,考虑第$i$种物体取$x$件和取$x+1$件会产生的新的价值,计算可得新的价值为:$a_i-(2x+1)b_i$,注意到新的价值只与当前去的件数有关,所以可以拿这个当做新取物品的权值(记一个$cnt[i]$表示第$i$种物品取的件数),开一个堆即可,时间复杂度$O(m\log_2n)$。

T2

  正着思考显然不会很好,考虑倒着思考,发现一个元素$0$只能和另一个元素合并或者不动,同时不难发现两个一个正数和其他数合并不会比他们分别减到$0$再合并要更优,于是统计一下每一种数的个数然后根据上述结论模拟一下即可,复杂度大概是$O(n\log_2n+n)$的。

  这道题考场上以为是数列,然后写了很久,最后$10$分钟发现是集合(更加容易了),随便写了一下就交上去了,事实上只有一个细节没有处理好(数据过弱导致自己甚至还有$30pts$)。

T3

  我也不知道为什么考场上没有想到正解。

  从每一个点开始向四周连边,边权为这两个点之间的较大点权,考虑一个点最多能放多少水,显然是它到外界的所有路径的边权最大值的最小值,所以考虑将外界看作一个点,由这个点开始求出整张图的最小生成树,最后求出每一个点到该点路径上边权的最大值,$\text{dfs}$即可。

6.25

T1

  一道思维好题。

  考虑一个什么样的数能作为一个区间的中位数,当且仅当这个区间内小于它的数的个数减去大于它的数的个数大于等于$0$且小于等于$1$才可以。

  利用这个性质我们可以采取二分答案求出中位数的中位数的方式,假设当前二分的中位数为$mid$,在原数列的一段区间中,如果小于等于它的数(记为$x$),与大于它的数(记为$y$)满足$x-y\ge 0$,则说明这个区间的中位数$\le mid$。

  令数列中小于等于它的数为$-1$,大于的数为$1$,找出所有的满足区间和$\le 0$的区间,可以记一个前缀和$s_i,i\in[0,n],s_0=0$,则一个满足条件的区间$[l,r]$可以表示为:$s_r-s_{l-1}\le 0$即$s_{l-1}\ge s_r$,利用树状数组可以方便地求出满足条件的区间个数。

  至于求出上面这些区间的个数可以用来干什么,如果个数大于$\frac {n(n+1)}{4}$,则说明二分的中位数过大,需要缩小,当$l>r$时,$l$就是中位数。

T4

  我承认这题我思维僵化了。

  考虑二分答案,贪心的选取每一次考试的最后时间,然后将考试的出现时间从小到大排序,记个剩余时间依次模拟即可。

  实际上是本场考试最容易的题。

T5

  贪心地考虑这个问题,我们肯定是要最大化放置一个关键点可以控制到的叶子数,假设当前的$k$值为$2$,存在某一个节点$t$有这样的两个叶子:一个叶子到该节点的距离为$2$,另一个叶子到它的距离为$1$,我们若要使放置下来的节点既要控制这两个叶子,也要最大化控制其他叶子节点的概率,所以我们选择在节点$t$放置。

  上述讨论启发我们将所有未被控制的的叶子按照深度从大到小排序,从头到尾处理每一个叶子,每处理到一个未被控制的叶子,将其$k$级祖先标记,然后更新控制情况,时间复杂度为$O(Tn^2)$

6.26

T1

  乍一看很难,实际上不难发现倒着处理操作会变得很容易,因为当我们倒序遍历到某一个操作时,之前的操作是无法影响它的执行次数的。

  所以开两个树状数组,一个维护整个数组的区间和,一个维护操作次数,倒序遍历到某一个操作,如果是操作$1$就将第一个$\text{BIT}$中的指定区间加上自身的执行次数(在第二个$\text{BIT}$中查询),操作$2$同理。

T2

  好题,不难得出结论$c=\prod\limits_{i=1}^n(a_i-i+1)$

  所以一个$a_i$的贡献就是$a_i-i+1$,设其为$b_i$,显然$b_i$与$a_i$一一对应,所以我们只需要最大化$b_n$,而$b$数组又是$c$的约数,所以可以枚举约数,同时,我们贪心地认为其他的$b_i$要尽可能大。

  额外要说的是:$\because a_i\le a_{i+1}\therefore b_i\le b_{i+1}+1$,所以在枚举$b$的时候我们要记得放大范围。

T3

  考虑到$k$个古城都是两两右边的,所以我们先不处理这些边,对$m$条边建出的图跑一次最短路,至少有一个古城可以算出最短路,所以我们可以利用已经算出最短路的古城中最短路最小的那个来更新其它的古城。

  然后我们就排除了这$k$个古城互相之间的影响,最后要做的就是用这$k$个古城来更新整张图的最短路。

T5

  一道很容易的题,差分一下维护区间最大值即可(有方法可以做到$O(n)$,但是没有必要)。

6.29

  $\text{Anson}$欢乐赛,看谁小错误更多。

T1

  我就想用树形依赖背包做,左儿子右兄弟可以做到$O(nm)$

T2

  第一次做这种类型的$dp$,之前都有意跳过了,当时觉得没有办法理解。现在看来是一个很简单的树形动规。

T3

  缩完点以后变成$\text{DAG}$,然后就只有一种决策了,拓扑排序模拟即可。

T4

  这题甚至在树剖查询区间写反还有$\text{20pts}$,树剖完以后,第一个子问题写一个$\text{BIT}$,第二个子问题写一个可持久化权值线段树。

7.12

  还是$\text{Anson}$快乐赛

T2

  一道很有意思的题,考虑到起点和终点都是加油站,所以不妨最短路处理出所有加油站之间的最短距离,然后离线做。

  具体就是将询问和边的权值分别从小到大排序,然后按照询问的权值将边权小于等于其的边加入图中,并查集维护连通性。

  但是边数是$O(n^2)$的,考虑怎么优化,一遍最短路计算出所有节点所能到达的最近的加油站$W$以及到它的距离$dist$,枚举原图每条边的两个端点$(u,v,w)$,建立一条边$(W[u],W[v],dist[u]+dist[v]+w)$($W$相等就不用加了),边数变为$O(m)$。正确性比较显然,这里不给出证明。

7.13

T1

  有如下结论(讨论一下可以得出):

点$a,b$在以$c$为根的树中的最近公共祖先为在原树中$lca(a,b),lca(a,c),lca(b,c)$中深度最大者。

  所以操作$1$我们只需要记下当前的根$rt$即可。

  对于剩下两个操作,我们只需要讨论查询的点是否在原树中$rt$到根的那条链上,不在则直接子树操作,否则先对于整颗树修改,然后再取消$rt$到查询点的那条链上查询点的儿子的子树的贡献。

  树剖可以找出我们需要的点,见附录。

  原题是$\text{CodeForces 916E}$。

T3

  倒着思考,设$f[u]$表示点$u$的答案,其取值为$f[v]+dis(u,v)$中的次小值(其中$v$表示$u$的一个出点)。

  由于已知终点的$f$,所以可以倒序求出所有点的$f$。

  原题是$\text{Bzoj 2622}$。

8.31

在本段集训的最后一天更一次博

T1

  就说一下 $\text{95pts}$ 的做法

附录

6.23 T1证明

设有两个分数$\frac ab=t_1$、$\frac cd=t_2$,其中$t1<t2$,$a,b,c,d<0$

则有:

$\because\frac{(t_2-t_1)d}{c+d}>0\therefore\frac{a+b}{c+d}>\frac ac$

7.13 关于树剖找出某两个点到其公共祖先下的两个对应点

  先找出$lca$,然后分开跳,如果某一时刻$lca$和当前的点在同一条重链上,则对应点为$lca$的重儿子,否则必有某一时刻$fa[top[]]==lca$,此时$top[]$就是需要找的点。

int di(int tp, int x) {//tp为lca,x为需要读入的点
    while(top[x] != top[tp]) {
        if(fa[top[x]] == tp) return top[x];
        x = fa[top[x]];
    } return son[tp];//同一条重链
}