hihoCoder挑战赛23
A.Emulator
题意
- 给一张图，有(N(N le 300))个点， 给出任意两点之间的最短路。
- 求最多可以去掉多少条边，使得任意两点的最短路长度不变。
思路
- 若一条边((i,j))可以去掉，那么必然存在路径(d(i, k) + d(k, j) = d(i, j))。
代码
B.Certificate
题意
- 已知有(N(N le 14))个变量，变量取值(0)或(1)。
- 已知(f(0,0,cdots,0)，cdots，f(1, 1,cdots,1))的函数值。
- 对于每种输入(x=(x_0,x_1,cdots,x_n))，求最少需要知道几个变量的值即可确定函数值。
- 举个例子：假设有两个变量，函数(f(a,b)=a verb'&' b)，那么对于(f(x)=0)，我们只要知道其中一个变量为0即可确定函数值为0，否则我们需要知道两个变量是否都为1，才能确定函数值为1。
思路
- (2^n)枚举每个取或不取，在要取的变量所有取值中判断是否只会取到唯一值，即不同时取到0和1，这样说明对应的取值是可以判定函数值的，时间复杂度(O(4^n))，约为(2 imes 10^8)，结合单点3000ms应该是可以过的。
- 显然官方题解肯定不是这么做的。
- 对于每个变量，显然只有3种状态，取0、取1或不取。这样做的复杂度为(O(n imes 3^n))。
代码
C.Little Y's Tree
题意
- 给一棵树，有(N(N le 10^5))个点。
- 有(Q(Q le 10^5))次操作，每次删掉(k)条边，求(k+1)个连通块的最远点对的距离和，保证(sum{k} le 10^5)。
思路
- 一个前提：是要会线段树维护子树的最远点对。
- 删除一条边，相当于把子树的dfs序挖掉了一些区间，在剩余区间中求最远点对即可。
代码