[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem

codeforces 1325 E

题意:给定一个长度1e5的数组$a$, $1 \le a_i \le 10^6$ ,满足 $a_i$的因子数量不超过7. 求 $a$ 的最短的满足所有元素相乘结果为完全平方数的子序列的长度。

这个题目做的时候。。一直在想怎么dp。。。完全没往图的方向想。太久没做题了就是这样,丢掉了很多东西,sigh
继续阅读“[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem”

[DP][字符串匹配][子序列] codeforces 1150 D Three Religions

vp了这一场,这个D题难到出现断层。。。C过了1k人的时候D没人过,太狠了

主要是能想到用dp搞字符串匹配的。。。div2里这样的人应该不多吧

但是这个题其实内涵里有诱导dp的思想:刚开始没有搞懂他这里的append是什么意思,后来才懂得他每次的+-操作都是在修改对应的religion的描述,这个描述是一个只有小写字母的先后顺序固定的字符串。。然后题目问的就是给定你一个字符串叫做word of universe,问3个religion能不能共存,其实意思就是能不能从这个word of universe分离出来三个subsequence,他们互不相交,又正好是3个religion的描述。

vp的时候毫无头绪,正解里的预处理表倒是想到了也写了但是没用上。确实没想到会是dp emmmm 。既然dp那一定有个数值型的对象吧,他这里就很妙的把问题转化为满足这三个subsequence共存的序列至少要多长了。。。当然给定的word of universe是确定的,这里其实可以认为后面还有无限长的字符串。。。但是长度大于n的时候我们认为没用了。。就输出NO就可以。不得不说确实是很精妙,legendary出的题确实厉害👍

具体地,设dp(n1,n2,n3)为region1满足前n1个字符,region2满足前n2个,region3满足前n3个这样的情况下所需要的在word of universe里的前缀至少有多长。有一个暴力的计算O(250^3)复杂度的,就是

\[
dp\left(n_{1}, n_{2}, n_{3}\right)=\min \left\{\begin{array}{ll}{Nst\left(dp\left(n_{1}-1, n_{2}, n_{3}\right)+1, \text{description}_{1}\left[n_{1}\right]\right)} & {\text { if } n_{1} \geq 1} \\ {Nst\left(dp\left(n_{1}, n_{2}-1, n_{3}\right)+1, \text{description}_{2}\left[n_{2}\right]\right)} & {\text { if } n_{2} \geq 1} \\ {Nst\left(dp\left(n_{1}, n_{2}, n_{3}-1\right)+1, \text { description }_{3}\left[n_{3}\right]\right)} & {\text { if } n_{3} \geq 1}\end{array}\right.
\]

继续阅读“[DP][字符串匹配][子序列] codeforces 1150 D Three Religions”

[CF][二分查找][×] codeforces 448D Multiplication Table

写这个题为了提醒自己先想简单的做法再想复杂的,不要一上来就跑偏到复杂操作上去。。。

题目要求给出n*m的乘法表中第K大的元素,n和m都是5e5数量级. 暴力显然不行,所以得找个快速的方法分辨出第k大,然后我由于这几天一直在搞数论,脑子抽了从质因数分解的角度考虑结果弄得巨复杂。。。最后看官方题解就一句话二分查找,醍醐灌顶。。。

由于生成表格的方法是i*j所以check只要把所有的x/i加和与k比较大小就是了。
继续阅读“[CF][二分查找][×] codeforces 448D Multiplication Table”

[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci

主要是利用了斐波那契数列对mod1e9+9时二次剩余的性质。说起来这个性质也是很奇葩,只见过两次应用这个题目的情况,一个是这个题一个是/cf.
二次剩余的定义是 当存在某个x使得x^2 \equiv d(mod p)成立时,称“d是模p的二次剩余”,当对任意不成立时,称“ d是模 p的二次非剩余”
而对于斐波那契数列有更具体的性质:
继续阅读“[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci”

[CF][二分check][贪心][×] codeforces 1132D Stressful Training

昨晚肝这一场是真的赔了,傻不拉几的C低级失误wa了一发,出完发现大家都会F然后跑去看了20min没头绪,折回去搞这个D,到最后也没过。。。感觉复杂度没错却一直tle,一直弄到两点受不了了睡觉去了,今早上课困得一批。

下午睡醒之后一直tle on test 27,给跪了好吧,疯狂卡常数真的有意思?最后把multiset改成priority_queue过了,真的服了,到目前为止52组数据吧,最狠的一组达到了2979ms,差21ms超时呵呵呵呵呵呵。。。

继续阅读“[CF][二分check][贪心][×] codeforces 1132D Stressful Training”

[线段树+][LCA][dfs序][二分查找][×] codeforces 1062E

http://codeforces.com/contest/1062/problem/E

这题两个难点,第一个是如何快速找到一堆不一定在一起的节点的公共LCA,第二个是如何确定这一堆节点中需要剔除哪一个。

可以先想一下,设原集合的lca为p1,可以取得最优答案的点为x,其他点为vi,那么x一定不在lca(所有的vi)这个点的子树上。这时候,任意一个vi和x的lca都是p1。这时假如维护一个S[l,r]表示[l,r]的公共LCA,根据上面说的性质,这个S序列一定存在一个断点,从这个点开始所有的S==p1,这样的话就可以利用二分查找找到这个断点,可以确定这个断点一定是候选答案之一。另外一个在二分的过程中其实是所有的lca都是基于最左边那个点积累过来的,所以除了分界点之外另外一个可能影响到答案的就是最左边这个点。到这里就算是找到了唯二可能影响答案的点,只需要对他们分别验证就可以了。从dalao的代码里学到了lca也可以作为线段树维护的变量。。。 继续阅读“[线段树+][LCA][dfs序][二分查找][×] codeforces 1062E”

[CF][补题][线段树][树] codeforces 1076E Vasya and a Tree

这个题自己当时主要还是思维限制,只想着怎么能有类似于dfs序线段树那种操作,或者是就某个点对他的子树做一个什么类似于线段树的打标记处理。。但是感觉太复杂了,没搞出来,而且也没有把可以离线这个点利用起来,还是too young

正解是在dfs过程中维护一个线段树,这棵树的下标是代表了当前dfs到的深度(而非节点),看到这儿就感觉是个很妙的操作,这样的话只需要每次进入到一个节点的时候把对应的属于该节点的所有的操作(这个需要离线处理,把对应的操作存用个vector存起来就可以了)都处理一遍,也就是把对应的所有的区间上的数值加上,dfs离开的时候把对应的区间上的数值减去,回滚一下,就可以保证在dfs过程中就把所有的操作处理完了。

继续阅读“[CF][补题][线段树][树] codeforces 1076E Vasya and a Tree”

[CF][图论][最短路树] codeforces 1076D Edge Deletion

这个题倒是不难,但是我当时对于题目的理解导致写出来很复杂,所以记一下踩的坑。其实就是最短路树的应用,我的想法是先删掉不在树上的边,然后对于树上的边先删除连叶子的边,以此类推。这样写倒是没有错也可以过。

但是!这个题题面里说的是最多k个,所以其实根本不用考虑去掉非树边什么的,假如k>n-1的话只输出n-1条树边也是对的!这就省了好多代码了。其次,根本不用使用拓扑排序那样的处理过程(就是先去掉叶子这种),因为想一下dijkstra的过程就可以发现,每次从优先队列中取出来一个节点后,这个节点的前驱最短路其实已经确定了,只要在这时候把其前驱记录下来,根据dijkstra的每一步往外扩展一步的操作,按照这个顺序搞下去最后的记录表中的顺序其实就是拓扑序。。。。依次输出即可。 继续阅读“[CF][图论][最短路树] codeforces 1076D Edge Deletion”

[CF][补题][递推计数][DP] codeforces 1043F Make It One

其实我用了一种操蛋的贪心试了一下,所有的cf测试数据里只有一组会错。。但是还没有搞明白为什么错了,也没有办法再继续证明正确性,所以还是放弃了去看tutorial,发现果然没思路就是dp。。。

然后这又不是一个正常的dp,甚至可以说不算是dp吧。。要从一堆数字里选出来一个集合使得gcd为1。确实,涉及到集合就很难操作。但是可以发现,如果这个集合存在,他的size是很小的,这里可以作为一个突破点去想。如果考虑枚举集合的大小,是否能有简单的计算方法。现在需要求的东西可以转化为,是否存在至少一个集合使得他的size为i然后gcd为1,当然这个也不好直接算,但如果再加一维,再枚举gcd,看看会不会有进展:这时候要求的转化为,是否存在至少一个集合,size为i,gcd为j。可以设一个dp[i][j]表示这种集合的数量,然后尝试是否可以递推。这时候可以发现这i个数字一定是从j的倍数里选出来的,所有的选法有C(cntj,i)种,其中cntj是原数列中j的倍数的数量。而这些里面又有一些不符合要求的,是因为他们的gcd=k*j,然后可以发现这些不符合要求的数量就是dp[i][k*j],这就实现了从大问题往小问题推的转移了。。。然后就只剩下边界的问题了,这个边界也很有意思:因为只考虑k*j<=max(ai)的gcd,所以大于的就是0就可以了

继续阅读“[CF][补题][递推计数][DP] codeforces 1043F Make It One”

[CF][尺取][减少重复计算] codeforces 1043D Mysterious Crime

emmm第一感觉好像后缀数组之类的结构,但是这个每个元素是个整数,而字符串处理中每个元素都是一个长度为1的字符,,,所以很难把他等同于字符串来处理。但是直接理解的话,要求的话一定是找到一个排列,然后考虑他的每个子段,然后再在其他所有的排列中去找有没有这个子段,直接裸暴力的话n^3*10,肯定不行,但是想一下如果仅仅是考虑所有的子段就一定是不小于n^2的了,所以起码要在这里进行优化。然后由字符串的性质就可以知道一个长度为i的串如果满足要求的话,那么他的所有子串也都是满足要求的这些子串可以不用再计算了,发现了这个之后怎么去实施这个想法?考虑以每个下标i为开始的最长子串,这里如果用暴力的方法每次从i开始递增, 然后在与其他串判断,则当然仍然是n^3的,但是可以发现与其他串判断这个过程其实有很多重复的判断,假如已经知道了i到i+k个存在的话,判断第i+k+1个时候只需要把这一个数字去和其他的串中对应的数字比较是否全部相等就可以了,这样的话把复杂度降到了n^2*10,但是仍然不够,再考虑之前说的,枚举字段中的重复假设已经知道以i开始的到i+k个数字满足要求,那么在算以i+1开始的子段的时候,可以直接从第i+1+k+1个数字开始,也就是说中间的那些都不用再考虑了,因为这些信息已经在算第i个的时候计算过了。所需要保存的只有每个序列中数字i出现的位置而已。

继续阅读“[CF][尺取][减少重复计算] codeforces 1043D Mysterious Crime”