k=2:先将这N个d维向量组成一个N*d的矩阵A,则A*AT&e1i&e3&e1j&e3(mod 2)就是向量i•向量j(mod 2),因此问题有解当且仅当A*AT不是全1.
随机1*N的向量v,看(v*A)*AT是否等于v*(N*N的全1矩阵),如果A*AT不是全1那么期望试两次就可以得到不等的结果.(如果试了10次都是相等,就视为无解)
如果两边的乘积不等,则找到那个不等的列,设为第i列,则必然存在一个解包含向量i,枚举另一个即可.时间复杂度O(Nd)
(正解需要某些很奇怪的性质,本沙茶看不出来,只会85分的)
问题是这个"一定条件"是什么(最难搞的地方囧)
第零,BFS&e1j+1..k&e3这一段的各个结点在DFS序列中的位置递增(这个很显然).
第一,BFS&e1j+1..k&e3这一段的各个结点在DFS序列中的位置之前都必须有在BFS&e1i..j&e3范围内的结点,作为它的父结点(这个也很显然);
第二,DFS序列中,所有在BFS&e1i..j&e3范围内的结点的下一个位置如果不是在BFS&e10..i-1&e3范围内的,就必须是BFS&e1j+1..k&e3范围内的,因为这表示它的第一个子结点(这个灰常难想到!本沙茶就挂在这里了囧......)
对于第零和第一,实际上是给出了k的上限,枚举k时不符合这个条件则退出,而第二则是给出了k的下限(所有的"下一个位置"要填满才能算);
此外,F和G要用long double(double也会爆,不用担心精度,本沙茶当时还在如何维护平均值的问题上纠结了很久......)
(本沙茶当时想到这个做法了,也想到了第零和第一,但木有想到第二,结果挂了......要是真得到85分,总分254,稳的rank1了......真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧,真悲剧......)
首先分析数据就不难发现这10个点其实是一种模型:
一开始有若干元钱(用变量v 2表示).
有若干个大块,每个大块可以选择进或者不进,如果进,就要付出一些钱,如果不进,就自动跳转到后面的某个大块.
在每个大块里有若干个(不超过25个)小块,有1或10个变量,每个小块也可以选择要或者不要,如果要,就对所有的变量各加上一个效果值(可正可负).
目标是所有变量的绝对值之和最大(每个大块末尾会结算一次,然后将所有变量的值清零)
首先每个大块内选哪些小块可以暴力枚举,然后得到最大的总绝对值,设为val&e1i&e3(i为大块编号),设如果不进第i个大块,跳到的大块编号为B&e1i&e3,第i个大块付出的钱为V&e1i&e3.
输出的时候注意一下,那里面有几个点,当钱不够时会自动选择不进当前大块,木有必要作出选择了.
重点是这个:所有的图形都可以拆成单列,一列一列地弄(本沙茶太弱了,这个都木有想起来),然后就是三维DP.
N:设F&e1i&e3&e1j&e3&e1k&e3&e1st&e3表示第i列,上下边界分别为j,k行,状态为第st个部分(第0部分为最左边一竖,第1部分为中间若干块,第2部分为最右边一竖)的最优解,计算好一列之后求出一大堆辅助值,就可以使下一列O(1)算出了.
I:设F&e1i&e3&e1j&e3&e1k&e3&e1st&e3表示第i列,上下边界分别为j,k行,状态为第st个部分(第0部分为那一竖的左边,第1部分为那一竖,第2部分为那一竖的右边)的最优解,不需要辅助值,直接求即可;
O:可以DP,但更好的办法是枚举左,右,上边界,然后扫描,说它更好是因为知道了左右边界,可以直接引出左边的N和右边的I的最优解.
具体实现的时候细节很多......真折磨人.还有要注意为节省空间,F数组要对i这一维滚动.
首先这是个无向环套树(关于这方面的总结见这里)
枚举开店的那条边,如果是树边,求出该边的较下结点往下的最大长度dist1,以及往其它结点的最远距离dist2,则结果即为min{dist1+x dist2+L-x},满足0<=x<=L,L为该边长度.dist1求法不说了,dist2分为两部分,树内的,可以转化为经典DP模型"树的中心点";树外的,先求出环上的每个结点往树中走的最大长度,作为这个结点的权值,然后就转化为一个带边权和点权的环,对于每个点i,求出max{i,j距离+j的权值}(j为环上的点)的值,这个值可以通过在环上扫描的方法求出:设G&e1i&e3为第i个点出发,逆时针走更优的位置最远到哪里.逆时针扫描这个环,然后所有的G就可以在线性时间内求出,求出G后,对每个点分别求出其逆时针更优区与顺时针更优区内的最大值(可以在扫描过程中用线段树维护),即可解决这个问题.
如果开店的边在环上,设其两端点为i,j(i->j为逆时针方向).很容易发现,如果在这条边上开店,则j的逆时针更优区内的所有点一定是逆时针到这个店更近,i的顺时针更优区内的所有点一定是顺时针到这个店更近,而其它的点则需要额外判断一下是顺时针更近还是逆时针更近(总判断次数为线性).这样也可以借助线段树在扫描过程中求出每条环边的顺,逆时针更优区,从而转化为与树边的问题一样的模型.时间复杂度O(NlogN).
二分最远距离(即结果)D,然后对于环上的所有点,找到这个环上到这个点距离大于(D-这个点树里的最大深度)的点集合(显然是连续的一段弧),对所有点的这种弧求并,如果能覆盖整个环,则最优解=D.