2020.10.3

· · 个人记录

模拟赛1

A.质数序列

​ 考场上直接按照子串理解题意，使用了尺取法优化，线性筛预处理质数判断，l和r代表子串的两个端点，因为是连续的子串，所以在r++，一个不合法的元素进入队列之中，就需要判断此时的[l,r]中的每个元素是否符合要求，不符合则l++。这样就能在O(n^2)的复杂度下完成查找，而n范围较小，时间不会被卡。

考场上还是蛮自信的，觉得是正解，就没再看

期望：100pts

结果：0

题解：

万万没想到，序列不是子串，子串必须连续，序列只要求顺序按照原序列。那么自然而然的就会想到质数的某些性质：

除2外均为奇数，所以我们首先会考虑到不含有1的奇数与偶数之和，检查新合成的数是否为质数，按要求输出即可；50pts到手

然后深入思考，就会发现，1是特殊的奇数，因为1+1=2，虽然为偶数，但仍为质数，所以我们要对1单独处理。但只找1是最优吗？并不，1虽然是特殊的奇数，但仍是奇数，与偶数相加也可能为质数，所以还要再找1个偶数，而且这个偶数是最大的

做法：按照奇数，偶数，1的分类方式分为三坨，对于奇数堆和偶数堆从大到小排序，然后把这两堆两两组合，选取和最大。然后与1堆比较，只要有符合条件的偶数（没有也可以），看这个数列与2相比，选择序列长的输出即可；

B.种花（？树）

国家集训队试题，嗯，老师相信我们的实力

考场思路：

想到了状压dp使用0/1表示是否选择，然后一个状态应运而生，f[i] [j] [0/1],表示前i个位置，放j盆花的最大收益，但是，题目要求“1与n算作相邻”，“花盆不能相邻放置”，然后，为了将思路延续下去，在第一个位置强行分为两种状态，f1数组与f0数组，表示第一个位置放或不放，然后2~n dp解决。如果有第一个位置和最后一个位置同时放置的情况，舍掉即可；

期望：50pts

实际得分：30pts

题解：带有反悔机制的贪心，使用堆和双向链表维护。

以本题为例，我们们把每个位置的美观值扔进大根堆里，这样每次出来的都是最优（起初），这样做在第一步是正确的，因为有可能不选此点，而选择与它相邻的两个点更优秀，这时候就需要反悔了。

那么如何实现呢？你已经在答案里加入了这个点的美观值，那么首先要把它减掉，再加上相邻两点的美观值，这样答案更优秀了。但如何找到选相邻的收益呢？每次选择一个点，就把这个点两边的点和被选择的点当做一个大点处理，这时候就需要链表，将被选点的前驱指向原前驱的前驱，将被选点的后位指向原后位的后位，这样就完成了维护，当然，bool数组标记是否选过也是必要的步骤；在注意一下环的处理即可；

c.挺进

考场思路：树形结构，不会！写会儿别的题吧·······

无期望，无得分

题解：还是不会，树形结构学的太烂，lca如何求解都已经忘记了（逃