一前言24年在这追着砍我今年也是成功的砍了回来模拟赛直接改名寻仇记25年有人在意我吗抛开过去的一些记忆不谈本次模拟赛依然出现了两个问题后段状态下滑和重要心态调整二成绩24年第二次模拟赛补题报告1下棋【100/100】两年前你一点戏份没有今年还是一点戏份没有2汪洋【100/100】两年不见你小子这么弱了啊3拯救小精灵【60/100】把我的删数还回来我再挑战一次4平分糖果【0/100】又捐再捐没了总分【260/400】高分班班级Rank2题目重叠的会不会有点太少了一样的题今年再看水炸了那你也没AK啊FW彩蛋我回去看了之前写的补题报告虽然说好题一不说了但我看的太难绷了真的有人类能想出来用循环减法模拟除法这种诡异东西吗我滴妈我在干啥这里再补充一下题一这个题其实是本质贪心是要算收益的以得出能合尽量合的这个贪心策略三题二//BilibiliWorld BW即为本题题目BigWater汪洋回顾一下这次这个第二题做的也是非常舒服了就是两年前的那种痛苦感和便秘感荡然无存了题面不放了bilibili可以看24年的重点我们重新分析一下为什么人物的行动轨迹恒为矩形它显然不能是凹多边形否则直接违反只能顺时针转的规则它显然不能是那种旋涡形状的东西不然肯定无法回到起点它显然只能是4边形那毕竟是每次转90度啊对应矩形上下左右四条边注意不合法的情况由于没法连续转两次显然一根棍形状的行动路线显然不可以有同学一直在说这个题非常难也是直接看到了之前的自己啊但其实看出来这个矩形路线本题无疑是简单的哦不不不不不不去年的65分今年也是有出现了正好这里来复习一下神秘二维前缀和for(int i1;in;i){ for(int j1;jn;j){ cina[i][j]; sum[i][j]sum[i-1][j]sum[i][j-1]-sum[i-1][j-1]a[i][j] } } 左上角(i1,j1) 右下角(i2,j2) sumssum[i2][j2]-sum[i1-1][j2]-sum[i2][j1-1]sum[i1-1][j1-1]AC代码不放了依旧在24年的倒也没啥好说的了为24年的自己心疼1秒钟啊四题三删数的恐惧感依然存在计划近期出一篇它的题解这个题做的非常卡非常诡异非常不顺但不痛苦也不恶心并没有成为了前年的汪洋还是树组本题赛前原本看到平分糖果这个老仇人都想跳第三题了额逼自己看了一会为了避免空悲切说是至少打个暴力结果也是一做直接就上瘾了好吧其实是高估它的难度了根本没有暴力写法做就满分本题赛中你们有没有那种写了一半不知道自己为什么要写这个的痛苦感一开始想简单了纯堆连数组都没有肯定不行啊于是想去看第四题过了一会其实是忘了第四题思路了回来了秉持不放弃原则继续做画图思考了一下想着搞dfs跑连通块非常复杂越写越觉得自己写的没有任何用处这题不配虽全部删除连vector建边都没了于是出现了65分代码本题赛后豆包把我的代码贬的一文不值也是直接用上了我废弃的思路dfs跑连通块啊结果你猜怎么着无解判断错了改两个字符||改成这期神了每期小作文结束看看题面精灵王国中有 x 只小精灵和 y 只怪物共有 m 条绳子连接着它们。所有角色依次编号为 1 到 xy其中编号 1 到 x 的角色是小精灵编号 x1 到 xy 的角色是怪物。为了让所有小精灵恢复自由你必须剪断所有至少有一端连接着小精灵的绳子。两端都连接着怪物的绳子不会被剪断。被剪断的每一条绳子都可以转化为一条封印绳。一条封印绳只能用来封印一只怪物也可以不使用。两端都连接着怪物的绳子不能转化为封印绳。如果一只怪物仍与另一只怪物通过未被剪断的绳子相连那么它已经被限制住不需要使用封印绳。否则这只怪物是自由的必须使用一条封印绳将它绑在封印柱上。第 i 只怪物的力量为 a_i。每条绳子都有一个初始强度 b。只有强度不小于怪物力量的封印绳才能封印这只怪物。你可以消耗魔力强化封印绳。每消耗 1 点魔力可以使一条封印绳的强度增加 1。不同封印绳可以分别强化封印绳不能合并或拆分。请你求出在让所有小精灵自由并且没有任何怪物自由的前提下最少需要消耗多少点魔力。如果无论如何都无法满足要求输出 -1。来分析一下我的思路是贪心将给出的与小精灵相连的边权直接扔进堆里再去看仅怪物与怪物相连的边这些边所连接的怪物都不再需要被封印这里想到了连通块但根本不用若只存贮这些边则只要有边与该怪物相连另一头一定连的也是怪物那这只怪物和那只怪物就不需要封印了搞一个标记数组将这些怪物标记之后再去遍历怪物将没有被标记的怪物的力量丢进堆里这是数据存储部分关于贪心丢进堆里大的怪物配大的封印绳是最优解我是自己带了组数数学证明是大量不等式这里不再说了关于无解判断显然1怪物数量大于封印绳数量或者2一个一个配对完后发现封印绳没有了但怪物还有或者3一条封印绳都没有的情况下有个大样例都无解我原本写的只有2看有个大样例是3我脑子一抽在配对完后补了一个没有封印绳就无解真的蠢啊那都配对完了你还有封印绳就怪了怪物和封印绳数量相等直接WA直接失去40分AC代码如下#includebits/stdc.h const int N2e55; using namespace std; int x,y,m,a[N],u,v,b; mapint,int vis; priority_queueint g,f; int main(){ //freopen(gremlin.in,r,stdin); //freopen(gremlin.out,w,stdout); scanf(%d%d%d,x,y,m); for(int i1;iy;i){ scanf(%d,a[i]); } for(int i1;im;i){ scanf(%d%d%d,u,v,b); if(ux||vx){ f.push(b);//只要有一头连接小精灵直接剪断扔进堆里不连边 } else{ vis[u]1; vis[v]1; } } for(int ix1;ixy;i){ if(!vis[i]){ g.push(a[i-x]); } } //(1)的话if(g.size()f.size())无解 long long ans0; while(!g.empty()!f.empty()){ if(g.top()f.top()){ ans(g.top()-f.top()); } g.pop(); f.pop(); } if(!g.empty()f.empty()){//封印绳不够了根本没有绳子 一定要是啊 printf(-1); } else{ printf(%lld,ans); } }五题四前年搞得不是很明白啊纯为了字数和装逼把题解粘贴上了我们现在来详细拆解一下在看题之前我们先来看一下多重背包直接讲透彻第一个是我们本题要用的朴素多重背包多重背包一共有 n 种物品第 i 种物品体积 v[i]价值 w[i]最多可以选 s[i] 件。背包总容量 V。求不超过背包容量下最大总价值。for(int i1;in;i){//枚举每一类物品第i类 for(int k1;ks[i];k){//i类物品一共有s[i]个所以拿物品的时候可以拿s[i]次相当于复制 //标准01背包倒序循环 for(int jV;jv[i];j--){ dp[j]max(dp[j],dp[j-v[i]]w[i]); } } }01背包倒序循环的详解在y1,y2刷题这是这个看题小可的妈妈给了小可很多的糖果已经糖果都有美味程度美味程度用1~6的整数表示。有一天达达来小可家做客小可要把糖果分给达达现在已知了美味程度为 i 的糖果有 a[i] 个请问小可能不能把糖果平分成美味程度之和相同的两部分。有没有人是直接加起来看是奇数还是偶数的呃显然不行都老大不小了那怎么做呢继承24年思路展开说说这其实不是简单的背包而是一个多重背包可行性问题我们设置一个二维可以滚动数组压掉dp[i][j]表示前i类物品能不能获得j的美味程度我们的初值dp[0][0]1前0类物品显然可以获得0的饱食度我们的目标状态dp[6][sum1]若为1即可有方案在6类糖果里获得总美味程度的一半自然分成了两半了状态转移输入的糖果a[i]个即为最多可以选s[i]件的s[i]我们枚举到这第i类糖果要k个能否达到j的美味程度的状态时转移如下我们按照朴素写法的思路将每个物品复制个数来转化为01背包所以有dp[i][j] | dp[i][j-i] 有循环且注意个数循环在容量循环前面j-i正确而不是j-k*i且由于我们是拆物品写法所以第一要提前继承本组一个都不选的状态第二在后面更新本组选多个状态的时候本组前面选少个的状态一定是被更新过了再选物品的情况下根据01背包理应变成dp[i-1][j-i]但一定是要从同类更新过的状态继承复用本轮第 i 类前面已经选好的状态所以能拿多个第 i 类糖果而异类则是在第一个要点更新的通俗一点说你状态的改变就是拿糖果对吧你从这一堆第一个开始拿你原本有前面所有堆里选择的糖果你拿完一个放到糖果堆里你想再从这一堆拿一个那你是肯定是要放在你放过刚才那一个糖果的那一堆里而不是放到你要拿这一堆糖果还一个没拿的初始那一堆要不然你拿拿拿到最后这一堆里还是只有一个这新的堆里的糖果呀dp[i]专门存「前 i 类」的所有状态。dp[i-1]只存「前 i-1 类」里面完全不含第 i 种糖果。我已经拿了 1 颗 i 糖果这个信息保存在 dp [i] 里面我再拿一颗就一共 2 颗。这个 “已经拿了 1 颗” 的状态在 dp [i] 里不在 dp [i-1] 里。还有符号的问题注意到是或这是很合理的异或和与显然不行这样的话朴素多重背包只能够得到45分#includebits/stdc.h using namespace std; int a[10],dp[10][20005]; int main(){ //freopen(candy.in,r,stdin); //freopen(candy.out,w,stdout); int cnt0; while(cina[1]a[2]a[3]a[4]a[5]a[6]){ cnt; memset(dp,0,sizeof dp); int sum0; for(int i1;i6;i){ suma[i]*i; } if(sum0){ break; } if(sum%2!0){ printf(Collection #%d:\nCant be divided.\n\n,cnt); continue; } dp[0][0]1; //dp[i][j]为前i种物品能否凑出j //dp[i][j]|dp[i-1][j-k*a[i]](第i种物品拿k个) for(int i1;i6;i){ for(int jsum1;j0;j--){ dp[i][j]dp[i-1][j];//一个都不拿 } for(int k1;ka[i];k){ for(int jsum1;ji;j--){ dp[i][j]|dp[i][j-i]; } } } if(dp[6][sum1]){ printf(Collection #%d:\nCan be divided.\n\n,cnt); } else{ printf(Collection #%d:\nCant be divided.\n\n,cnt); } } }我们来进行优化从二进制优化版本的多重背包开始说把一包糖果拆成几堆每堆有2的幂次方数个拆的堆数显然不会很多自然时间复杂度就低了对这几堆跑01背包就完成了问题的转换这样拿物品的所有情况自然出来了拿1个拿1那一堆 拿2个拿2那一堆 拿3个拿1那一堆和2那一堆拿4个拿4那一堆 拿5个拿4那一堆和1那一堆二进制数为1的数位是要拿的拆完剩下的也要作为一堆来跑01背包其实这么搞完再套上滚动数组每一“类”这个概念已经淡化了AC代码在去年博客六总结从篇幅上的转移上来说重心落在了第三四题上面也体现了本次备考的中心好了就这样七祝福这个环节也是复活了好吧祝同学们金榜题名