B - Magical Subsequence （CCPC2021哈尔滨）

本文主要是介绍B - Magical Subsequence （CCPC2021哈尔滨），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

（1）问题：对于已知数组，每组依次选两个，尽量选更多组，选的每组和相等；（假定和为x)

（2）于是问题拆分为两步，

1. x是多少
2. x确定时，怎样选更多组

（3）对于问题1，注意到A：（1，100）,所以x：（2，200）枚举即可；

对于问题2，x确定条件下，显然能选则选最多，此时有两条思路，

1. 前面拿到值从后面找（复杂度O（n^2)且不能保证尽可能长）
2. 后面拿到值往前面找，（开st[]数组查询，此时充分利用前面信息，复杂度O（n+100),且尽可能靠前进行查找；

（4）于是选择思路2，（注意使用set会超时，数组小时应尽量用数组，因为查询复杂度小）

代码：

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e5 + 10;LL a[N];
LL st[210];
int main()
{int n;cin >> n;for(int i = 0;i < n;i ++)scanf("%d",&a[i]);LL maxn = 0;for(int i = 2;i <= 200;i ++){memset(st,0,sizeof st);LL tmp = 0;for(int j = 0;j < n;j ++){if(st[i - a[j]] == 1){tmp += 2;maxn = max(maxn,tmp);memset(st,0,sizeof st);}else st[a[j]] = 1;}}cout << maxn<< endl;return 0;
}

这篇关于B - Magical Subsequence （CCPC2021哈尔滨）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---