2019-team154-020

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 概述 ==

上海网络赛

[https://www.jisuanke.com/contest/3003/ 计蒜客3003]

team2137

[[Image(Shanghai.png,700px)]]


== 总结 ==


=== dafu456 ===

上海网络赛，怎么全是计数问题呢？？？？

网络赛通病：读不懂英文？？？

虽然今天的体验有点狗屎，但是还是一场“可圈可点”的比赛？过题大师peh过掉了BJL，我用爆搜过了D，dzf预处理然后暴力过了F（好像很容易写挂的样子），都是1A诶。最后剩一个小时的时候我和dzf弄出了C题的做法，peh提示中间一个过程可以用FFT做。我写了N^2的代码交给dzf把其中一个部分替换成FFT。但是dzf并不会写FFT，peh也不太记得了，看了红书就往上写了，过程非常曲折，代码非常长。好不容易四十分钟左右写好了，过了样例，交上去T了。peh说用自己的板子试一试，结果还是T了。T的原因是我们用了9次DFT就T了，其他人都是6次所以过了。。。。。。期间peh也知道A题用点分治就可以过了，然而也好久没写了。。。。

所以，FFT要好好学55555，点分治要好好学。

有很大的遗憾，马马虎虎吧。


=== 题解 ===
C：先对A中每个元素与B中每个元素的和进行计数，虽然数很多但是范围一定在[2, 200000]中间。再计算C的计数的前缀和。再算出因C过大而不合法的方案数，cnt[i] * (n - sum[i])求和。考虑将A过大、B过大、C过大加起来，就得到所有不合法的情况，用全集减去即可。在计算和的计数的时候，需要用到FFT。

D：推一推发现最多只有12个数字不是1，爆搜即可。中间计算组合数过程会爆long long，提前预处理出逆元即可。

F：总共就26位，顺次枚举这一位应该是哪个字母即可。当然，要提前预处理，26*26，f[alpha, pos]表示alpha第一次出现在pos，且在pos后面都是A的时候，的名次。

概述

上海网络赛

计蒜客3003

team2137

总结

dafu456

上海网络赛，怎么全是计数问题呢？？？？

网络赛通病：读不懂英文？？？

虽然今天的体验有点狗屎，但是还是一场“可圈可点”的比赛？过题大师peh过掉了BJL，我用爆搜过了D，dzf预处理然后暴力过了F（好像很容易写挂的样子），都是1A诶。最后剩一个小时的时候我和dzf弄出了C题的做法，peh提示中间一个过程可以用FFT做。我写了N^2的代码交给dzf把其中一个部分替换成FFT。但是dzf并不会写FFT，peh也不太记得了，看了红书就往上写了，过程非常曲折，代码非常长。好不容易四十分钟左右写好了，过了样例，交上去T了。peh说用自己的板子试一试，结果还是T了。T的原因是我们用了9次DFT就T了，其他人都是6次所以过了。。。。。。期间peh也知道A题用点分治就可以过了，然而也好久没写了。。。。

所以，FFT要好好学55555，点分治要好好学。

有很大的遗憾，马马虎虎吧。

题解

C：先对A中每个元素与B中每个元素的和进行计数，虽然数很多但是范围一定在[2, 200000]中间。再计算C的计数的前缀和。再算出因C过大而不合法的方案数，cnt[i] * (n - sum[i])求和。考虑将A过大、B过大、C过大加起来，就得到所有不合法的情况，用全集减去即可。在计算和的计数的时候，需要用到FFT。

D：推一推发现最多只有12个数字不是1，爆搜即可。中间计算组合数过程会爆long long，提前预处理出逆元即可。

F：总共就26位，顺次枚举这一位应该是哪个字母即可。当然，要提前预处理，26*26，f[alpha, pos]表示alpha第一次出现在pos，且在pos后面都是A的时候，的名次。

附加文件