hdu4876 深搜+(随机枚举剪枝)
随机 枚举 剪枝
2023-09-11 14:13:59 时间
题意:
给你n个数,让你从选择k个数,然后排成一个环(k个数的顺序随意,但是排成一个环后就不能变了),然后可以在这个环上任意的找连续w个数(w<=k),可以找多次,得到一个值等于当前找的连续的数的异或和,最后问你能找到>=L&&<=R的最大的R,L,R之间的数必须全部存在,给你N,K,L,求最大的R.
思路:
给你n个数,让你从选择k个数,然后排成一个环(k个数的顺序随意,但是排成一个环后就不能变了),然后可以在这个环上任意的找连续w个数(w<=k),可以找多次,得到一个值等于当前找的连续的数的异或和,最后问你能找到>=L&&<=R的最大的R,L,R之间的数必须全部存在,给你N,K,L,求最大的R.
思路:
直接先暴力找到k个数(最多C(20,6)),然后在枚举这k个数的全排列(全排列有STL函数,不想用可以自己深搜枚举),对于每一个序列求出所有可能解,找到最大的R,更新答案,这里有一个很重要的剪枝,也是这个题目的核心就是在全排列之前可以先判断一下是否可能存在可以更新R的最优解,直接深搜枚举当前这k个数(不用管顺序,是找可能存在),看看组成的最大的是否比当前的最大R大,如果不是,那么就没必要全排列再去枚举了,时间复杂度 深搜判断是 O(2^5) 而直接来全排列+枚举是 O(5! * 5 * 5),题目说的是随机数据,所以不存在那种全是极端数据,也就是所有情况都满足的数据,所以相比之下,还是加上那个剪枝比较合算。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int N ,K ,L ,R ,ks; int num[25] ,mark[130]; int now[25]; void mk_jude(int k ,int sum) { if(k == K + 1) return ; mark[sum ^ now[k]] = 1; mk_jude(k + 1 ,sum ^ now[k]); mk_jude(k + 1 ,sum); } int jude(int k ,int sum) { memset(mark ,0 ,sizeof(mark)); mk_jude(1 ,0); for(int i = L ;i <= R ;i ++) if(!mark[i]) return 0; return 1; } void dfs(int k ,int I) { if(k == K + 1) { if(!jude(1 ,0)) return; int tmp[25]; for(int i = 1 ;i <= K ;i ++) tmp[i] = now[i]; for(int tt = 1 ;tt <= ks ;tt ++) { memset(mark ,0 ,sizeof(mark)); for(int i = 1 ;i <= K ;i ++) { int sum = 0; for(int j = 1 ;j <= K ;j ++) { int a = i + j - 1; if(a > K) a -= K; sum = sum ^ tmp[a]; mark[sum] = 1; } } int mk = 0; for(int i = L ;1 ;i ++) if(!mark[i]) { mk = i - 1; break; } if(R < mk) R = mk; next_permutation(tmp + 1 ,tmp + K + 1); } return ; } if(I == N + 1) return; now[k] = num[I]; dfs(k + 1 ,I + 1); dfs(k ,I + 1); } int main () { int i; while(~scanf("%d %d %d" ,&N ,&K ,&L)) { for(i = 1 ;i <= N ;i ++) scanf("%d" ,&num[i]); for(R = 0 ,ks = 1 ,i = 2 ;i <= K ;i ++) ks *= i; dfs(1 ,1); if(R < L) R = 0; printf("%d\n" ,R); } return 0; }
相关文章
- hdu4876 深搜+(随机枚举剪枝)
- .NET C#生成随机颜色,可以控制亮度,生成暗色或者亮色 基于YUV模式判断颜色明亮度
- 【THUWC2017】随机二分图(动态规划)
- Google Earth Engine(GEE)——利用已经加载的特定土地分类的研究区提取随机样本点参与随机森林土地分类
- 利用随机函数实现随机范围的改变
- 如何在 Linux 中产生、加密或解密随机密码
- KAFKA随机产生JMX 端口指定的问题
- 利用Linux系统生成随机密码的8种方法
- 【Java】+随机生成字符串
- 第十节:详细讲解一下Java多线程,随机文件
- Hard 随机洗牌函数 @CareerCup
- 秒懂算法 | 基于主成分分析法、随机森林算法和SVM算法的人脸识别问题
- 随机森林法特点
- [LeetCode] 478. Generate Random Point in a Circle 生成圆中的随机点