本文共 4123 字,大约阅读时间需要 13 分钟。
现在不是非常爽,感觉智商掉没了,就整理一下最近弱省胡策的题目吧.
其实题目质量还是很高的. 如果实在看不懂官方题解,说不定这里bb的能给您一些帮助呢?【弱省胡策】Round #0 A
20%数据, O(n4) 傻逼dp.
40%数据, O(n3) 傻逼dp. 100%数据,令 f(x1,y1,x2,y2) 表示从 (x1,y1) 走到 (x2,y2) 的路径条数.于是所有路径就是 f(1,2,n−1,m)×f(2,1,n,m−1) .然而两条路径可能在中间的某个点相交,我们找出最早的交点,并在这个交点互换两条路径的后半部分,这样就成了一条 (1,2) 到 (n,m−1) 的路径以及一条 (2,1) 到 (n−1,m) 的路径,而且两者之间是一一对应关系. 于是答案等于:【弱省胡策】Round #0 B
首先要知道什么是DFA,就是一个自动机,在相同的转移下到达的节点一定相同.
分别建立两个串的后缀自动机以及子序列自动机,令 fi,j 表示在自动机 1 中转移到了【弱省胡策】Round #0 C
提答题弃疗辣~~
【弱省胡策】Round #1 A
令字符集大小为 |S| ,所有串的总长度为 ∑L .
如果内存大一点的话,就可以直接fail树+主席树了,这样空间和时间是 O(∑L|S|+∑Llogn) . 由于空间的常数有点大,这样就MLE了. 考虑把所有的询问拆分到 O(logn) 个线段树节点上,然后对于每个线段树节点,我们建立这个节点的所有串的ac自动机,然后对于这个节点上所有的询问暴力在上面走一遍. 这样每个串都会被建到 O(logn) 的ac自动机上,然后每个询问串都会被走 O(logn) 遍. 这样时间复杂度是 O(∑Llogn) ,但内存是线性的,于是很轻松就过了.【弱省胡策】Round #1 B
按照第一维排序,然后就变成了按顺序插入一个点,并每次询问一个三维空间的最大值.
我们可以直接用kdtree搞定. 时间复杂度 O(nn−−√) .【弱省胡策】Round #1 C
一个状态就是一个合法的点集,权值即为所有点集里面的点的父亲边的权值和.
那么我们依然利用优先队列来维护,弹出一个状态的时候在队列中加入比这个状态大且最小的状态,这样做 k 次就行了. 要想比这个状态大一点点,我们首先可以考虑添加一个儿子,同时这个儿子父亲边的权值最小. 对于每个状态,我们维护一个堆,里面存的是所有接下来可以拓展的儿子,那么拓展下一个状态直接取堆顶就行喽. 然而比这个状态大一点点不一定就是拓展出一个新的儿子. 考虑这个状态的父亲状态,在这个父亲状态中我们取堆顶的左右儿子进行拓展不也是比这个状态大一点点嘛. 所以我们得到一个状态,首先拓展出一个添加最小儿子的状态,然后再添加一个将堆顶删除掉的状态. (说不太明白,不过容易发现这样是对的 然后这些东西都用可持久化可并堆来维护.【弱省胡策】Round #2 A,B,C
【弱省胡策】Round #3 A
一开始通过在树上打标记,然后dfs一边得到每个点的实际
【弱省胡策】Round #3 B
太神,见官方题解.
【弱省胡策】Round #3 C
我的做法:首先要有姿势 gcd(Fibi,Fibj)=Fibgcd(i,j) ,然后要找规律,然后用一些基本的容斥原理就行啦.
具体见官方题解.【弱省胡策】Round #4 A
无脑分数规划+最大权闭合图,有点卡精度,比赛时inf设成了1e12是70分,后来改成了1e10就过了.
【弱省胡策】Round #4 B
一个非常有用的事实:一个边双连通图必定是一个边双连通子图再加上条链组合成的.
一个点自己可以是一个边双连通子图,也可以看成一条链. 这样可以令 fi 表示 i 这个集合内部的点组成一个双连通图的最小代价. 再令【弱省胡策】Round #4 C
原题大赛:BZOJ3302
暴力很好写,就是枚举把哪条边割断,然后两个部分分别求一下重心就行了. 然后现在我们知道树的高度很小,于是我们可以先做一些预处理,然后我们找出每个点子树权值和最大以及次大的儿子,这样找重心的时候 O(1) 就能知道走向哪个儿子了. 然后依然枚举割断哪条边,但是不同的是这次我们直接 O(h) 就能找到重心,然后根据我们之前处理出的信息 O(1) 就能知道现在的代价. 所以这样做的复杂度 O(nh) .【弱省胡策】Round #5 A
考试时:
通过找规律发现了 Ai=∑nj=iCij(−1)j−iBj . 然后?不会啦… 明明展开之后用一点技巧就变成卷积了… 结果我根本没展开,而是构造了一个大多项式,但是并没有卵用. 我真TM是大逗比.【弱省胡策】Round #5 B
考试是没看出来是构造一个无向图…反而硬找规律…
其实就是构造一个连通无向图使得最长的最短路为 k . 我们可以构造一个长度为【弱省胡策】Round #5 C
好神的dp…
考虑一个 n×m 的矩阵,假设现在我们要往里面填充第 k 种颜色. 那么现在是有一个长度为【弱省胡策】Round #6 A
大意:首先注意到就是求出一个最大的循环串集合,使得集合中的任意两个循环串在模 a 意义下相等或者模
【弱省胡策】Round #6 B
思路:首先将树树链剖分,则任何一颗联通的子树都必定可以用一条链上的一段作为主链来表示,主链上的每个点会向下连出一些子链,我们仅需考虑子链的最大前缀和,若其 >0 ,则加到这个点的点权中.然后再搞出这个链的最大子段和更新答案.
维护一个全局堆记录所有重链的最大子段和. 考虑修改,只需要修改这个点的权值,更新链的最大子段和,在堆中修改,然后更新父亲重链的点权,并以此类推就行了. 时间复杂度 O(log2n) . 我的代码在ch上不明所以的RE,本地可以AC.【弱省胡策】Round #6 C
想了好长时间的性质未果,于是暴力.
可是没有注意到答案的下界是 sumk ,好像真正的答案到下界的距离不超过 w ? 这个我并不会证. 但是从这个下界开始向上【弱省胡策】Round #7 A
首先肯定是要枚举环的长度 k ,关键的是剩下的怎么搞.
依然考虑prufer序列,将环上的【弱省胡策】Round #7 B
对每个高度维护一颗线段树维护最长连续存在区间,注意到存在性是随着高度递减有包含关系的,所以直接用持久化线段树,空间复杂度 O(nlogn) .
维护一个全局堆表示每个高度的答案,同时每次修改相当于对两个高度进行单点修改,直接改一下,然后在全局堆里面修改就行了. 于是时间复杂度 O((n+m)logn) .【弱省胡策】Round #7 C
提答题弃疗啦~~
转载地址:https://blog.csdn.net/wyfcyx_forever/article/details/46551835 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!