一前言今天大概是5场模拟赛打的最好的一把了除了刚开始30分钟的时候睡得有点懵之外剩下的时间状态都不错诶也算是对5天的集训进行了一个良好的收尾虽然打的还不错但是也有细节和可惜的地方值得后续的注意让我们来看一看这套题目补完题四后气死我了啊啊啊啊啊啊啊啊啊啊稳上300班级Rank1啊啊啊啊气死我了这个细节把控二成绩1稳住读数【100/100】炮灰你好2漏掉的指令【85/100】没有了过往的记忆那我又算是什么3应急通行【25/100】你这家伙老老实实去第四题或者提高组去啊4分批烘干【25/100】假如我再给你一些时间亲爱的你还会给我一个机会吗我恨你总分【235/400】今日班级rank 4(开心诶) 注意T4最高分【25/100】这套题呢与前年没有任何相同的题目这样也好没有任何水分在了题目依旧官方认证的难哦还我树组让我再做一次吧哭补完题四后嗯我可以说我原本应该325分的吗补充1题一还是不说了但是这回还是小创我一下打了40分钟才过只能说进入状态是很重要的关于语法题的思路还是建议写写注释这会也有一定的审题错误一定审好再做2本次官方认证难度 3241三题四在补题之前我对我的25分沾沾自喜认为走运了打了班里第一但是补完之后我直接将它的顺序放到了第一个我的专属好好好你终于来了这是我第一个AC的第四题这是我第一个用20分钟做完的第四题显然这个题是不好做的班级最高分25啊但是它撞上了巅峰状态的我那我直接神挡杀神佛挡杀佛直接写了一篇换3个字符就AC的代码没开longlong啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊我分没了每年都有我原本以为今年已经逃过去了啊啊啊啊啊啊然而没有我相信我是整个班对待补题报告最认真的也确实管用除了long long之外我的代码完全正确这基本归功于我对每套模拟赛第34题的补题报告重点在26年第一次模拟补题的第4题本题基本与之类似吧甚至我觉得更简单状态全部写对了简单看一下这个题直接过吧实验室有 n 份样品按编号 1∼n 排列。样品 i 的最低烘干强度为 a​i​​完成处理后可以获得 vi​​ 点研究价值。实验员可以选择部分样品分成若干批处理规则如下每批必须是原序列中的一个非空连续区间[l,r]这一批包括编号从 l 到 r 的全部样品。不同批次不能重叠每份样品最多处理一次两个批次可以紧挨着例如 [1,2] 和 [3,3] 可以分别处理。可以跳过样品但跳过后原本不相邻的样品不能直接拼成一个批次。例如跳过第 2 份后第 1、3 份仍不能单独组成一批。处理一批 [l,r] 时机器采用该批样品中最大的烘干强度。设每次启动的固定能耗为 C则这一批消耗的能量为C(r−l1)×max l≤i≤r ai获得的研究价值为∑il到r vi实验室的总能量预算为 B要求所有批次消耗的能量之和不超过 B。请你求出最多能够获得多少总研究价值。允许一份样品都不处理此时总能耗和总价值均为 0。思路如下非常简单题意可以把连续若干物品打包为一组。一组的代价 C 组内物品数量 × 组内a的最大值一组价值 组内所有v相加。DP状态定义dp[i][j] 处理前i件物品花费代价j能获得的最大价值。转移两种选择1. 不把i放进新组继承dp[i-1][j]2. 枚举左端点k将k~i打包成单独一组 维护区间[k,i]的a最大值计算本组代价sumc、价值sumv。 若预算足够则从dp[k-1][j-sumc]转移更新dp[i][j]。AC代码#includebits/stdc.h using namespace std; long long dp[405][2005]; int main(){ //freopen(dry.in,r,stdin); //freopen(dry.out,w,stdout); int n,B,C,v[405],a[405]; cinnBC; for(int i1;in;i){ cina[i]v[i]; } for(int i1;in;i){ for(int jB;j0;j--){ dp[i][j]max(dp[i][j],dp[i-1][j]);//完全不选 //往前找进行组合 long long sumc,sumv0; int maxxa[i]; for(int ki;k1;k--){//只选一个作为一批次也要算ki maxxmax(maxx,a[k]); sumcC1ll*(i-k1)*maxx; sumvv[k]; if(jsumc) break; dp[i][j]max(dp[i][j],dp[k-1][j-sumc]sumv); } } } coutdp[n][B]; }写这个的主要目的还是警醒自己必须开long long其实我写的时间复杂度什么的都符合条件一直没想到能Along long根本就没想到这回事四题二好了真正第四题来袭p1过往题二的记忆失效之后才想起来我24年被第二题被创的有多惨啊不可小觑p2这边可以考虑删掉思维题吗第二题就老老实实的给我出大模拟啊喂p3呜呜呜呜我的分啊啊啊细节把握和反例举证真的太难了啊啊啊啊p3注思路和算法完全正确改掉一处细节4个字符直接AC心理状态结束今年心态好好啊这个题可是做了2个小时呢越做越爽越做越有感觉越做不出来越想做相比24年的又哭又闹现在才是正确状态我们来一起看一下这道思维好题数学题结尾再说说细节的把控先看题面一个循环计数器初始显示 0。计数器的显示值始终是 0 到 m−1 中的整数。原计划依次执行 n 条指令每条指令是以下两种之一 a将当前显示值加上 a然后对 m 取模。* a将当前显示值乘以 a然后对 m 取模。执行结束后工作人员怀疑发生过漏执行故障希望按照以下情况核对记录恰好有一条指令没有执行其他指令仍然按照原来的顺序正确执行。现在给出原计划的全部指令以及执行结束后记录的数 r。请你计算有多少个遗漏位置能够在上述情况下得到 r。不保证工作人员的推测一定成立。位置不同就视为不同的可能即使两个位置上的指令内容相同。执行一条指令后数值可能保持不变这样的指令也可能是遗漏指令。允许乘以 0且 m 不一定是质数。如果没有任何一个遗漏位置能够得到结果 rr输出 0。如果 n1遗漏唯一的指令后不再执行任何指令计数器保持初始显示 0。先简单说说官方思路(我的思路虽与其不同但也是正解)对于思维题自己的做法才是重中之重仿射变换法呦呦呦又装上了这次不一样不是直接复制粘贴我用自己的话把它说明白我们设置一个转换器不要管放进去它的东西是什么也不用管输出的东西是什么我们设计的转换器就是打包一段操作不管把什么扔进去都会对这个东西进行这个转换器打包的这段操作然后给一个输出值这个转换器我们把它命名为f(x)本题的操作只有*两种所以我们的转换器大概长这样f(x)AxB(mod m)加法乘法定义来说初始A1B0若我们此时对一段操作求它对应转换器的AB一次函数k,b 7 A1B7* 3 A3B214 A3B25那这一段操作的对应的转换器就是f(x)AxB(mod m)3x25(mod m)扔进一个x就会得到f(x)是3x25这个值等价于对x执行7 *3 4的操作直接把这一段操作的信息直接转换成两个数我们此时有一些前缀的操作和后缀的操作对应设置结构体数组pre[]suf[]我们对于前i项操作按上述递推方式得到转换器pre[i].Apre[i].B此时就有xx*pre[i].Apre[i].B将x执行前i项操作后的值更新给x我们对于i到n项末i项操作继续递推类似后缀和得到转换器suf[i].Asuf[i].B此时就有xx*suf[i].Asuf[i].B将x值执行第i到第n项操作后的值更新给x我们如果要扔掉第k个操作就是把初值扔到pre[k-1]中这样获得了经过第1个操作到k-1个操作的值再把这个新值扔到suf[k1]中对它执行第k1次操作到n次操作得到的值就是遗弃第k次操作的值这是显而易见的正片开始考场思路来了p1我们去考虑每个运算对于最终答案的贡献观察到有一个特殊样例全部都是加法运算这种样例中遗弃一个运算就是在最终结运算果里面减去这个加数“减去”伏笔也给我们埋下了 “扣掉贡献” 的思路p2这种情况是朴素的那加上乘法之后呢我们希望将这些操作转化为这种xyzabc...w朴素情况所以我们将乘法转为加法考虑对于这样一个运算7*3显然它等效于714对于这样一个运算A*B显然它等效于AA*(B-1)这个A不是代表一个数而是在计算*B这个运算之前前面所有运算后得到的值即执行这条乘法指令之前计数器已经算出的值A这个东西我们通过前缀打表来求解所以*B这个运算就转化为了A*(B-1)这样我们把乘法转化为了形式上的加法就是把 “多出来的增量” 变成加法p3这里我们得到原本的加法和乘法转为的加法显然这两种加法并不与那种朴素情况中的加法相同我们考虑乘法分配律将其转化为真正意义上的“加法”考虑这么一个式子[(74)*35]*27这个运算的贡献怎么算把式子用分配律拆开7*3*24*3*25*27变成了7*3*25变成了5*2没错我们加法的转为朴素形式就是乘上后面所有乘法累乘起来的乘积得到这样的一个真正的加法可以利用p1的方法直接求解那我们在上一步乘法转化为的形式加法显然也要再转换成为真正的加法乘上后面所有乘法累乘起来的乘积再去使用p1的方法进行求解我们前文所说的“真正的加法”就是每个值对于最终答案的贡献我把这个求法叫做贡献法AI润一下把乘法等效改为虚拟加法再利用分配律预处理出每条指令后方所有乘法的乘积算出单条加法指令对最终答案的总贡献。跳过该指令等价于从总结果减去这份贡献注意模运算相关两个点1模运算添加的位置是有影响的显然不是所有运算的位置都能无脑套上取模我被坑完自己调出来了2这边非常难调虽然很难想但是真的有样例是这样的一个运算的贡献大于总结果哇也是直接给我卡掉15分%运算取模结果与被除数符号一致但显然我们题目要的是非负数所以回顾一下模运算减法A-B%m一定要这么写[A-B%mm]%m看完T4的大坑我觉得这15分也无所吊谓了AC代码//乘法转化为加法:设该乘法前面所有数的运算结果为x(前缀打表求解) //运算该乘法*A后得到结果为x*A该乘法可被转化为x(A-1)*x //即将*A转化为(A-1)*xx的求解利用前缀打表 //删除x即结果直接减去 //删除加法带来的影响是容易计算的 //其后面所有乘法的乘积乘法分配律乘以该加法即为该加法对答案的贡献 #includebits/stdc.h const int N2e55; using namespace std; char op[N]; int n,m,r; long long a[N],sum[N],f[N]; int main(){ freopen(omit.in,r,stdin); freopen(omit.out,w,stdout); scanf(%d%d%d,n,m,r); for(int i1;in;i){ scanf(%s%lld,op[i],a[i]); if(op[i]) sum[i]sum[i-1]a[i]; else if(op[i]*) sum[i]sum[i-1]*a[i];//嘻嘻 sum[i]%m; } f[n]1; for(int in-1;i1;i--){ f[i]f[i1]; if(op[i1]*) f[i]*a[i1]; f[i]%m; } int cnt0; for(int i1;in;i){ long long finalsum[n]; if(op[i]) finalm-1ll*a[i]*f[i]%m; else if(op[i]*) finalm-1ll*sum[i-1]*(a[i]-1)*f[i]%m; final%m; if(finalr) cnt; } coutcnt; }五题三这边赛上也是非常简单且诡异。毫无思路想暴搜又想到昨天说找短路不能用dfs再看了眼数据于是放弃由于接触过提高组知识莫名想到了单源最短路迪杰斯特拉误闯天家。那只能宽搜了其实这就是正解但昨天被误导了说带权图不可以用bfs跑最短路也倒是歪打正着去做了第4题然后。。。回来看到有部分数据非常诡异的是一条链强强直接跑了二分答案拿到25分二分答案也是正解这个题的赛后更是诡异至极老师没有讲正解思路我不知道问豆包给出了与题解截然不同的解法我对着写了半天题解好多好多字结果她自己没AC而官方题解非常难想不好弄说骗分思路也没啥必要了55分是容易获得的豆包写的。。。应该是官方的70分思路但是落下来就成了15分这个题的正解是多源BFS和正反向搜索给定有向图n个站点m条单向道路。每条道路有通行要求a[i]。 有起点S、终点T应急模式最多连续走K条道路基础能力P移动规则 整条路径分为三段可以某段为空普通模式只能走a[i]P的道路应急模式可走任意道路连续最多 K 条边普通模式只能走a[i]P的道路。求满足条件的最小P嗯这是根据正解思路反推整理出的题面实际做的时候还有从题面转成上述文字的需要饿啊对于每个P二分答案中的mid大致就是正向从起点跑一遍BFS只走直接能到不开应急a[i]P的路路上的点就是第二段的开始点反向从终点跑一遍BFS只走直接能到不开应急的路路上的点就是第二段的结束点然后对正向BFS跑出的所有点跑BFS起点有多个就是多源最短路看看能不能有在距离小于K时遍历到标记好的结束点若有则证明该P可行那这个题就这样吧。。。悲催六总结不要骄傲还是要以稳定专注细心的状态来背赛应赛加油注意细节模运算负数long long问题时间把握能骗则骗我们赛场见七祝福这里也要祝福自己啦祝前程似锦