莫名其妙拿到了一个名额
A.Namomo Subsequence
题意
挺长的,简化一下就是,求出一个字符串中,满足和$namomo$性质相同的子序列个数,即第一个字符和第二个字符与其他的都不相同,第三个字符和第五个字符相同和其它的不相同,第四个字符和第六个字符相同,和其它的不相同。
题解
我们先考虑将这个字符串拆分成$na$和$momo$两部分,我们发现倒着枚举会比正着枚举方便。
$omom$部分:
考虑$dp[i][x][y]$,$i$为当前$x=s[i]$所处的位置状态,分别为$yxmom,yxom,oxym,omyx$这四种情况,$x,y$就表示两种字符,他们总方案数是多少,则有转移
其中$y$是枚举的不为$x$的其它字符,而我们想要的实际上就是$omyx$这种情况,即$dp[2][x][y]$。
$an$部分:
首先我们需要知道两个不同字母可以构成多少个子序列,实际上就是$cnt[x]*cnt[y]$,为什么,实际上考虑$xy$个数+$yx$个数,就是$x$,$y$总共能贡献的,实际上就是每个$x$都可以和$y$匹配。
有了这个之后我们就可以容斥一下,假设现在字母个数为$tot$,所有字母个数的平方和$pwtot$,其中我们不要$xx$,则所有不同字母可以获得的实际上就是$\frac {(tot\times tot-pwtot)}{2}$个,但是还有一点,就是我们不想要$momo$中那两种字母出现,那假设这俩为$i,j$,则有$\frac{((tot-cnt[i]-cnt[j])\times(tot-cnt[i]-cnt[j])-pwtot)}{2}$,但我们发现$pwtot$会多减去两个的平方和,所以最终就是$\frac{((tot-cnt[i]-cnt[j])\times(tot-cnt[i]-cnt[j])-pwtot+cnt[i]\times cnt[i]+cnt[j]\times cnt[j])}{2}$
枚举的同时将两部分合起来就是$dp[2][x][y]*cal(x,y)$
代码
1 |
|
F.Rooks
题意
有黑白两种点,各有$n(\le 2e5)$和$m(\le 2e5)$个,他们的坐标是$x_i,y_i(-1e9\le x_i,y_i\le 1e9)$,并且他们放的位置不重叠。定义一个点能到另一个点,当且仅当他们的$x$或者$y$坐标相等,并且他们沿途没有其它点。问每个点是否能到达其相反颜色的点。
题解
刚开始用map去写模拟然后$T$了,应该是常数很大,所以想了一下,实际上只需要对$x$和$y$分开考虑就行了,写两个排序函数,一个以$x$为主,然后排序枚举,另一个以$y$为主,同理。
代码
1 |
|
L.Square
题意
现有一个长为$n$的序列$a$,你需要构造一个序列$t$,使得$\sqrt{a_i\times t_i\times a_{i+1}\times t_{i+1}}\in\Z(1\le i < n)$,并且$\prod_{i=1}^{n}t_i$最小,求这个最小值。
题解
首先很明显的就是我们需要考虑的是质因子的幂次的奇偶性,那么对于一个某一个质因子是奇数的位置,考虑这个质因子我们填在哪,那么肯定是要么$t_i$,要么就$t_{i-1},t_{i+1}$,如果填在后面的情况,那么如果那两个位置这个质因子出现次数为偶数,他也会变成奇数,就会往继续传下去,namo就可以发现,实际上这个质因子在$t$中的出现是$min(n-mp[i],mp[i])$,$mp[i]$为某个质因子幂次为奇数的下标个数。
代码
1 |
|
- 本文作者: baddog
- 本文链接: https://katoli.github.io/2022/06/15/2020-EC-f/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!