当前位置: 代码迷 >> 综合 >> Gym 102152 problem D XOR Permutations
  详细解决方案

Gym 102152 problem D XOR Permutations

热度:2   发布时间:2023-12-22 13:54:05.0

题目入口
题意:给你三个10位的二进制数,试问将三个数列按照一定排序后的XOR结果最大值是多少(依旧以二进制数表达)。
在这里插入图片描述
思路:刚开始想得很简单,觉得可以直接两两异或得到max答案便可。多次失败后才知道,原来还是必须三个数同时考虑,需先经量多得考虑1 1 0得情况,再求得剩下的1 1 1情况,所得的数量就是答案中1得个数,贪心一下就好。
代码实现:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#define int long long
#define lowbit(x) (x &(-x))
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {
    {
    1, 0}, {
    -1, 0}, {
    0, 1}, {
    0, -1}};
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int  INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double EXP = 1e-8;
const ll   MOD = 1e9 + 7;
const int  N = 2e6 + 5;
int t;
int n[5];
signed main()
{
    IOS;cin >> t;while(t --){
    me(n);int sum = 0;for(int i = 0; i < 3; i ++){
    string s;cin >> s;for(int j = 0; j < 10; j ++)if(s[j] == '1') n[i] ++;sum += n[i];}if(sum <= 10){
    for(int i = 0; i < sum; i ++)cout << 1;for(int i = 0; i < 10 - sum; i ++)cout << 0;cout << endl;continue;}sort(n, n + 3);while(n[0] && sum > 10){
    n[0] --;n[1] --;sum -= 2;}if(sum <= 10){
    for(int i = 0; i < sum; i ++)cout << 1;for(int i = 0; i < 10 - sum; i ++)cout << 0;cout << endl;}else{
    for(int i = 0; i < 20 - sum; i ++)cout << 1;for(int i = 0; i < sum - 10; i ++)cout << 0;cout << endl;}}return 0;
}
  相关解决方案