0%

题解-CF888E

发表于 更新于 分类于
个人很喜欢的一道题，随机踩标程

咳咳…这道题的正解是meet-in-middle折半搜索

但是！！我要讲讲大家喜闻乐见的玄学算法：随机化

随机化的代码一般很简短，仅仅是简单的模拟而已。

$Q1$：为什么这题可以随机化？

$A1$：这道题题目简单，数据种类少，数据关联性小，正常遍历数量大，所以考虑随机化优化时间复杂度。

$Q2$：随机化不是很玄吗？$WA$会不会霸屏？

$A2$：就一般的随机化而言，$WA$是在所难免的，由于随机化属于骗分技巧，所以可以说你的$rp$和调参水平决定了你的分数。

那么这道题怎么随机化？

我们不妨从随机的对象说起：我们问的是选择其中的一些数，使得$mod$后最大，我们就可以像背包问题的模拟退火解决（感兴趣的可以看看）那样，随机化选择或者不选。

模拟退火的操作需要产生能量差，所以本题我直接进行基本随机化：

$rand()$重复次数，$rand()$选择个数，$rand()$选择数字。

三重$rand()$的稳定性较低，所以循环常数不能小。但是循环常数大了容易$TLE$，所以调参对于一名合格的randomerOIer相当重要，这里我开的常数在$50000±3000$，能够保证在500ms左右，正确率$80%-90%$。

Here’s my code:

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
47
48
49
50
51
52
#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;//结束
}