作者推荐
本文涉及知识点
LeetCode730. 统计不同回文子序列
给你一个字符串 s ，返回 s 中不同的非空回文子序列个数 。由于答案可能很大，请返回对 109 + 7 取余 的结果。
字符串的子序列可以经由字符串删除 0 个或多个字符获得。
如果一个序列与它反转后的序列一致，那么它是回文序列。
如果存在某个 i , 满足 ai != bi ，则两个序列 a1, a2, … 和 b1, b2, … 不同。
示例 1：
输入：s = ‘bccb’
输出：6
解释：6 个不同的非空回文子字符序列分别为：‘b’, ‘c’, ‘bb’, ‘cc’, ‘bcb’, ‘bccb’。
注意：‘bcb’ 虽然出现两次但仅计数一次。
示例 2：
输入：s = ‘abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba’
输出：104860361
解释：共有 3104860382 个不同的非空回文子序列，104860361 是对 109 + 7 取余后的值。
提示：
1 <= s.length <= 1000
s[i] 仅包含 ‘a’, ‘b’, ‘c’ 或 ‘d’
动态规划
动态规划的转移方程
s[left,right] 中不重复 回文的数量，分类：
- 情况一：长度1的回文： 如果a 出现，则必定有回文a。b,c,d。类似。
- 情况二：长度为2的回文：如果a出现两次则必定有aa。bb或cc或dd类似。
- 情况三：长度为x(x>2)的回文：分四种 a+长度为x-2的回文+a b+长度为x-2的回文+b c+长度为x-2的回文+c d+长度为x-2的回文+d 。如果多个a，取最左、最右的a，b,c,d类似。
first(ch) 是ch在s[left,r]的最小下标，end(ch)是s[left,r]的最大下标。Cnt(ch)表示ch在s[left,r]中出现次数。 转移方程为：
dp[left][right] = Sum′ a ′ , ′ b ′ , ′ c ′ , ′ d ′ c h \Large^{ch}_{'a','b','c','d'}′a′,′b′,′c′,′d′ch(Cnt(ch)>=1 + Cnt(ch)>=2 + dp[first(ch)+1,end(ch)-1]
dp[first(ch)+1,end(ch)-1] 之间不会重复，因为左右各有ch。由于长度不同，所以情况一、情况二、情况三之间不会重复。由于长度不同，不同层次的dp[first(ch)+1,end(ch)-1] 也不会相同。
代码
封装类
template<int MOD = 1000000007> 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(long long 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;; };
核心代码
class Solution { public: int countPalindromicSubsequences(string s) { m_c = s.length(); for (int i = 0; i < s.length(); i++) { m_indexs[s[i] - 'a'].emplace_back(i); } m_dp.assign(m_c, vector<C1097Int<>>(m_c)); m_bDo.assign(m_c, vector<bool>(m_c)); return Cal(0, m_c - 1).ToInt(); } C1097Int<> Cal(const int left, const int r) { if (left> r) { return 0; } if (m_bDo[left][r]) { return m_dp[left][r]; } m_bDo[left][r] = true; C1097Int<> biRet; for (int i = 0; i < 4; i++) { auto it1 = std::lower_bound(m_indexs[i].begin(), m_indexs[i].end(), left); auto it2 = std::upper_bound(m_indexs[i].begin(), m_indexs[i].end(), r); const int iCnt = it2 - it1 ; biRet += min(2, iCnt); if (iCnt >= 2) { biRet += Cal(*it1 + 1, *std::prev(it2) - 1); } } return m_dp[left][r] = biRet; } int m_c; vector<int> m_indexs[4]; vector<vector<C1097Int<>>> m_dp; vector<vector<bool>> m_bDo; };
测试用例
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() { string s; { Solution sln; s = "bccb"; auto res = sln.countPalindromicSubsequences(s); Assert(6, res); } { Solution sln; s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"; auto res = sln.countPalindromicSubsequences(s); Assert(104860361, res); } { Solution sln; s = "dcabdacadbbabdabbacbdbadcacaadddabbdccadbaacdacacaadacccbadaccaddcccabccdcbdccdccaadbbcbcccbaadbccddcdbdbcbbadcdccbcabcddcdbcadcadaccacbdcccaacccbdccdcbbccbdbccbacabdbddaacccdccbaaadbbcdccdbddbbcbaacddbbacdbdcdacddbabdcdcbdcbbbcdcdaacbaacdacadacdcdcdcbdbbbaacccdddddddbbdadcaacaddbabbddccabacccaacbdddccaabbdcdccabadccbcdbdaccdcaadaccdbaaaababddddbdacdbdbaabbabcbbabbabcbadacdbccbbcccabaddddcbadbbadcabdbbddbbaacbdbbbbacdddbcdddbdbdcbcdadcccccdccddacddccbddbacababbbcbcadaddbdddcbddbaadacdbdabbabbbcdbdcccdadcbddbacccbacbcbcdccbadcaabdbacbdcddadcbddcadccddaddcdacdabbcbcdadbaacdadacacadbabcbdcabbdcbdbcbddbcddabbaaabadccdbccddcabddabcdbccaacbabacaccbbaccdcbcbdbcbdbccaddcadaaabcaaaaabcbdcadaacadbbbcdddbaabdcdabdbcacdcaaccdcbabadddddcaabbbacabdadcabdacddcdcadadbddccbabbabbcdbadcccacdcaaaadabcadaabcdaacadccdbbbacddabdadaabcbddcdabcaabbbdcccbcaaabaccbbcbbdbcadcdaadddacdbaccccdbcbbaccadacdbaccadabbbbcabcacabaaccbdcdbaddccdbdbdaacbdbcdadbdaddccbdddaadabdabadbacaabbbbabcdabbcbbddbcaadabadbbdacadadabd"; auto res = sln.countPalindromicSubsequences(s); Assert(369668464, res); } }
2023年1月版
class CBigMath
{
public:
static void AddAssignment(int* dst, const int& iSrc)
{
*dst = (*dst + iSrc) % s_iMod;
}
static void AddAssignment(int* dst, const int& iSrc, const int& iSrc1) { *dst = (*dst + iSrc) % s_iMod; *dst = (*dst + iSrc1) % s_iMod; } static void AddAssignment(int* dst, const int& iSrc, const int& iSrc1, const int& iSrc2) { *dst = (*dst + iSrc) % s_iMod; *dst = (*dst + iSrc1) % s_iMod; *dst = (*dst + iSrc2) % s_iMod; } static void SubAssignment(int* dst, const int& iSrc) { *dst = (s_iMod - iSrc + *dst) % s_iMod; } static int Add(const int& iAdd1, const int& iAdd2) { return (iAdd1 + iAdd2) % s_iMod; } static int Mul(const int& i1, const int& i2) { return((long long)i1 *i2) % s_iMod; }
private:
static const int s_iMod = 1000000007;
};
class Solution {
public:
int countPalindromicSubsequences(string s) {
m_c = s.length();
for (int i = 0; i < 4; i++)
{
m_dp[i].assign(m_c, vector(m_c,-1));
}
int iRet = 0;
for (char ch = ‘a’; ch <= ‘d’; ch++)
{
CBigMath::AddAssignment(&iRet, Rec(ch, s, 0, s.length() - 1));
}
return iRet;
}
int Rec(const char& ch,const string& s, int left, int right)
{
while ((left <= right) && (ch != s[left]))
{
left++;
}
if (left > right)
{
return 0;
}
while ((right > left) && (ch != s[right]))
{
right–;
}
if (left == right)
{
return 1;
}
auto& iNum = m_dp[ch - ‘a’][left][right];
if (-1 != iNum)
{
return iNum;
}
iNum = 2;
for (char ch1 = ‘a’; ch1 <= ‘d’; ch1++)
{
CBigMath::AddAssignment(&iNum, Rec(ch1, s, left + 1, right - 1));
}
return iNum;
}
int m_c;
vector<vector> m_dp[4];
};
2023年6月版
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;
}
}
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 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);
}
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); }
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)MOD2m_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_vConnetNO(iSize), m_vConnectSize(iSize, 1)
{
for (int i = 0; i < iSize; i++)
{
m_vConnetNO[i] = i;
}
m_iConnetSize = iSize;
}
int GetConnectNO(int iNode)
{
int& iConnectNO = m_vConnetNO[iNode];
if (iNode == iConnectNO)
{
return iNode;
}
return iConnectNO = GetConnectNO(iConnectNO);
}
void Union(int iNode1, int iNode2)
{
const int iConnectNO1 = GetConnectNO(iNode1);
const int iConnectNO2 = GetConnectNO(iNode2);
if (iConnectNO1 == iConnectNO2)
{
return ;
}
m_iConnetSize–;
if (iConnectNO1 > iConnectNO2)
{
UnionConnect(iConnectNO1, iConnectNO2);
}
else
{
UnionConnect(iConnectNO2, iConnectNO1);
}
}
int GetAConnectSizeByNode(int iNode)
{
return m_vConnectSize[GetConnectNO(iNode)];
}
bool IsConnect(int iNode1, int iNode2)
{
return GetConnectNO(iNode1) == GetConnectNO(iNode2);
}
int ConnetSize()const
{
return m_iConnetSize;
}
private:
void UnionConnect(int iFrom, int iTo)
{
m_vConnectSize[iTo] += m_vConnectSize[iFrom];
m_vConnetNO[iFrom] = iTo;
}
vector m_vConnetNO;//各点所在联通区域的编号,本联通区域任意一点的索引，为了增加可理解性，用最小索引
vector m_vConnectSize;//各联通区域点数量
int m_iConnetSize;
};
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.ConnetSize() > 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_iNumo.m_iNum, m_iDenoo.m_iDeno);
}
SDecimal operator/(const SDecimal& o)const
{
return SDecimal(m_iNumo.m_iDeno, m_iDenoo.m_iNum);
}
SDecimal operator+(const SDecimal& o)const
{
const int iGCD = GCD(m_iDeno, o.m_iDeno);
const int iDeno = m_iDenoo.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_iDenoo.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(rr - dd);
//计算垂线
point ba(b.x - a.x, b.y - a.y);
point hd(-ba.y, ba.x);
double len = sqrt(hd.xhd.x + hd.yhd.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<int>& 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<int> m_arr; vector<bool> 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 countPalindromicSubsequences(const string s) {
m_c = s.length();
//m_ret.assign(m_c + 1, vector<vector<C1097Int<>>>(m_c, vector<C1097Int<>>(26)));
for (int i = 0; i <= m_c; i++)
{
for (int j = 0; j < m_c; j++)
{
for (int k = 0; k < 4; k++)
{
m_ret[i][j][k] = ((1==i)&&(s[j]==k+‘a’)) ? 1 : 0;
}
}
}
for (int len = 2; len <= m_c; len++)
{
for (int begin = 0; begin + len - 1 < m_c; begin++)
{
for (int iC = 0; iC < 4; iC++)
{
C1097Int<>& iNum = m_ret[len][begin][iC];
int end = begin + len - 1;
if (s[begin] == iC + ‘a’)
{
while (s[end] != iC + ‘a’ )
{
end–;
}
if (begin == end)
{
iNum = 1;
continue;
}
iNum = 2;
for (int iC2 = 0; iC2 < 4; iC2++)
{
iNum += m_ret[(end-1) - (begin + 1) + 1][begin + 1][iC2];
}
continue;
}
iNum = m_ret[len - 1][begin + 1][iC];
}
}
}
C1097Int<> iRet = 0;
for (int iC = 0; iC < 4; iC++)
{
iRet += m_ret[m_c][0][iC];
}
return iRet.ToInt();
}
int m_c;
C1097Int<> m_ret[1001][1000][4];//一维：长度；二维：起始位置；三维：回文起始字符-‘a’
};
2023年8月
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 ELE> static void Out(const vector<ELE>& vec, const string& strColSep = " ", const string& strRowSep = "\r\n") { OutToConsoleInner(vec, strColSep); std::cout << strRowSep.c_str(); } template<class ELE> static void Out(const vector<vector<ELE>>& 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 ELE> static void Out(const std::map<ELE, 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 ELE > static void Out(const ELE& 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;
};
//通过 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 ELE& 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(ELE* seft, const ELE& other)
{
*seft = min(*seft, other);
}
template
void MaxSelf(ELE* seft, const ELE& 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); } //返回第一个大于等于iMax的节点索引，没有大于等于iMax，则返回-1 int GetFirstMaxIndex(int iMax) { int iNO = 1; if (m_vData[1] < iMax) { return -1; } int left = 1, r = m_iArrSize; while (r > left) { const int mid = (left + r) / 2; if (m_vData[iNO * 2] < iMax) { iNO = iNO * 2 + 1; left = mid + 1; } else { iNO *= 2; r = mid; } } return r - 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] = 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] = 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); } ELE Query(int iLeftIndex, int iRightIndex) { return Query(1, 1, m_iEleSize, iLeftIndex + 1, iRightIndex + 1); }
private:
ELE 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;
ELE 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] += ELE(iValue) * (min(iDataRight, iOpeRight) - max(iDataLeft, iOpeLeft) + 1);
if ((iOpeLeft <= iDataLeft) && (iOpeRight >= iDataRight))
{
m_vChildAdd[iNode] += ELE(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<ELE> m_vArr; vector<int> m_vChildAdd;
};
template
class CTreeArr
{
public:
CTreeArr(int iSize) :m_vData(iSize + 1)
{
} void Add(int index, ELE value) { index++; while (index < m_vData.size()) { m_vData[index] += value; index += index & (-index); } } ELE Sum(int index) { index++; ELE ret = 0; while (index) { ret += m_vData[index]; index -= index & (-index); } return ret; } ELE 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;
}
}
//iMinValue将被编码为0,iMaxValue被编码为iMaxValue-iMinValue。
CHashStr(const int* data,int len, int iMinValue = 0, int iMaxValue = 9 ) {
m_c = len;
m_vP.resize(m_c + 1);
m_vP[0] = 1;
m_vHash.resize(m_c + 1);
const int P = iMaxValue - iMinValue + 1;
for (int i = 0; i < m_c; i++)
{
const int iCurCode = data[i] - iMinValue;
assert((iCurCode >= 0) && (iCurCode < P));
m_vHash[i + 1] = m_vHash[i] * P + iCurCode;
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);
}
C2HashStr(const int* data, int len, int iMinValue = 0, int iMaxValue = 9)
{
m_pHash1 = std::make_unique<CHashStr<>>(data, len, iMinValue, iMaxValue);
m_pHash2 = std::make_unique < CHashStr>(data, len, iMinValue, iMaxValue);
}
//包括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];
};
template<class T > void ShellSort(vector<T>& v) { T tMax = *std::max_element(v.begin(), v.end()); T exp = 1; while (tMax >= exp) { int vNums[10] = { 0 }; for (const auto& n : v) { vNums[n / exp % 10]++; } int indexs[10] = { 0 }; for (int i = 1; i < 10; i++) { indexs[i] = vNums[i - 1] + indexs[i-1]; } vector<T> tmp(v.size()); for (const auto& n : v) { const int cur = n / exp % 10; tmp[indexs[cur]] = n; indexs[cur]++; } v.swap(tmp); exp *= 10; } } template<class T,class _Pr = less<T> > void MergeSort(vector<T>& v, const vector<T>& v1, const vector<T>& v2) { int i1 = 0, i2 = 0; while ((i1 < v1.size()) && (i2 < v2.size())) { if (std::less()(v1[i1], v2[i2])) { v.emplace_back(v1[i1++]); } else { v.emplace_back(v2[i2++]); } } while (i1 < v1.size()) { v.emplace_back(v1[i1++]); } while (i2 < v2.size()) { v.emplace_back(v2[i2++]); } }
}
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 ELE> void PopIsTopIsDel(ELE& 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,int iBase=0)
{
m_vNeiB.resize(n);
for (const auto& v : edges)
{
m_vNeiB[v[0]- iBase].emplace_back(v[1]- iBase);
if (!bDirect)
{
m_vNeiB[v[1]- iBase].emplace_back(v[0]- iBase);
}
}
}
vector<vector> m_vNeiB;
};
class CNeiBo3
{
public:
CNeiBo3(int n, vector<vector>& edges, bool bDirect, int iBase = 0)
{
m_vNeiB.resize(n);
for (const auto& v : edges)
{
m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase,v[2]);
if (!bDirect)
{
m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase,v[2]);
}
}
}
vector<vector<std::pair<int,int>>> 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<int>& 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<int> m_arr; vector<bool> m_vNeedFreshChilds;
};
template<class ELE, class ResultType, ELE minEle, ELE maxEle>
class CLowUperr
{
public:
CLowUperr(int iResutlCount)
{
m_iResutlCount = iResutlCount;
m_vPre.assign(4, vector(iResutlCount));
}
void Init(const ELE* pLower, const ELE* pHigh, int iNum)
{
if (iNum <= 0)
{
return;
}
InitPre(pLower, pHigh);
iNum–;
while (iNum–)
{
pLower++;
pHigh++;
vector<vector> dp(4, vector(m_iResutlCount));
OnInitDP(dp);
//处理非边界
for (auto tmp = minEle; tmp <= maxEle; tmp++)
{
OnDo(dp, 0, 0, tmp - minEle);
}
//处理下边界
OnDo(dp, 1, 1, *pLower - minEle);
for (auto tmp = *pLower + 1; tmp <= maxEle; tmp++)
{
OnDo(dp, 1, 0, tmp - minEle);
}
//处理上边界
OnDo(dp, 2, 2, *pHigh - minEle);
for (auto tmp = minEle; tmp < *pHigh; tmp++)
{
OnDo(dp, 2, 0, tmp - minEle);
}
//处理上下边界
if (*pLower == *pHigh)
{
OnDo(dp, 3, 3, *pLower - minEle);
}
else
{
OnDo(dp, 3, 1, *pLower - minEle);
for (auto tmp = *pLower + 1; tmp < *pHigh; tmp++)
{
OnDo(dp, 3, 0, tmp - minEle);
}
OnDo(dp, 3, 2, *pHigh - minEle);
}
m_vPre.swap(dp);
}
}
ResultType Total(int iMinIndex, int iMaxIndex)
{
ResultType ret;
for (int status = 0; status < 4; status++)
{
for (int index = iMinIndex; index <= iMaxIndex; index++)
{
ret += m_vPre[status][index];
}
}
return ret;
}
protected:
int m_iResutlCount; virtual void OnDo(vector<vector<ResultType>>& dp, int preStatus, int curStatus, int cur) = 0; virtual void OnInitDP(vector<vector<ResultType>>& dp) { } virtual void InitPre(const ELE* const pLower, const ELE* const pHigh) { for (ELE j = *pLower; j <= *pHigh; j++) { const ELE cur = j - minEle; if (*pLower == j) { const int index = *pLower == *pHigh ? 3 : 1; if (cur < m_iResutlCount) { m_vPre[index][cur] = 1; } } else if (*pHigh == j) { if (cur < m_iResutlCount) { m_vPre[2][cur] = 1; } } else { if (cur < m_iResutlCount) { m_vPre[0][cur] = 1; } } } } vector<vector<ResultType>> m_vPre;
};
//马拉车计算回文回文
class CPalindrome
{
public:
//vOddHalfLen[i]表示 以s[i]为中心，且长度为奇数的最长回文的半长，包括s[i]
//比如：“aba” vOddHalfLen[1]为2 “abba” vEvenHalfLen[1]为2
static void CalHalfLen(vector& vOddHalfLen, vector& vEvenHalfLen, const string& s)
{
vector v;
for (const auto& ch : s)
{
v.emplace_back(ch);
v.emplace_back(‘*’);
}
v.pop_back();
const int len = v.size(); vector<int> vHalfLen(len); int center = -1, r = -1; //center是对称中心,r是其右边界（闭） for (int i = 0; i < len; i++) { int tmp = 1; if (i <= r) { int pre = center - (i - center); tmp = min(vHalfLen[pre], r - i + 1); } for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++); vHalfLen[i] = --tmp; const int iNewR = i + tmp - 1; if (iNewR > r) { r = iNewR; center = i; } } vOddHalfLen.resize(s.length()); vEvenHalfLen.resize(s.length()); for (int i = 0; i < len; i++) { if (i & 1) { vEvenHalfLen[i / 2] = vHalfLen[i] / 2; } else { vOddHalfLen[i / 2] = (vHalfLen[i] + 1) / 2; } } } //vOddLen[i]表示以i开始，奇数长度 最长回文 //vEvenLen[i]表示以i开始，偶数长度 最长回文 static void CalLen(vector<int>& vOddLen, vector<int>& vEvenLen, const string& s) { vector<char> v; for (const auto& ch : s) { v.emplace_back(ch); v.emplace_back('*'); } v.pop_back(); const int len = v.size(); vector<int> vHalfLen(len); int center = -1, r = -1; //center是对称中心,r是其右边界（闭） for (int i = 0; i < len; i++) { int tmp = 1; if (i <= r) { int pre = center - (i - center); tmp = min(vHalfLen[pre], r - i + 1); } for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++); vHalfLen[i] = --tmp; const int iNewR = i + tmp - 1; if (iNewR > r) { r = iNewR; center = i; } } vOddLen.resize(s.length()); vEvenLen.resize(s.length()); for (int i = 0; i < len; i++) { const int iHalfLen = (i & 1) ? (vHalfLen[i] / 2) : ((vHalfLen[i] + 1) / 2); const int left = i / 2 - iHalfLen + 1; if (i & 1) { vEvenLen[left] = vHalfLen[i] / 2*2; } else { vOddLen[left] = (vHalfLen[i] + 1) / 2*2-1; } } }
};
//使用实例
//vector vOddHalfLen, vEvenHalfLen;
//CPalindrome::Do(vOddHalfLen, vEvenHalfLen, s);
class CKMP
{
public:
static vector Next(const string& s)
{
const int len = s.length();
vector vNext(len, -1);
for (int i = 1; i < len; i++)
{
int next = vNext[i - 1];
while ((-1 != next) && (s[next + 1] != s[i]))
{
next = vNext[next];
}
vNext[i] = next + (s[next + 1] == s[i]);
}
return vNext;
}
};
template
class CMergeSortIndex
{
public:
CMergeSortIndex(const vector& nums) :m_nums(nums)
{
m_c = nums.size();
m_vIndexs.resize(nums.size());
iota(m_vIndexs.begin(), m_vIndexs.end(), 0);
}
void SortIndex(int left, int right)
{
if (right - left <= 1)
{
return;
}
const int mid = left + (right - left) / 2;
SortIndex(left, mid);
SortIndex(mid, right);
OnSortLeftRightEnd(left, mid, right);
//nums的[left,mid) 和[mid,right)分别排序
m_vSortIndexs.clear();
int i1 = left, i2 = mid;
while ((i1 < mid) && (i2 < right))
{
if (m_nums[m_vIndexs[i1]] > m_nums[m_vIndexs[i2]])
{
m_vSortIndexs.emplace_back(m_vIndexs[i2++]);
}
else
{
m_vSortIndexs.emplace_back(m_vIndexs[i1]);
OnAdd1(i1++, i2, left, mid, right);
}
}
while (i1 < mid)
{
m_vSortIndexs.emplace_back(m_vIndexs[i1]);
OnAdd1(i1++, i2, left, mid, right);
}
while (i2 < right)
{
m_vSortIndexs.emplace_back(m_vIndexs[i2++]);
}
for (int i = 0; i < m_vSortIndexs.size(); i++)
{
m_vIndexs[i + left] = m_vSortIndexs[i];
}
}
vector Sort()
{
SortIndex(0, m_c);
vector vRet(m_c);
for (int i = 0; i < m_c; i++)
{
vRet[i] = m_nums[m_vIndexs[i]];
}
return vRet;
}
protected:
virtual void OnSortLeftRightEnd(int left, int mid, int right)
{
} virtual void OnAdd1(int i1, int i2, int left, int mid, int right) { } int m_c; const vector<T>& m_nums; vector<int> m_vIndexs; vector<int> m_vSortIndexs;
};
template<class T = int, class _Pr = std::less >
class CTopK
{
public:
CTopK(int k) :m_iMinNum(k)
{
} void Do(vector<T>& m_v, T* begin, int num) { for (; num; begin++, num--) { while (m_v.size() && _Pr()(*begin, m_v.back()) && (m_iMinNum - m_v.size() + 1 <= num)) { m_v.pop_back(); } if (m_v.size() < m_iMinNum) { m_v.push_back(*begin); } } }
protected:
const int m_iMinNum;
};
class CUnionFindDirect
{
public:
CUnionFindDirect(int iSize)
{
m_vRoot.resize(iSize);
iota(m_vRoot.begin(), m_vRoot.end(), 0);
}
void Connect(bool& bConflic, bool& bCyc, int iFrom, int iTo)
{
bConflic = bCyc = false;
if (iFrom != m_vRoot[iFrom])
{
bConflic = true;
}
Fresh(iTo); if (m_vRoot[iTo] == iFrom) { bCyc = true; } if (bConflic || bCyc) { return; } m_vRoot[iFrom] = m_vRoot[iTo]; }
private:
int Fresh(int iNode)
{
if (m_vRoot[iNode] == iNode)
{
return iNode;
}
return m_vRoot[iNode] = Fresh(m_vRoot[iNode]);
}
vector m_vRoot;
};
#define MACRO_BEGIN_END(n) n.begin(),n.end()
#define MacroTopSort(que,vNeiBo)
while (que.size())
{
const int cur = que.front();
que.pop();
for (const auto& next : vNeiBo[cur])
{
vDeg[next]–;
if (1 == vDeg[next])
{
}
}
}
#define Macro2DBFS(queRowCol,m_r,m_c)
queue<pair<int, int>> queRowCol;
vector<vector> vDis(m_r, vector(m_c, -1));
while (queRowCol.size())
{
const auto [r, c] = queRowCol.front();
queRowCol.pop();
auto Move = [&vDis, &queRowCol, this](int r, int c, int iDis)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
if (-1 != vDis[r][c])
{
return;
}
vDis[r][c] = iDis;
queRowCol.emplace(r, c);
};
const int iDis = vDis[r][c] + 1;
Move(r + 1, c, iDis);
Move(r - 1, c, iDis);
Move(r, c + 1, iDis);
Move(r, c - 1, iDis);
}
/*
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 countPalindromicSubsequences(string s) {
m_c = s.length();
memset(m_bres, 0, sizeof(m_bres));
m_res.assign(m_c, vector<C1097Int<>>(m_c));
for (int i = 0; i < m_c; i++)
{
m_indexs[s[i] - ‘a’].emplace_back(i);
}
return (Rec(0, m_c - 1)-1).ToInt();
}
C1097Int<> Rec(int left, int r)
{
if (r < left)
{
return 1;
}
if (m_bres[left][r])
{
return m_res[left][r];
}
C1097Int<> biRet=1;
for (int i = 0; i < 4; i++)
{
auto it = std::lower_bound(m_indexs[i].begin(), m_indexs[i].end(), left);
auto ij = std::upper_bound(m_indexs[i].begin(), m_indexs[i].end(), r);
int iNum = ij - it;
if (0 == iNum)
{
continue;
}
biRet += 1;
if (iNum < 2)
{
continue;
}
ij–;
biRet += Rec(*it + 1, *ij - 1);
}
m_bres[left][r] = true;
return m_res[left][r] = biRet;
}
vector<vector<C1097Int<>>> m_res; bool m_bres[1000][1000]; int m_c; vector<int> m_indexs[4];
};
