多省省选联考全真模拟考试7

http://csp.ac/contest/15

最后一场,会T1却因为没有理清思路挂了

我真的不喜欢惠惠啦

T1

给定NN个数a1,a2,,aNa1,a2,⋯,aN,你可以做若干次操作,每次操作是把一个数变成它和它前面那个数的异或和。求经过若干次操作之后,最长上升子序列的长度最长能够是多少。

不难发现每个数都可以异或上前面任意的多少个数

因为每个数一定可以异或上前面一段区间,然后被异或的那段区间可以是前面几段区间异或的结果qwq

所以前面任意一个子序列都可以

然后考虑构造,f[i]表示长度为i的最长上升子序列的最后一个位置的最小是什么

然后考虑暴力,可以把一个位置前面2^n处理下,所有的取值也能搞出来qwq然后取个最小去更新就能够最大化了

紧接着可以考虑线性基,前面所有数线性基一下a,使得a要大于f[i]f[i]?

先把a变得最小,再从高到低能够异或后大于f[i]f[i]就更新答案,否则就让a^那个数,因为如果这一位不让他是1之后一定小于f[i]f[i]了,这样就可以构造出了

T2

计算几何

考虑先分数规划,变成了

f(T,A,B)>=kf(S,A,B)f(T,A,B)>=kf(S,A,B)

然后我们发现A,B具体是什么没有意义,只有他们的比值有意义,所以设A为x,B为(1-x)就能取遍所有值了qwq

然后开始考虑怎么计算几何,式子变一下

max(aix+bi(1x))=max((aibi)x+bi)max(a_ix+b_i(1-x))=max((a_i-b_i)x+b_i)

所以我们发现这个是一个点带进一条直线啊,那么凸壳吧

也就是说S集合本身的凸壳有了是固定的,但是乘上k后凸壳会变...

所以我们可以求出线段和乘上k之后的凸壳的交点,然后去贪心的选择,用最少的线段覆盖这个凸壳

之后就可以知道能不能只用R线段就得到最优

T3

第一第二个点是环,选择一个最近的点去出发就好

第三四五三个点是可以将线段看成点,然后去用模拟退火跑旅行商就好

第六个点所有的线段没有离群的,所以可以跑一个费用流

第七个点和第六个点一样

最后几个点要求我们每个小部分跑一个费用流,再在全局跑一个旅行商

qwq