询问各位大神这题该如何解

思路：递归

确实是好题。

有时间的楼友帮我检查一下后面的情况。

匿名提问者,AC了。

AC (148ms, 732KB)
记忆体使用: 732 KB
程式码长度: 3797 Bytes
执行档大小: 11903 Bytes

修改之后的版本虽然比原来难读懂，但是效率高多了。
原来PerformanceTest()3分钟，现在2秒多钟。

#include

using namespace std;

int adj[13] = {
4+8, // c0: c2, c3
4+32, // c1: c2, c5
2+8+32+64, // c2: c1, c3, c5, c6
4+16+64+128, // c3: c2, c4, c6, c7
8+128, // c4: c3, c7
2+4+64+256+512, // c5: c1, c2, c6, c8, c9
4+8+32+128+512+1024, // c6: c2, c3, c5, c7, c9, c10
8+16+64+1024+2048, // c7: c3, c4, c6, c10, c11
32+512, // c8: c5, c9
32+64+256+1024+4096, // c9: c5, c6 c8 c10 c12
64+128+512+2048+4096, //c10: c6, c7, c9, c11, c12
128+1024, //c11: c7, c10
512+1024 //c12: c9, c10
};

class HexagramChess
{
public:
HexagramChess():states(0){}
HexagramChess(int s):states(s){}

// return 1=if first player has advantage to win; 0=second player has
bool Analyze() const;

inline const HexagramChess& operator=(HexagramChess& hgc)
{states = hgc.states; return *this;}

inline const HexagramChess& operator=(int s)
{states = s; return *this;}

public:
// static void SelfTest();
// static void PerformanceTest();

private:
int CircleCount() const;

// n=[0,12]
// Returns 1=circled(occupied),0=removed(empty)
inline bool GetState(int n) const;
inline bool GetState(int s, int n) const;

// n=[0,12]
// Returns an array of cells' indexes
bool IsAdjacents(int index, int n) const;

void Remove(int n);

private: // data
// 32 bits enough for 2^13
unsigned int states;
};

void HexagramChess::Remove(int n)
{
//assert(GetState(n));
int bit=~(0x01 << n);
states &= bit;
}

int HexagramChess::CircleCount() const
{
unsigned int s(states);
int count(0);
while(s)
{
if(s & 1) count++;
s = s >>1;
}
return count;
}

inline bool HexagramChess::GetState(int n) const
{
return (0!=(states & 0x01 << n));
}

inline bool HexagramChess::GetState(int s, int n) const
{
return (0!=(s & 0x01 << n));
}

bool HexagramChess::IsAdjacents(int index, int n) const
{
return (GetState(adj[n],index) && GetState(index));
}

// returns the number of moves
bool HexagramChess::Analyze() const
{
const unsigned int circleCount(CircleCount());

if(circleCount==2)
return true;
else if(circleCount==1)
return false;

// Do analysis for each circle
for(unsigned int cir(0); cir<13;cir++)
{
//the chosen circle index
if(GetState(cir))
{
// single move
HexagramChess backup = *this;
backup.Remove(cir);
if( !backup.Analyze() ) // next not wins, this move is good for me!
{
return true;
}

// double move
for(unsigned i(0);i<13;i++)
{
if(backup.IsAdjacents(i, cir))
{
if(i < cir) // Don't double check
continue; // for i:adj

HexagramChess backup2 = backup;
backup2.Remove(i);
if( !backup2.Analyze() ) // next not wins, this move is good for me!
{
return true;
}
}
}
}
}
return false;
}

int main()
{
HexagramChess* games = NULL;

//输入整数n
int n(1);
int count(0);
while(n)
{
cin >> n;
if(!n)break;

if( games)
delete [] games;

games = new HexagramChess[n];

for(int i(0);i {
int s(0);
cin >> s;
games[i] = s;
}
for(int i(0);i {
cout << games[i].Analyze() <<" ";
}
cout <
if(count++>2)break;
}
return 0;
}

/*

#include
void HexagramChess::PerformanceTest()
{
const int BITS = 8191;//2^12-1

double diff(0);
clock_t start = clock();

int bits(0);
int res(0);
for(;bits {
res =HexagramChess(bits).Analyze();
if( bits%400 == 0)
{
diff = (clock()-start)/ (double)CLOCKS_PER_SEC;

cout << diff<<"\t"< }
}
diff = (clock()-start)/ (double)CLOCKS_PER_SEC;
cout << diff<<"\t"<}

void HexagramChess::SelfTest()
{
bool testResult(true);

//【1】一环
//缺心眼才玩 => 0
HexagramChess hgc1(1); //0
cout <<"【1】\t"<< hgc1.Analyze() << endl;

testResult &= (hgc1.Analyze()==0);

//【2】两环
//总是有利于先手 => 1
HexagramChess hgc2_1(12); //2,3 相邻2-3
cout <<"【2】\t" << hgc2_1.Analyze() << endl;

testResult &= (hgc2_1.Analyze()==1);

// 总是有利于先手 => 1
HexagramChess hgc2_2(12); //2,4
cout <<"【2】\t" << hgc2_2.Analyze() << endl;

testResult &= (hgc2_2.Analyze()==1);

//三环
//【3.1】如果有相邻环，先手有利 => 1
HexagramChess hgc3_1(1664); //7,9,10 相邻7-10-9
cout <<"【3.1】\t"<< hgc3_1.Analyze() << endl;

testResult &= (hgc3_1.Analyze()==1);

//【3.2】如果无相邻环，后手有利 => 0
HexagramChess hgc3_2(8+32+2048); //3,5,11
cout <<"【3.2】\t"<< hgc3_2.Analyze() << endl;

testResult &= (hgc3_2.Analyze()==0);

//如果无相邻环，后手有利 => 0
HexagramChess hgc3_3(8+32+1024); //3,5,10
cout <<"【3.2】\t"<< hgc3_3.Analyze() << endl;

testResult &= (hgc3_3.Analyze()==0);

//四环
//【4.1】四个不相邻，化归成【3.2】，先手有利 => 1
HexagramChess hgc4_1(1+2+64+16); //0,1,6,4
cout <<"【4.1】\t"<< hgc4_1.Analyze() << endl;

testResult &= (hgc4_1.Analyze()==1);

//【4.2】三角环+一相邻，无法化归成三环和二环里面的后手有利情况，后手有利 => 0
HexagramChess hgc4_2(1+4+8+128); //0,2,3,7
cout <<"【4.2】\t"<< hgc4_2.Analyze() << endl;

testResult &= (hgc4_2.Analyze()==0);

//【4.3】链式，无法化归成三环和二环里面的后手有利情况，后手有利 => 0
HexagramChess hgc4_3(2+4+8+16); //1,2,3,4
cout <<"【4.3】\t"<< hgc4_3.Analyze() << endl;

testResult &= (hgc4_3.Analyze()==0);

//【4.4】一相邻+二单，取相邻其一，化归成【3.2】先手有利 => 1
HexagramChess hgc4_4(1+4+16+512); //0,2,4,9
cout <<"【4.4】\t"<< hgc4_4.Analyze() << endl;

testResult &= (hgc4_4.Analyze()==1);

//五环
//【5.1】都相邻（同一个世界），取短底上其一，化归成【4.2】，先手有利 => 1
HexagramChess hgc5_1(2+4+8+32+64); //1,2,3,5,6
cout <<"【5.1】\t"<< hgc5_1.Analyze() << endl;
testResult &= (hgc5_1.Analyze()==1);

//【5.2】链式，取两头其一，化归成【4.3】，先手有利 => 1
HexagramChess hgc5_2(2+32+64+128+16); //1，5，6，7，4
cout <<"【5.2】\t"<< hgc5_2.Analyze() << endl;
testResult &= (hgc5_2.Analyze()==1);

//【5.3】A字形，取A字一横的两个，化归成【3.2】，先手有利 => 1
HexagramChess hgc5_3(2+4+8+32+128); //1,2,3,5,7
cout <<"【5.3】\t"<< hgc5_3.Analyze() << endl;
testResult &= (hgc5_3.Analyze()==1);

//【5.4】五不邻，只能变成【4.1】，后手有利 => 0
HexagramChess hgc5_4(2+16+64+256+2048); //1,4,6,8,11
cout <<"【5.4】\t"<< hgc5_4.Analyze() << endl;
testResult &= (hgc5_4.Analyze()==0);

//【5.5】四邻+1（斧形），化归为【4.3】先手有利 => 1
HexagramChess hgc5_5(1+4+8+64+512); //0,2,3,6,9
cout <<"【5.5】\t"<< hgc5_5.Analyze() << endl;
testResult &= (hgc5_5.Analyze()==1);

//【5.6】四邻+1（伞形），取伞柄中上两环，化归为【3.2】，先手有利 => 1
HexagramChess hgc5_6(2+4+32+64+256); //1,2,5,6,8
cout <<"【5.6】\t"<< hgc5_6.Analyze() << endl;
testResult &= (hgc5_6.Analyze()==1);

//六环
//【6.1】都相邻-- 环状，取走两个化归为【4.3】，先手有利 => 1
HexagramChess hgc6_1(2+8+128+1024+512+32); //2,3,7,10,9,5
cout <<"【6.1】\t"<< hgc6_1.Analyze() << endl;
testResult &= (hgc6_1.Analyze()==1);

//【6.2】都不相邻，只能转化为【5.4】，先手有利 => 1
HexagramChess hgc6_2(1+2+256+4096+2048+16); //0,1,8,12,11,4
cout <<"【6.2】\t"<< hgc6_2.Analyze() << endl;
testResult &= (hgc6_2.Analyze()==1);

//【6.3】链式，取走两个化归为【4.3】，先手有利 => 1
HexagramChess hgc6_3(2+4+8+128+1024+4096); //1,2,3,7,10,12
cout <<"【6.3】\t"<< hgc6_3.Analyze() << endl;
testResult &= (hgc6_3.Analyze()==1);

cout <<"测试结果\t"<< testResult << endl;
}

*/

貌似akyeren的回答是特殊化了，没有自己输入啊

好学之人啊，继续努力！！！

有些难理解...

太简单了，我不会

不会