[数论][图论][思维] 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”

[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)

题目链接

题意:

给定一个长度为 $n$ 的序列 $a$ ,$n \le 10^6$ ,每个数字 $a_i$ ,满足 $0 \le a_i \le 10^6$ .

可以对这个序列进行一种操作,把第 $i$ 个数字中的一份移动到 $i-1$ 或者 $i+1$ .即操作过后 $i$ 处变为 $a_i-1 , a_{i+1}$ 或者 $a_{i-1}$变为 原来的数字+1.

问最少需要多少次操作使得存在某个数字 $k>1$ 满足所有的 $a_i$ 都可以被k整除($0$可以被任何数整除),操作过程要满足所有的 $0\le a_i$ 。

题解:

考虑操作完成之后的结果,如果每一个数字都能被 $k$ 整除,那么显然 $S = \sum_{i=1}^{n} a_i$ 也可以被k整除。所以 $k$ 一定是 $S$ 的一个因数。

然后显然 $k$ 为合数时的情况,要么被 $k=其质因子$ 的情况包括,要么就劣于这种情况。所以我们只需要考虑 $k$ 为质数的情况,也就是 $S$ 的所有质因子。

由 $S$ 最大为 $10^{12}$ 可知,其质因子最多应该只有$10-20$种,而且分解出质因子可以用时间复杂度 $O(\sqrt{n})$ 的算法,也就是约 $10^6$ 。

继续阅读“[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)”

[单调性优化DP][二分][比赛补题][×][思维] codeforces gym 101412 I Beautiful Spacing

题目链接

题意:

要求给一片文章排版,要求每行 $W$ 个格子,每一行的要求是首单词必须顶格,除了最后一行之外的尾单词也必须顶格,然后单词之间至少有 $1$ 个空格,单词内部不能有空格,也不能改变单词之间的顺序。现在问在排版方案满足这些要求的条件下,单词之间的最大空格最小是多少。数据量: 每一行的格子数: $3\le W \le 80,000$, 总共的单词数:$2\le N\le 50,000$ 每个单词的长度 $x_i$ 满足 $1\le x_i \le \frac{W-1}{2}$
继续阅读“[单调性优化DP][二分][比赛补题][×][思维] codeforces gym 101412 I Beautiful Spacing”

[比赛补题][线段树][连通分量][二分图] codeforces gym 102055 B Balance of the Force (CCPC 2018 Final)

题目链接

题意:

给定 $N$ 个人,每个人可以选择加入黑暗 $Dark$ 或者光明 $Light$ 两种阵营,他们加入不同的阵营之后获得的力量值是不同的,即 $D_i$ 和 $L_i$ 。然后有些人之间有矛盾,是不能加入同一阵营的,矛盾的对数共有 $M$ 对,现在给出所有的矛盾和所有的 $L_i D_i$,问在所有可能存在的最终阵营分配情况中,力量值最大的人和力量值最小的人之间的差最小可能是多少?如果说不可能分配的话输出$IMPOSSIBLE$。其中 $1\le N\le 2*10^5$, $0\le M\le 2*10^5$, $1\le L_i D_i \le 10^9$ ,共20组test,时限4S

题解:

一个非常有意思的,看上去像是图论其实是数据结构的题目。。其实以前做过类似的?应该是今年西安邀请赛时候,区别在于那个题目应该是一种背包的性质,一个联通分量要么选,要么不选,而这个题是每个连通分量都得选,但是要从两套孪生方案中选择一种,每一种都会有一个最大值和一个最小值。

把两两不能在一起的人之家连一条无向边,那么一堆互相有关系的人就形成了一个连通分量,不在同一个分量里的人互相是完全没有影响的,无论这个人是选择D还是L都跟我的选择没关系。而在同一个联通分量里的情况的话,可以发现只要有一个人的状态确定了就可以用二分染色的方法确定连通分量里其他所有人的状态。因此我们首先用染色法对每个连通分量判定,如果能染色成功那么就说明有可行解存在,否则输出$IMPOSSIBLE$,另外,在dfs的过程中还要顺便把每个连通分量的两种方案的最大值最小值总共四个数分别求出来(这里我当时就写假了emmm)。之后考虑如何让差值最小化,一般让某个东西最小化很容易想到二分,但是这个题目的条件下,如果要二分就必须再 $O(n)$ 枚举一个下界,乘上 $O(n)$ 的check的话就n方了,显然无法接受。这时候观察这个题目,此时的每个元素(连通分量)正好有两个属性,发现我们可以用一个常用的套路来尝试,那就是按照其中一个属性排序然后对另一个属性套某种log的数据结构。。对这个题来说,回想我们刚才考虑的二分,他必须有一个操作就是枚举出一个下界or上界,那么如果我们就着这个操作进行下去会怎么样?如果我们能一边枚举一边很快的计算出来当当前枚举到的最小值是最小值的时候最大值最小是多少,那么这个问题就可以解决了。
继续阅读“[比赛补题][线段树][连通分量][二分图] codeforces gym 102055 B Balance of the Force (CCPC 2018 Final)”

[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query

题目链接

题意:

给定 $N$ 个数字, $Q$ 次询问,每次询问为查询下标在 $[l,r]$ 之间的所有数字中所有可能的子段的 $gcd$ 有多少种。$N,Q < 10^5 , a_i < 10^6$

题解:

首先一个重要的结论:以固定点为结尾的子段的 $gcd$ 种数不超过 $max(n,log(max(a_i)))$ 证明:每次往原有的序列里加入一个数字的话, $gcd$ 要么不变,要么至少变为原来的1/2,因此为指数级减小。

有了这个结论,我们可以试着来枚举一个端点考虑本题,不妨枚举每个段的右端点$r_j$ , 假设集合$S$表示以$r_{j-1}$ 为结尾的所有 $gcd$ ,那么要求出以$r_j$为结尾的所有 $gcd$ ,只需遍历S中的每个数字$d_k$,计算其与$a_j$ 的 $gcd$ ,放入新集合$S^{‘}$即可。这样的话我们可以得到一个空间为$O(nlogn)$的结果,表示以每个点为结尾的所有段的 $gcd$ 都是哪些数字。

现在来考虑查询。每次查询的话是要求出来$[l,r]$之间所有可能的 $gcd$ 。直接暴力不可取,由上面的结果可以试着考虑能否转化为前缀问题。可以发现,如果我们对所有的$[l,r]$离线处理,按$r$从小到大排序,并且按照这个顺序来调整已经遇到过的 $gcd$ 的信息的话,每次的查询只需要考虑有多少个 $gcd$ 出现的最右左端点大于等于l,这句话具体的意思是,一个 $gcd$ 可能出现过了很多次,不同的段都可以得到这个 $gcd$ ,但是我们只考虑这些段中左端点l_j最大的那个点$p_j$,这样的话如果$l<=p_j$那么可以确定$[l,r]$中一定有这个 $gcd$ (种类+1),这就就转化成了一个计数问题。 继续阅读“[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query”

[数位DP][二进制性质][异或][贪心] 百度之星初赛Round 2 1003 度度熊与运算式1


题意:给一堆1,中间由运算符 $op$ 隔开,$op$ 可能是按位异或 $\oplus$ 或者$?$, 问现在把 $?$ 换成 $\oplus$ 或者 $+$ ,能让整个运算式取最大的方案结果是多少?

题解:首先注意到一点是位运算优先级比异或运算高,这样的话显然我们可以把原来的不能更换的 $\oplus$ 当作分隔,把原式分割成一些段,现在的问题就是怎么处理这些段里的符号使得最后结果最大。
继续阅读“[数位DP][二进制性质][异或][贪心] 百度之星初赛Round 2 1003 度度熊与运算式1”

[比赛补题][DP][递推计数][思维] 牛客2019多校 第一场 E ABBA

比赛时候:第一眼这不就DP吗,第二眼欸这东西怎么转移啊。。gg

当时迷了一直在想以AB和BA的数目为下标推,但是这样会有很多去重的问题。。。于是就没整出来,后来滚去推高数题了

看了叉姐的一句话题解大概懂了,推的时候直接用x和y的数目做下标,这样首先可以避免重复的问题。也就是设dp[i][j]为i个A,j个B时可用的前缀有多少种。这里面最重要的就是这个“可用的”怎么确定。这里的判断写出来很简单(i-j<=n&&j-i<=m).为什么是这样的呢?现在来考虑一个前缀,什么时候我们可以判断这个前缀一定不能作为最终答案中的某一个方案的前缀(也就是对最终答案没有任何贡献)?首先考虑凑AB,要用这个前缀的话,最终的结果是在他后面再补上(n+m-i)个A和(n+m-j)个B,注意这里的后面的排列并没有确定,也就是说我为了用到这个前缀(使答案+=它这种情况),可以尽力的去想办法摆布后面的A和B使得满足要求。那么有一个结论是在i-j>n的时候无论后面如何摆都满足不了要求:这个前缀至少可以配成j-1个AB或者BA,在加一个AB或者BA,然后如果i比j多了n个以上,那么意味着这多出来的i-j个A跟后面的配对只能配AB了,这样的话AB的总数就超过了n,由于AB和BA的总数确定的,这时候就一定不满足要求了;反之如果i-j<=n,则一定可以通过后面的调整来满足n个AB,m个BA的要求,可以自己试试看,只要注意到AB和BA的互换就行了。比如ABAB可以看出俩AB也可以看出一个AB一个BA(中间的)。。

然后dp边界是dp[i<=n][0]=1,dp[0][j<=m]=1,这个很好理解,全是A或者全是B就只有一种情况的。。。

这题还有点卡常,dp每次不要都memset,否则会tle 继续阅读“[比赛补题][DP][递推计数][思维] 牛客2019多校 第一场 E ABBA”

[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”

[DP][思维][×] codeforces 1183H Subsequences (hard version)

题目链接

题意:给定一个字符串S,长度为n≤100,然后定义一个操作是将S的一个含有L个字符的子序列看作一个字符串插入到一个无重复元素的set里,每次操作的cost是(n-L),然后问对于给定的k(k最大可取1e12),最少需要多少总cost才能使得set的元素个数达到k。难度2200分,有点虚高其实,不过还是不那么好想的。用先后顺序去重是关键idea。

做这种代码段但是考思维的小题还是挺有意思的。。。。

这题是mike出的,感觉挺经典那种。他有一个easy version是k≤100,这个要求的话就很松了,mike的题解直接用了一种及其暴力的方法:把每个subsequence当作一个点,相差一个字符的点之间连边建图,直接暴力跑bfs。。。这个肯定是个时间和空间复杂度都爆炸的算法,但是k≤100的时候很快就能搜到,只要及时跳出bfs就可以了。

这个H版本要求k最大可能是1e12,这就不能再那么操作了。首先写几个简单的样例就可以发现这个主要跟unique的子序列的长度和数量有关系,如果我们能求出来对应于某一长度j的unique子序列有多少个,那就可以解决这个问题了。这个就是一个引导方向,可以先试着设dp[i][j]表示以i为结尾的长度为j的子序列个数。状态定义好了之后考虑转移,按照大问题转化为小问题的思想,dp[i][j]表示的以i结尾的unique子序列,那么如果去掉s[i]之后这些子序列一定是互不相同的长度为j-1的子序列,数量没有多也没有少。所以现在就是要考虑怎么算出来前i-1个字符构成的子序列里面有多少个了。利用已经计算得得信息,这个一定是某些dp[pos][j-1]之和,但是有一种情况的是不同的pos对应的子串可能一样,所以这个题目最精彩的部分就来了,每次在相同的字符中选取最靠后的作为计算点。第一这样起码不会比选择前面的点坏,如果前面的点能凑成q个子序列那么后面的点凑成的相同长度的子序列只会多不会少,即不漏;第二这个就避免了重复计算的现象,不重不漏即为正确的dp转移。所以如果用\[lst[i][w]\]表示前i个字符里面字符为\[‘a’+w (w \in [0,25])\],可以写出来状态转移方程为

\[dp[i][j]=\sum_{w=0}^{25} dp[lst[i-1][w]][j-1]\]

至于lst显然很简单的一个dp就推出来了lst[i][j]=((int)(s[i]-‘a’)==j)?i:lst[i-1][j];
继续阅读“[DP][思维][×] codeforces 1183H Subsequences (hard version)”

[比赛补题][×] 2019 ICPC南昌邀请赛网络赛 K MORE XOR

2019 ICPC南昌邀请赛网络赛 K MORE XOR

题目链接

(⊙﹏⊙)不知道为什么比赛时候这个题和D题死推不出来,比赛完了5分钟ac,我大概脑子坏掉了。真的是超超超超级简单的一个题,但是我光顾着用数学公式推了所以推出来结果巨复杂(⊙﹏⊙)服了自己了。

题解:先说怎么求g(l,r): 首先f(l,r)很好求,利用异或的性质,预处理出来前缀异或和就可以了。设预处理出来p1[x]表示从a[1]到a[x]的异或和,那么很容易得到\[f(l,r)=p1[l-1]\oplus p2[r] \], 那么可以由g的定义就可以知道 \[ g(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} f(i,j) =\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} p1[i-1]\oplus p1[j] \];当然这个东西还是很复杂的,我们想办法把他复杂度搞到O(1):考虑每个p1[x]出现的次数,列个表可以发现,在这个求和式中出现的所有下标,从l-1变化到r, 而每个下标出现的次数都是一样的,这个次数等于 r-l+1 ,那么就可以得出结论,如果r-l+1为偶数,则g(l,r)应为0,否则应为\[ \sum_{i=l-1}^{r} p1[i] \],注意到这个式子又可以用p1的前缀和来O(1)计算,所以又可以提前求出来p1的前缀和p2,这样的话g(l,r)就可以表示为

\[g(l,r)=
\begin{cases}
0& \text{(r-l+1) is odd}\\
p2[l-2]\oplus p2[r]& \text{else }
\end{cases}\]

有了g(l,r)再来考虑w(l,r),\[w(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} g(i,j) \],就跟g的表达式很像,但是这里不能直接再套用g关于p1的公式,因为g里面有很多的0是跟p2无关的,换句话说这些0并不是由p2[l-2]^p2[r]求出来的,所以要分类讨论。分析方法跟g是类似的,列一个表观察每个p2出现的规律,可以发现,这个规律是4个一循环的结构,设\[t=(r-l+1)\mod 4\]; 则当t==0时,所有的p2下标出现次数均为偶数次,也就是结果一定为0,t==2时,所有的p2下标出现次数均为奇数,这样的话即等于\[\sum_{i=l-1}^{r} p2[i] \],这个式子说明我们可以再用一个p2的前缀和p3来O(1)计算这个结果。这是比较简单的两种情况,另外两种是t==1和t==3,这两种一种是奇数项的出现次数为奇数偶数项为偶数,另一种是奇数项出现次数为偶数而偶数项出现次数为奇数,这意味着可以用一个分奇偶的前缀和来O(1)求得这个式子只不过仍需要分类讨论一次。。若令p31[i]和p32[i]分别表示p2的奇偶前缀和,t=(r-l+1)%4, 则w(l,r)的表达式为

\[
w(l,r)=
\begin{cases}
0& \text{t=0}\\
p31[r]\oplus p31[l-3]& \text{t=1 and r is odd}\\
p32[r]\oplus p32[l-3]& \text{t=1 and r is even}\\
p3[l-3]\oplus p3[r]& \text{t=2}\\
p32[r-1]\oplus p32[l-2]& \text{t=3 and r is odd}\\
p31[r]\oplus p31[l-3]& \text{t=3 and r is even}
\end{cases}
\]

这样的话整个问题就可以O(1)解决了。。不知道我当时脑子怎么回事就没推出来
继续阅读“[比赛补题][×] 2019 ICPC南昌邀请赛网络赛 K MORE XOR”