P10236 [yLCPC2024] D. 排卡题目背景经过千辛万苦扶苏终于到达了机厅。但是她很快发现机厅排起了大 b 队不是省选的 B 队。舞萌玩家们在人多的时候经常采取排卡的方式决定谁下一个上机。因为人实在是太多了他们在排卡的时候便注意到了卡上的编号。他们向扶苏提了一个问题你能解决吗题目描述扶苏有一个双端队列aaa。这个队列与计算机科学中队列的概念类似不同的是这个队列既可以从队列头读取和弹出元素也可以在队列尾部读取和弹出元素因此被称为『双端队列』。这个队列中有nnn个数。扶苏将通过nnn次操作构造一个长度为nnn的序列bbb第iii1≤i≤n1 \leq i \leq n1≤i≤n次操作会可以进行如下两个过程之一令bib_ibi​为aaa的队列头并在aaa的头部弹出一个元素。令bib_ibi​为aaa的队列尾并在aaa的尾部弹出一个元素。我们定义一个数对(i,j)(i, j)(i,j)的得分为score(i,j)ij mod 998244353\mathrm{score}(i,j) i^j \bmod 998244353score(i,j)ijmod998244353即iii的jjj次幂对998244353998244353998244353取余数的结果。特别的在本题中我们规定0000^0 0000。现在扶苏想用最优的策略构造bbb序列最大化如下式子的值∑i1n−1score(bi,bi1)\sum_{i 1}^{n - 1} \mathrm{score}(b_i, b_{i 1})i1∑n−1​score(bi​,bi1​)即bbb所有相邻两项按原顺序计算的得分之和。注意我们仅在计算一个数对的时候将得分对998,244,353998,244,353998,244,353取模在计算求和时不再将这个和取余。输入格式本题单个测试点内有多组测试数据。第一行是一个正整数表示数据组数TTT。对每组数据第一行是一个整数nnn2≤n≤1032 \leq n \leq 10^32≤n≤103表示序列的长度。第二行有nnn个整数a1,a2,…ana_1, a_2, \dots a_na1​,a2​,…an​0≤ai998,244,3530 \leq a_i 998,244,3530≤ai​998,244,353按从头到尾的顺序表示队列aaa里每个数字的值。数据保证单个测试点内nnn的和不超过10310^3103。输出格式对每组测试数据输出一行一个整数表示答案。输入输出样例 #1输入 #12 5 5 3 1 4 2 6 6 5 1 4 2 3输出 #11168 15655C实现#includebits/stdc.husingnamespacestd;#definelllonglongll mod998244353;llquickpow(ll x,ll y){if(x0y0){return0;//特判}ll ans1,px;while(y0){if(y1){ans(ans*p)%mod;}p(p*p)%mod;y1;}returnans;}ll T,dp[1009][1009][2],a[1009],n;intmain(){cinT;while(T--){cinn;for(ll i1;in;i){cina[i];}memset(dp,0,sizeof(0));//多测清空for(ll lenn;len1;len--){for(ll i1;in-len1;i){ll jilen-1;dp[i][j][0]max(dp[i-1][j][0]quickpow(a[i-1],a[i]),dp[i][j1][1]quickpow(a[j1],a[i]));dp[i][j][1]max(dp[i-1][j][0]quickpow(a[i-1],a[j]),dp[i][j1][1]quickpow(a[j1],a[j]));}}ll ans0;for(ll i1;in;i){ansmax(ans,dp[i][i][0]);ansmax(ans,dp[i][i][1]);}coutansendl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容