A Find The Array 题意 给你一个 a a a数组，这个数组是好的当且仅当这个数组的元素为1或者 a i a_i ai?-1、 a i a_i ai?-2在数组中出现过。给你一个数组和 s s s，问数组最小多长就可以满足数组和为 s s s。 s < = 1 e 3 s<=1e3 s<=1e3 思路 考虑贪心做法即 [ 1 , 3 , 5 , 7 ] [1 , 3 , 5 , 7] [1,3,5,7]方式构造即可。 代码

B Maximum Cost Deletion 题意 给定一个 01 01 01串，我们可以对元素相同的连续子串(全0或全1)进行删除操作，删除该区间后，左右两个区间会拼接，能得到 a ? l a*l a?l+b的价值, l l l为你删除的长度。问你若干次操作删掉所有数后能得到的最大价值。 n < = 100 n <= 100 n<=100 思路 首先比较好观察到的性质是a一定被加上了 n n n次，答案只与 b b b有关，考虑对 b b b分正负数两种情况讨论，正数则让 b b b一个一个删，负数就尽可能的少删即可。 代码

C Manhattan Subarrays 题意 一个区间被认为是好的当且仅当不存在三元组 ( a i , a j , a z ) (a_i,a_j,a_z) (ai?,aj?,az?)是不下降或不上升。给定一个数组 a a a，问你有多少子区间是好的区间。 n < = 2 e 5 n<=2e5 n<=2e5 思路 手完一下我们可以发现手完到四个数的时候，到第五个数的时候我们发现一定必存在三元组 ( a i , a j , a z ) (ai,aj,az) (ai,aj,az)是不下降或不上升的。所以我们暴力长度为 1 ? 4 1-4 1?4的区间即可，判断可以暴力 k 2 k^2 k2判断。 代码

D Excellent Arrays 题意 给定一个数组 a a a,这个数组是好的当且仅当所有的 a i ! = i a_i != i ai?!=i,而且 a i + a j = = i + j ai + aj == i + j ai+aj==i+j的对数在 a a a所有的取值情况最大, a i ai ai的取值在 l l l和 r r r之间。 l < = 1 , r > = n , n < = 2 e 5 l<=1 , r >=n , n <= 2e5 l<=1,r>=n,n<=2e5，求有多少 a a a数组满足上述要求，答案对 1 e 9 + 7 1e9 + 7 1e9+7取模。 思路 vp时想了一小时，转化为了一个更好表达的思路，我们可以发现 a i + a j = = i + j a_i + a_j == i + j ai?+aj?==i+j这个式子可以转化为 a i ? i = j ? a j a_i - i = j - a_j ai??i=j?aj?,然后我们可以去枚举 k k k使得 a i ? i = = k a_i - i == k ai??i==k或者 i ? a i = = k i - a_i == k i?ai?==k。我们暂且把 a i ? i = = k a_i - i == k ai??i==k称为式子1， i ? a i = = k i - a_i == k i?ai?==k称为式子2，我们可以比较容易的发现，当 k k k的取值为 n n n的一半时，答案最大。这个情况一定是存在的，我们可以贪心的让前一半为式子1，后一半为式子2，我们发现一定能构造合法解，因为 l < = 1 , r > = n l<=1 , r >=n l<=1,r>=n。 然后考虑 k k k变大的情况，我们发现当 k k k变大到一定程度的时候，会影响式子1能够取到的最大值和式子2能够取到的最小值，在这里我们分情况讨论 1. k k k不会影响到两个式子的取值，我们的取值的方案数为 C ( n , n / 2 ) C(n , n / 2) C(n,n/2), C C C为组合数。 2. k k k会影响到两个式子的取值，我们需要考虑式子1能取到的最大值和式子2能取到的最小值。然后式子1最大值右侧的数一定选择式子2，式子2最小值左侧的数一定选择式子1，然后我们只需要在两侧之间选择剩余的数即可。需要注意的是当 n n n为奇数的时候分类讨论即可。 代码按照最终思路也是比较好写。这里我放一下vp时写的核心代码

void solve() { int n = read() , l = read() , r = read() ; int t = min(1 - l , r - n) ; int ans = t * C(n , n / 2) ; if(n & 1) ans = ans * 2 % mod ; for(int i = 1 ; i <= n ; i ++){ t ++ ; int rr = min(r - t , n) ; int ll = max(l + t , 1ll) ; ans = (ans + C(rr - ll + 1 , n / 2 - ll + 1)) % mod ; if(n & 1) ans = (ans + C(rr - ll + 1 , (n + 1) / 2 - ll + 1)) % mod ; } write(ans , '\n') ; }

也是回到了历史上的今天辣，当时感觉学长让人遥不可及，已经慢慢地变成了可以比肩并且超越学长的存在了！

---

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。