UOJ Logo ydc的博客

博客

NOIp2014 Day1 民间题解

2014-11-08 13:57:22 By ydc

萌萌哒ydc来放题解了

先放day1,day2明天才考

T1

考你会不会编程

T2

$n$个点$n-1$条边的无向连通图就是个树

考虑距离为2的点对,可以理解为枚举$i$,$i$能走到的点集两两之间距离为$2$

我们要做的是对于一个数组$a_1,a_2,a_3,\ldots,a_m$,要求$a_ia_j,i \neq j$的Σ与max

max是个很简单的事情,你只要求$a$数组的最大值与次大值即可

至于Σ,我们知道$\sum\limits_{i=1}^n \sum\limits_{j=1}^n a_ia_j=(\sum\limits_{i=1}^na_i)^2$,于是容易推出我们要求的就是$(\sum\limits_{i=1}^na_i)^2-\sum\limits_{i=1}^n a_i^2$

当然你也可以令$s=\sum\limits_{i=1}^n a_i$,求$\sum\limits_{i=1}^n a_i(s-a_i)$

复杂度应该是$O(n)$的

T3

我们很容易看出一个很经典的完全背包的框架:我们可以在某个时刻上升$1,2,3,\ldots \infty$次,有$n$个时刻

当然根据题意,这题和完全背包有很多的不同,比如能下降,不能选择上升$0$次,下界不可到上界不可越,有些位置不允许,等等等等

即使如此,我们仍然能以完全背包的思想为核心,解决这个题

由于是完全背包,显然可以用滚动数组优化将空间降为$O(m)$。为了便于理解,我们用二维状态来描述:$dp_{i,j}$表示横坐标为$i$,纵坐标为$j$的最小步数

由于不能上升$0$次,我们这样转移:$dp_{i,j}=\min(dp_{i-1,j-x_i}+1,dp_{i,j-x_i}+1)$

由于有障碍,我们求出$dp_{i,j}$后再将障碍位置的值赋值为$\infty$

由于上界可以越过,所以要特殊转移一下,$dp_{i,m}=\min(dp_{i-1,k}+s_k)$,$s_k$为$k$达到$m$处的花费,他是个式子,在此不将其展开

最后由于能下降,所以$dp_{i,j}$还可以由上一步在$j+y_i$的状态转移

如此问题就解决了,时间复杂度$O(nm)$

评论

UncleGai
T2一个O(nm) T3一个O(nm^2) 都没想到怎么把m优化掉 呜呜
ydc
@UncleGai T2的m是什么?
1756500824
"由于有障碍,我们求出dpi,j后再将障碍位置的值赋值为∞"赋这个是在什么时候赋,另外要不要赋多次?@ydc
TKD
回复ydc:我猜他打的是SPFA。。。。。。。
ydc
@1756500824 唔,我是按照我写代码的过程来写的题解,以及赋了一次值之后就不用再赋值了吧?
1756500824
好像是的,只有在“由于不能上升0次,我们这样转移:dpi,j=max(dpi−1,j−xi+1,dpi,j−xi+1)”的时候对后面有影响,而之后的更新好像没有影响,放哪里都可以。@ydc
dwjshift
@ydc T3是min吧……
613
p2不是可以建完树就输出答案的吗 p3不是dp慢动作吗 @ydc @TKD 难道我都错了
ydc
@1756500824 恩,我只是写一下大致思路,如果看懂了细节可以自己想
ydc
@dwjshift 唔,是我不小心写错了
ydc
@613 我的意思是连建树都不需要……你只要对每个点连出去的所有点算一下就好了,建树还要写个BFS。至于后面那句话我不知道什么叫dp慢动作
sbit
@ydc 第二题我写了dfs转有根树会不会爆QAQ
ydc
@sbit dfs的话有可能会爆栈吧。我是BFS转的。不建树的技巧是别人告诉我的
OnlyaDouBi
哪位大神放上民间数据供蒟蒻测测
ydc
@sbit 不过也不一定,因为深度太大,度数相对而言就会变小,说不定会把暴力放过去,所以可能没有这种数据吧……数据吧……吧……
Gromah
大神不愧是大神。请容本渣渣膜拜一下。orz

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。