a
倒推,每次删掉最后一个b[i]=i的即可
b
一开始发现可以构造完全二分图,使两边和同为S,这样每个点的和=对面二分图点的和=S,然后n=6和为奇数
进一步发现可以直接分成A组组内和为B的组,然后组之间连边,此时S=(A-1)B,有AB=n(n+1)/2
当n为奇数时取A=(n+1)/2,B=n,n单独一组其他大匹配小;n为偶数时A=n/2,B=n+1,直接大匹配小
c
图连通,显然不能有奇数度数
可以一眼盯真发现最大度数=2时只有一个环,No
最大度数>=6时,取最大度数点作为起点,每次出-进作为一个环,那么至少有3个环,Yes
最大度数=4且有>=3个4度点时,任意取3个4度点xyz,从其中一个4度点出发,除了x-y-z-x-y-z-x只能走出2个环以外其他都是至少3个环
手玩一下,发现x-y-z-x-y-z-x这样x,y,z之间都有2条路,所以存在x-y-x-y-z-y-x的走法,这样也有至少3个环,所以都是Yes
当最大度数=4且有1个4度点时是两个环+一个交点,No
最后剩下最大度数=4且有2个4度点,此时可能是2个环相交两次,也可能是3个环按顺序相交。删掉其中一个4度点,连通是前者,不连通是后者
d
由于A操作可以任意选区间,所以等于把任何一个数往后移;B操作等于前移
考虑序列2 5 1 4 7 3 6 8,选择2468不动,其间大的左移小的右移;所有的方案都可以这样表示,变成选一个上升子序列不动,其他的左/右(不用严格保证两项之间无再选,少选了更劣)
所以直接dp,\(f[i][j]\)表示考虑完1..i怎么动,最后一个不动的大小为j,j单调递增
加入一个小于j的只能左移,加入一个大于j的可以右移或者留下作为j'
在序列前加一个0,初值为\(f[0][0]=0\)
非常简单(
e
重要结论(from 小粉兔):
证一下右边3个:
旧蓝线(a,b)>=新蓝线,并且旧蓝线和新红线之间有公共元素b,所以新红线为(b,c)
此时旧蓝线=a+b,新红线=b+c-m=(c-m)+b,a>=0>c-m,所以旧蓝线>=新红线
因此旧max>=旧蓝线>=新max,所以会变小
然后合法的分界点序列(偶数位置)是一段区间,过左会让右边最小的匹配对小于m,过右会让左边的大于等于m
(最大匹配最小实际是max最小,min最大的匹配方式),且一定存在至少一个合法分界(初始任意连,然后自然调整得到一种方案)
而且分界越往左答案越小,所以二分找到第一个满足右侧合法性的即可
f(不会)
没想明白转化的正确性(
标签:度数,max,匹配,一个,题解,蓝线,度点,agc032 From: https://www.cnblogs.com/gmh77/p/18537012