【CodeForces】913 E. Logical Expression
2024-10-15 04:35:10
【题意】令x=11110000(2),y=11001100(2),z=10101010(2),n次询问,每次要求用[与][或][非][括号]构成含至多各1个xyz的表达式使得结果等于给定的数字(0~255),要求表达式最短(一样短时字典序最小)。n<=10000
【算法】数学+最短路?
【题解】实际上给的数字只有256种情况,所以思路是先预处理再直接回答询问。
对每个表达式我们只关心其结果和最后进行的运算符优先级,所以至多有3*256种状态,令n=3*256。
关于优先级,定义三层优先级,最高F为!和(),次高T为&,最低E为|,表达式的优先级为其最后计算的符号的优先级,低优先级遇到高优先级需要打括号。
令F[i]表示最高优先级结果为i的最短表达式,T[i]和E[i]同理,这三种优先级转移如下:
一、F
1.F[i]=min{ F[i] , "(" + E[i] + ")" }
2.F[i]=min{ F[i] , "!" + F[i^255] }
二、T
1.T[i]=min{ T[i] , F[i] }
2.T[i&j]=min{ T[i&j] , T[i]&T[j] }
三、E
1.E[i]=min{ E[i] , T[i] }
2.E[i&j]=min{ E[i&j] , E[i]&E[j] }
只需要这六种转移,三层优先级就可以实现循环转移,可以运用dijkstra,n个结点,转移连边,复杂度O(n^3)。或直接迭代实现至无法更新结束,复杂度O(n^2)。(复杂度分析不太清楚)
最终答案就是ans=E[x],x为输入。
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std; string f[],t[],e[];
char s[];
int n;
bool cmp(string& a,string& b){return a.size()!=b.size()?a.size()<b.size():a<b;}
bool modify(string& a,string b){return (a==""||cmp(b,a))?a=b,:;}
int main(){
f[]="x";f[]="y";f[]="z";
while(){
bool ok=;
for(int i=;i<;i++)if(e[i]!="")ok|=modify(f[i],"("+e[i]+")");
for(int i=;i<;i++)if(f[i]!="")ok|=modify(f[i^],"!"+f[i]);
for(int i=;i<;i++)if(f[i]!="")ok|=modify(t[i],f[i]);
for(int i=;i<;i++)if(t[i]!="")for(int j=;j<;j++)if(t[j]!="")ok|=modify(t[i&j],t[i]+"&"+t[j]);
for(int i=;i<;i++)if(t[i]!="")ok|=modify(e[i],t[i]);
for(int i=;i<;i++)if(e[i]!="")for(int j=;j<;j++)if(e[j]!="")ok|=modify(e[i|j],e[i]+"|"+e[j]);
if(!ok)break;
}
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",s);int c=;
for(int j=;j<;j++)c|=((s[j]-'')<<j);
cout<<e[c]<<endl;
}
return ;
}
最新文章
- 在注册表中无Python3.5安装路径的情况下安装pywin32-
- spring ehcache 页面、对象缓存
- # 20145210 《Java程序设计》第05周学习总结
- HDU4714+三分
- 第3组UI组件:AdapterView及其子类
- 应用360云盘与SVN版本管理服务器搭建基于云端的版本控制软件
- MESH
- 如何调用EcStore中的API接口
- 深入理解JS原型链与继承
- nginx+vaadin配置
- Python量化投资知识总结贴
- nginx常用配置系列-虚拟主机
- Redis 概念以及底层数据结构
- java高并发实战(三)——Java内存模型和线程安全
- 如何设计一款优秀的短视频 SDK
- 如何使用JDBC查询所有记录
- 绝版Node--Sequlize搭建服务(Node全栈之路 二)
- MySQL 在各种程序语音的连接字符串(转)
- 【图论】POJ-3255 次短路径
- Oracle等待事件之Latch Free