时间戳

首页 > 解决方案 > 我们缺少 n>2 的一些条件，有人可以帮助找到我们的代码缺少的特殊情况吗？

c++ - 我们缺少 n>2 的一些条件，有人可以帮助找到我们的代码缺少的特殊情况吗？

问题描述

问题陈述：

给定一个序列 A1、A2、...、AN，您必须执行以下操作正好 X 次：

找到可以通过恰好执行此操作 X 次获得的字典最小序列。

问题的副本可以是https://www.codechef.com/DEC20B/problems/HXOR

方法：

在这里，我们正在处理 X 次操作的 N 个整数，我们正在对数组中的所有整数执行 xor 函数，具有 2 个元素的幂 (2^p)，p 表示非 -ve 整数。

为了找到字典上最小的序列，我们对每个元素进行异或，直到它变得最小，然后我们转移到下一个元素。同时，我们还存储了前面步骤中使用的元素来进行配对。

测试用例：

输入：

4 3

2 2 3 3

输出：

0 0 0 0

#include <bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define ll long long

#define pb push_back


ll bs(vector<ll> check, ll key){
    ll n = check.size();
    for(ll i=0; i<n; i++)
    {
        if(check[i]==key)
        {
            return i;
        }
    }

    return -1;
}

ll highestPowerof2(ll n)
{
   ll p = (ll)log2(n);
   return (ll)pow(2, p);
}

void smallestSequence()
{
    ll t;
    cin >> t;
    while(t--)
    {
        ll n,x;
        cin >> n >> x;
        ll a[n];
        for(ll i=0;i<n;i++)
        {
            cin >> a[i];
        }

        if(n==2)
        {
            for(int i=1; i<n; i++)
            {
                a[i]^=a[0];
            }
            a[0]=0;

            if(x%2==0)
            {
                a[0]^=1;
                for(int i=1; i<n; i++)
                {
                    a[i]^=1;
                }   
            }
            
            for(ll i=0;i<n;i++)
            {
                cout << a[i] <<" ";
            }
            cout << endl;
            continue;
        }
        ll temp = x;
        x = 2*x;

        vector <ll> check;
        ll i;
        ll flag=0;
        for(i=0;i<n;i++)
        {
            ll p=1;
            while(a[i]!=0 && x>0)
            {
                if(bs(check, highestPowerof2(a[i]))>=0)
                {
                    check.erase(check.begin()+ bs(check, highestPowerof2(a[i])));
                }
                else{
                    if(temp>0)
                    {
                        check.pb(highestPowerof2(a[i]));
                        temp--;
                    }else {
                        ll j = 0;
                        ll si = check.size();
                        for(j=0; j<si; j++)
                        {
                            ll res = check[j]^a[i];
                            if(res<=a[i])
                            {
                                a[i]^=check[j];
                                x--;
                                check.erase(check.begin()+j);
                                j--;
                                si--;
                            }
                        }
                        break;
                    }
                }
                a[i]^=highestPowerof2(a[i]);
                x--;
            }

            if(a[i]!=0)
            {
                flag=1;
            }
        }
        
        // if(flag==0 && temp>0 && (temp*2)==x)
        // {
        //  if(temp%2==1)
        //  {
        //      a[n-1]=a[n-2]=1;
        //  }
        // }

        while(x>=0 && !check.empty())
        {
            a[i-1]^=check[0];
            check.erase(check.begin());
        }

        for(ll i=0;i<n;i++)
        {
            cout << a[i] <<" ";
        }
        cout << endl;
    }
}


int main()
{
    fast;

    smallestSequence();

    return 0;
}

建议将不胜感激！我已经为这个问题尝试了将近 5 天，我不想要一个解决方案，我只想知道我的代码提供 WA 的一些特殊 TC。

标签： c++bit-manipulationxorlexicographicbitwise-xor

解决方案

这是一场持续的比赛。所以这是我能帮助你的最好的。

输入：

1
4 4
1 2 3 4

你的输出：

0 0 0 4

正确的输出：

0 0 1 5

推荐阅读