![打卡信奥刷题（3644）用C++实现信奥题 P12027 [USACO25OPEN] Ski Slope S](http://pic.xiahunao.cn/yaotu/打卡信奥刷题（3644）用C++实现信奥题 P12027 [USACO25OPEN] Ski Slope S)
P12027 [USACO25OPEN] Ski Slope S题目描述贝茜要和朋友们一起去滑雪。雪山上有NNN个路标1≤N≤1051 \leq N \leq 10^51≤N≤105按海拔从低到高依次标记为1,2,…,N1, 2, \ldots, N1,2,…,N路标111位于山脚。对于每个路标i1i 1i1有一条从路标iii出发终点为路标pip_ipi1≤pii1 \leq p_i i1≤pii的滑雪道。这条滑道的难度为did_idi0≤di≤1090 \leq d_i \leq 10^90≤di≤109乐趣值为eie_iei0≤ei≤1090 \leq e_i \leq 10^90≤ei≤109。贝茜的MMM个朋友1≤M≤1051 \leq M \leq 10^51≤M≤105每人会进行如下操作选择一个起始路标iii然后沿着滑道向下滑行依次经过pi,ppip_i,p_{p_i}pi,ppi依此类推直到抵达路标111。每位朋友获得的乐趣值等于他们经过的所有滑道的乐趣值之和。每个朋友有不同的技能水平sjs_jsj0≤sj≤1090 \leq s_j \leq 10^90≤sj≤109和勇气值cjc_jcj0≤cj≤100 \leq c_j \leq 100≤cj≤10这限制他们选择的起始路标必须满足滑行过程中最多有cjc_jcj条滑道的难度超过sjs_jsj。请为每位朋友计算他们能获得的最大乐趣值。输入格式第一行包含NNN。接下来222到NNN行每行包含三个整数pip_ipidid_idi和eie_iei。随后一行包含MMM。接下来MMM行每行包含两个整数sjs_jsj和cjc_jcj。输出格式输出MMM行每行对应一个朋友的答案。注意由于涉及大整数运算可能需要使用 64 位整数类型如 C/C 中的long long。输入输出样例 #1输入 #14 1 20 200 2 30 300 2 10 100 8 19 0 19 1 19 2 20 0 20 1 20 2 29 0 30 0输出 #10 300 500 300 500 500 300 500说明/提示第一位朋友只能选择路标111作为起点因为其他路标都会导致至少经过一条难度超过191919的滑道。总乐趣值为000。第二位朋友可以选择路标444依次滑行至路标222和111。总乐趣值为100200300100 200 300100200300其中有一条滑道难度超过191919。第三位朋友可以选择路标333依次滑行至路标222和111。总乐趣值为300200500300 200 500300200500其中有两条滑道难度超过191919。测试点2∼42\sim42∼4N,M≤1000N, M \leq 1000N,M≤1000。测试点5∼75\sim75∼7所有cj0c_j 0cj0。测试点8∼178\sim178∼17无额外限制。C实现#includebits/stdc.husingnamespacestd;intn,p[100010],k;//一次性longlonge[100010],d[100010],_max[12][100010],ans[12][100010];structNode{longlonge,max_[12];booloperator(constNodex){returnmax_[k]x.max_[k];}}a[100010];longlongmax_[12][100010];intmain(){cinn;for(inti2;in;i){cinp[i]d[i]e[i];e[i]e[p[i]];a[i].ee[i];for(intj1;j11;j)_max[j][i]_max[j][p[i]];for(intj1;j11;j){if(d[i]_max[j][i])swap(d[i],_max[j][i]);a[i].max_[j]_max[j][i];}}for(k1;k11;k){sort(a1,a1n);for(inti2;in;i){ans[k][i]max(ans[k][i-1],a[i].e);max_[k][i]a[i].max_[k];}}intm;cinm;while(m--){ints,c;cinsc;c;intidupper_bound(max_[c]1,max_[c]n1,s)-max_[c]-1;coutans[c][id]\n;}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
P12027 [USACO25OPEN] Ski Slope S题目描述贝茜要和朋友们一起去滑雪。雪山上有NNN个路标1≤N≤1051 \leq N \leq 10^51≤N≤105按海拔从低到高依次标记为1,2,…,N1, 2, \ldots, N1,2,…,N路标111位于山脚。对于每个路标i1i 1i1有一条从路标iii出发终点为路标pip_ipi1≤pii1 \leq p_i i1≤pii的滑雪道。这条滑道的难度为did_idi0≤di≤1090 \leq d_i \leq 10^90≤di≤109乐趣值为eie_iei0≤ei≤1090 \leq e_i \leq 10^90≤ei≤109。贝茜的MMM个朋友1≤M≤1051 \leq M \leq 10^51≤M≤105每人会进行如下操作选择一个起始路标iii然后沿着滑道向下滑行依次经过pi,ppip_i,p_{p_i}pi,ppi依此类推直到抵达路标111。每位朋友获得的乐趣值等于他们经过的所有滑道的乐趣值之和。每个朋友有不同的技能水平sjs_jsj0≤sj≤1090 \leq s_j \leq 10^90≤sj≤109和勇气值cjc_jcj0≤cj≤100 \leq c_j \leq 100≤cj≤10这限制他们选择的起始路标必须满足滑行过程中最多有cjc_jcj条滑道的难度超过sjs_jsj。请为每位朋友计算他们能获得的最大乐趣值。输入格式第一行包含NNN。接下来222到NNN行每行包含三个整数pip_ipidid_idi和eie_iei。随后一行包含MMM。接下来MMM行每行包含两个整数sjs_jsj和cjc_jcj。输出格式输出MMM行每行对应一个朋友的答案。注意由于涉及大整数运算可能需要使用 64 位整数类型如 C/C 中的long long。输入输出样例 #1输入 #14 1 20 200 2 30 300 2 10 100 8 19 0 19 1 19 2 20 0 20 1 20 2 29 0 30 0输出 #10 300 500 300 500 500 300 500说明/提示第一位朋友只能选择路标111作为起点因为其他路标都会导致至少经过一条难度超过191919的滑道。总乐趣值为000。第二位朋友可以选择路标444依次滑行至路标222和111。总乐趣值为100200300100 200 300100200300其中有一条滑道难度超过191919。第三位朋友可以选择路标333依次滑行至路标222和111。总乐趣值为300200500300 200 500300200500其中有两条滑道难度超过191919。测试点2∼42\sim42∼4N,M≤1000N, M \leq 1000N,M≤1000。测试点5∼75\sim75∼7所有cj0c_j 0cj0。测试点8∼178\sim178∼17无额外限制。C实现#includebits/stdc.husingnamespacestd;intn,p[100010],k;//一次性longlonge[100010],d[100010],_max[12][100010],ans[12][100010];structNode{longlonge,max_[12];booloperator(constNodex){returnmax_[k]x.max_[k];}}a[100010];longlongmax_[12][100010];intmain(){cinn;for(inti2;in;i){cinp[i]d[i]e[i];e[i]e[p[i]];a[i].ee[i];for(intj1;j11;j)_max[j][i]_max[j][p[i]];for(intj1;j11;j){if(d[i]_max[j][i])swap(d[i],_max[j][i]);a[i].max_[j]_max[j][i];}}for(k1;k11;k){sort(a1,a1n);for(inti2;in;i){ans[k][i]max(ans[k][i-1],a[i].e);max_[k][i]a[i].max_[k];}}intm;cinm;while(m--){ints,c;cinsc;c;intidupper_bound(max_[c]1,max_[c]n1,s)-max_[c]-1;coutans[c][id]\n;}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
