荆门网站建设服务,专业建设思路,做uml图网站,太平洋建设21局网站作者推荐
【动态规划】【数学】【C算法】18赛车
涉及知识点
动态规划 二分查找
LeetCode730. 统计不同回文子序列
给你一个字符串 s #xff0c;返回 s 中不同的非空回文子序列个数 。由于答案可能很大#xff0c;请返回对 109 7 取余 的结果。 字符串的子序列可以经由…作者推荐
【动态规划】【数学】【C算法】18赛车
涉及知识点
动态规划 二分查找
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(x2)的回文分四种 a长度为x-2的回文a b长度为x-2的回文b c长度为x-2的回文c d长度为x-2的回文d 。如果多个a取最左、最右的ab,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] 也不会相同。
代码
封装类
templateint 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, vectorC1097Int(m_c));m_bDo.assign(m_c, vectorbool(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;vectorint m_indexs[4];vectorvectorC1097Int m_dp;vectorvectorbool m_bDo;
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT 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; vectorvector 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 (i1) % 25) { std::cout std::endl; } else if (0 (i 1) % 5) { std::cout strSep.c_str(); } } }
class CConsole { public :
templateclass T
static void Out(const vectorT vec, const string strColSep , const string strRowSep \r\n)
{OutToConsoleInner(vec, strColSep);std::cout strRowSep.c_str();
}templateclass T
static void Out(const vectorvectorT 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();}
}templateclass T
static void Out(const std::mapT, std::vectorint 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();
}templateclass 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]); } }
//[iBeginiEnd]之和 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_queueint,vector,std::greater m_ladders; unsigned int m_uLadderNum; long long m_iEaqualBicks 0; };
struct CPeo { CPeo(string strName, CPeo* pParentnullptr) { m_strName strName; m_pParent pParent; } string m_strName; vectorCPeo* m_childs; CPeo* m_pParent nullptr; };
class CNeighborTable { public: void Init(const vectorvector edges) { }vectorvectorint 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) { }templateclass ITvoid Add(IT begin, IT end){CTrieiTypeNum, cBegin * pNode this;for (; begin ! end; begin){pNode pNode-AddChar(*begin).get();}}templateclass ITbool 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_sharedCTrieiTypeNum, 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::vectorstd::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::setstring 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_ptrCWords 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 tmp9; (tmp2)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_mapint, 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, iLeftIndex1, iRightIndex1, 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;vectorT m_vArr;vectorint m_vChildAdd;};
template class CTreeArr { public: CTreeArr(int iSize) :m_vData(iSize1) { }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; vectorC1097Int m_vP; vectorC1097Int m_vHash; };
template class C2HashStr { public: C2HashStr(string s) { m_pHash1 std::make_uniqueCHashStr(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_ptrCHashStr m_pHash1; std::unique_ptrCHashStr 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;C1097IntMOD m_iHash;C1097IntMOD 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::pairClass1, int p, Class1 iData) { return p.first iData; } templateclass Class1bool Greater(const std::pairClass1, int p, Class1 iData){return p.first iData;}templateclass _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;}
};templateclass _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;
}
templateclass T
void PopIsTopIsDel(T que, std::unordered_multisetint 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_queueint m_queTopMax;
std::priority_queueint, vectorint, greaterint m_queTopMin;
std::unordered_multisetint m_setTopMaxDel, m_setTopMinDel;};
template class CDistanceGrid { public: CDistanceGrid(const vectorvector 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)
{ vectorvectorint vDis(iMaxRow, vectorint(iMaxCol, INT_MAX));auto Add [vDis, this](std::priority_queuepairint, int, vectorstd::pairint, int, greaterpairint, 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_queuepairint, int, vectorstd::pairint, int, greaterpairint, 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_queuepairint, int, vectorstd::pairint, int, greaterpairint, 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 vectorvector m_grid;
};
class CBFSGridDist { public: CBFSGridDist(const vectorvector 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 vectorvector Dis()const { return m_vDis; } const vectorvector m_bCanVisit; private: //INT_MAX/2 表示无法到达 void Dist(int r, int c) { m_vDis.assign(m_r, vector(m_c, INT_MAX / 2)); vectorvector vHasDo(m_r, vector(m_c)); std::queuestd::pairint, 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);}}
vectorvectorint 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();
}
vectorstd::string m_vVars;
int m_iCoefficient1;//系数、倍率
std::string ToString()const
{std::ostringstream os;os m_iCoefficient ;for (const autos : 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;
}
vectorstd::string ToStrings()const
{vectorstd::string vRet;for (const auto item : m_items){if (0 item.m_iCoefficient){continue;}vRet.emplace_back(item.ToString());}return vRet;
}
std::setSValueItem 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;
vectorbool m_bDels;
vectorint 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 vectorint 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 vectorvectorint edges)
{for (const auto v : edges){Add(v);}
}
void Add(const vectorint 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;
}
vectorbool m_bDo;
vectorlong long m_vDis;
vector vectorstd::pairint, int m_vNeiTable;
long long m_iMST 0;};
typedef pairlong long,int PAIRLLI; class CDis { public: static void Dis(vector vDis, int start, const vectorvectorpairint, int vNeiB) { std::priority_queuePAIRLLI, 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 vectorvectorpairint, int vNeiB)
{m_vDis.assign(m_iSize, -1);m_vPre.assign(m_iSize, -1);vectorbool 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, vectorvectorint edges)
{vectorvectorpairint, 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 vectorlong long DIS;
const vectorint PRE;private: const int m_iSize; vector m_vDis;//各点到起点的最短距离 vector m_vPre;//最短路径的前一点 };
class CNeiBo2 { public: CNeiBo2(int n, vectorvector 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]); } } } vectorvector m_vNeiB; };
struct SDecimal { SDecimal(int iNum0, 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_iNum0;//分子 int m_iDeno1;//分母 };
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 vectorint 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;
vectorint m_arr;
vectorbool 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; } vectorTreeNode* 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, vectorvectorC1097Int(m_c, vectorC1097Int(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] ((1i)(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:
templateclass ELE
static void Out(const vectorELE vec, const string strColSep , const string strRowSep \r\n)
{OutToConsoleInner(vec, strColSep);std::cout strRowSep.c_str();
}templateclass ELE
static void Out(const vectorvectorELE 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();}
}templateclass ELE
static void Out(const std::mapELE, std::vectorint 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();
}templateclass 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]); } }
//[iBeginiEnd]之和 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_queueint, 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; vectorCPeo* 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) {
}
templateclass IT
void Add(IT begin, IT end)
{CTrieiTypeNum, cBegin* pNode this;for (; begin ! end; begin){pNode pNode-AddChar(*begin).get();}
}
templateclass 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_sharedCTrieiTypeNum, 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::vectorstd::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::setstring 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_ptrCWords 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_mapint, 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;
vectorELE m_vArr;
vectorint 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; vectorC1097Int m_vP; vectorC1097Int m_vHash; };
template class C2HashStr { public: C2HashStr(string s) { m_pHash1 std::make_uniqueCHashStr(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_uniqueCHashStr(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_ptrCHashStr m_pHash1; std::unique_ptrCHashStr 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;
C1097IntMOD m_iHash;
C1097IntMOD 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]; };
templateclass T
void ShellSort(vectorT 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];}vectorT 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;}
}templateclass T,class _Pr lessT
void MergeSort(vectorT v, const vectorT v1, const vectorT 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::pairClass1, int p, Class1 iData) { return p.first iData; }
templateclass Class1
bool Greater(const std::pairClass1, int p, Class1 iData)
{return p.first iData;
}templateclass _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;}
};templateclass _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;
}
templateclass ELE
void PopIsTopIsDel(ELE que, std::unordered_multisetint 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_queueint m_queTopMax;
std::priority_queueint, vectorint, greaterint m_queTopMin;
std::unordered_multisetint m_setTopMaxDel, m_setTopMinDel;};
template class CDistanceGrid { public: CDistanceGrid(const vectorvector 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)
{vectorvectorint vDis(iMaxRow, vectorint(iMaxCol, INT_MAX));auto Add [vDis, this](std::priority_queuepairint, int, vectorstd::pairint, int, greaterpairint, 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_queuepairint, int, vectorstd::pairint, int, greaterpairint, 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_queuepairint, int, vectorstd::pairint, int, greaterpairint, 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 vectorvector m_grid;
};
class CBFSGridDist { public: CBFSGridDist(const vectorvector 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 vectorvector Dis()const { return m_vDis; } const vectorvector m_bCanVisit; private: //INT_MAX/2 表示无法到达 void Dist(int r, int c) { m_vDis.assign(m_r, vector(m_c, INT_MAX / 2)); vectorvector vHasDo(m_r, vector(m_c)); std::queuestd::pairint, 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);}}
vectorvectorint 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();
}
vectorstd::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;
}
vectorstd::string ToStrings()const
{vectorstd::string vRet;for (const auto item : m_items){if (0 item.m_iCoefficient){continue;}vRet.emplace_back(item.ToString());}return vRet;
}
std::setSValueItem 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;
vectorbool m_bDels;
vectorint 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;
}
vectorint GetNodeCountOfRegion()//各联通区域的节点数量
{const int iNodeSize m_vNodeToRegion.size();vectorint 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 vectorint 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 vectorvectorint edges)
{for (const auto v : edges){Add(v);}
}
void Add(const vectorint 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;
}
vectorbool m_bDo;
vectorlong long m_vDis;
vector vectorstd::pairint, int m_vNeiTable;
long long m_iMST 0;};
typedef pairlong long, int PAIRLLI; class CDis { public: static void Dis(vector vDis, int start, const vectorvectorpairint, int vNeiB) { std::priority_queuePAIRLLI, 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 vectorvectorpairint, int vNeiB)
{m_vDis.assign(m_iSize, -1);m_vPre.assign(m_iSize, -1);vectorbool 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, vectorvectorint edges)
{vectorvectorpairint, 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 vectorlong long DIS;
const vectorint PRE;private: const int m_iSize; vector m_vDis;//各点到起点的最短距离 vector m_vPre;//最短路径的前一点 };
class CNeiBo2 { public: CNeiBo2(int n, vectorvector edges, bool bDirect,int iBase0) { 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); } } } vectorvector m_vNeiB; };
class CNeiBo3 { public: CNeiBo3(int n, vectorvector 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]); } } } vectorvectorstd::pairint,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 vectorint 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;
vectorint m_arr;
vectorbool m_vNeedFreshChilds;};
templateclass 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; vectorvector 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(vectorvectorResultType dp, int preStatus, int curStatus, int cur) 0;
virtual void OnInitDP(vectorvectorResultType 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;}}}
}
vectorvectorResultType 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();vectorint 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(vectorint vOddLen, vectorint vEvenLen, const string s)
{vectorchar v;for (const auto ch : s){v.emplace_back(ch);v.emplace_back(*);}v.pop_back();const int len v.size();vectorint 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 vectorT m_nums;
vectorint m_vIndexs;
vectorint m_vSortIndexs;};
templateclass T int, class _Pr std::less class CTopK { public: CTopK(int k) :m_iMinNum(k) {
}
void Do(vectorT 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) queuepairint, int queRowCol; vectorvector 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; } vectorTreeNode* 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, vectorC1097Int(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 biRet1; 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; }
vectorvectorC1097Int m_res;
bool m_bres[1000][1000];
int m_c;
vectorint m_indexs[4];}; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
