企业官网建设流程全解析

一，前言

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 i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>a[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) sums=sum[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 到 x+y，其中编号 1 到 x 的角色是小精灵，编号 x+1 到 x+y 的角色是怪物。

为了让所有小精灵恢复自由，你必须剪断所有至少有一端连接着小精灵的绳子。两端都连接着怪物的绳子不会被剪断。

被剪断的每一条绳子都可以转化为一条封印绳。一条封印绳只能用来封印一只怪物，也可以不使用。两端都连接着怪物的绳子不能转化为封印绳。

如果一只怪物仍与另一只怪物通过未被剪断的绳子相连，那么它已经被限制住，不需要使用封印绳。否则，这只怪物是自由的，必须使用一条封印绳将它绑在封印柱上。

第 i 只怪物的力量为 a_i。每条绳子都有一个初始强度 b。只有强度不小于怪物力量的封印绳才能封印这只怪物。

你可以消耗魔力强化封印绳。每消耗 1 点魔力，可以使一条封印绳的强度增加 1。不同封印绳可以分别强化，封印绳不能合并或拆分。

请你求出，在让所有小精灵自由并且没有任何怪物自由的前提下，最少需要消耗多少点魔力。如果无论如何都无法满足要求，输出 -1。

来分析一下，我的思路是贪心

将给出的与小精灵相连的边权直接扔进堆里，再去看仅怪物与怪物相连的边，这些边所连接的怪物都不再需要被封印（这里想到了连通块，但根本不用），若只存贮这些边，则只要有边与该怪物相连（另一头一定连的也是怪物），那这只怪物（和那只怪物）就不需要封印了，搞一个标记数组，将这些怪物标记之后再去遍历怪物，将没有被标记的怪物的力量丢进堆里，这是数据存储部分

关于贪心：丢进堆里，大的怪物配大的封印绳是最优解，我是自己带了组数，数学证明是大量不等式，这里不再说了

关于无解判断：显然（1）怪物数量大于封印绳数量，或者（2）一个一个配对完后发现封印绳没有了但怪物还有，或者（3）一条封印绳都没有的情况下（有个大样例）都无解

我原本写的只有（2），看有个大样例是（3），我脑子一抽，在配对完后补了一个没有封印绳就无解，真的蠢啊，那都配对完了，你还有封印绳就怪了（怪物和封印绳数量相等直接WA），直接失去40分

AC代码如下

#include<bits/stdc++.h> const int N=2e5+5; using namespace std; int x,y,m,a[N],u,v,b; map<int,int> vis; priority_queue<int> g,f; int main(){ //freopen("gremlin.in","r",stdin); //freopen("gremlin.out","w",stdout); scanf("%d%d%d",&x,&y,&m); for(int i=1;i<=y;i++){ scanf("%d",&a[i]); } for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&b); if(u<=x||v<=x){ f.push(b);//只要有一头连接小精灵直接剪断扔进堆里，不连边 } else{ vis[u]=1; vis[v]=1; } } for(int i=x+1;i<=x+y;i++){ if(!vis[i]){ g.push(a[i-x]); } } //(1)的话if(g.size()>f.size())无解 long long ans=0; 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 i=1;i<=n;i++){//枚举每一类物品（第i类） for(int k=1;k<=s[i];k++){//i类物品一共有s[i]个，所以拿物品的时候可以拿s[i]次，相当于复制 //标准01背包倒序循环 for(int j=V;j>=v[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][sum>>1]若为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分

#include<bits/stdc++.h> using namespace std; int a[10],dp[10][20005]; int main(){ //freopen("candy.in","r",stdin); //freopen("candy.out","w",stdout); int cnt=0; while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]){ cnt++; memset(dp,0,sizeof dp); int sum=0; for(int i=1;i<=6;i++){ sum+=a[i]*i; } if(sum==0){ break; } if(sum%2!=0){ printf("Collection #%d:\nCan't 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 i=1;i<=6;i++){ for(int j=sum>>1;j>=0;j--){ dp[i][j]=dp[i-1][j];//一个都不拿 } for(int k=1;k<=a[i];k++){ for(int j=sum>>1;j>=i;j--){ dp[i][j]|=dp[i][j-i]; } } } if(dp[6][sum>>1]){ printf("Collection #%d:\nCan be divided.\n\n",cnt); } else{ printf("Collection #%d:\nCan't be divided.\n\n",cnt); } } }

我们来进行优化，从二进制优化版本的多重背包开始说

把一包糖果拆成几堆，每堆有2的幂次方数个，拆的堆数显然不会很多，自然时间复杂度就低了，对这几堆跑01背包就完成了问题的转换，这样拿物品的所有情况自然出来了

拿1个，拿1那一堆 拿2个，拿2那一堆 拿3个，拿1那一堆和2那一堆

拿4个，拿4那一堆 拿5个，拿4那一堆和1那一堆（二进制数为1的数位是要拿的）

拆完剩下的也要作为一堆来跑01背包

其实这么搞完再套上滚动数组，每一“类”这个概念已经淡化了

AC代码在去年博客

六，总结

从篇幅上的转移上来说，重心落在了第三，四题上面，也体现了本次备考的中心，好了就这样

七，祝福

这个环节也是复活了好吧

祝同学们金榜题名