bzoj3668 [Noi2014]起床困难综合症——贪心
2024-09-08 07:14:04
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3668
一开始想着倒序推回去看看这一位能不能达到来着,因为这样好中途退出(以为不这样会T);
没想到正着的0和1可能出现一样的结果...
这是WA代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=1e5+;
int n,m,t[maxn],ans,cnt[],op[maxn],c;
char ch[];
int cal(int x)
{
memset(cnt,,sizeof cnt);
int ret=;
while(x)cnt[++ret]=x%,x/=;
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
int mx=;
for(int i=;i<=n;i++)
{
scanf("%s%d",&ch,&t[i]);
if(ch[]=='A')op[i]=;//&
if(ch[]=='O')op[i]=;//|
if(ch[]=='X')op[i]=;//^
mx=max(mx,t[i]);
}
int k=cal(mx);
for(int i=k;i;i--)
{
// if(ans+(1<<(i-1))>m)continue;
bool flag=;int nw=;
for(int j=n;j;j--)
{
cal(t[j]);
if(op[j]==&&nw==&&cnt[i]==){flag=;break;}
if(op[j]==&&nw==&&cnt[i]==){flag=;break;}
if(op[j]==)nw^=cnt[i];
}
if(!flag)
{
if(nw==)ans+=(<<(i-));
else if(c+(<<(i-))<=m)c+=(<<(i-)),ans+=(<<(i-));
}
}
printf("%d",ans);
return ;
}
囧
而且 i 不是从 mx 的最高位开始而是从 m 的最高位开始的...
也不用中途退出什么的,因为位数没有那么大;
可以先用0得到一个 ans 作为底线,然后看看能不能通过某些位上放1让答案更大。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const maxn=1e5+;
int n,m,t[maxn],ans,cnt[],op[maxn],c;
char ch[];
int cal(int x)
{
memset(cnt,,sizeof cnt);
int ret=;
while(x)cnt[++ret]=x%,x/=;
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
int mx=;
for(int i=;i<=n;i++)
{
scanf("%s%d",&ch,&t[i]);
if(ch[]=='A')op[i]=,ans&=t[i];//&
if(ch[]=='O')op[i]=,ans|=t[i];//|
if(ch[]=='X')op[i]=,ans^=t[i];//^
}//得到输入0后的ans
int k=cal(m);k--;
for(int i=k;i>=;i--)
{
int tmp=(<<i);
if(tmp>m||(ans&(<<i)))continue;
for(int j=;j<=n;j++)
{
if(op[j]==)tmp&=t[j];
if(op[j]==)tmp|=t[j];
if(op[j]==)tmp^=t[j];
}
if(tmp&(<<i))ans|=(<<i),m-=(<<i);
}
printf("%d",ans);
return ;
}
最新文章
- Linux命令学习总结:reboot命令
- 错误信息:内存位置访问无效。 (Exception from HRESULT: 0x800703E6)
- zigbee学习之路(十四):基于协议栈的无线数据传输
- ORACLE行转列通用过程
- SQL Server如何添加登录名
- JavaScript-CheckBox全选/反选
- APACHE支持.htaccess以及 No input file specified解决方案
- 【转】cocos2d-x 开发中使用的一些工具
- Python运行机制
- 网易云课堂_程序设计入门-C语言_第二周:判断_2信号报告
- Android 动画animation 深入分析
- UVALive 6869(后缀数组)
- 《java入门第一季》之面向对象(谈谈接口)
- arcEngine开发之加载栅格数据
- dubbo 2.7.0 中缺乏 <;dubbo:annotation />; 的解决方案
- web.xml配置web中的key points(上)
- ASP.NET Core 企业开发架构概述
- [转]客户端js判断文件类型和文件大小即限制上传大小
- vimrc同步文档
- java笔试总结
热门文章
- Oracle臨時表空間過大問題解決
- BZOJ4552 - [TJOI2016]排序
- poj 3678 XOR和OR和AND(简单2-sat问题)
- [HNOI2015]实验比较 树形dp+组合数学
- Linux(3):linux目录结构
- Codevs 二叉树遍历问题 合集
- Codeforces Round #296 (Div. 2) D. Clique Problem [ 贪心 ]
- Android操作系统架构
- 使用imageMagick 制作圆角矩形和图片加水印
- cppcon