hdu2848（博弈）

两个人轮流切割一个数字n，要求将数字切割成k份，第二个人切割的数字是第一个人切割完后各个片段的求和，不能切割者输

len(n) < 19，k<len(n)

做法是枚举第一个人的切法，寻找是否有一种切法使得第二个人怎么切都输

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
ll n, k, base[25];

void init() {
    base[0] = 1;
    for (int i = 1; i < 20; i++)
        base[i] = base[i-1] * 10;
}

bool dfs2(ll , ll, ll, ll);

bool dfs1(ll num, ll len) {
    ll tmp = num, k = 0;
    while (tmp > 0) {k++; tmp /= 10;}
    if (k < len) return false;
    return dfs2(num, len, 1, 0);
}

bool dfs2(ll num, ll len, ll now, ll sum) {
    if (len == now) return !dfs1(sum+num, len);//轮流交替，因为只要有一种切法能赢dfs2就会返回true，!dfs1就表示第二个人
    for (int i = 1; i < 20; i++) {              //无论怎么切都会输
        ll a = num % base[i];
        ll b = num / base[i];
        if (b == 0) break;
        if (dfs2(b, len, now+1, sum+a)) return true;
    }
    return false;
}

int main() {
    init();
    while (scanf("%lld%lld",&n, &k) != EOF) {
        printf("%d\n", dfs1(n, k));
    }
    return 0;
}