#include<iostream>
#include<string>
#include<vector>
#include <algorithm>
using namespace std;

#define NC 9

vector<string>vc = { "黄色","绿色","翠绿","青色","蓝色","紫色","棕色","橙色","红色" };
vector<vector<int>>vm; //试管
vector<double>score(NC); //各色被压制程度
int avail[NC]; //各色出现次数

void OutMap()
{
	for (int i=0;i<vc.size();i++)
	{
		cout << i << " "<<vc[i]<<"   ";
	}
}

void Input()
{
	int a;
	cout << "\n输入负载试管数目";
	cin >> a;
	vm.resize(a);
	cout << "输入试管容量  ";
	cin >> a;
	for (auto &vi : vm) {
		vi.resize(a);
	}
	cout << "依次输入各试管内颜色，从上往下\n";
	for (auto &vi:vm) {
		for (int j = a - 1; j >= 0; j--)cin >> vi[j], avail[vi[j]]++;
	}
}

bool Check()
{
	int a = vm[0].size();
	for (int i = 0; i < NC; i++)if (avail[i] != 0 && avail[i] != a)return false;
	return true;
}

void Init()
{
	OutMap();
	do {
		Input();
	} while (!Check());
}

void InitScore()
{
	for (double & si : score)si = 0;
	for (auto vi : vm) {
		for (int j = 0; j < vi.size(); j++) {
			score[vi[j]] += vi.size() - j;
		}
	}
}

void PageRank()
{
	vector<double>newScore(NC);
	for (auto vi : vm) {
		double s = 0;
		for (int j = vi.size() - 1; j >= 0; j--) {
			newScore[vi[j]] += s, s += score[vi[j]];
		}
	}
	score = newScore;
}

template<typename T>
vector<int> sortId(vector<T>v);

void GetScore()
{
	vector<int>id = sortId(score);
	for (auto i : id) {
		if(avail[i])cout << vc[i] << " ";
	}
	cout << endl;
}

int main()
{
	Init();
	InitScore();
	GetScore();
	for (int i = 0; i < 5; i++) {
		PageRank();
		GetScore();
	}
	return 0;
}

输出：

紫色 绿色 蓝色 翠绿 黄色 红色 棕色
紫色 蓝色 绿色 翠绿 黄色 红色 棕色
紫色 蓝色 绿色 黄色 翠绿 红色 棕色
紫色 蓝色 绿色 黄色 翠绿 红色 棕色
紫色 蓝色 绿色 黄色 翠绿 红色 棕色
紫色 蓝色 绿色 黄色 翠绿 红色 棕色

所以这一关的两个关键颜色就是紫色和蓝色。

3，ABAB模型

如果两个试管的上面两个元素都是上A下B，那么我们就有很大的理由相信A是关键颜色，也有一定理由相信B的二级关键颜色。

如上第64关，黄色和棕色就是ABAB模型。

又如第71关，有大量的ABAB模型：

4，ABCA模型

如果一个试管的上面是上A下B，另外一个试管的上面是上C下A，那么我们就赋予C相对常规模型来说更高的自由度。

因为，C倒出去之后，2个A就可以合并了，B也能倒出去了。

更进一步，如果B有较高的自由度，我们就赋予C相对常规模型来说更高的自由度。

如第13关的黄色元素：

5，ABBA模型（循环压制模型）

如果一个试管的上面是上A下B，另外一个试管的上面是上B下A，那么我们相信，A和B至少有一个要赋予更高的自由度。

如第57关：

更一般的，n(n>1)个颜色的元素，都可以构成循环压制。

七，单点处理策略——死锁识别

有些状态已经是死亡状态了，如果能早点识别出来，就不用再往下尝试了。

死亡状态中，一个很有用的模型是死锁模型。

死锁又分为两种：循环压制死锁、单色压制死锁

1，循环压制死锁

最简单的循环压制死锁就是2个试管，即上文ABAB模型

循环压制死锁是不可能后期产生的，只能是开局自带的。

2，单色压制死锁

最简单的单色压制死锁就是2个试管，每个试管的最上面都是元素A，每个试管中A的下面至少还有一个颜色的其他元素，

这样，因为空间不够，就无法把A移动到同一个试管中，那么这些试管就无法进行任何操作，除非有别的试管参与进来。

3，死锁组合

如果若干个试管形成死锁，那么至少需要一个别的试管，才能完成水排序。

如果所有试管都没有空位，而且形成1个或若干个互不相关的死锁，那么显然这就已经成了死亡状态。（互不相关指的是没有共同颜色的元素，如下如第53关）

如第53关：

这就是2个死锁。

PS：死锁不一定是每个颜色都被另外一个颜色压制形成循环依赖，也有可能是如上这种，虽然没有被压制，但是没有足够的操作空间。

其实这2个死锁可以拆开来看，单是黄色元素所在的2个试管，就构成了死锁，于是黄色元素下面的橙色和蓝色元素也无法操作了。

还有非常复杂的死锁模型：

八，终极形态

1，终极形态

通过72关之后，就解锁了每日挑战。

而从第72关开始所有的偶数关卡，和所有的每日挑战，都进入了终极形态：14个试管，12个颜色。

除了试管新增3个，颜色新增3个，其他规则并没有变化。

2，图谱、算法求解

既然进入了终极形态，那就干脆做个图谱吧，方便描述。

? ?????

相应的，终极形态的代码也需要修改2行

#define NC 12
vector<string>vc = { "黄色","绿色","翠绿","青色","蓝色","紫色","棕色","橙色","红色" ,"灰蓝","褐色","粉色"};