本解题报告非本人原创,程序为本人原创。转载请注明出处并保留本注释。
题目描述
Polygons
两个做游戏的人在玩一种多边形游戏。一个有n个顶点的凸多边形需要由
n-3条对角线划分成n-2个三角形。这些对角线只会相交在顶点。划分后的三角形中有一个是黑色的,其余的都是白色。两个选手轮流取,每一个选手每一次要从多边形中切下一个三角形。每个选手只允许沿着一条对角线切下一个三角形。切下黑色三角形的选手获得比赛的胜利。
注意:我们称一个多边形是凸多边形当且仅当任意两个顶点的连线都被包含在多边形的内部。

任务:编写程序,
1、从文本文件gra.in中读入关于凸多边形的描述。
2、判断是否先取的选手有一种必胜的策略。
3、将结果写入文件gra.out。

输入:
输入文件gra.in的第一行包含一个整数n,4 <= n <= 50000,表示多边形的顶点数。顶点按顺时针编号为0至n-1。
以下的n-2行描述该多变形划分成的三角形。第i+1行(1≤i≤n-2)包含三个非负整数,表示第i个三角形的三个顶点的编号。第一个描述的三角形是黑色的。

输出:
输出文件gra.out包含一个单词:
‘TAK’(在波兰文中表示“是”),如果先走的选手有必胜策略。
‘NIE’(在波兰文中表示“否”),如果先走的选手没有必胜策略。

样例输入:
6
0 1 2
2 4 3
4 2 0
0 5 4

样例输出:
TAK

《Polygons》解题报告
一、分析。
为了描述方便,我们用三角形的三个顶点的编号来表示三角形,如下图中的黑色三角形为(1,3,6)。
在 下图中,要切下黑色三角形(1,3,6),就必须切下三角形集合{(0,1,6)},{(1,2,3)},{(3,5,6),(3,4,5)}中的两个。 同样,对于任何一个凸多边形,要切下黑色三角形都必须切下三个三角形集合中的两个。切下一个三角形集合所需的步数是一定的,而与切的顺序无关,所以对于任 何一个三角形集合中我们只需考虑集合中三角形的个数而不必考虑分别是哪几个三角形。
设三个三角形集合的元素个数分别为a,b,c。下面的问题就是如何从状态(a,b,c)判断是否有必胜状态。
先分析必胜状态,首先(0,0,1)一定是必胜状态。若初始状态不是(0,0,n)则状态(0,0,c),c>1,实际是不可能出现的。
证明:(1)、状态(0,0,n)不存在。
(2)、若(0,0,c)n>=c>=2不存在,由于(0,0,c-1)只能从(0,0,c)和(0,1,c-1)中得到。
状态(0,0,c)不存在,而从(0,1,c-1)出发可以得到比(0,0,c-1)更优的(0,1,c-2),所以不可能选择(0,0,c-1)。 因此,若状态(0,0,(0,0,c-1)也不存在。
所以(0,0,c),c>1不存在,则(0,0,c-1)也是不存在的。
∴ 若初始状态不是(0,0,n),则不可能出现(0,0,c),c>1。因此必胜状态只有一个(0,0,1)。
接 着,分析状态(a,b,c),a≠0,令s=a+b+c,称s为奇数的状态为奇状态,s为偶数的状态为偶状态。由于每一步只能将a,b,c中的一个数减 1,所以每一步都使s减1,也就是每一步都要改变s的奇偶性。由于必胜状态是奇状态,所以如果初始状态(不是(0,0,n))是奇状态,则要经过偶数步才 能到达必胜状态,如果初始状态是偶状态,则需要经过奇数步才能到达必胜状态。所以如果初始状态是奇状态,则先走的人有必胜策略,否则无必胜策略。
由此,我们得出了一个判断是否有必胜策略的简单办法,设初始状态是(a,b,c)(a>=b>=c) 则若((a=0) and (b=0)) or odd(a+b+c)则有必胜策略,否则没有。
二、实现。
根据读入的黑色三角形三个顶点s1,s2,s3求出初始状态,先将三个顶点排序,使s1>s2>s3,则a=s2-s1-1,b=s3-s2-1,c=n-s3+s1-1。即得到初始状态。

Ceeji 提醒:本题需要注意的是,如何判断一个三角形属于题解中说的a,b,还是c。由于数据较弱本人采用了遍历,但实际上还可优化。a,b,c分别存储的是黑三 角形三侧的三角形的数量。显然这些三角形之间至少有一个公共边。优化就在于一个公共边无须穷举,因为最多有两个三角形用一个公共边。但当然最好是直接用题 解中的方法。

Ceeji的完整代码

 
//By Ceeji 
//Date: 2009-4-9 
//Type: Boyi 
//HAOI test 2 - Problem 1: (POI) GRA 
//State: Accepted 
Program gra; 
Const 
   inf='gra.in'; 
   ouf='gra.out'; 
   maxn=50000Var 
   n,ia,ib,ic,a,b,c,n1,n2,n3:longint; 
   e:array[0..maxn,1..4]of longint; 
   bl:array[0..maxn,0..maxn]of booleanProcedure blp(a,b:longintvar c:longint); 
var i:longintbegin 
   if bl[a,b] then exit; 
   bl[a,b]:=true; 
   bl[b,a]:=true; 
   for i:=1 to n-3 do 
   begin 
      if (e[i,4]=0)and(((e[i,1]=a)and(e[i,2]=b))or((e[i,2]=a)and(e[i,3]=b))or((e[i,1]=a)and(e[i,3]=b))or((e[i,1]=b)and(e[i,2]=a))or((e[i,2]=b)and(e[i,3]=a))or((e[i,1]=b)and(e[i,3]=a))) then 
      begin 
         e[i,4]:=1; 
         inc(c); 
         blp(e[i,1],e[i,2],c); 
         blp(e[i,2],e[i,3],c); 
         blp(e[i,1],e[i,3],c); 
      end; 
   endendProcedure init; 
var i:longintbegin 
   assign(input,inf);  reset(input); 
   assign(output,ouf); rewrite(output); 
   readln(n); 
   readln(ia,ib,ic); 
   fillchar(e,sizeof(e),0); 
   n1:=0; n2:=0; n3:=0; 
   for i:=1 to n-3 do 
   begin 
      readln(e[i,1],e[i,2],e[i,3]); 
      e[i,4]:=0; 
   end; 
   fillchar(bl,sizeof(bl),0); 
endbegin 
   init; 
   close(input); 
   blp(ia,ib,n1); 
   blp(ia,ic,n2); 
   blp(ib,ic,n3); 
   if odd(n1+n2+n3) then writeln('TAK'else writeln('NIE'); 
   close(output); 
end.