A- Portal
任务就是要依次经过2k个点
考虑最暴力的DP
设f[i][u][a][b]表示已经完成了前i个任务,当前在点u,两个传送门分别位于a和b的最短距离。• 转移有三种:
1.在u设立传送门
2.从u走到一个相邻节点
3.如果u等于a或者b,那么可以使用传送门
这个DP的转移显然是有环的,因此需要使用Dijkstra算法。
仔细观察,发现记录两个传送门的位置是没有用的,只需要记录一个。因为如果我们要使用一个传送门, 一定是走到那个节点再使用(我们可以随时在当前节点创建传送门)。
设f[i][u][p]表示当前已经完成了前i个任务,在节点u,其中一个传送门位于点p。
转移有4种:
1.从u走到相邻节点
2.在u设置传送门,令p=u
3.从u传送到p
4.在u设置传送门,传送到p,并只保留u的传送门(交换u和p)
再仔细观察,发现可以继续精简状态,设c[i]表示第i个任务的节点。
设f[i][p]表示当前已经完成了前i个任务,当前正在c[i]上,传送门的位置在p。
可以证明,只需要3种转移,就可以覆盖所有情况:
1.直接从c[i]走到c[i+1]
2.枚举走到c[i+1]之后,传送门的位置变为了哪个节点,设这个节点是q。第二种转移是从c[i]走到q,在q设置传送 门,从q传送到p,再从p走到c[i+1]
3.第三种转移是从c[i]传送到p,从p走到q,在q设置传送门,最后从q走到c[i+1]
复杂度为O(kn^2)
B- Graph
做法:可以发现任意两个点之间连边的权值都是固定的。由于图始终联通,所以两点间始终存在至少一条 路径,如果存在多条,根据环的异或和为0,两点间的路径的异或和应该相等,且始终是固定的。
所以可以给每个点一个权值,那么两点间的连边权值就应该是两端点权的异或。
接下来的问题就是异或最小生成树。
字典树
boruvka
C-Easy
做法:
生成函数 𝛴min(N, M)*(x^N)*(y^M) = xy/((1-x)(1-y)(1-xy)) 枚举(1/(1-xy))^K的次数
用1/(1-x)^K 和1/(1-y)^K补到N-K和M-K
D- Drop Voicing
题解:
我们将模型转换成有一个圆盘,圆盘上有n个位置,且有一个指针(初始时指针指向原 来的最后一个元素)
连续若干次操作1等价为改变指针指向的数所处的位置连续若干次操作
连续若干次操作2等价为改变指针的位置
容易观察到,我们只需要取环上最长的一个上升子序列,然后调整其它数,即可得到答 案
时间复杂度O(n^3)或O(n^2)
E-Bogo Sort
所有cycle 长度的LCM。
由于cycle 长度总和是n,所以一定不会大于n 位数,不取模即可。
最长的答案也就几百位。
F- DPS
做法:
模拟即可。注意恰好爆int。double 可能有精度问题。
G-Greetings Souvenir
题解:
首先进行预处理,我们可以通过DFS以及启发式合并预处理出每个子树中的颜色分布,从而计算得到
每个节点u可以得到哪些不同的value[u]
我们可以由此得到一个二分图:左侧为n个不同的点,右侧为n个不同的value,如果左侧的节点u可以 得到右侧的value则进行连边。
可惜这样边数为O(n^2),而本题内存只有64MB,是不能通过此题的。
事实上我们可以把二分的log去掉
假设当前答案在[L,R]之间,我们先判断mid=(L+R)/2是否合法
如果mid不合法,我们继续对[L,mid]进行二分
如果mid合法,我们继续对[mid,R]进行二分,此时我们只需要在mid状态下的残余网络上继续进行网 络流即可。
时间复杂度O(n^2logn)
这里向本题被卡TLE/MLE的选手表示一下抱歉,可能这个题确实卡的比较紧。
H-Interval
做法:对于固定的左端点或者右端点,不同的值至多只有log个• 先把这些值找出来,然后去掉具有包含关系的相同的值
对于固定的左端点或者右端点,不同的值至多只有log个
先把这些值找出来,然后去掉具有包含关系的相同的值
单纯的二维偏序求和无法处理相同的值
那么把相同的值按顺序放在一起(l1,r1)(l2,r2)...(lp,rp)
那么如果查询包含了(l1,r2)(l2,r3)...(lp-1,rp)这些区间,答案就应该-1 。所以设置一些权值为-1的区间,再二维偏序即可。
I-Hard Math Problem
做法:(i+j)%3 =0 交错2和3
答案是2/3
因为这样每个1旁边恰好有一个2和3,而任意两个2和3不相邻。
可以计算出这是上限。
J-Cone Walker
题意:无穷大的圆锥表面上两个不同的圆,求相交的面积
思路:计算几何,分类讨论
做法:
1.先把圆锥面按照两个圆心的角度分成四块,分别展开成扇形,转化为扇形和两个圆的交
2.分类讨论,按照两个圆的位置关系(包含和相交),扇形顶点和两个圆的位置关系(在交的 内部和外部),以及扇形的两条射线和两圆相交区域的交点情况(相交,相切,不相交)分类讨论。
K-Git Merge
做法:
大模拟
先预处理出两个文件,然后dp[i][j][0/1/2] 表示第一个文件第i 行,第二个文 件第j 行,在公用/ifdef 1/ifdef 2 内,切换有代价1,dp n m 0 是答案。dp 可以存在short 里。
全部评论
(1) 回帖