题解 CF888E 【Maximum Subsequence】
first_fan
·
·
题解
咳咳...这道题的正解是meet-in-middle折半搜索
但是！！我要讲讲大家喜闻乐见的玄学算法：随机化
随机化的代码一般很简短，仅仅是简单的模拟而已。
$A1$：这道题题目简单，数据种类少，数据关联性小，正常遍历数量大，所以考虑随机化优化时间复杂度。
$Q2$：随机化不是很玄吗？$WA$会不会霸屏？
$A2$：就一般的随机化而言，$WA$是在所难免的，由于随机化属于骗分技巧，所以可以说你的$rp$和调参水平决定了你的分数。
------------
那么这道题怎么随机化？
我们不妨从随机的对象说起：我们问的是选择其中的一些数，使得$mod$后最大，我们就可以像[背包问题的模拟退火解决](https://www.luogu.org/blog/firstfan/SA-solves-Package)（感兴趣的可以看看）那样，随机化选择或者不选。
模拟退火的操作需要产生能量差，所以本题我直接进行基本随机化：
>$rand()$重复次数，$rand()$选择个数，$rand()$选择数字。
三重$rand()$的稳定性较低，所以循环常数不能小。但是循环常数大了容易$TLE$，所以调参对于一名合格的~~randomer~~OIer相当重要，这里我开的常数在$50000±3000$，能够保证在500ms左右，正确率$80%-90%$。
Here's my code:
```cpp
#include <bits/stdc++.h>
#define ri register int
#pragma GCC optimize("O3")//O3优化对于平时练习时的卡常有奇效
using namespace std;
int read()
{
int num=0;
char c=getchar();
while(!isdigit(c))
{
c=getchar();
}
while(isdigit(c))
{
num=(num<<1)+(num<<3)+(c^48);
c=getchar();
}
return num;
}//快读
const int maxn=20031125;
int a[maxn];
bool vis[maxn];
int main()
{
srand((time)(0));
int n=read();
int mod=read();
for(ri i=1;i<=n;i++)
{
a[i]=read();
}//输入数据
int rnd=rand()%3000;
int ans=0;
for(ri i=1;i<=50000+rnd;i++)//随机循环次数
{
for(ri j=1;j<=n;j++)//清空vis数组
{
vis[j]=0;
}
for(ri j=1;j<=rand()%n+1;j++)//随机选择个数
{
int rd=rand()%n+1;//随机选择数字
if(vis[rd])//剪枝
{
continue;
}
ans=max(ans,(ans+a[rd])%mod);//更新答案
vis[rd]=true;//打标记
}
}
cout<<ans<<endl;//结束
}
```