乌市地区建设工程门户网站,crm客户管理系统软件,win主机安装wordpress,北京网站制作招聘网本文涉及知识点
C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 CDFS 树上倍增 LCA
P10391 [蓝桥杯 2024 省 A] 零食采购
题目描述
小蓝准备去星际旅行#xff0c;出发前想在本星系采购一些零食#xff0c;星系内有 nnn 颗星球#x…本文涉及知识点
C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 CDFS 树上倍增 LCA
P10391 [蓝桥杯 2024 省 A] 零食采购
题目描述
小蓝准备去星际旅行出发前想在本星系采购一些零食星系内有 nnn 颗星球由 n−1n-1n−1 条航路连接为连通图第 iii 颗星球卖第 cic_ici 种零食特产。小蓝想出了 qqq 个采购方案第 iii 个方案的起点为星球 sis_isi 终点为星球 tit_iti 对于每种采购方案小蓝将从起点走最短的航路到终点并且可以购买所有经过的星球上的零食包括起点终点请计算每种采购方案最多能买多少种不同的零食。
输入格式
输入的第一行包含两个正整数 nnnqqq用一个空格分隔。 第二行包含 nnn 个整数 c1,c2,⋯,cnc_1,c_2,\cdots, c_nc1,c2,⋯,cn相邻整数之间使用一个空格分隔。 接下来 n−1n - 1n−1 行第 iii 行包含两个整数 ui,viu_i,v_iui,vi用一个空格分隔表示一条 航路将星球 uiu_iui 与 viv_ivi 相连。 接下来 qqq 行第 iii 行包含两个整数 $s_i , t_i $用一个空格分隔表示一个采购方案。
输出格式
输出 qqq 行每行包含一个整数依次表示每个采购方案的答案。
输入输出样例 #1
输入 #1
4 2
1 2 3 1
1 2
1 3
2 4
4 3
1 4输出 #1
3
2说明/提示
第一个方案路线为 {4,2,1,3}\{4, 2, 1, 3\}{4,2,1,3}可以买到第 1,2,31, 2, 31,2,3 种零食 第二个方案路线为 {1,2,4}\{1, 2, 4\}{1,2,4}可以买到第 1,21, 21,2 种零食。
对于 20% 的评测用例$1 ≤ n, q ≤ 5000 $ 对于所有评测用例1≤n,q≤1051≤ci≤201≤ui,vi≤n1≤si,ti≤n1 ≤ n, q ≤ 10^51 ≤ c_i ≤ 201 ≤ u_i , v_i ≤ n1 ≤ s_i , t_i ≤ n1≤n,q≤1051≤ci≤201≤ui,vi≤n1≤si,ti≤n。
DFS 树上前缀和 LCA
以1(0)为根cnt[i][j]记录第j个星球是否有货物i。preSum[i][j]节点j到根节点整个路径包括货物i的星球数量。初始化只需要一次DFS。时间复杂度O(20n) 每次查询令u和v的最近公共祖先g如果preSum[i][u]preSum[i][v]-2preSum[i][g]cnt[i][g] 0则可以买到货物i。 是否复杂度O(20qlogn)
代码
核心代码
#include iostream
#include sstream
#include vector
#includemap
#includeunordered_map
#includeset
#includeunordered_set
#includestring
#includealgorithm
#includefunctional
#includequeue
#include stack
#includeiomanip
#includenumeric
#include math.h
#include climits
#includeassert.h
#includecstring
#includelist
#includearray#include bitset
using namespace std;templateclass T1, class T2
std::istream operator (std::istream in, pairT1, T2 pr) {in pr.first pr.second;return in;
}templateclass T1, class T2, class T3
std::istream operator (std::istream in, tupleT1, T2, T3 t) {in get0(t) get1(t) get2(t);return in;
}templateclass T1, class T2, class T3, class T4
std::istream operator (std::istream in, tupleT1, T2, T3, T4 t) {in get0(t) get1(t) get2(t) get3(t);return in;
}templateclass T1, class T2, class T3, class T4, class T5, class T6, class T7
std::istream operator (std::istream in, tupleT1, T2, T3, T4,T5,T6,T7 t) {in get0(t) get1(t) get2(t) get3(t) get4(t) get5(t) get6(t);return in;
}templateclass T int
vectorT Read() {int n;cin n;vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}
templateclass T int
vectorT ReadNotNum() {vectorT ret;T tmp;while (cin tmp) {ret.emplace_back(tmp);if (\n cin.get()) { break; }}return ret;
}templateclass T int
vectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {cin ret[i];}return ret;
}templateint N 1000000
class COutBuff
{
public:COutBuff() {m_p puffer;}templateclass Tvoid write(T x) {int num[28], sp 0;if (x 0)*m_p -, x -x;if (!x)*m_p 48;while (x)num[sp] x % 10, x / 10;while (sp)*m_p num[sp--] 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p strlen(sz);AuotToFile();}inline void write(char ch){*m_p ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer N - 100) {ToFile();}}char puffer[N], * m_p;
};templateint N 1000000
class CInBuff
{
public:inline CInBuff() {}inline CInBuffN operator(char ch) {FileToBuf();while ((\r *S) || (\n *S) || ( *S)) { S; }//忽略空格和回车ch *S;return *this;}inline CInBuffN operator(int val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f | (*S -);while (isdigit(*S))x (x 1) (x 3) (*S ^ 48);val f ? -x : x; S;//忽略空格换行 return *this;}inline CInBuff operator(long long val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f | (*S -);while (isdigit(*S))x (x 1) (x 3) (*S ^ 48);val f ? -x : x; S;//忽略空格换行return *this;}templateclass T1, class T2inline CInBuff operator(pairT1, T2 val) {*this val.first val.second;return *this;}templateclass T1, class T2, class T3inline CInBuff operator(tupleT1, T2, T3 val) {*this get0(val) get1(val) get2(val);return *this;}templateclass T1, class T2, class T3, class T4inline CInBuff operator(tupleT1, T2, T3, T4 val) {*this get0(val) get1(val) get2(val) get3(val);return *this;}templateclass T intinline CInBuff operator(vectorT val) {int n;*this n;val.resize(n);for (int i 0; i n; i) {*this val[i];}return *this;}templateclass T intvectorT Read(int n) {vectorT ret(n);for (int i 0; i n; i) {*this ret[i];}return ret;}templateclass T intvectorT Read() {vectorT ret;*this ret;return ret;}
private:inline void FileToBuf() {const int canRead m_iWritePos - (S - buffer);if (canRead 100) { return; }if (m_bFinish) { return; }for (int i 0; i canRead; i){buffer[i] S[i];//memcpy出错 }m_iWritePos canRead;buffer[m_iWritePos] 0;S buffer;int readCnt fread(buffer m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt 0) { m_bFinish true; return; }m_iWritePos readCnt;buffer[m_iWritePos] 0;S buffer;}int m_iWritePos 0; bool m_bFinish false;char buffer[N 10], * S buffer;
};class CNeiBo
{
public:static vectorvectorint Two(int n, const vectorpairint, int edges, bool bDirect, int iBase 0){vectorvectorint vNeiBo(n);for (const auto [i1, i2] : edges){vNeiBo[i1 - iBase].emplace_back(i2 - iBase);if (!bDirect){vNeiBo[i2 - iBase].emplace_back(i1 - iBase);}}return vNeiBo;}static vectorvectorint Two(int n, const vectorvectorint edges, bool bDirect, int iBase 0){vectorvectorint vNeiBo(n);for (const auto v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);}}return vNeiBo;}static vectorvectorstd::pairint, int Three(int n, vectorvectorint edges, bool bDirect, int iBase 0){vectorvectorstd::pairint, int vNeiBo(n);for (const auto v : edges){vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);if (!bDirect){vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);}}return vNeiBo;}static vectorvectorstd::pairint, int Three(int n, const vectortupleint, int, int edges, bool bDirect, int iBase 0){vectorvectorstd::pairint, int vNeiBo(n);for (const auto [u, v, w] : edges){vNeiBo[u - iBase].emplace_back(v - iBase, w);if (!bDirect){vNeiBo[v - iBase].emplace_back(u - iBase, w);}}return vNeiBo;}static vectorvectorint Mat(vectorvectorint neiBoMat){vectorvectorint neiBo(neiBoMat.size());for (int i 0; i neiBoMat.size(); i){for (int j i 1; j neiBoMat.size(); j){if (neiBoMat[i][j]){neiBo[i].emplace_back(j);neiBo[j].emplace_back(i);}}}return neiBo;}
};class CBFSLeve {
public:static vectorint Leve(const vectorvectorint neiBo, vectorint start) {vectorint leves(neiBo.size(), -1);for (const auto s : start) {leves[s] 0;}for (int i 0; i start.size(); i) {for (const auto next : neiBo[start[i]]) {if (-1 ! leves[next]) { continue; }leves[next] leves[start[i]] 1;start.emplace_back(next);}}return leves;}templateclass NextFunstatic vectorint Leve(int N, NextFun nextFun, vectorint start) {vectorint leves(N, -1);for (const auto s : start) {leves[s] 0;}for (int i 0; i start.size(); i) {auto nexts nextFun(start[i]);for (const auto next : nexts) {if (-1 ! leves[next]) { continue; }leves[next] leves[start[i]] 1;start.emplace_back(next);}}return leves;}static vectorvectorint LeveNodes(const vectorint leves) {const int iMaxLeve *max_element(leves.begin(), leves.end());vectorvectorint ret(iMaxLeve 1);for (int i 0; i leves.size(); i) {ret[leves[i]].emplace_back(i);}return ret;};static vectorint LeveSort(const vectorint leves) {const int iMaxLeve *max_element(leves.begin(), leves.end());vectorvectorint leveNodes(iMaxLeve 1);for (int i 0; i leves.size(); i) {leveNodes[leves[i]].emplace_back(i);}vectorint ret;for (const auto v : leveNodes) {ret.insert(ret.end(), v.begin(), v.end());}return ret;};
};
class CParents
{
public:CParents(vectorint vParent, long long iMaxDepth){int iBitNum 0;for (; iMaxDepth; iBitNum) {const auto mask 1LL iBitNum;if (mask iMaxDepth) { iMaxDepth iMaxDepth ^ mask; }}const int n vParent.size();m_vParents.assign(iBitNum 1, vectorint(n, -1));m_vParents[0] vParent;//树上倍增for (int i 1; i m_vParents.size(); i){for (int j 0; j n; j){const int iPre m_vParents[i - 1][j];if (-1 ! iPre){m_vParents[i][j] m_vParents[i - 1][iPre];}}}}int GetParent(int iNode, int iDepth)const{int iParent iNode;for (int iBit 0; iBit m_vParents.size(); iBit){if (-1 iParent){return iParent;}if (iDepth (1 iBit)){iParent m_vParents[iBit][iParent];}}return iParent;}inline int GetBitCnt()const { return m_vParents.size(); };inline const int GetPow2Parent(int iNode, int n)const {return m_vParents[n][iNode];}//在leftNodeExclude的1到rightLeve级祖先中查找符合pr的最近祖先templateclass _Print FindFirst(int leftNodeExclude, int rightLeve, _Pr pr) {for (int iBit GetBitCnt() - 1; iBit 0; iBit--) {const int iMask 1 iBit;if (!(iMask rightLeve)) { continue; }if (pr(m_vParents[iBit][leftNodeExclude])) {return BFindFirst(leftNodeExclude, iBit, pr);}leftNodeExclude m_vParents[iBit][leftNodeExclude];}return -1;}//在node的0到rightLeve级祖先中查找符合pr的最远祖先比node高多少层次,这些层次必须存在templateclass _Print FindEnd(int node, int rightLeve, _Pr pr) {int leve 0;for (int iBit GetBitCnt() - 1; iBit 0; iBit--) {const int iMask 1 iBit;if (!(iMask rightLeve)) { continue; }if (!pr(m_vParents[iBit][node])) {return leve BFindEnd(node, iBit, pr);}node m_vParents[iBit][node];leve leve ^ iMask;}return leve;}
protected://在leftNodeExclude的1到2^pow^级祖先中查找符合pr的最近祖先templateclass _Print BFindFirst(int leftNodeExclude, int pow, _Pr pr) {while (pow 0) {const int mid m_vParents[pow - 1][leftNodeExclude];if (pr(mid)) {}else {leftNodeExclude mid;}pow--;}return m_vParents[0][leftNodeExclude];}//在node的[0,2^pow^-1]级祖先中寻找符合的最后一个templateclass _Print BFindEnd(int node, int pow, _Pr pr) {int leve 0;while (pow 0) {pow--;const int mid m_vParents[pow][node];if (pr(mid)) {node mid;leve leve ^ (1 pow);}else {}}return leve;}vectorvectorint m_vParents;
};class C2Parents : public CParents
{
public:C2Parents(vectorint vParent, const vectorint vDepth) :m_vDepth(vDepth), CParents(vParent, *std::max_element(vDepth.begin(), vDepth.end())){}int GetPublicParent(int iNode1, int iNode2)const{int leve0 m_vDepth[iNode1];int leve1 m_vDepth[iNode2];if (leve0 leve1){iNode2 GetParent(iNode2, leve1 - leve0);leve1 leve0;}else{iNode1 GetParent(iNode1, leve0 - leve1);leve0 leve1;}if (iNode1 iNode2) { return iNode1; }for (int iBit GetBitCnt() - 1; iBit 0; iBit--) {const int iMask 1 iBit;if (iMask leve0) {const int i1 GetPow2Parent(iNode1, iBit);const int i2 GetPow2Parent(iNode2, iBit);if (i1 i2) {while (iBit 0) {const int i3 GetPow2Parent(iNode1, iBit - 1);const int i4 GetPow2Parent(iNode2, iBit - 1);if (i3 ! i4) {iNode1 i3; iNode2 i4;}iBit--;}return GetPow2Parent(iNode1, 0);}else {iNode1 i1; iNode2 i2; leve0 - iMask;}}}return iNode1;}
protected:vectorvectorint m_vParents;const vectorint m_vDepth;
};
class Solution {
public:vectorint Ans(const int N, vectorint c, vectorpairint, int edge, vectorpairint, int que) {auto neiBo CNeiBo::Two(N, edge, false, 1);vectorvectorint cnt(20, vectorint(N)), preSum(20, vectorint(N));vectorint vpar(N, -1);functionvoid(int, int) DFS [](int cur, int par) {vpar[cur] par;for (int i 0; i 20; i){cnt[i][cur] (i c[cur] - 1);preSum[i][cur] cnt[i][cur];if (-1 ! par) {preSum[i][cur] preSum[i][par];}}for (const auto next : neiBo[cur]) {if (next par) { continue; }DFS(next, cur);}};DFS(0, -1);auto leves CBFSLeve::Leve(neiBo, { 0 });C2Parents p2(vpar, leves);vectorint ans;for (auto [u, v] : que) {u--, v--;const int g p2.GetPublicParent(u, v);int cur 0;for (int i 0; i 20; i) {cur (preSum[i][u] preSum[i][v] - 2 * preSum[i][g] cnt[i][g] 0);}ans.emplace_back(cur);}return ans;}
};int main() {
#ifdef _DEBUGfreopen(a.in, r, stdin);
#endif // DEBUG ios::sync_with_stdio(0); cin.tie(nullptr);//CInBuff in; COutBuff10000000 ob;int N, Q;cin N Q;auto c Readint(N);auto edge Readpairint, int(N - 1);auto que Readpairint, int(Q);
#ifdef _DEBUG printf(N%d, N);Out(c, ,c);Out(que, ,que);Out(edge, ,edge);//Out(edge2, ,edge2);//Out(rr, ,rr);//Out(ab, ,ab);//Out(par, par);//Out(que, que);//Out(B, B);
#endif // DEBUG Solution slu;auto res slu.Ans(N,c,edge,que);for (const auto i : res){cout i \n;}return 0;
};单元测试
int N;vectorint c;vectorpairint, int edge, que;TEST_METHOD(TestMethod01){N 4, c { 1,2,3,1 }, que { {4,3},{1,4} }, edge { {1,2},{1,3},{2,4} };auto res Solution().Ans(N, c, edge, que);AssertEx({ 3,2 }, res);}扩展阅读
我想对大家说的话工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作有效学习明确的目标 及时的反馈 拉伸区难度合适 专注闻缺陷则喜(喜缺)是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛失败反思成功 成功反思成功
视频课程
先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771 如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
