负担集训-9.9(icpc乌鲁木齐站-网络赛)
2017年中国大学生扫大街竞赛打铁记(CCPC秦皇岛)

负担集训-9.10(icpc沈阳站网络赛)

YYY posted @ 2017年9月10日 20:45 in ACM with tags 懒得写了 , 615 阅读
_THIS_IS_START_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分成一段一段的,每段都是同号的。
显然我们要在一个正数段的开头开始,一个负数段的中间结束。
而且我们结束之后,下一个有意义的开始就是下一个正数段的开始。
因此这样暴力搞就行了。
----------------------------------------------------------------
_THIS_IS_END_OF_ARTICLE_

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter