标签
暂无

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

2018.6.17题解

2018-06-17 13:00:22 By skyline

注意到原问题等价于{1,3,7,15,31,...}的无限背包 暴力跑背包即可

证明:

令$a_1=v_1,a_2=v_2-2v_1,a_3=v_3-2v_2,...,a_m=v_m-2v_{m-1}$

带入得 $(2^m-1)a_1+...+3a_{m-1}+a_m=n$

其中 $a_1\ge 1$ $a_2,a_3,...,a_m\ge 0$

所以是一个{1,3,7,15,31,...}的无限背包

时间复杂度O(nlogn)

对时间建线段树 套线性基

对于每个光源 把它所有存在的时间放到线段树上 注意一直开到最后的光源也要加进去

这样一共是nlogn块存在时间

然后按dfs序遍历线段树来计算答案

进入一个节点的时候 复制当前的线性基 然后用节点中的光源更新线性基

如果到了底层就计算该节点的所有询问

退出一个节点的时候 用备份的线性基恢复原来的线性基

时间复杂度O(nlog^2n)

还有一个O(nlogn)的更优做法

维护一个动态线性基 优先程度为此数的删除时间

删除时间越靠后 优先级越高

删除的时候直接把那一位变成0即可

为了更清楚的理解这个O(nlogn)做法 你可以看这份代码 http://acm.nflsoj.com/submission/5980

B和C的贡献是确定的

用费用流计算A的贡献

对每个(i,j) 建一个点 连到t一个流量1费用0的边

如果f(i,j)=1 j向(i,j) 连到一个流量1费用0的边

如果f(i,j)=-1 i向(i,j) 连到一个流量1费用0的边

如果f(i,j)=0 i j各向(i,j) 连到一个流量1费用0的边

s向1-n每个点连n条边 流量都是1 费用都是{A,3A,5A,7A,...}

这样 任何一对(i,j) i和j中恰好一个的出现次数+1

而对i来说 出现k次费用刚好是Ak^2

时间复杂度O(费用流)

just a test

2018-04-16 20:39:36 By skyline

fizzydavid

skyline

fizzydavid

10个代表(#72字符串O(n)做法)

2018-02-14 18:16:47 By skyline

全相等那种情况略

对于S(i,0)-S(i,1)=xi,S(i,1)-S(i,2)=yi,S(i,2)-S(i,0)=zi

我们有:(j,i]可行<==>xi!=xj,yi!=yj,zi!=zj

所以我们对每个i,找到最小的j,0<=j< i, xi!=xj, yi!=yj, zi!=zj, 然后用i-j更新答案即

对于xi!=0,yi!=0,zi!=0,j=0

对于xiyizi恰好2个等于0,不可能,因为x+y+z=0

对于xiyizi恰好1个等于0

考虑x=0的情况

我们需要维护3个代表即可:

第一个:最小的p使xp!=0

yp=y且zp=z是不可能的,因为y+z=0,yp+zp!=0

对于yp=y的情况,我们知道了这组为(0,yp,-yp),对这一组找一个最小代表即可

对于zp=z的情况,我们知道了这组为(0,-zp,zp),对这一组找一个最小代表即可

y=0,z=0情况同x=0

对x=0,y=0,z=0 找一个代表即可

一共是10个代表

代码

http://acm.nflsoj.com/submission/4226

一组成功的hack数据与算法修正

2018-02-14 17:54:14 By skyline

数据:24 CBBSSCCBSCBSCBSCBSCBSCBS

同时我找到了一种26个代表的做法 可以被严格证明 如果开学前我找不到k个代表(k<=10),我会给大家26个代表的做法和证明

8个代表出锅了

2018-02-14 15:47:30 By skyline

大家好 蒟蒻skyline的垃圾数据结构8个代表本身好像出锅了

对于数据结构本身 我们可以这样卡掉:000/011/022/000/000/000/000/101

至于那个代码是否能AC,我需要再研究一下 毕竟题目有其他条件

非常的抱歉 欢迎大家差评

共 13 篇博客