【codeforces 779E】Bitwise Formula
2024-10-01 01:19:39
【题目链接】:http://codeforces.com/contest/779/problem/E
【题意】
给你n个长度为m的二进制数
(有一些是通过位运算操作两个数的形式给出);
然后有一个未知数字,用符号’?’表示;
(所有的数字都是长度为m的二进制数);
然后让你确定这个’?’使得n个数字的和最大、最小;
【题解】
模拟题;
会有嵌套的情况;
即
a=x & y
b=a&?
类似这样.
所以在算b之前,先把a的值确定下来;
明白了怎么算之后;
枚举那个未知数字的m位的每一位;
每一位都只有两种可能,即为0或者为1;
假设为0;
然后带进去算一下最后结果,这一位的和为多少;
假设为1
然后带进去算一下最后结果,这一位的和为多少;
如果要最大值就选那个大的对应的数字,最小值则相反。
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define ps push_back
#define fi first
#define se second
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define ref(x) scanf("%lf",&x)
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };
const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };
const double pi = acos(-1.0);
const int M = 1e3+100;
const int N = 5e3 + 100;
struct abc
{
int a, b, p;
int sz[M];
};
int n, m,change,f[N];
string name,s;
map <string, int> dic;
abc a[N];
vector<int>v1, v2;
int get_val(int pos)
{
int sum = 0;
f[0] = change;
rep1(i, 1, n)
{
if (a[i].p == 0)
{
sum += a[i].sz[pos];
f[i] = a[i].sz[pos];
continue;
}
int x = f[a[i].a], y = f[a[i].b];
int p = a[i].p;
if (p == 1)
f[i] = x&y;
if (p == 2)
f[i] = x | y;
if (p == 3)
f[i] = x^y;
sum += f[i];
}
return sum;
}
int main()
{
//freopen("F:\\rush.txt", "r", stdin);
rei(n), rei(m);
dic["?"] = 0;
rep1(i, 1, n)
{
cin >> name; dic[name] = i;
cin >> s; cin >> s;
if (s[0] == '1' || s[0] == '0')
{
a[i].p = 0;
rep1(j, 1, m)
a[i].sz[j] = s[j - 1]-'0';
}
else
{
a[i].a = dic[s];
cin >> s;
if (s[0] == 'A') a[i].p = 1;
if (s[0] == 'O') a[i].p = 2;
if (s[0] == 'X') a[i].p = 3;
cin >> s;
a[i].b = dic[s];
}
}
rep1(i, 1, m)
{
change = 0; int temp0 = get_val(i);
change = 1; int temp1 = get_val(i);
if (temp0 <= temp1)
v1.ps(0);
else
v1.ps(1);
if (temp0 >= temp1)
v2.ps(0);
else
v2.ps(1);
}
rep1(i, 0, m - 1)
printf("%d", v1[i]);
puts("");
rep1(i, 0, m - 1)
printf("%d", v2[i]);
puts("");
//printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
最新文章
- shared_ptr
- CreateFile() 打开u盘 物理设备
- Java面试笔记
- shopex最新版前台一处想不到的SQL注入漏洞
- Node.js中的模块化
- Matlab中find函数的使用
- (5)Quartz学习
- <;audio>; 标签简介
- SQL Server 改变数据库的名字
- java学习之异常笔记
- python 命名规范
- java 多线程 一个博客
- Head First设计模式之生成器模式
- [ZJOI2008]骑士
- Flask 扩展 表单
- [POJ 3728]The merchant
- OSGi简介
- 这篇说的是Unity Input 输入控制器
- Java常考面试题(三)
- vs2015上使用github进行版本控制
热门文章
- bzoj3505 [Cqoi2014]数三角形——组合数+容斥
- python - 解决 ModuleNotFoundError: No module named &#39;pip&#39;
- python 学习笔记一 (数据结构和算法)
- 记Spring下autowire为name时的一个现象
- SAS学习笔记之《SAS编程与数据挖掘商业案例》(1)系统简介和编程基础
- 模拟测试—moq:简单一两句
- 重现apache commons fileupload DOS漏洞
- JS高级——沙箱
- GitHub代码托管平台搭建
- .net 程序集加载,版本不匹配的解决方法