Xor和动态编程 [英] Xor and dynamic programming

问题描述

这个问题在竞赛中被提出。我正在提供问题的链接。

编程问题和竞争:: HackerRank [ ^ ]



问题主要是使用博弈论和动态编程的概念。



我的尝试：



我知道赢得我们需要做的nim游戏的条件。所以我可以破译逻辑，但主要的问题是找出范围，我只能想到蛮力方法。然后我阅读了社论，他们使用动态编程来查找范围。我无法理解相应的实现。你可以帮忙吗。

我正在粘贴描述和代码。

如果爱丽丝被允许做出特别的举动，那么她赢了，当且仅当鲍勃失去了随后在爱丽丝没有移除的堆上玩的Nim游戏。

现在，因为它已经知道并且可以在不费力的情况下证明当前玩家在Nim中有一个获胜位置，当且仅当桩的大小不等于0时，Alice才会获胜，当且仅当她在她的特殊动作中移除桩时，其剩余桩的大小为XOR。 />
如果是所有桩的大小，那么Alice会胜出，当且仅当她以这样的方式移除连续范围的桩时，xor b xor c .. = 0。

计算此类范围数量的直接方法只是计算前缀和后缀xor-sums，然后迭代所有可能的范围，以检查删除这样的范围是否留下具有大小等于的XOR的桩。使用前缀和后缀xor-sums，可以在O（1）时间内执行单个此类检查。但是，这种方法具有总时间复杂度，因为要检查的是二次数范围。

它们现在使用计数数组来跟踪范围。他们首先修复范围的左端。我们想要的是l之前和之后的数字x（范围的右端）= 0.



这是代码。

 #include< iostream> 
 #include< cstdio> 
 #include< string> 
 #include< sstream> 
 #include< vector> 
 #include< set> 
 #include< map> 
 #include< queue> 
 #include< stack> 
 #include< cmath> 
 #include< algorithm> 
 #include< cstring> 
 #include< ctime> 
 #include< cassert> 
 #include< unordered_map> 
 using namespace std; 
 
 #define pb push_back 
 #define fi first 
 #define se second 
 #define REP（i，a，b）for（int（i）=（ a）;（i）< =（b）; ++ i）
 #define REPD（i，a，b）for（int（i）=（a）;（i）> =（b ）;  -  i）
 
 
 typedef long long ll; 
 const int INF = 1e9; 
 
 const int N = 5e5; 
 const int V = 1e5; 
 
 int a [N + 1]; 
 int pref [N + 1]; 
 
 int main（）
 {
 int n; 
 scanf（％d，& n）; 
断言（n> = 1&& n< = N）; 
 REP（i，1，n）{
 scanf（％d，& a [i]）; 
断言（a [i]> = 1&& a [i]< = V）; 
} 
 pref [1] = a [1]; 
 REP（i，2，n）{
 pref [i] = pref [i-1] ^ a [i]; 
} 
 
 ll res = 0; 
 
 unordered_map< int，int> CNT; 
 REP（i，0，n-1）{
 if（cnt.find（pref [i]）== cnt.end（））{
 cnt [pref [i]] = 1; 
} else {
 cnt [pref [i]] ++; 
} 
} 
 int cur = 0; 
 REPD（i，n-1,0）{
 auto it = cnt.find（cur）; 
 if（it！= cnt.end（））{
 res + = it-> se; 
} 
 it = cnt.find（pref [i]）; 
 if（it！= cnt.end（））{
 if（it-> se> 1）{
 it-> se--; 
} else {
 cnt.erase（it）; 
} 
} 
 cur ^ = a [i + 1]; 
} 
 printf（％lld \ n，res）; 
 
返回0; 
} 

解决方案

什么时候可以赢得Nim游戏？当移动后的Num数为0.

因此，请考虑该上下文中的第一步（特殊移动）...

计算所有可能的移除选项。对于所有这些计算移除后的Nim数。给出0的所有内容对你都有好处...



（如果不是这个问题，唯一的答案就是删除所有并获胜...）

This question was asked in a contest.I am providing the link to question.
Programming Problems and Competitions :: HackerRank[^]

The problem mainly uses concept of game theory and dynamic programming.

What I have tried:

I know the condition to win the nim game that we need to do.So I could decipher the logic but the main problem was to find out the ranges and I could only think of the brute force method. Then I read the editorial and they used dynamic programming to find the ranges. I could not understand the corresponding implementation. Can you please help.
I am pasting both the description as well as the code.
If Alice is allowed to make her special move, then she wins if and only if Bob loses the subsequent Nim game played on piles Alice hasn't removed.

Now, since it's known and can be also proven without much effort that the current player has a winning position in Nim if and only if XOR of sizes of piles is different than 0, Alice wins if and only if she removes piles in her special move in such a way that the XOR of sizes of remaining piles is .
It follows that if are sizes of all piles, then Alice wins if and only if she removes a continuous range of piles in such a way that a xor b xor c..=0 .
A direct approach to count the number of such ranges is just by computing prefix and suffix xor-sums of piles and then iterate over all possible ranges to check if removing such a range leaves piles with XOR of its sizes equal to . Using prefix and suffix xor-sums one can perform a single such check in O(1)time. However, this approach has total time complexity since there are quadratic number of ranges to check.
They use a count array now to keep track of the ranges. They first fix the left end of range. What we want is xor of numbers before l and after r(the right end of range) =0.

Here is the code.

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
#include <unordered_map>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)


typedef long long ll;
const int INF = 1e9;

const int N = 5e5;
const int V = 1e5;

int a[N+1];
int pref[N+1];

int main()
{
    int n;
    scanf("%d", &n);
    assert(n >= 1 && n <= N);
    REP(i, 1, n) {
        scanf("%d", &a[i]);
        assert(a[i] >= 1 && a[i] <= V);
    }
    pref[1] = a[1];
    REP(i, 2, n) {
        pref[i] = pref[i-1] ^ a[i];
    }

    ll res = 0;

    unordered_map<int, int> cnt;
    REP(i, 0, n-1) {
        if (cnt.find(pref[i]) == cnt.end()) {
            cnt[pref[i]] = 1;
        } else {
            cnt[pref[i]]++;
        }
    }
    int cur = 0;
    REPD(i, n-1, 0) {
        auto it = cnt.find(cur);
        if (it != cnt.end()) {
            res += it->se;
        }
        it = cnt.find(pref[i]);
        if (it != cnt.end()) {
            if (it->se > 1) {
                it->se--;
            } else {
                cnt.erase(it);
            }
        }
        cur ^= a[i+1];
    }
    printf("%lld\n", res);

    return 0;
}

解决方案

When one can win a Nim game? When the Num number after ones move is 0.
So think of the first move (the special move) in that context...
Compute all the possible remove options. For all these compute the Nim number AFTER the remove. All that gives 0 are good for you...

(If it wasn't for this question the one and only answer is to remove all and win...)

这篇关于Xor和动态编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！