CF888E

Posted on Edited on In

click

今天听了钟皓曦大神的讲解，扫了一眼题解区，大家都是在论述折半搜索 但是对于排完序之后的数组，进行互相匹配的时候，几乎说的都不是太透彻（个人观点，随便来喷）

于是我决定写一篇较为详细且严谨的题解

考虑当前有一个p属于对于前一半进行dfs得到的数组里面的一个数字，

考虑当前有一个q属于对于后一半进行dfs得到的数组里面的一个数字，

显然，我们知道：\(p<m,q<m\)，因此可以推出\(p+q<2\times m\)

我们也知道我们的答案是\((p+q)\;mod\;m\)，因此需要来讨论\(p+q\)的大小对m造成的影响

第一种情况：

  • \(m<p+q<2\times m\)
  • 此时显然\(p+q\)往大里取最好，因为取的值越大，在\(mod\;m\)之后所得到的结果越大

第二种情况：

  • \(p+q<m\)
  • \(O(n^2)\)匹配来找答案，显然不优，此时需要搞一个双指针来优化
1
2
3
4
5
6
7
sort(sum1 + 1, sum1 + cnt1 + 1), sort(sum2 + 1, sum2 + cnt2 + 1);
l = cnt1, r = 1;
for (r = 1; r <= cnt2; ++ r)
{
   while (sum1[l] + sum2[r] >= mod) -- l;
   res = max(res, sum1[l] + sum2[r]);
}

将两个数组排序，初始化的时候l指向sum1数组的末尾（最大值），r指向sum2数组的开头（最小值）

考虑对于sum2数组中的每一个数字，在sum1中找到某一个数字，使得两者加起来在小于m的情况下最大

具体实现见代码。

此外，给出证明：由于sum1与sum2数组是递增序列，所以一遍扫过来，找到的一定是最优解

如果\(sum1[l] + sum2[r]>m\)，显然，\(sum1[l] +sum2[r+1]\)也一定是大于m的，l递减显然没有问题

代码给出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e7+66;

int cnt1, cnt2, n, mid, m;
int sum1[N], sum2[N], a[N];

inline void dfs1(int now, int sum)
{
   if (now > mid) {sum1[++ cnt1] = sum; return;}
   dfs1(now + 1, sum);
   dfs1(now + 1, (sum + a[now]) % m);
}

inline void dfs2(int now, int sum)
{
   if (now > n) {sum2[++ cnt2] = sum; return;}
   dfs2(now + 1, sum);
   dfs2(now + 1, (sum + a[now]) % m); 
}

inline int thestars()
{
   int i, l, r, res(0);
   scanf ("%d%d", &n, &m);
   for (i = 1; i <= n; ++ i) scanf ("%d", a + i), a[i] %= m;
   mid = (n >> 1);
   dfs1(1, 0), dfs2(mid + 1, 0);
   sort(sum1 + 1, sum1 + cnt1 + 1), sort(sum2 + 1, sum2 + cnt2 + 1);
   l = cnt1, r = 1;
   for (r = 1; r <= cnt2; ++ r)
   {
      while (sum1[l] + sum2[r] >= m) -- l;
      res = max(res, sum1[l] + sum2[r]);
   }
   res = max(res, (sum1[cnt1] + sum2[cnt2]) % m);
   cout << res << '\n';
   return 0;
}

int youngore = thestars();

signed main() {;}