闻缺陷则喜何志丹

闻缺陷则喜何志丹

关注
发信
关注(28)粉丝(399)

【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总
状态压缩 广度优先搜索

LeetCode1494. 并行课程 II

给你一个整数 n 表示某所大学里课程的数目，编号为 1 到 n ，数组 relations 中， relations[i] = [xi, yi] 表示一个先修课的关系，也就是课程 xi 必须在课程 yi 之前上。同时你还有一个整数 k 。
在一个学期中，你 最多 可以同时上 k 门课，前提是这些课的先修课在之前的学期里已经上过了。
请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。
示例 1：
输入：n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
输出：3
解释：上图展示了题目输入的图。在第一个学期中，我们可以上课程 2 和课程 3 。然后第二个学期上课程 1 ，第三个学期上课程 4 。
示例 2：
输入：n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2
输出：4
解释：上图展示了题目输入的图。一个最优方案是：第一学期上课程 2 和 3，第二学期上课程 4 ，第三学期上课程 1 ，第四学期上课程 5 。
示例 3：
输入：n = 11, relations = [], k = 2
输出：6
提示：
1 <= n <= 15
1 <= k <= n
0 <= relations.length <= n * (n-1) / 2
relations[i].length == 2
1 <= xi, yi <= n
xi != yi
所有先修关系都是不同的，也就是说 relations[i] != relations[j] 。
题目输入的图是个有向无环图。

状态压缩

15门课程。枚举最后一次选择（选择1到15门） 和之前的选择（0到15门）。共多少种可能。暴力做法是：2。

枚举第一门课 第二门课第三门课 的可能

不包括0，共7种可能。
const int iMaxMask = (1 << 3)-1;
for (int mask = iMaxMask; mask; mask = (mask - 1) & iMaxMask)
{
char sz1[100],sz2[100];
_itoa_s(mask, sz1, 2);
_itoa_s(iMaxMask - mask, sz2, 2);
std::cout << “最后一次选择:\t” << sz1 << " 之前的选择:\t" << sz2 << std::endl;
}
最后一次选择: 111 之前的选择: 0
最后一次选择: 110 之前的选择: 1
最后一次选择: 101 之前的选择: 10
最后一次选择: 100 之前的选择: 11
最后一次选择: 11 之前的选择: 100
最后一次选择: 10 之前的选择: 101
最后一次选择: 1 之前的选择: 110

枚举第一、三、四

不包括0，共7种可能，不需要枚举16种可能。自动忽略了不可能存在的状态2。
const int iMaxMask = 1+4+8;

最后一次选择: 111 之前的选择: 0
最后一次选择: 110 之前的选择: 1
最后一次选择: 101 之前的选择: 10
最后一次选择: 100 之前的选择: 11
最后一次选择: 11 之前的选择: 100
最后一次选择: 10 之前的选择: 101
最后一次选择: 1 之前的选择: 110

枚举iMaxMask [0,2)

总时间复杂度是:O(3) 3大约1.4e7。注意剪枝，否则容易超时。

动态规划

动态规划的状态表示

pre记录i学期能够完成的课程，dp记录i+1学期可以完成的课程。vHasDo记录已经完成的状态。状态没必要重复处理，i1<i2，如果某种状态i1学期能处理，那没必要i2学期处理。
空间复杂度:状态数 ,2
时间复杂度: O(3)

动态规划的转移方程

当前学期的课程，必须满足三个条件：
一，课程数小于等于k。
二，所有前置课程都已经完成。
三，这些课程没学习过。可以省略，会被淘汰。
预处理：
vPre[i] 表示第i门课需要的前面状态。
vNext[mask] 记录完成mask课程后，能够学习的课程。

动态规划的初始值

pre={0}

动态规划的填表顺序

i从0到大

动态规划的返回值

pre 包括(1<<n)-1时的i。

代码

核心代码

//通过 x &= (x-1)实现
int bitcount(unsigned x) {
	int countx = 0;
	while (x) {
		countx++;
		x &= (x - 1);
	}
	return countx;
}

class Solution {
public:
	int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
		const int iMaskCount = 1 << n;
		vector<int> vPre(n);
		for (const auto& v : relations)
		{
			vPre[v[1] - 1] |= 1 << (v[0] - 1);
		}
		vector<int> vNext(iMaskCount);
		for (int i = 0; i < iMaskCount; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if ((vPre[j] & i) == vPre[j])
				{
					vNext[i] |= (1 << j);
				}
			}
		}

		vector<int> pre = { 0 };
		vector<bool> vHasDo(iMaskCount);
		for (int i = 0; ; i++)
		{
			vector<int> dp;
			for (const int& iPre : pre)
			{
				if (iPre + 1 == iMaskCount)
				{
					return i;
				}
				const int iRemain = (iMaskCount - 1) - iPre;
				const int iCanSel = iRemain& vNext[iPre];
				auto Add = [&](const int& cur)
				{
					const int iNew = cur | iPre;
					if (!vHasDo[iNew])
					{
						dp.emplace_back(iNew);
						vHasDo[iNew] = true;
					}
				};
				if (bitcount((unsigned int)iCanSel) <= k)
				{
					Add(iCanSel);
					continue;
				}
				for (int cur = iCanSel; cur; cur = (cur - 1) & iCanSel)
				{					
					if (bitcount((unsigned int)cur) == k)
					{
						Add(cur);
					}
				}
			}
			pre.swap(dp);
		}
		return -1;
	}
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	int n, k;
	vector<vector<int>> relations;
	{
		Solution sln;
		n = 4, relations = { {2,1},{3,1},{1,4} }, k = 2;
		auto res = sln.minNumberOfSemesters(n, relations, k);
		Assert(3, res);
	}
	{
		Solution sln;
		n = 5, relations = { {2,1},{3,1},{4,1},{1,5} }, k = 2;
		auto res = sln.minNumberOfSemesters(n, relations, k);
		Assert(4, res);
	}
	{
		Solution sln;
		n = 11, relations = {}, k = 2;
		auto res = sln.minNumberOfSemesters(n, relations, k);
		Assert(6, res);
	}
}

动态规划

剪枝 忽略非法的前者状态。

//通过 x &= (x-1)实现
int bitcount(unsigned x) {
	int countx = 0;
	while (x) {
		countx++;
		x &= (x - 1);
	}
	return countx;
}

template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
	*seft = min(*seft,(ELE) other);
}

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
	*seft = max(*seft, other);
}

class Solution {
public:
	int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
		const int iMaskCount = 1 << n;		
		vector<int> vPre(n);
		for (const auto& v : relations)
		{
			vPre[v[1] - 1] |= 1 << (v[0] - 1);
		}
		vector<int> vNext(iMaskCount), vLen(iMaskCount);
		for (int i = 0; i < iMaskCount; i++)
		{
			vLen[i] = bitcount((unsigned int)i);
			for (int j = 0; j < n; j++)
			{
				if ((vPre[j] & i) == vPre[j])
				{
					vNext[i] |= (1 << j);
				}
			}
		}
		vector<int> vRet(iMaskCount,100);
		vRet[0] = 0;
		for (int i = 0; i < iMaskCount; i++)
		{		
            if(vRet[i] >= 100 )
            {
                continue;
            }
			const int iNeedStudy = (iMaskCount - 1) ^ i;//未学课程
			const int iCanStudy = iNeedStudy & vNext[i]; //只能学前置课程已学的课程
			if (vLen[iCanStudy] <= k)
			{
				MinSelf(&vRet[i| iCanStudy], vRet[i] + 1);
			}
			for (int j = iCanStudy; j; j= iCanStudy &(j-1))
			{//i是已学课程，j是本学期将学的课程	
				if (bitcount((unsigned )j) != k )
				{
					continue;
				}
				MinSelf(&vRet[i | j], vRet[i] + 1);
			}
		}	
		return vRet.back();
	}
};

2023年2月第一版

class Solution {
public:
int minNumberOfSemesters(int n, vector<vector>& relations, int k) {
m_iN = n;
m_iK = k;
m_iMaskNum = 1 << n;
m_vPreCourse.resize(n);
for (const auto& v : relations)
{
m_vPreCourse[v[1] - 1] |= (1 << (v[0] - 1));
}
m_vMinSemesters.resize(m_iMaskNum, m_iNotMay);
vector pre(1);
m_vMinSemesters[0] = 0;
for (int iSem = 0;; iSem++)
{
vector dp;
for (const auto& pr : pre)
{
if (pr + 1 == m_iMaskNum)
{
return iSem;
}
int iCanStudy = GetCanStudy(pr);
dfs(dp, pr, iCanStudy, iCanStudy, k,-1);
}
pre.swap(dp);
}
return 0;
}
inline int GetCanStudy(int preMask)const
{
int iCanStudy = 0;
for (int n = 0; n < m_iN; n++)
{
if (preMask & (1 << n))
{//之前已经学习
continue;
}
if ((m_vPreCourse[n] & preMask) != m_vPreCourse[n])
{//先行课程没有学习
continue;
}
iCanStudy |= (1 << n);
}
return iCanStudy;
}
void dfs(vector& dp, const int& preMask, const int& iCanStudy, int iRemain, int iLeve,int iPreN)
{
if ((0 == iLeve) || (0 == iRemain))
{
const int iNewMask = preMask |(iCanStudy - iRemain );
if (m_iNotMay != m_vMinSemesters[iNewMask])
{
return;
}
dp.push_back(iNewMask);
m_vMinSemesters[iNewMask] = m_vMinSemesters[preMask] + 1;
return;
}
for (int n = iPreN+1; n < m_iN; n++)
{
if (iRemain & (1 << n))
{
dfs(dp, preMask, iCanStudy, iRemain -(1 << n ), iLeve - 1,n);
}
}
}
vector m_vPreCourse;
vector m_vMinSemesters;
int m_iMaskNum;
int m_iK;
int m_iN;
const int m_iNotMay = 1000 * 1000;
};

2023年2月第二版

class Solution {
public:
int minNumberOfSemesters(int n, vector<vector>& relations, int k) {
m_iN = n;
m_iK = k;
m_iMaskNum = 1 << n;
m_vPreCourse.resize(n);
for (const auto& v : relations)
{
m_vPreCourse[v[1] - 1] |= (1 << (v[0] - 1));
}
m_vMinSemesters.resize(m_iMaskNum, m_iNotMay);
vector pre(1);
m_vMinSemesters[0] = 0;
for (int iSem = 0;; iSem++)
{
vector dp;
for (const auto& pr : pre)
{
if (pr + 1 == m_iMaskNum)
{
return iSem;
}
int iCanStudy = GetCanStudy(pr);
dfs(dp, pr, iCanStudy, iCanStudy, k, iCanStudy);
}
pre.swap(dp);
}
return 0;
}
inline int GetCanStudy(int preMask)const
{
int iCanStudy = 0;
for (int n = 0; n < m_iN; n++)
{
if (preMask & (1 << n))
{//之前已经学习
continue;
}
if ((m_vPreCourse[n] & preMask) != m_vPreCourse[n])
{//先行课程没有学习
continue;
}
iCanStudy |= (1 << n);
}
return iCanStudy;
}
void dfs(vector& dp, const int& preMask, const int& iCanStudy, int iRemain, int iLeve,int iCanSel)
{
if ((0 == iLeve) || (0 == iCanSel))
{
const int iNewMask = preMask |(iCanStudy - iRemain );
if (m_iNotMay != m_vMinSemesters[iNewMask])
{
return;
}
dp.push_back(iNewMask);
m_vMinSemesters[iNewMask] = m_vMinSemesters[preMask] + 1;
return;
}
while (iCanSel)
{
const int iNextCanSel = (iCanSel - 1)& iCanSel;
const int n = iCanSel - iNextCanSel;
iCanSel = iNextCanSel;
dfs(dp, preMask, iCanStudy, iRemain-n, iLeve - 1, iCanSel);
}
}
vector m_vPreCourse;
vector m_vMinSemesters;
int m_iMaskNum;
int m_iK;
int m_iN;
const int m_iNotMay = 1000 * 1000;
};

2023年7月版

using namespace std;

template
void OutToConsoleInner(const vector& vec, const string& strSep = " ")
{
for (int i = 0; i < vec.size(); i++)
{
if (0 != i % 25)
{
std::cout << strSep.c_str();
}
std::cout << setw(3) << setfill(’ ') << vec[i];
if (0 == (i + 1) % 25)
{
std::cout << std::endl;
}
else if (0 == (i + 1) % 5)
{
std::cout << strSep.c_str();
}
}
}

class CConsole
{
public:

template<class T>
static void Out(const vector<T>& vec, const string& strColSep = " ", const string& strRowSep = "\r\n")
{
	OutToConsoleInner(vec, strColSep);
	std::cout << strRowSep.c_str();
}

template<class T>
static void Out(const vector<vector<T>>& matrix, const string& strColSep = " ", const string& strRowSep = "\r\n")
{
	for (int i = 0; i < matrix.size(); i++)
	{
		OutToConsoleInner(matrix[i], strColSep);
		std::cout << strRowSep.c_str();
	}
}

template<class T>
static void Out(const std::map<T, std::vector<int> >& mTopPointToPoints, const string& strColSep = " ", const string& strRowSep = "\r\n")
{
	for (auto kv : mTopPointToPoints)
	{
		std::cout << kv.first << ":";
		OutToConsoleInner(kv.second, strColSep);
		std::cout << strRowSep.c_str();
	}
}


static void Out(const  std::string& t, const string& strColSep = " ", const string& strRowSep = "\r\n")
{
	std::cout << t.c_str() << strColSep.c_str();
}

template<class T  >
static void Out(const T& t, const string& strColSep = " ", const string& strRowSep = "\r\n")
{
	std::cout << t << strColSep.c_str();
}

};

void GenetateSum(vector& sums, const vector& nums)
{
sums.push_back(0);
for (int i = 0; i < nums.size(); i++)
{
sums.push_back(nums[i] + sums[i]);
}
}

//[iBegin，iEnd]之和
long long Total(int iBegin, int iEnd)
{
return (long long)(iBegin + iEnd) * (iEnd - iBegin + 1) / 2;
}

class CLadderhlp
{
public:
CLadderhlp(int ladders)
{
m_uLadderNum = ladders;
}
void AddNeedBick(int iNeedBick)
{
if (0 == m_uLadderNum)
{
return;
}
if (m_ladders.size() < m_uLadderNum)
{
m_ladders.push(iNeedBick);
m_iEaqualBicks += iNeedBick;
return;
}
int iTop = m_ladders.top();
if (iTop >= iNeedBick)
{
return;
}
m_iEaqualBicks -= iTop;
m_iEaqualBicks += iNeedBick;
m_ladders.pop();
m_ladders.push(iNeedBick);
}
std::priority_queue<int, vector, std::greater > m_ladders;
unsigned int m_uLadderNum;
long long m_iEaqualBicks = 0;
};

struct CPeo
{
CPeo(string strName, CPeo* pParent = nullptr)
{
m_strName = strName;
m_pParent = pParent;
}
string m_strName;
vector<CPeo*> m_childs;
CPeo* m_pParent = nullptr;
};

class CNeighborTable
{
public:
void Init(const vector<vector>& edges)
{

}
vector<vector<int>> m_vTable;

};

//通过 x &= (x-1)实现
int bitcount(unsigned x) {
int countx = 0;
while (x) {
countx++;
x &= (x - 1);
}
return countx;
}

int bitcount(unsigned long long x) {
int countx = 0;
while (x) {
countx++;
x &= (x - 1);
}
return countx;
}

class CRange
{
public:
template
CRange(const T& v)
{
m_iBegin = 0;
m_iEnd = v.size();
}
bool In(int iIndex)
{
return (iIndex >= m_iBegin) && (iIndex < m_iEnd);
}
const int End()
{
return m_iEnd;
}
protected:
int m_iBegin;
int m_iEnd;
};

template
class CTrie
{
public:
CTrie() :m_vPChilds(iTypeNum)
{

}
template<class IT>
void Add(IT begin, IT end)
{
	CTrie<iTypeNum, cBegin>* pNode = this;
	for (; begin != end; ++begin)
	{
		pNode = pNode->AddChar(*begin).get();
	}
}
template<class IT>
bool Search(IT begin, IT end)
{
	if (begin == end)
	{
		return true;
	}

	if ('.' == *begin)
	{
		for (auto& ptr : m_vPChilds)
		{
			if (!ptr)
			{
				continue;
			}
			if (ptr->Search(begin + 1, end))
			{
				return true;
			}
		}
	}

	auto ptr = GetChild(*begin);
	if (nullptr == ptr)
	{
		return false;
	}
	return ptr->Search(begin + 1, end);
}

protected:
std::shared_ptr AddChar(char ch)
{
if ((ch < cBegin) || (ch >= cBegin + iTypeNum))
{
return nullptr;
}
const int index = ch - cBegin;
auto ptr = m_vPChilds[index];
if (!ptr)
{
m_vPChilds[index] = std::make_shared<CTrie<iTypeNum, cBegin>>();
}
return m_vPChilds[index];
}
std::shared_ptr GetChild(char ch)const
{
if ((ch < cBegin) || (ch >= cBegin + iTypeNum))
{
return nullptr;
}
return m_vPChilds[ch - cBegin];
}
std::vector<std::shared_ptr> m_vPChilds;
};

class CWords
{
public:
void Add(const string& word)
{
m_strStrs.insert(word);
}
bool Search(const string& word)
{
return Search(m_strStrs.begin(), m_strStrs.end(), 0, word.length(), word);
}
protected:
bool Search(std::set::const_iterator begin, std::set::const_iterator end, int iStrBegin, int iStrEnd, const string& str)
{
int i = iStrBegin;
for (; (i < iStrEnd) && (str[i] != ‘.’); i++);
auto it = std::equal_range(begin, end, str, [&iStrBegin, &i](const string& s, const string& sFind)
{
return s.substr(iStrBegin, i - iStrBegin) < sFind.substr(iStrBegin, i - iStrBegin);
});
if (i == iStrBegin)
{
it.first = begin;
it.second = end;
}
if (it.first == it.second)
{
return false;
}
if (i == iStrEnd)
{
return true;
}
if (i + 1 == iStrEnd)
{
return true;
}
string tmp = str;
for (char ch = ‘a’; ch <= ‘z’; ch++)
{
tmp[i] = ch;
auto ij = std::equal_range(it.first, it.second, tmp, [&ch, &i](const string& s, const string& sFind)
{
return s[i] < sFind[i];
});
if (ij.first == ij.second)
{
continue;
}

		if (Search(ij.first, ij.second, i + 1, iStrEnd, str))
		{
			return true;
		}
	}
	return false;
}

std::set<string> m_strStrs;

};
class WordDictionary {
public:
WordDictionary() {
for (int i = 0; i < 26; i++)
{
m_str[i] = std::make_unique();
}
}

void addWord(string word) {
	m_str[word.length()]->Add(word);
}

bool search(string word) {
	return m_str[word.length()]->Search(word);
}
std::unique_ptr<CWords> m_str[26];

};

template
class C1097Int
{
public:
C1097Int(long long llData = 0) :m_iData(llData% MOD)
{

}
C1097Int  operator+(const C1097Int& o)const
{
	return C1097Int(((long long)m_iData + o.m_iData) % MOD);
}
C1097Int& operator+=(const C1097Int& o)
{
	m_iData = ((long long)m_iData + o.m_iData) % MOD;
	return *this;
}
C1097Int& operator-=(const C1097Int& o)
{
	m_iData = (m_iData + MOD - o.m_iData) % MOD;
	return *this;
}
C1097Int  operator-(const C1097Int& o)
{
	return C1097Int((m_iData + MOD - o.m_iData) % MOD);
}
C1097Int  operator*(const C1097Int& o)const
{
	return((long long)m_iData * o.m_iData) % MOD;
}
C1097Int& operator*=(const C1097Int& o)
{
	m_iData = ((long long)m_iData * o.m_iData) % MOD;
	return *this;
}
bool operator<(const C1097Int& o)const
{
	return m_iData < o.m_iData;
}
C1097Int pow(int n)const
{
	C1097Int iRet = 1, iCur = *this;
	while (n)
	{
		if (n & 1)
		{
			iRet *= iCur;
		}
		iCur *= iCur;
		n >>= 1;
	}
	return iRet;
}
C1097Int PowNegative1()const
{
	return pow(MOD - 2);
}
int ToInt()const
{
	return m_iData;
}

private:
int m_iData = 0;;
};

template
int operator+(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator+(C1097Int(iData)).ToInt();
return iRet;
}

template
int& operator+=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator+(C1097Int(iData)).ToInt();
return iData;
}

template
int operator*(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator*(C1097Int(iData)).ToInt();
return iRet;
}

template
int& operator*=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator*(C1097Int(iData)).ToInt();
return iData;
}

template
void MinSelf(T* seft, const T& other)
{
*seft = min(*seft, other);
}

template
void MaxSelf(T* seft, const T& other)
{
*seft = max(*seft, other);
}

int GetNotRepeateNum(int len, int iHasSel)
{
if (0 == len)
{
return 1;
}
if ((0 == iHasSel) && (1 == len))
{
return 10;
}
int iRet = 1;
if (iHasSel > 0)
{
for (int tmp = 10 - iHasSel; (tmp >= 2) && len; tmp–, len–)
{
iRet *= tmp;
}
}
else
{
iRet *= 9;
len–;
for (int tmp = 9; (tmp >= 2) && len; len–, tmp–)
{
iRet *= tmp;
}
}
return iRet;
}

int GCD(int n1, int n2)
{
int t1 = min(n1, n2);
int t2 = max(n1, n2);
if (0 == t1)
{
return t2;
}
return GCD(t2 % t1, t1);
}

void CreateMaskVector(vector& v, const int* const p, int n)
{
const int iMaxMaskNum = 1 << n;
v.resize(iMaxMaskNum);
for (int i = 0; i < n; i++)
{
v[1 << i] = p[i];
}
for (int mask = 1; mask < iMaxMaskNum; mask++)
{
const int iSubMask = mask & (-mask);
v[mask] = v[iSubMask] + v[mask - iSubMask];
}
}

class CMaxLineTree
{
public:
CMaxLineTree(int iArrSize) :m_iArrSize(iArrSize), m_vData(iArrSize * 4)
{

}
//iIndex 从0开始
void Modify(int iIndex, int iValue)
{
	Modify(1, 1, m_iArrSize, iIndex + 1, iValue);
}
//iNeedQueryLeft iNeedQueryRight 从0开始
int Query(const int iNeedQueryLeft, const int iNeedQueryRight)
{
	return Query(1, 1, m_iArrSize, iNeedQueryLeft + 1, iNeedQueryRight + 1);
}

protected:
int Query(const int iTreeNodeIndex, const int iRecordLeft, const int iRecordRight, const int iNeedQueryLeft, const int iNeedQueryRight)
{
if ((iNeedQueryLeft <= iRecordLeft) && (iNeedQueryRight >= iRecordRight))
{
return m_vData[iTreeNodeIndex];
}
const int iMid = (iRecordLeft + iRecordRight) / 2;
int iRet = 0;
if (iNeedQueryLeft <= iMid)
{
iRet = Query(iTreeNodeIndex * 2, iRecordLeft, iMid, iNeedQueryLeft, iNeedQueryRight);
}
if (iNeedQueryRight > iMid)
{
iRet = max(iRet, Query(iTreeNodeIndex * 2 + 1, iMid + 1, iRecordRight, iNeedQueryLeft, iNeedQueryRight));
}
return iRet;
}
void Modify(int iTreeNodeIndex, int iLeft, int iRight, int iIndex, int iValue)
{
if (iLeft == iRight)
{
m_vData[iTreeNodeIndex] = max(m_vData[iTreeNodeIndex], iValue);
return;
}
const int iMid = (iLeft + iRight) / 2;
if (iIndex <= iMid)
{
Modify(iTreeNodeIndex * 2, iLeft, iMid, iIndex, iValue);
}
else
{
Modify(iTreeNodeIndex * 2 + 1, iMid + 1, iRight, iIndex, iValue);
}
m_vData[iTreeNodeIndex] = max(m_vData[iTreeNodeIndex * 2], m_vData[iTreeNodeIndex * 2 + 1]);
}
const int m_iArrSize;
std::vector m_vData;
};

class CMaxLineTreeMap
{
public:
CMaxLineTreeMap(int iArrSize) :m_iArrSize(iArrSize)
{

}
//iIndex 从0开始
void Modify(int iIndex, int iValue)
{
	Modify(1, 1, m_iArrSize, iIndex + 1, iValue);
}
//iNeedQueryLeft iNeedQueryRight 从0开始
int Query(const int iNeedQueryLeft, const int iNeedQueryRight)
{
	return Query(1, 1, m_iArrSize, iNeedQueryLeft + 1, iNeedQueryRight + 1);
}

protected:
int Query(const int iTreeNodeIndex, const int iRecordLeft, const int iRecordRight, const int iNeedQueryLeft, const int iNeedQueryRight)
{
if ((iNeedQueryLeft <= iRecordLeft) && (iNeedQueryRight >= iRecordRight))
{
return m_mData[iTreeNodeIndex];
}
const int iMid = (iRecordLeft + iRecordRight) / 2;
int iRet = 0;
if (iNeedQueryLeft <= iMid)
{
iRet = Query(iTreeNodeIndex * 2, iRecordLeft, iMid, iNeedQueryLeft, iNeedQueryRight);
}
if (iNeedQueryRight > iMid)
{
iRet = max(iRet, Query(iTreeNodeIndex * 2 + 1, iMid + 1, iRecordRight, iNeedQueryLeft, iNeedQueryRight));
}
return iRet;
}
void Modify(int iTreeNodeIndex, int iLeft, int iRight, int iIndex, int iValue)
{
if (iLeft == iRight)
{
m_mData[iTreeNodeIndex] = max(m_mData[iTreeNodeIndex], iValue);
return;
}
const int iMid = (iLeft + iRight) / 2;
if (iIndex <= iMid)
{
Modify(iTreeNodeIndex * 2, iLeft, iMid, iIndex, iValue);
}
else
{
Modify(iTreeNodeIndex * 2 + 1, iMid + 1, iRight, iIndex, iValue);
}
m_mData[iTreeNodeIndex] = max(m_mData[iTreeNodeIndex * 2], m_mData[iTreeNodeIndex * 2 + 1]);
}
const int m_iArrSize;
std::unordered_map<int, int> m_mData;
};

template
class CSumLineTree
{
public:
CSumLineTree(int iEleSize) :m_iEleSize(iEleSize), m_vArr(m_iEleSize * 4), m_vChildAdd(m_iEleSize * 4)
{

}
void Add(int iLeftIndex, int iRightIndex, int iValue)
{
	Add(1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1, iValue);
}
T Query(int iLeftIndex, int iRightIndex)
{
	return Query(1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1);
}

private:
T Query(int iNode, int iDataLeft, int iDataRight, int iOpeLeft, int iOpeRight)
{
if ((iOpeLeft <= iDataLeft) && (iOpeRight >= iDataRight))
{
return m_vArr[iNode];
}
Fresh(iNode, iDataLeft, iDataRight);
const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
T ret(0);
if (iMid >= iOpeLeft)
{
ret += Query(iNode * 2, iDataLeft, iMid, iOpeLeft, iOpeRight);
}
if (iMid + 1 <= iOpeRight)
{
ret += Query(iNode * 2 + 1, iMid + 1, iDataRight, iOpeLeft, iOpeRight);
}
return ret;
}
/* 暴力解法
void Add(int iNode, int iDataLeft, int iDataRight, int iOpeLeft, int iOpeRight, int iValue)
{
m_vArr[iNode] += T(iValue)*(min(iDataRight, iOpeRight) - max(iDataLeft, iOpeLeft)+1);
if (iDataLeft == iDataRight)
{
return;
}
const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
if (iMid >= iOpeLeft)
{
Add(iNode * 2, iDataLeft, iMid, iOpeLeft, iOpeRight, iValue);
}
if (iMid + 1 <= iOpeRight)
{
Add(iNode * 2 + 1, iMid + 1, iDataRight, iOpeLeft, iOpeRight, iValue);
}
}
*/
void Fresh(int iNode, int iDataLeft, int iDataRight)
{
const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
if (m_vChildAdd[iNode] != 0)
{
Add(iNode * 2, iDataLeft, iMid, iDataLeft, iMid, m_vChildAdd[iNode]);
Add(iNode * 2 + 1, iMid + 1, iDataRight, iMid + 1, iDataRight, m_vChildAdd[iNode]);
m_vChildAdd[iNode] = 0;
}
}
//懒惰法
void Add(int iNode, int iDataLeft, int iDataRight, int iOpeLeft, int iOpeRight, int iValue)
{
m_vArr[iNode] += T(iValue) * (min(iDataRight, iOpeRight) - max(iDataLeft, iOpeLeft) + 1);
if ((iOpeLeft <= iDataLeft) && (iOpeRight >= iDataRight))
{
m_vChildAdd[iNode] += T(iValue);
return;
}

	Fresh(iNode, iDataLeft, iDataRight);
	const int iMid = iDataLeft + (iDataRight - iDataLeft) / 2;
	if (iMid >= iOpeLeft)
	{
		Add(iNode * 2, iDataLeft, iMid, iOpeLeft, iOpeRight, iValue);
	}
	if (iMid + 1 <= iOpeRight)
	{
		Add(iNode * 2 + 1, iMid + 1, iDataRight, iOpeLeft, iOpeRight, iValue);
	}
}

const int m_iEleSize;
vector<T> m_vArr;
vector<int> m_vChildAdd;

};

template
class CTreeArr
{
public:
CTreeArr(int iSize) :m_vData(iSize + 1)
{

}
void Add(int index, T value)
{
	index++;
	while (index < m_vData.size())
	{
		m_vData[index] += value;
		index += index & (-index);
	}
}
T Sum(int index)
{
	index++;
	T ret = 0;
	while (index)
	{
		ret += m_vData[index];
		index -= index & (-index);
	}
	return ret;
}
T Get(int index)
{
	return Sum(index) - Sum(index - 1);
}

private:
vector m_vData;
};

//iCodeNum 必须大于等于可能的字符数
template
class CHashStr {
public:
CHashStr(string s, int iCodeNum, int iCodeBegin = 1, char chBegin = ‘a’) {
m_c = s.length();
m_vP.resize(m_c + 1);
m_vP[0] = 1;
m_vHash.resize(m_c + 1);
for (int i = 0; i < m_c; i++)
{
const int P = iCodeBegin + iCodeNum;
m_vHash[i + 1] = m_vHash[i] * P + s[i] - chBegin + iCodeBegin;
m_vP[i + 1] = m_vP[i] * P;
}
}
//包括left right
int GetHash(int left, int right)
{
return (m_vHash[right + 1] - m_vHash[left] * m_vP[right - left + 1]).ToInt();
}
inline int GetHash(int right)
{
return m_vHash[right + 1].ToInt();
}
int GetHashExincludeRight(int left, int right)
{
return (m_vHash[right ] - m_vHash[left] * m_vP[right - left ]).ToInt();
}
inline int GetHashExincludeRight(int right)
{
return m_vHash[right].ToInt();
}
int m_c;
vector<C1097Int> m_vP;
vector<C1097Int> m_vHash;
};

template
class C2HashStr
{
public:
C2HashStr(string s) {
m_pHash1 = std::make_unique<CHashStr<>>(s, 26);
m_pHash2 = std::make_unique < CHashStr>(s, 27, 0);
}
//包括left right
long long GetHash(int left, int right)
{
return (long long)m_pHash1->GetHash(left, right) * (MOD2 + 1) + m_pHash2->GetHash(left, right);
}
long long GetHash(int right)
{
return (long long)m_pHash1->GetHash(right) * (MOD2 + 1) + m_pHash2->GetHash(right);
}
//包括Left，不包括Right
long long GetHashExincludeRight(int left, int right)
{
return (long long)m_pHash1->GetHashExincludeRight(left, right) * (MOD2 + 1) + m_pHash2->GetHashExincludeRight(left, right);
}
long long GetHashExincludeRight(int right)
{
return (long long)m_pHash1->GetHashExincludeRight(right) * (MOD2 + 1) + m_pHash2->GetHashExincludeRight(right);
}
private:
std::unique_ptr<CHashStr<>> m_pHash1;
std::unique_ptr<CHashStr> m_pHash2;
};

template
class CDynaHashStr {
public:
CDynaHashStr(int iCodeNum, int iCodeBegin = 1, char chBegin = ‘a’) :m_iUnit(iCodeNum + iCodeBegin), m_iP(1), m_iBegin(iCodeBegin - chBegin)
{

}
inline void push_back(const char& ch)
{
	const int iNum = ch + m_iBegin;
	m_iHash *= m_iUnit;
	m_iHash += iNum;
	m_iP *= m_iUnit;
}
inline void push_front(const char& ch)
{
	const int iNum = ch + m_iBegin;
	m_iHash += m_iP * iNum;
	m_iP *= m_iUnit;
}
inline int GetHash() const
{
	return m_iHash;
}
const int m_iUnit;
const int m_iBegin;
C1097Int<MOD> m_iHash;
C1097Int<MOD> m_iP;

};

template
class C2DynaHashStr {
public:
C2DynaHashStr(int iCodeNum, int iCodeBegin = 1, char chBegin = ‘a’)
{
m_pHash1 = new CDynaHashStr<>(iCodeNum, iCodeBegin, chBegin);
m_pHash2 = new CDynaHashStr(iCodeNum, iCodeBegin, chBegin);
}
~C2DynaHashStr()
{
delete m_pHash1;
delete m_pHash2;
}
inline void push_back(const char& ch)
{
m_pHash1->push_back(ch);
m_pHash2->push_back(ch);
}
inline void push_front(const char& ch)
{
m_pHash1->push_front(ch);
m_pHash2->push_front(ch);
}
long long Hash()const
{
return (long long)MOD2 * m_pHash1->m_iHash.ToInt() + m_pHash2->m_iHash.ToInt();
}
bool operator==(const C2DynaHashStr& other) const
{
return (m_pHash1->m_iHash.ToInt() == other.m_pHash1->m_iHash.ToInt()) && (m_pHash2->m_iHash.ToInt() == other.m_pHash2->m_iHash.ToInt());
}
CDynaHashStr<>* m_pHash1;
CDynaHashStr* m_pHash2;
};
namespace NSort
{
template
bool SortVecVec(const vector& v1, const vector& v2)
{
return v1[ArrIndex] < v2[ArrIndex];
};
}

namespace NCmp
{
template
bool Less(const std::pair<Class1, int>& p, Class1 iData)
{
return p.first < iData;
}

template<class Class1>
bool  Greater(const std::pair<Class1, int>& p, Class1 iData)
{
	return p.first > iData;
}

template<class _Ty1, class _Ty2>
class CLessPair
{
public:
	bool operator()(const std::pair<_Ty1, _Ty2>& p1, const std::pair<_Ty1, _Ty2>& p2)const
	{
		return p1.first < p2.first;
	}
};

template<class _Ty1, class _Ty2>
class CGreatePair
{
public:
	bool operator()(const std::pair<_Ty1, _Ty2>& p1, const std::pair<_Ty1, _Ty2>& p2)const
	{
		return p1.first > p2.first;
	}
};

}

class CIndexVector
{
public:
template
CIndexVector(vector& data)
{
for (int i = 0; i < data.size(); i++)
{
m_indexs.emplace_back(i);
}
std::sort(m_indexs.begin(), m_indexs.end(), [data](const int& i1, const int& i2)
{
return data[i1] < data[i2];
});
}
int GetIndex(int index)
{
return m_indexs[index];
}
private:
vector m_indexs;
};

class CMedian
{
public:
void AddNum(int iNum)
{
m_queTopMin.emplace(iNum);
MakeNumValid();
MakeSmallBig();
}
void Remove(int iNum)
{
if (m_queTopMax.size() && (iNum <= m_queTopMax.top()))
{
m_setTopMaxDel.insert(iNum);
}
else
{
m_setTopMinDel.insert(iNum);
}

	PopIsTopIsDel(m_queTopMin, m_setTopMinDel);
	PopIsTopIsDel(m_queTopMax, m_setTopMaxDel);
	MakeNumValid();
	MakeSmallBig();
}
double Median()
{
	const int iMaxNum = m_queTopMin.size() - m_setTopMinDel.size();
	const int iMinNum = m_queTopMax.size() - m_setTopMaxDel.size();
	if (iMaxNum > iMinNum)
	{
		return m_queTopMin.top();
	}
	return ((double)m_queTopMin.top() + m_queTopMax.top()) / 2.0;
}
template<class T>
void PopIsTopIsDel(T& que, std::unordered_multiset<int>& setTopMaxDel)
{
	while (que.size() && (setTopMaxDel.count(que.top())))
	{
		setTopMaxDel.erase(setTopMaxDel.find(que.top()));
		que.pop();
	}
}
void MakeNumValid()
{
	const int iMaxNum = m_queTopMin.size() - m_setTopMinDel.size();
	const int iMinNum = m_queTopMax.size() - m_setTopMaxDel.size();
	//确保两个队的数量
	if (iMaxNum > iMinNum + 1)
	{
		int tmp = m_queTopMin.top();
		m_queTopMin.pop();
		m_queTopMax.emplace(tmp);
		PopIsTopIsDel(m_queTopMin, m_setTopMinDel);
	}
	if (iMinNum > iMaxNum)
	{
		int tmp = m_queTopMax.top();
		m_queTopMax.pop();
		m_queTopMin.push(tmp);
		PopIsTopIsDel(m_queTopMax, m_setTopMaxDel);
	}
}
void MakeSmallBig()
{
	if (m_queTopMin.empty() || m_queTopMax.empty())
	{
		return;
	}
	while (m_queTopMin.top() < m_queTopMax.top())
	{
		const int iOldTopMin = m_queTopMin.top();
		const int iOldTopMax = m_queTopMax.top();
		m_queTopMin.pop();
		m_queTopMax.pop();
		m_queTopMin.emplace(iOldTopMax);
		m_queTopMax.emplace(iOldTopMin);
		PopIsTopIsDel(m_queTopMin, m_setTopMinDel);
		PopIsTopIsDel(m_queTopMax, m_setTopMaxDel);
	}
}
std::priority_queue<int> m_queTopMax;
std::priority_queue<int, vector<int>, greater<int>> m_queTopMin;
std::unordered_multiset<int> m_setTopMaxDel, m_setTopMinDel;

};

template
class CDistanceGrid
{
public:
CDistanceGrid(const vector<vector>& grid) :m_grid(grid), m_r(grid.size()), m_c(grid[0].size())
{

}
//单源路径 D 算法 ,时间复杂度:r*c*log(r*c)
inline int Dis(int r1, int c1, int r2, int c2)
{
	vector<vector<int>> vDis(iMaxRow, vector<int>(iMaxCol, INT_MAX));

	auto Add = [&vDis, this](std::priority_queue<pair<int, int>, vector<std::pair<int, int>>, greater<pair<int, int>>>& queCur, int iDis, int r, int c)
	{
		const int iRowColMask = iMaxCol * r + c;
		if (iDis >= vDis[r][c])
		{
			return;
		}
		queCur.emplace(iDis, iRowColMask);
		vDis[r][c] = iDis;
	};
	auto Move = [&](std::priority_queue<pair<int, int>, vector<std::pair<int, int>>, greater<pair<int, int>>>& queCur, int iDis, int r, int c)
	{
		if ((r < 0) || (r >= m_r))
		{
			return;
		}
		if ((c < 0) || (c >= m_c))
		{
			return;
		}
		if (m_grid[r][c] < 1)
		{
			return;
		}
		Add(queCur, iDis, r, c);
	};

	std::priority_queue<pair<int, int>, vector<std::pair<int, int>>, greater<pair<int, int>>> que;
	Add(que, 0, r1, c1);
	while (que.size())
	{
		const int iDis = que.top().first;
		const int iStart = que.top().second;
		que.pop();
		const int r = iStart / iMaxCol;
		const int c = iStart % iMaxCol;
		if ((r == r2) && (c == c2))
		{
			return iDis;
		}
		if (iDis > vDis[r][c])
		{
			continue;
		}

		Move(que, iDis + 1, r + 1, c);
		Move(que, iDis + 1, r - 1, c);
		Move(que, iDis + 1, r, c + 1);
		Move(que, iDis + 1, r, c - 1);
	}

	return -1;
}

private:
virtual bool IsCanMoveStatue(int r, int c)
{
return m_grid[r][c] >= 1;
}
const int m_r;
const int m_c;
const vector<vector>& m_grid;

};

class CBFSGridDist
{
public:
CBFSGridDist(const vector<vector>& bCanVisit, int r, int c) :m_bCanVisit(bCanVisit), m_r(m_bCanVisit.size()), m_c(m_bCanVisit[0].size())
{
m_vDis.assign(m_r, vector(m_c, INT_MAX / 2));
Dist(r, c);
}
bool Vilid(const int r, const int c)
{
if ((r < 0) || (r >= m_r))
{
return false;
}
if ((c < 0) || (c >= m_c))
{
return false;
}
return true;
}
const vector<vector>& Dis()const
{
return m_vDis;
}
const vector<vector>& m_bCanVisit;
private:
//INT_MAX/2 表示无法到达
void Dist(int r, int c)
{
m_vDis.assign(m_r, vector(m_c, INT_MAX / 2));
vector<vector> vHasDo(m_r, vector(m_c));
std::queue<std::pair<int, int>> que;
auto Add = [&](const int& r, const int& c, const int& iDis)
{
if (!Vilid(r, c))
{
return;
}
if (vHasDo[r][c])
{
return;
}
if (!m_bCanVisit[r][c])
{
vHasDo[r][c] = true;
return;
}
if (iDis >= m_vDis[r][c])
{
return;
}

		que.emplace(r, c);
		m_vDis[r][c] = iDis;
		vHasDo[r][c] = true;
	};
	Add(r, c, 0);
	while (que.size())
	{
		const int r = que.front().first;
		const int c = que.front().second;
		que.pop();
		const int iDis = m_vDis[r][c];
		Add(r + 1, c, iDis + 1);
		Add(r - 1, c, iDis + 1);
		Add(r, c + 1, iDis + 1);
		Add(r, c - 1, iDis + 1);
	}

}
vector<vector<int>> m_vDis;
const int m_r;
const int m_c;

};

class C2BNumTrieNode
{
public:
C2BNumTrieNode()
{
m_childs[0] = m_childs[1] = nullptr;
}
bool GetNot0Child(bool bFirstRight)
{
auto ptr = m_childs[bFirstRight];
if (ptr && (ptr->m_iNum > 0))
{
return bFirstRight;
}
return !bFirstRight;
}
int m_iNum = 0;
C2BNumTrieNode* m_childs[2];
};

template
class C2BNumTrie
{
public:
C2BNumTrie()
{
m_pRoot = new C2BNumTrieNode();
}
void Add(int iNum)
{
m_setHas.emplace(iNum);
C2BNumTrieNode* p = m_pRoot;
for (int i = iLeveNum - 1; i >= 0; i–)
{
p->m_iNum++;
bool bRight = iNum & (1 << i);
if (nullptr == p->m_childs[bRight])
{
p->m_childs[bRight] = new C2BNumTrieNode();
}
p = p->m_childs[bRight];
}
p->m_iNum++;
}
void Del(int iNum)
{
auto it = m_setHas.find(iNum);
if (m_setHas.end() == it)
{
return;
}
m_setHas.erase(it);
C2BNumTrieNode* p = m_pRoot;
for (int i = iLeveNum - 1; i >= 0; i–)
{
p->m_iNum–;
bool bRight = iNum & (1 << i);
p = p->m_childs[bRight];
}
p->m_iNum–;
}
int MaxXor(int iNum)
{
C2BNumTrieNode* p = m_pRoot;
int iRet = 0;
for (int i = iLeveNum - 1; i >= 0; i–)
{
bool bRight = !(iNum & (1 << i));
bool bSel = p->GetNot0Child(bRight);
p = p->m_childs[bSel];
if (bSel == bRight)
{
iRet |= (1 << i);
}
}
return iRet;
}
C2BNumTrieNode* m_pRoot;
std::unordered_multiset m_setHas;
};

struct SValueItem
{
SValueItem()
{

}
SValueItem(int iValue)
{
	m_iCoefficient = iValue;
}
SValueItem operator*(const SValueItem& o)const
{
	SValueItem ret(m_iCoefficient * o.m_iCoefficient);
	int i = 0, j = 0;
	while ((i < m_vVars.size()) && (j < o.m_vVars.size()))
	{
		if (m_vVars[i] < o.m_vVars[j])
		{
			ret.m_vVars.emplace_back(m_vVars[i]);
			i++;
		}
		else
		{
			ret.m_vVars.emplace_back(o.m_vVars[j]);
			j++;
		}
	}
	ret.m_vVars.insert(ret.m_vVars.end(), m_vVars.begin() + i, m_vVars.end());
	ret.m_vVars.insert(ret.m_vVars.end(), o.m_vVars.begin() + j, o.m_vVars.end());
	return ret;
}
bool operator<(const SValueItem& o)const
{
	if (m_vVars.size() == o.m_vVars.size())
	{
		return m_vVars < o.m_vVars;
	}
	return m_vVars.size() > o.m_vVars.size();
}
vector<std::string> m_vVars;
int m_iCoefficient = 1;//系数、倍率
std::string ToString()const
{
	std::ostringstream os;
	os << m_iCoefficient;
	for (const auto& s : m_vVars)
	{
		os << "*" << s;
	}
	return os.str();
}

};

struct SValue
{
SValue()
{

}
SValue(int iValue)
{
	SValueItem item;
	item.m_iCoefficient = iValue;
	m_items.emplace(item);
}
SValue(std::string strName)
{
	SValueItem item;
	item.m_vVars.emplace_back(strName);
	m_items.emplace(item);
}
SValue operator-(const SValue& o)const
{
	SValue ret;
	ret.m_items = m_items;
	for (auto it : o.m_items)
	{
		ret -= it;
	}
	return ret;
}
SValue operator+(const SValue& o)const
{
	SValue ret;
	ret.m_items = m_items;
	for (auto it : o.m_items)
	{
		ret += it;
	}
	return ret;
}
SValue operator*(const SValue& o)const
{
	SValue ret;
	for (const auto it : m_items)
	{
		for (const auto ij : o.m_items)
		{
			ret += it * ij;
		}
	}
	return ret;
}
SValue& operator+=(const SValueItem& item)
{
	auto it = m_items.find(item);
	if (m_items.end() == it)
	{
		m_items.emplace(item);
	}
	else
	{
		auto tmp = *it;
		tmp.m_iCoefficient += item.m_iCoefficient;
		m_items.erase(it);
		m_items.emplace(tmp);
	}
	return *this;
}
SValue& operator-=(const SValueItem& item)
{
	auto it = m_items.find(item);
	if (m_items.end() == it)
	{
		auto tmp = item;
		tmp.m_iCoefficient *= -1;
		m_items.emplace(tmp);
	}
	else
	{
		auto tmp = *it;
		tmp.m_iCoefficient -= item.m_iCoefficient;
		m_items.erase(it);
		m_items.emplace(tmp);
	}
	return *this;
}
vector<std::string> ToStrings()const
{
	vector<std::string> vRet;
	for (const auto& item : m_items)
	{
		if (0 == item.m_iCoefficient)
		{
			continue;
		}
		vRet.emplace_back(item.ToString());
	}
	return vRet;
}
std::set<SValueItem> m_items;

};

class CDelIndexs
{
public:
CDelIndexs()
{

}
CDelIndexs(int iSize)
{
	Init(iSize);
}
void Init(int iSize)
{
	m_bDels.assign(iSize, false);
	m_vNext.resize(iSize);
	for (int i = 0; i < iSize; i++)
	{
		m_vNext[i] = i + 1;
	}
}
void Del(int index)
{
	if ((index < 0) || (index >= m_vNext.size()))
	{
		return;
	}
	if (m_bDels[index])
	{
		return;
	}
	m_bDels[index] = true;

}
void SetCur(int index)
{
	if (index < 0)
	{
		m_iCur = m_vNext.size();
	}
	else
	{
		m_iCur = FreshCur(index);
	}
}
int NextIndex()
{
	if (m_iCur >= m_vNext.size())
	{
		return -1;
	}
	auto ret = m_iCur;
	SetCur(m_vNext[m_iCur]);
	return ret;
}

private:
int FreshCur(int index)
{
if (index >= m_vNext.size())
{
return m_vNext.size();
}
if (!m_bDels[index])
{
return index;
}

	return m_vNext[index] = FreshCur(m_vNext[index]);
}
int m_iCur = 0;
vector<bool> m_bDels;
vector<int> m_vNext;

};

class CUnionFind
{
public:
CUnionFind(int iSize) :m_vNodeToRegion(iSize)
{
for (int i = 0; i < iSize; i++)
{
m_vNodeToRegion[i] = i;
}
m_iConnetRegionCount = iSize;
}
int GetConnectRegionIndex(int iNode)
{
int& iConnectNO = m_vNodeToRegion[iNode];
if (iNode == iConnectNO)
{
return iNode;
}
return iConnectNO = GetConnectRegionIndex(iConnectNO);
}
void Union(int iNode1, int iNode2)
{
const int iConnectNO1 = GetConnectRegionIndex(iNode1);
const int iConnectNO2 = GetConnectRegionIndex(iNode2);
if (iConnectNO1 == iConnectNO2)
{
return;
}
m_iConnetRegionCount–;
if (iConnectNO1 > iConnectNO2)
{
UnionConnect(iConnectNO1, iConnectNO2);
}
else
{
UnionConnect(iConnectNO2, iConnectNO1);
}
}

bool IsConnect(int iNode1, int iNode2)
{
	return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
}
int GetConnetRegionCount()const
{
	return m_iConnetRegionCount;
}
vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
{
	const int iNodeSize = m_vNodeToRegion.size();
	vector<int> vRet(iNodeSize);
	for (int i = 0; i < iNodeSize; i++)
	{
		vRet[GetConnectRegionIndex(i)]++;
	}
	return vRet;
}

private:
void UnionConnect(int iFrom, int iTo)
{
m_vNodeToRegion[iFrom] = iTo;
}
vector m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
int m_iConnetRegionCount;
};

class CUnionFindMST
{
public:
CUnionFindMST(const int iNodeSize) :m_uf(iNodeSize)
{

}
void AddEdge(const int iNode1, const int iNode2, int iWeight)
{
	if (m_uf.IsConnect(iNode1, iNode2))
	{
		return;
	}
	m_iMST += iWeight;
	m_uf.Union(iNode1, iNode2);
}
void AddEdge(const vector<int>& v)
{
	AddEdge(v[0], v[1], v[2]);
}
int MST()
{
	if (m_uf.GetConnetRegionCount() > 1)
	{
		return -1;
	}
	return m_iMST;
}

private:
int m_iMST = 0;
CUnionFind m_uf;
};

class CNearestMST
{
public:
CNearestMST(const int iNodeSize) :m_bDo(iNodeSize), m_vDis(iNodeSize, INT_MAX), m_vNeiTable(iNodeSize)
{

}
void Init(const vector<vector<int>>& edges)
{
	for (const auto& v : edges)
	{
		Add(v);
	}
}
void Add(const vector<int>& v)
{
	m_vNeiTable[v[0]].emplace_back(v[1], v[2]);
	m_vNeiTable[v[1]].emplace_back(v[0], v[2]);
}
int MST(int start)
{
	int next = start;
	while ((next = AddNode(next)) >= 0);
	return m_iMST;
}
int MST(int iNode1, int iNode2, int iWeight)
{
	m_bDo[iNode1] = true;
	for (const auto& it : m_vNeiTable[iNode1])
	{
		if (m_bDo[it.first])
		{
			continue;
		}
		m_vDis[it.first] = min(m_vDis[it.first], (long long)it.second);
	}
	m_iMST = iWeight;

	int next = iNode2;
	while ((next = AddNode(next)) >= 0);
	return m_iMST;
}

private:
int AddNode(int iCur)
{
m_bDo[iCur] = true;
for (const auto& it : m_vNeiTable[iCur])
{
if (m_bDo[it.first])
{
continue;
}
m_vDis[it.first] = min(m_vDis[it.first], (long long)it.second);
}

	int iMinIndex = -1;
	for (int i = 0; i < m_vDis.size(); i++)
	{
		if (m_bDo[i])
		{
			continue;
		}
		if ((-1 == iMinIndex) || (m_vDis[i] < m_vDis[iMinIndex]))
		{
			iMinIndex = i;
		}
	}
	if (-1 != iMinIndex)
	{
		if (INT_MAX == m_vDis[iMinIndex])
		{
			m_iMST = -1;
			return -1;
		}
		m_iMST += m_vDis[iMinIndex];
	}

	return iMinIndex;
}
vector<bool> m_bDo;
vector<long long> m_vDis;
vector < vector<std::pair<int, int>>> m_vNeiTable;
long long m_iMST = 0;

};

typedef pair<long long, int> PAIRLLI;
class CDis
{
public:
static void Dis(vector& vDis, int start, const vector<vector<pair<int, int>>>& vNeiB)
{
std::priority_queue<PAIRLLI, vector, greater> minHeap;
minHeap.emplace(0, start);
while (minHeap.size())
{
const long long llDist = minHeap.top().first;
const int iCur = minHeap.top().second;
minHeap.pop();
if (-1 != vDis[iCur])
{
continue;
}
vDis[iCur] = llDist;
for (const auto& it : vNeiB[iCur])
{
minHeap.emplace(llDist + it.second, it.first);
}
}

}

};

class CNearestDis
{
public:
CNearestDis(int iSize) :m_iSize(iSize), DIS(m_vDis), PRE(m_vPre)
{

}
void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
{
	m_vDis.assign(m_iSize, -1);
	m_vPre.assign(m_iSize, -1);
	vector<bool> vDo(m_iSize);//点是否已处理
	auto AddNode = [&](int iNode)
	{
		//const int iPreNode = m_vPre[iNode];
		long long llPreDis = m_vDis[iNode];

		vDo[iNode] = true;
		for (const auto& it : vNeiB[iNode])
		{
			if (vDo[it.first])
			{
				continue;
			}

			if ((-1 == m_vDis[it.first]) || (it.second + llPreDis < m_vDis[it.first]))
			{
				m_vDis[it.first] = it.second + llPreDis;
				m_vPre[it.first] = iNode;
			}
		}

		long long llMinDis = LLONG_MAX;
		int iMinIndex = -1;
		for (int i = 0; i < m_vDis.size(); i++)
		{
			if (vDo[i])
			{
				continue;
			}
			if (-1 == m_vDis[i])
			{
				continue;
			}
			if (m_vDis[i] < llMinDis)
			{
				iMinIndex = i;
				llMinDis = m_vDis[i];
			}
		}
		return (LLONG_MAX == llMinDis) ? -1 : iMinIndex;
	};

	int next = start;
	m_vDis[start] = 0;
	while (-1 != (next = AddNode(next)));
}
void Cal(const int start, vector<vector<int>>& edges)
{
	vector<vector<pair<int, int>>> vNeiB(m_iSize);
	for (int i = 0; i < edges.size(); i++)
	{
		const auto& v = edges[i];
		vNeiB[v[0]].emplace_back(v[1], v[2]);
		vNeiB[v[1]].emplace_back(v[0], v[2]);
	}
	Cal(start, vNeiB);
}
const vector<long long>& DIS;
const vector<int>& PRE;

private:
const int m_iSize;
vector m_vDis;//各点到起点的最短距离
vector m_vPre;//最短路径的前一点
};

class CNeiBo2
{
public:
CNeiBo2(int n, vector<vector>& edges, bool bDirect)
{
m_vNeiB.resize(n);
for (const auto& v : edges)
{
m_vNeiB[v[0]].emplace_back(v[1]);
if (!bDirect)
{
m_vNeiB[v[1]].emplace_back(v[0]);
}
}
}
vector<vector> m_vNeiB;
};

struct SDecimal
{
SDecimal(int iNum = 0, int iDeno = 1)
{
m_iNum = iNum;
m_iDeno = iDeno;
int iGCD = GCD(abs(m_iNum), abs(m_iDeno));
m_iNum /= iGCD;
m_iDeno /= iGCD;
if (m_iDeno < 0)
{
m_iDeno = -m_iDeno;
m_iNum = -m_iNum;
}
}
SDecimal operator*(const SDecimal& o)const
{
return SDecimal(m_iNum * o.m_iNum, m_iDeno * o.m_iDeno);
}
SDecimal operator/(const SDecimal& o)const
{
return SDecimal(m_iNum * o.m_iDeno, m_iDeno * o.m_iNum);
}
SDecimal operator+(const SDecimal& o)const
{
const int iGCD = GCD(m_iDeno, o.m_iDeno);
const int iDeno = m_iDeno * o.m_iDeno / iGCD;
return SDecimal(m_iNum * (iDeno / m_iDeno) + o.m_iNum * (iDeno / o.m_iDeno), iDeno);
}
SDecimal operator-(const SDecimal& o)const
{
const int iGCD = GCD(m_iDeno, o.m_iDeno);
const int iDeno = m_iDeno * o.m_iDeno / iGCD;
return SDecimal(m_iNum * (iDeno / m_iDeno) - o.m_iNum * (iDeno / o.m_iDeno), iDeno);
}
bool operator==(const SDecimal& o)const
{
return (m_iNum == o.m_iNum) && (m_iDeno == o.m_iDeno);
}
bool operator<(const SDecimal& o)const
{
auto tmp = *this - o;
return tmp.m_iNum < 0;
}
int m_iNum = 0;//分子
int m_iDeno = 1;//分母
};

struct point {
double x, y;
point(double i, double j) :x(i), y(j) {}
};

//算两点距离
double dist(double x1, double y1, double x2, double y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

//计算圆心
point CircleCenter(point& a, point& b, int r) {
//算中点
point mid((a.x + b.x) / 2.0, (a.y + b.y) / 2.0);
//AB距离的一半
double d = dist(a.x, a.y, mid.x, mid.y);
//计算h
double h = sqrt(r * r - d * d);
//计算垂线
point ba(b.x - a.x, b.y - a.y);
point hd(-ba.y, ba.x);
double len = sqrt(hd.x * hd.x + hd.y * hd.y);
hd.x /= len, hd.y /= len;
hd.x *= h, hd.y *= h;
return point(hd.x + mid.x, hd.y + mid.y);
}

class C01LineTree
{
public:
C01LineTree(const vector& nums) :m_iEleSize(nums.size())
{
m_arr.resize(m_iEleSize * 4);
Init(nums, 1, 1, m_iEleSize);
m_vNeedFreshChilds.assign(m_iEleSize * 4, false);
}
void Rotato(int iLeftZeroIndex, int iRightZeroIndex)
{
int iRotatoLeft = iLeftZeroIndex + 1;
int iRotatoRight = iRightZeroIndex + 1;
Rotato(1, 1, m_iEleSize, iRotatoLeft, iRotatoRight);
}
int Query()
{
return m_arr[1];
}
private:
void Rotato(int iSaveIndex, int iDataBegin, int iDataEnd, int iRotatoLeft, int iRotatoRight)
{
if ((iRotatoLeft <= iDataBegin) && (iRotatoRight >= iDataEnd))
{//整个范围需要更新
RotatoSelf(iSaveIndex, iDataBegin, iDataEnd);
return;
}
int iMid = iDataBegin + (iDataEnd - iDataBegin) / 2;
if (m_vNeedFreshChilds[iSaveIndex])
{
RotatoSelf(iSaveIndex * 2, iDataBegin, iMid);
RotatoSelf(iSaveIndex * 2 + 1, iMid + 1, iDataEnd);
m_vNeedFreshChilds[iSaveIndex] = false;
}
if (iMid >= iRotatoLeft)
{
Rotato(iSaveIndex * 2, iDataBegin, iMid, iRotatoLeft, iRotatoRight);
}
if (iMid + 1 <= iRotatoRight)
{
Rotato(iSaveIndex * 2 + 1, iMid + 1, iDataEnd, iRotatoLeft, iRotatoRight);
}
m_arr[iSaveIndex] = m_arr[iSaveIndex * 2] + m_arr[iSaveIndex * 2 + 1];
}
void RotatoSelf(int iSaveIndex, int iDataBegin, int iDataEnd)
{
//总数量 - 翻转后0(翻转前1）的数量
m_arr[iSaveIndex] = (iDataEnd - iDataBegin + 1) - m_arr[iSaveIndex];
//懒惰法，标记本节点的子孙节点没更新
m_vNeedFreshChilds[iSaveIndex] = !m_vNeedFreshChilds[iSaveIndex];
}
void Init(const vector& nums, int iSaveIndex, int iDataBegin, int iDataEnd)
{
if (iDataBegin == iDataEnd)
{
m_arr[iSaveIndex] = nums[iDataBegin - 1];
return;
}
int iMid = iDataBegin + (iDataEnd - iDataBegin) / 2;
Init(nums, iSaveIndex * 2, iDataBegin, iMid);
Init(nums, iSaveIndex * 2 + 1, iMid + 1, iDataEnd);
m_arr[iSaveIndex] = m_arr[iSaveIndex * 2] + m_arr[iSaveIndex * 2 + 1];
}
const int m_iEleSize;
vector m_arr;
vector m_vNeedFreshChilds;
};

/*
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
TreeNode(int x, int iLeft) : val(x), left(new TreeNode(iLeft)), right(nullptr) {}
TreeNode(int x, int iLeft, int iRghit) : val(x), left(new TreeNode(iLeft)), right(new TreeNode(iRghit)) {}
};

namespace NTree
{
TreeNode* Init(const vector& nums, int iNull = 10000)
{
if (0 == nums.size())
{
return nullptr;
}
vector<TreeNode*> ptrs(nums.size() + 1), ptrParent(1);
for (int i = 0; i < nums.size(); i++)
{
if (iNull == nums[i])
{
continue;
}
const int iNO = i + 1;
ptrs[iNO] = new TreeNode(nums[i]);
ptrParent.emplace_back(ptrs[iNO]);
if (1 == iNO)
{
continue;
}
if (iNO & 1)
{//奇数是右支
ptrParent[iNO / 2]->right = ptrs[iNO];
}
else
{
ptrParent[iNO / 2]->left = ptrs[iNO];
}
}
return ptrs[1];
}
}
*/

class Solution {
public:
int minNumberOfSemesters(int n, vector<vector>& relations, int k) {
m_iMaskNum = 1 << n;
vector dp(m_iMaskNum,1000*1000),vPre(m_iMaskNum);
for (const auto& v : relations)
{
vPre[1 << (v[1] - 1)] |= (1 << (v[0] - 1));
}
dp[0] = 0;
for (int i = 0; i < m_iMaskNum; i++)
{
vPre[i] = vPre[i & (-i)] | vPre[i & (i - 1)];
if ((i | vPre[i]) != i)
{
continue;//非发课程：前置课程没学
}
unsigned int uCanStudy = vPre[i] ^ i;
if (bitcount(uCanStudy) <= k)
{
dp[i ] = min(dp[i ], dp[i- uCanStudy] + 1);
continue;
}
for (unsigned int uStudy = uCanStudy; uStudy; uStudy = uCanStudy & (uStudy - 1))
{
if (bitcount(uStudy) <= k)
{
dp[i] = min(dp[i ], dp[i - uStudy] + 1);
}
}
}
return dp.back();
}
int m_iMaskNum;
};
.

【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II-LMLPHP

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II-LMLPHP

02-05 23:58
Powered by LMLPHP ©2024 闻缺陷则喜何志丹 0.001971