首页 > 代码库 > 2017CodeM复赛
2017CodeM复赛
A、配对游戏(loj6191)
题目:
https://loj.ac/problem/6191
分析:
g[i][j]表示前i个位置尽可能合并,合并到最后右边剩下j个>,这样情况的概率
那么g[i][j]=0.5*g[i-1][j-1]+0.5*g[i-1][j+1]
我们能不能根据概率来求期望呢?
emmmmm...有点困难,因为我们只知道每种情况下右边剩余>的个数,却不知道左边剩余<的个数
其实这两个是对称的,所以结果*2就行了
如果没发现这个怎么办呢?那就老老实实设期望
f[i][j]表示在g[i][j]描述背景下剩余个数的期望
那么f[i][j]=0.5*(g[i-1][j-1]+1*f[i-1][j-1])+0.5*(g[i-1][j+1]-1*f[i-1][j+1])
时间复杂度O(n^2)
B、城市网络(loj6192)
题目:
https://loj.ac/problem/6192
分析:
直观想法是要在树上维护一个可撤销的单调栈……但好像不太好弄……换思路
首先可以把询问(u,v,c)转换成u点下挂个点,这个点的点权是c
现在关键问题就是如何快速找到树上每个点的father,这个father是点到根路径上最近的比它大的那个点
可以这样搞,倍增求出fa[i][j]表示i的j级父亲,mx[i][j]表示i向上到j级父亲下面这段点的最大点权
那么就可以根据mx倍增走出每个点的最近父亲,然后对于新的父亲进行倍增
对于每个询问根据深度倍增就行了
时间复杂度O(nlogn)
C、神秘代号(loj6193)
题目:
https://loj.ac/problem/6193
分析:
n个点n条边构成的是一个基环外向树,那个环所表示的模方程正好首位相接,可以解出一个未知数xi的值
然后发现如果确定了一个点的值,那么其它点的值都可以通过bfs得到,并且不会冲突
注意可能有多个基环外向树
D、排列(loj6194)
待填坑
2017CodeM复赛