本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P7077 [CSP-S 2020] 函数调用 - 洛谷【题目描述】函数是各种编程语言中一项重要的概念借助函数我们总可以将复杂的任务分解成一个个相对简单的子任务直到细化为十分简单的基础操作从而使代码的组织更加严密、更加有条理。然而过多的函数调用也会导致额外的开销影响程序的运行效率。某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类将数据中的指定元素加上一个值将数据中的每一个元素乘以一个相同值依次执行若干次函数调用保证不会出现递归即不会直接或间接地调用本身。在使用该数据库应用时用户可一次性输入要调用的函数序列一个函数可能被调用多次在依次执行完序列中的函数后系统中的数据被加以更新。某一天小 A 在应用该数据库程序处理数据时遇到了困难由于频繁而低效的函数调用系统在执行操作时进入了无响应的状态他只好强制结束了数据库程序。为了计算出正确数据小 A 查阅了软件的文档了解到每个函数的具体功能信息现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。【输入】第一行一个正整数n nn表示数据的个数。第二行n nn个整数第i ii个整数表示下标为i ii的数据的初始值为a i a_iai​。第三行一个正整数m mm表示数据库应用程序提供的函数个数。函数从1 ∼ m 1 \sim m1∼m编号。接下来m mm行中第j jj1 ≤ j ≤ m 1 \le j \le m1≤j≤m行的第一个整数为T j T_jTj​表示j jj号函数的类型若T j 1 T_j 1Tj​1接下来两个整数P j , V j P_j, V_jPj​,Vj​分别表示要执行加法的元素的下标及其增加的值若T j 2 T_j 2Tj​2接下来一个整数V j V_jVj​表示所有元素所乘的值若T j 3 T_j 3Tj​3接下来一个正整数C j C_jCj​表示j jj号函数要调用的函数个数随后C j C_jCj​个整数g 1 ( j ) , g 2 ( j ) , … , g C j ( j ) g^{(j)}_1, g^{(j)}_2, \ldots , g^{(j)}_{C_j}g1(j)​,g2(j)​,…,gCj​(j)​依次表示其所调用的函数的编号。第m 4 m 4m4行一个正整数Q QQ表示输入的函数操作序列长度。第m 5 m 5m5行Q QQ个整数f i f_ifi​第i ii个整数表示第i ii个执行的函数的编号。【输出】一行n nn个用空格隔开的整数按照下标1 ∼ n 1 \sim n1∼n的顺序分别输出在执行完输入的函数序列后数据库中每一个元素的值。答案对998244353 \boldsymbol{998244353}998244353取模。【输入样例】3 1 2 3 3 1 1 1 2 2 3 2 1 2 2 2 3【输出样例】6 8 12【算法标签】#提高# #拓扑排序#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN200005,mod998244353;// 函数结构体表示每个操作structFunc{intop,p,v;// op: 操作类型, p: 位置参数, v: 值参数}func[N];// 边结构体表示图的边structEdge{intv,w;// v: 目标节点, w: 边权};intn,m,q;// n: 初始变量数量, m: 操作数量, q: 查询数量intmul[N];// 乘法因子表示从该节点开始的累积乘积intans[N];// 最终答案数组intin[N];// 入度数组用于拓扑排序intp[N];// 系数数组表示每个节点对最终结果的贡献系数vectorEdgeadj[N];// 邻接表表示有向图// 递归计算从节点u开始的累积乘积intinit(intu){if(mul[u]!-1||adj[u].empty())// 如果已经计算过或者是叶子节点{returnmul[u];}mul[u]1;// 初始化为1// 递归计算所有后继节点的乘积for(inti0;iadj[u].size();i){intvadj[u][i].v;mul[u]mul[u]*init(v)%mod;}returnmul[u];}// 计算每条边的权重voidwork(){for(intu0;unm;u)// 遍历所有节点{intr1;// 从右向左的累积乘积// 从后向前遍历邻接表for(intiadj[u].size()-1;i0;i--){intvadj[u][i].v;adj[u][i].wr;// 设置边的权重为右侧的累积乘积rr*mul[v]%mod;// 更新累积乘积}}}// 拓扑排序计算每个节点的贡献系数voidtopo(){queueintq;// 用于拓扑排序的队列p[0]1;// 起点节点的系数为1// 将所有入度为0的节点加入队列for(inti0;inm;i){if(in[i]0){q.push(i);}}// 拓扑排序主循环while(!q.empty()){intuq.front();q.pop();// 遍历u的所有出边for(inti0;iadj[u].size();i){intvadj[u][i].v;intwadj[u][i].w;// 更新后继节点的系数p[v](p[v]w*p[u]%mod)%mod;in[v]--;// 减少入度// 如果入度变为0加入队列if(in[v]0){q.push(v);}}}}signedmain(){memset(mul,-1,sizeof(mul));// 初始化mul数组为-1// 第一部分输入初始变量cinn;for(inti1;in;i){cinfunc[i].v;// 输入初始值func[i].op1;// 操作类型1赋值func[i].pi;// 赋值位置mul[i]1;// 乘法因子为1in[i];// 增加入度adj[0].push_back({i,0});// 从0节点连接到i节点}// 第二部分输入操作cinm;for(intin1;imn;i){cinfunc[i].op;// 输入操作类型if(func[i].op1)// 操作类型1赋值{cinfunc[i].pfunc[i].v;// 输入位置和值mul[i]1;// 乘法因子为1}elseif(func[i].op2)// 操作类型2乘法{cinfunc[i].v;// 输入乘数mul[i]func[i].v;// 乘法因子为v}else// 操作类型3函数调用{intc,g;cinc;// 输入参数个数for(intj1;jc;j){cing;// 输入每个参数adj[i].push_back({gn,0});// 添加边in[gn];// 增加入度}}}// 第三部分输入查询cinq;for(intj1;jq;j){intf;cinf;// 输入查询的函数adj[0].push_back({fn,0});// 从0节点连接到查询函数in[fn];// 增加入度}// 第四部分计算和处理init(0);// 从0节点开始计算累积乘积work();// 计算边权topo();// 拓扑排序计算系数// 第五部分计算结果for(inti1;inm;i){if(func[i].op1)// 如果是赋值操作{// 将值乘以系数累加到对应位置ans[func[i].p](ans[func[i].p]func[i].v*p[i]%mod)%mod;}}// 输出结果for(inti1;in;i){coutans[i] ;}coutendl;return0;// 程序正常结束}【运行结果】3 1 2 3 3 1 1 1 2 2 3 2 1 2 2 2 3 6 8 12