NFLSPC #1 E题 Hack it 题解

2019-06-30 22:25:49 By skyline

这是多校一个题(hdu6313)的加强版 我现场做的时候发现可以做得好不少 于是有了这个题

我们先考虑1的个数的最大上界

记二元组(x,y)对出现次数为:有多少个i使 i行x列 与 i行y列 都是1

发现每个二元组最多出现一次 不然就会出现四角为1的矩形

记$a_i$为第i行1的个数 有:$c(a_1,2)+c(a_2,2)+...+c(a_n,2) \le c(n,2)$

不妨在不影响数量级的情况下做一个近似,变为:$a_1^2+a_2^2+...+a_n^2 \le n^2$

取$k=sqrt(n)$ 由柯西不等式,有:

$(k\times a_1+k\times a_2+...+k\times a_n)^2 \le (k^2+k^2+...+k^2)\times (a_1^2+a_2^2+...+a_n^2) \le n^4$

于是$(a_1+a_2+..+a_k) \le n\times k$ 取等时$a_i=k$

这给了我们一个方向:在1较多时,每行大约sqrt(n)个1

在取$n=p^2$ (p代表质数)时 我们有了一个优美的构造:

请看int main里第一个for循环

但是,我们的n并不是一个质数的平方,我们有2种好的选择:

用若干个小正方形拼起来 用某个大正方形的一部分

因为$43^2 < 2018 < 47^2$ 而47的平方据2018更近(而且实测效果好不少) 所以采用“用某个大正方形的一部分”的方法

这样,就可以得到大约90分的高分了

我们注意到,截小正方形的位置很灵活,可以在任何位置截(事实上还可以不连续,但是实现起来较为麻烦) 我们可以在所以位置中找答案最大的截

但是上面那个构造过于优美导致过于平均,大的答案也并没有很大

我们给出一个类似但不太均匀的构造,再来找答案最大的小正方形输出即可

其中solve是构造,其它部分是找小正方形

另外这是一个吊打std的做法

这篇题解咕了8个月 因为我感觉构造题没什么好讲的 而且这个破方法还被最后一个做法吊打了 但是看那个题解合集一直缺一题难受 最后还是补上了

蝶梦 题解

2019-03-31 12:34:28 By skyline

注意到这个距离的定义类似曼哈顿距离,只是把 $+$ 变成了 $-$

联想到曼哈顿距离转切比雪夫距离,我们发现把坐标 $(x,y)$ 变为 $((x+y)/2,(x-y)/2)$ 后,两点之间的距离变为它们横坐标/纵坐标差值的较小值。

把横/纵坐标相同的并起来,分别沿着横坐标/纵坐标扫一遍,用每个横/纵坐标和之前一个距离不为 $0$ 的坐标的差更新最小值 再用同样方法扫一遍更新最小值的个数。

实现这种做法的最优复杂度是 $\Theta(n)$。

考虑操作的性质其实是一某种方式遍历树花费的总距离,所以最小值是 $2$ 倍边数减去从 $1$ 出发最长的一条链长度(即根深度为 $0$ 定义下的树的深度)。

再考虑方案数,注意到进入一颗子树后必须经过所有节点才能出来(才能保证最小)。

考虑树形 DP,记录:进入一个子树经过所有节点再出来 和 进入一个子树经过所有节点 的方案数。

同时dp记录,进入一个子树经过所有节点再出来 的方案数的逆元,去掉一个快速幂的 $\log$。

时间复杂度 $\Theta(n)$。

这道题等价与问你有多少组不同的不下降序列,最小值不小于 $x$,和为 $n$。

取 $m=\sqrt n$,把每组序列拆成 $2$ 部分,分别为不大于 $m$ 的数和大于 $m$ 的数。

先计算对于任意 $i\le n$,有多少组不同的不下降序列,满足最小值不小于 $x$,最大值不大于 $m$,和为 $n$。直接背包 DP 即可。

再计算对于任意 $i\le n$,有多少组不同的不下降序列,最小值不小于 $\max(x,m+1)$,和为 $n$。

考虑 $dp(i,j)$ 表示有多少组不同的不下降序列,最小值不小于 $\max(x,m+1)$,和为 $n$,长度为 $j$。

$dp(i,j)$ 向 $dp(i+j,j)$(每个数 $+1$)和 $dp(i+\max(x,m+1),j+1)$(头上添加一个数 $\max(x,m+1)$)转移即可。

最后将 $2$ 部分的答案进行卷积,即得到最终答案。

时间复杂度 $\Theta (n\sqrt n)$。

NFLSPC #1 C题 Balance 题解

2018-12-02 11:33:39 By skyline

首先我们考虑2种特殊情况

第一种特殊情况 什么时候输出yjztxdy (杨骏昭天下第一)呢?

如果所有蒟蒻崇拜同一个神犇 显然应该输出yjztxdy

如果不是所有蒟蒻崇拜同一个神犇 一定有相邻2个蒟蒻不崇拜同一个神犇 这2个蒟蒻构成平衡区间

第二种特殊情况 如果整个长度为n的区间是平衡区间 显然它是唯一最长的

我们考虑一般情况

考虑任一个最长平衡区间 它可以由整个长度为n的区间每次去掉一个数得到

由于它是最长平衡区间 所以这个过程中的所有区间都是不平衡的

设整个长度为n的区间中最多的数为x x的出现次数超过一半

每次去掉一个数的过程中 如果x的出现次数变为不超过一半 那它的出现次数一定恰好为一半

如果某一个数在一个平衡区间内出现恰好一半次 显然这是平衡区间

于是我们得到:过程中的区间x的出现都超过一半 最长的那个区间中x出现恰好一半

故x出现一半为区间为最长平衡区间的必要条件 而x出现一半为区间为平衡区间的充分条件

我们把所有x变为1 所以其它数变为-1 找最长的和为0的区间的长度和个数即可

我们可以用前缀和来实现这一想法

std https://acm.nflsoj.com/submission/9697

利用blog实现无限nflsoj

2018-11-25 14:05:00 By skyline

利用blog实现无限nflsoj

bug

2018-06-25 18:41:45 By skyline

访问 http://acm.nflsoj.com/contest/41

出现

Warning: mysql_fetch_array() expects parameter 1 to be resource, boolean given in /home/nflsoj/app/models/DB.php on line 51

Warning: mysql_fetch_array() expects parameter 1 to be resource, boolean given in /home/nflsoj/app/models/DB.php on line 42

Warning: mysql_fetch_array() expects parameter 1 to be resource, boolean given in /home/nflsoj/app/models/DB.php on line 51

Warning: mysql_fetch_array() expects parameter 1 to be resource, boolean given in /home/nflsoj/app/models/DB.php on line 42

skyline Avatar