首页 > ACM题库 > HDU-杭电 > HDU 4664-Triangulation-博弈论-[解题报告]HOJ
2015
09-17

HDU 4664-Triangulation-博弈论-[解题报告]HOJ

Triangulation

问题描述 :

There are n points in a plane, and they form a convex set.

No, you are wrong. This is not a computational geometry problem.

Carol and Dave are playing a game with this points. (Why not Alice and Bob? Well, perhaps they are bored. ) Starting from no edges, the two players play in turn by drawing one edge in each move. Carol plays first. An edge means a line segment connecting two different points. The edges they draw cannot have common points.

To make this problem a bit easier for some of you, they are simutaneously playing on N planes. In each turn, the player select a plane and makes move in it. If a player cannot move in any of the planes, s/he loses.

Given N and all n’s, determine which player will win.

输入:

First line, number of test cases, T.
Following are 2*T lines. For every two lines, the first line is N; the second line contains N numbers, n1, …, nN.

Sum of all N <= 106.
1<=ni<=109.

输出:

First line, number of test cases, T.
Following are 2*T lines. For every two lines, the first line is N; the second line contains N numbers, n1, …, nN.

Sum of all N <= 106.
1<=ni<=109.

样例输入:

2
1
2
2
2 2

样例输出:

Carol
Dave

一个平面上有n个点(一个凸多边形的顶点),每次可以连接一个平面上的两个点(不能和已经连接的边相交),如果平面上已经出现了一个三角形,则不能在这个平面上继续连接边了。

现在总共有N个平面,每个平面上都有若干点。(就是有N个相同的游戏同时进行了)。


想法很单纯,就是计算出每一个平面上游戏的sg函数值,然后求Nim和就哦了。

sg函数暴力求法:

一个平面上连接点时,不能连接已经有边的顶点,因为对方只需要再连接一次就可以组成一个三角形了。又所有的边不能相交,因此每连接一条边,就相当于把整个平面上的点划分成了两个部分,在接下来的游戏中,只能单独在两部分里面进行,相当于将一个游戏划分成了两个游戏。因此当前状态x的sg函数值就是两个子游戏的Nim和了。

即:sg(x) = mex{ sg(i)^sg(x-i-2) }


这样复杂度很高。但是这道题目有规律,在大数据的范围下,会出现循环,循环长度为34,因此只需要小数据暴力,大数据打表就哦了。


#include <cstdio>
#include <cstring>
typedef long long ll;
#define N 1002
bool vis[N];
int sg[N];
int a[] = {4,8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7};
int SG(int x) {
    if (sg[x] != -1) return sg[x];
    if (x == 0) return 0;
    if (x == 1) return 0;
    if (x == 2) return 1;
    if (x == 3) return 1;
    memset(vis, false, sizeof(vis));
    for (int i=0; i<x-1; i++) vis[SG(i)^SG(x-i-2)] = true;
    for (int i=0; ;i++) if (!vis[i]) return i;
}
int get_sg(int x) {
    if (x <= 100) return sg[x];
    return a[x%34];
}
int main() {
    memset(sg, -1, sizeof(sg));
    for (int i=0; i<=100; i++) sg[i] = SG(i);

    int T, n, x; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int ans = 0;
        while (n--) { scanf("%d", &x); ans ^= get_sg(x); }
        puts(ans ? "Carol" : "Dave");
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/yang_7_46/article/details/9864301