多省省选联考全真模拟考试7
http://csp.ac/contest/15
最后一场,会T1却因为没有理清思路挂了
我真的不喜欢惠惠啦
T1
给定个数,你可以做若干次操作,每次操作是把一个数变成它和它前面那个数的异或和。求经过若干次操作之后,最长上升子序列的长度最长能够是多少。
不难发现每个数都可以异或上前面任意的多少个数
因为每个数一定可以异或上前面一段区间,然后被异或的那段区间可以是前面几段区间异或的结果qwq
所以前面任意一个子序列都可以
然后考虑构造,f[i]表示长度为i的最长上升子序列的最后一个位置的最小是什么
然后考虑暴力,可以把一个位置前面2^n处理下,所有的取值也能搞出来qwq然后取个最小去更新就能够最大化了
紧接着可以考虑线性基,前面所有数线性基一下a,使得a要大于?
先把a变得最小,再从高到低能够异或后大于就更新答案,否则就让a^那个数,因为如果这一位不让他是1之后一定小于了,这样就可以构造出了
T2
计算几何
考虑先分数规划,变成了
然后我们发现A,B具体是什么没有意义,只有他们的比值有意义,所以设A为x,B为(1-x)就能取遍所有值了qwq
然后开始考虑怎么计算几何,式子变一下
所以我们发现这个是一个点带进一条直线啊,那么凸壳吧
也就是说S集合本身的凸壳有了是固定的,但是乘上k后凸壳会变...
所以我们可以求出线段和乘上k之后的凸壳的交点,然后去贪心的选择,用最少的线段覆盖这个凸壳
之后就可以知道能不能只用R线段就得到最优
T3
第一第二个点是环,选择一个最近的点去出发就好
第三四五三个点是可以将线段看成点,然后去用模拟退火跑旅行商就好
第六个点所有的线段没有离群的,所以可以跑一个费用流
第七个点和第六个点一样
最后几个点要求我们每个小部分跑一个费用流,再在全局跑一个旅行商
qwq