Happy Matt Friends(dp)
Happy Matt Friends
Time Limit: 6000/6000 MS (Java/Others) Memory Limit: 510000/510000 K (Java/Others)
Total Submission(s): 1810 Accepted Submission(s): 715
Each of Matt’s friends has a magic number. In the game, Matt selects
some (could be zero) of his friends. If the xor (exclusive-or) sum of
the selected friends’magic numbers is no less than M , Matt wins.
Matt wants to know the number of ways to win.
For each test case, the first line contains two integers N, M (1 ≤ N ≤ 40, 0 ≤ M ≤ 106).
In the second line, there are N integers ki (0 ≤ ki ≤ 106), indicating the i-th friend’s magic number.
case number (starting from 1) and y indicates the number of ways where
Matt can win.
3 2
1 2 3
3 3
1 2 3
Case #2: 2
In the first sample, Matt can win by selecting:
friend with number 1 and friend with number 2. The xor sum is 3.
friend with number 1 and friend with number 3. The xor sum is 2.
friend with number 2. The xor sum is 2.
friend with number 3. The xor sum is 3. Hence, the answer is 4.
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=<<;
int dp[][MAXN<<];//刚开始开到MAXN+10 RE,改成这才对;
int main(){
int T,N,M,flot=;
int m[];
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M);
memset(dp,,sizeof(dp));
dp[][]=;
int x=;
for(int i=;i<N;i++){
x^=;
scanf("%d",m+i);
for(int j=;j<=MAXN;j++){
dp[x][j]=dp[x^][j]+dp[x^][j^m[i]];
//代表上一次值为j^m[i]现在再^m[i]等于j了再加上上次j的个数;
}
}
long long ans=;
for(int i=M;i<=MAXN;i++)ans+=dp[x][i];
printf("Case #%d: %lld\n",++flot,ans);
}
return ;
}
暴力超时:
#include<stdio.h>
int ans,dt[];
int N,M;
void dfs(int top,int sox,int num,int t){
if(num==t){
if(sox>=M)ans++;
return;
}
for(int i=top;i<N;i++){
dfs(i+,sox^dt[i],num+,t);
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M);
for(int i=;i<N;i++)scanf("%d",dt+i);
ans=;
for(int i=;i<=N;i++){
dfs(,,,i);
}
printf("%d\n",ans);
}
return ;
}
最新文章
- NHibernate常见问题及解决方法
- WebP 原理和 Android 支持现状介绍(转)
- 6. Samba服务和防火墙配置笔记
- java.lang.IncompatibleClassChangeError: Implementing class的解决办法,折腾了一天总算解决了
- css3之background-clip与background-origin的区别
- ExtJS4之Ext.MessageBox的各种用法
- python字典根据value排序
- 【Xamarin开发 Android 系列 7】 Android 结构基础(下)
- IE8对css文件的限制
- php composer包管理工具
- Linux段管理,BSS段,data段,.rodata段,text段
- 基于MAC OS 操作系统安装、配置mysql
- 基于 socket.io, 简单实现多平台类似你猜我画 socket 数据传输
- leetcode刷题笔记342 4的幂
- [LeetCode] 20. 有效的括号
- 第十三届东北师范大学程序设计竞赛热身赛 C(exgcd+欧拉函数)
- springboot 静态注入 单例
- js filter 数组去重
- hive lock命令的使用
- python—函数
热门文章
- calltree看代码调用图
- ThinkPHP实现导出
- 四轴飞行器1.1 Matlab 姿态显示
- <;!DOCTYPE html PUBLIC ";-//W3C//DTD XHTML 1.0 Frameset//EN"; ";http://www.w3.org/TR/xhtml1/DTD/xhtml1-frameset.dtd";>;的含义
- SQL Server ansi_null_default | ansi_null_dflt_on
- MySQLD 配置
- HUB主要芯片方案
- 《Linux命令行与shell脚本编程大全》 第十五章 学习笔记
- linux之线程之互斥
- window.showModalDialog刷新父窗口和本窗口的方法及注意