负担集训-9.10（icpc沈阳站网络赛）
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
----------------------------------------------------------------
赛前大奶了一口
“虽然hdoj的机子很辣鸡，但是应该还是不至于变成OI赛制的”
然而...
----------------------------------------------------------------
02：
题意是说有K个颜色不同的灯，M个屏幕，要求连接线路，使得任意选K个屏幕都能让他显示出全部K种颜色，一个屏幕要显示某个颜色当且仅当有一条从这个灯连向他的线路。
最小化线路个数。
发现每种颜色至少要(M-K+1)个，所以答案就是K*(M-K+1)
----------------------------------------------------------------
03:
题意是说你跟一个小朋友玩游戏，规则是有n个数，每次可以拿掉最左边的或者最右边的，拿的数的和较大的人获胜。
小朋友不会玩，所以他每次从左右较大的数中选，如果一样他就选左边的。
你要让小朋友赢，但是同时最大化你们俩的分数之差。
预处理一下max[i][j]表示[i,j]这个区间你无脑让小朋友，你们分数的差的最大值，min[i][j]表示[i,j]这个区间你疯狂碾压小朋友，你们分数的差的最小值（小朋友的分数-你的分数，可以是负数）
然后dfs，用上述两个数组剪枝就行了。比如说当前答案加上这个区间的max都还<0，或者加上这个区间的min都还>之前的答案，那么就直接退出
----------------------------------------------------------------
05：
给定一个k，求最小的不能用k个斐波那契数表示的数（每个数只能用一次）
首先由样例知道k=1,答案是4
那么我们只需要找到第一个和后一个数的差>4的数，把他+4就是k=2的答案
每一次都是找到和后一个数的差>上一次的答案的数，加上上一次的答案就是这一次的答案
现在来证明这个：
首先这个一定是不能被表示的，因为显然前面的数表示不出上一次的答案
其次这个数一定是最小的，因为如果一个数跟最近的小于他的斐波那契数的差<上一次的答案的话，我们只需要用k-1个数表示出这个差，然后加上离他最近的那个数，就把他表示出来了。
然后第一个数是4，是5-1，而5是一个斐波那契数，那么5的后一个数，跟他下一个数的差就是5=4+1，那么他+4就是答案
而他又是一个斐波那契数-1，由此我们可以归纳出答案就是f[2*k-1]，其中f表示斐波那契数列
----------------------------------------------------------------
08:
题意就是说给你一棵树，每个节点有一个权值，每条边也有一个权值，要求你选两个点，使得他们的权值只差-距离最大
设dep[i]表示i的深度
枚举lca，发现答案就是max{a[i]-a[j]-dep[i]-dep[j]}+2*dep[lca]，其中i，j是lca子树中两个不相关的点
然后拿个线段树维护一下a[i]-dep[i],-a[j]-dep[j]分别的最大值就好。
----------------------------------------------------------------
12：
说是有一个数组a，有一个数组b，一开始你可以把第一个元素拿到最后去（a跟b同时操作）多次，然后开始游戏。
游戏是这样的，你从左往右，不断地+a[i]-b[i]，直到你的值<0为止，然后你的答案就是a[i]之和
最大化答案
为了方便设c[i]=a[i]-b[i]
我们可以吧c分成一段一段的，每段都是同号的。
显然我们要在一个正数段的开头开始，一个负数段的中间结束。
而且我们结束之后，下一个有意义的开始就是下一个正数段的开始。
因此这样暴力搞就行了。
----------------------------------------------------------------
评论 (0)
