首页 > 代码库 > CodeForces 778B - Bitwise Formula

CodeForces 778B - Bitwise Formula

2024-09-06 23:39:24   217人阅读

题意：

　　选择一个 m 位的二进制数字，总分为 n 个算式的答案之和。问得到最低分和最高分分别应该取哪个二进制数字

分析：

　　因为所有数字都是m位的，因为高位的权重大于地位 ，我们就从高到低考虑 ans 的每一位是取 0 还是取 1，统计该位的权重（即n个式子该位结果之和）即可。

 

 1 #include <bits/stdc++.h> 2 using namespace std; 3 int n, m; 4 map<string, int> mp; 5 struct query{ 6     string f; 7     int num; 8     int a, op, b; 9 }q[5005];10 void init()11 {12     cin >> n >> m;13     string s;14     mp["?"] = 0;15     for (int i = 1;  i <= n; i++)16     {17         cin >> s;18         mp[s] = i;19         cin >> s; 20         cin >> s;21         if (s[0] >= ‘0‘ && s[0] <= ‘9‘)22         {23              q[i].op = 0;24              q[i].f = s;25         } 26         else27         {28             q[i].a = mp[s];29             cin >> s;30             if (s[0] == ‘A‘) q[i].op = 1;31             if (s[0] == ‘O‘) q[i].op = 2;32             if (s[0] == ‘X‘) q[i].op = 3;33             cin >> s;34             q[i].b = mp[s];35         }36     }37 }38 int find(int x, int p)39 {40     int ret = 0;41     q[0].num = p;42     for (int i = 1; i <= n; i++)43     {44         if (q[i].op == 0) q[i].num = q[i].f[x]-‘0‘;45         else46         {47             int a = q[q[i].a].num;48             int b = q[q[i].b].num;49             if (q[i].op == 1) q[i].num = a&b;50             if (q[i].op == 2) q[i].num = a|b;51             if (q[i].op == 3) q[i].num = a^b;52         }53         ret += q[i].num;54     }55     return ret;56 }57 void solve()58 {59     string ans1, ans2;60     for (int i = 0; i < m; i++)61     {62         int x0 = find(i, 0);63         int x1 = find(i, 1);64         x0 <= x1 ? ans1 += ‘0‘ : ans1 += ‘1‘;65         x0 >= x1 ? ans2 += ‘0‘ : ans2 += ‘1‘;66     }67     cout << ans1 << endl << ans2 << endl;68 }69 int main()70 {71     init();72     solve();73 }

 

CodeForces 778B - Bitwise Formula


联系
我们