一前言24年第3次模拟补题感觉不大行啊瓶颈了记忆中24年做的时候第四题非常难所以本次先押了第三题发现不大行啊尝试打第四题的暴力直接喜提零蛋只能说T3,4阻力依旧很大今天的补题尽量正经一些多说题相关的内容二成绩1.环形储物柜【100/100】嗯这波卡了兄弟2.是否同构【100/100】恨意从未消退3.书籍调序【20/100】大妈你谁4.社恐的聚会【0/100】我没捐啊神特喵比前年还低总分【220/400】今日班级Rank8榜一题四满分老师官方认证的这套题难题一稍微卡了一会题二做的倒是不慢三四题真实难以跨越的鸿沟三题二在这里对前年的内容进行一些补充吧重放题面有两个长度为 n 的数组 a,b。如果存在一个整数 k满足0≤k≤并且保持数组 b 不动将数组 a 的前 k 项与后 k 项对应交换也就是对于所有 1≤i≤k交换 ai​​ 与 a​n−ki​​交换后得到的数组恰好等于 b则称数组 a 和数组 b 同构。给定多组数组 a,b请分别判断它们是否同构。这是考场注释//检查方法a所有元素互不相同b中的元素一定有一个唯一的a[i]与之对应//要使b与a完全重合b[1]对应的唯一的a[i]必须要换到a[1]且i位置若换到1位置的话每个i会对应一个唯一的k//换完检查合法性即为答案a1 2 5 6 3 4b3 4 5 6 1 23(b[1])对应一个唯一的a[5]a[5]必须换到a[1]唯一对应的k为2(6-51)为1或3或其他均无法将a[5]换到a[1]看完这个基本这个题就结束了回看24年心态真是够差的今年反而呢淡了一些吧四题三去年挑战csp-s第一题的时候犯了相同的错误两个题都是本质贪心我却写了两个DP这一次的赛上放24年绝对得崩溃但其实今年的表现也没有好多少先放题面书架上一开始从左到右摆放了 n 本书第 i 本书的编号为 a​i​​。老师希望把书架调整成目标顺序 b1,b2,...,bn。每次操作可以选择当前书架上的任意一本书并将它移动到书架最前面。如果两个序列包含的书不完全相同则无法完成调整输出-1否则请计算最少需要执行多少次操作。编号相同的书可以看作完全相同的书。好吧初始思路还是骗分本质老鼠我的思路是求最长公共子序列LCS感觉脑子已经有点迷糊了我一写代码直接就发现了3个问题1由于对这个算法不够熟悉不知道它的dp写法不转LIS二分没有优化方法最优时间复杂度为O(n方)导致我还沉浸于先写一个普通的再慢慢优化的幻想数据范围卡掉O(n方)也证明了LCS不是这个题的答案2不会写LCS这个事也是直接影响了我好一会我没有因为考到这个但发现忘了不会写这个心态炸掉而是好不容易又手推又回忆的终于写出了完全正确的算法却突然发现这个题用不了LCS的时候心态才炸也自然改不动了一直觉得LCS是对的尝试在它上面优化最终失败3过不了样例的时候没有选择放弃3个题面样例都过了但我自己手推的样例怎么着都过不了都写不出来一直觉得是我没考虑到一些情况但没想到这是算法上的硬伤包括还有脑子推自己的样例很难得到正确答案等诸多问题除了心态和状态我们现在来分析一下题目本身简单贪心把书分为两类一类是被移动过的书一次到多次集合T还有一类自始至终都没有被移动过的书集合S而集合S不动相对顺序永远不变因为往前放的原则所有被移动的书一定会出现在没有被移动的书的前面即有最终序列满足 T重新排列S顺序不变集合S必须是目标序列的一段后缀这就是它和LCS的本质区别并不是值一样就行了LCS只要求选出的元素在 a 和 b 中相对顺序一致不要求选出的元素是 b 的后缀最关键的是存在某个 k使得并且 S 在原数组 a 中出现的相对顺序和 b 里面一致本题要求b里的公共子序列必须要是b的末尾连续一段贪心策略就是让不动集合S最大所以就是找最大的k建议使用双指针T自然不用多说不管要求的前缀排列是什么都可以通过改变T中元素移动的顺序来得到这里面的元素显然不能不动又最优每个元素移动一次只做最后一次到位的移动可以通过顺序来调整所以T中元素个数即为答案AC代码注意无解判断真的短啊好简单#includebits/stdc.h using namespace std; const int N5e35; int a[N],b[N],dp[N][N],aa[N],bb[N]; int main(){ int n; cinn; for(int i1;in;i){ cina[i]; aa[i]a[i]; } for(int i1;in;i){ cinb[i]; bb[i]b[i]; } sort(aa1,aan1); sort(bb1,bbn1); for(int i1;in;i){ if(aa[i]!bb[i]){ cout-1\n; return 0; } } int rn,ln,cnt0; while(l0){ if(a[l]b[r]){ r--;l--; cnt; } else{ l--; } } coutn-cnt; }五题四真正的魔王来了但是魔王其实也是小萝莉仅输出-1———20分仅输出————65分我滴妈加起来85分了你直接给我A了算了不说别的今天说好要正经直接看题必须解决这个萦绕在我心里两年的梦魇有 n 个患有社交恐惧症的人想参与一个聚会但是这个聚会只有两张桌子。每张桌子上的任意两个人都必须相互认识。认识关系不一定对称也就是说可能第 i 个人认识第 j 个人但第 j 个人并不认识第 i 个人。只有两个人互相都认识时他们才可以被安排在同一张桌子上。允许某一张桌子为空。请判断能否将所有人安排到两张桌子上使得每张桌子内部任意两个人都是相互认识的。如果可以请进一步求出两张桌子中人数最多的那张桌子的最少人数。前年光顾着装逼了把题解粘贴上去啥也看不懂这个题并不是二分最小化答案现在我们详细说说这个题到底怎么做拓展二分图我们先明确一下二分图的定义一个无向图如果可以把所有顶点分成两个互不相交的集合 (X,Y满足图里所有的边只能跨集合连接X 连到 Y同一个集合内部没有任何边。判定是找奇环本来初赛就应该学的但我啥也不知道一个无向图是二分图当且仅当图中不存在长度为奇数的环奇环好有了二分图这样的一个先导知识我们来做这道题p1神秘p1回归首先建图我们把所有不互相认识的人之间连一条无向边这条边是为了标记哪两个人不可以放到同一张桌子上的打dfs进行黑白染色法无向边一端染黑色一端染白色染黑色1的放在桌1或者桌2都无所谓染白色0的放在桌2也可以是桌1这样根据二分图的判定有奇环染色失败的情况直接无解顺便可以想象一下我和你互相不认识咱俩不能在一个桌 我染黑色你染白色你和他互相不认识你俩不能在一个桌 你染白色他染黑色他和我互相不认识我他不能在一个桌 我染黑色他染白色怎么有人既染白色也染黑色啊喵的一共就俩桌还分个屁啊buship2这样我们对于每个每个连通块都染好色了连通块和连通块之间没有边证明没有不能同桌的限制我们把每个连通块视为两个物品把其中一张桌子作为当前的收益对一个连通块的两个物品只能选择其中一个这就是一个分组背包卡了一会但又觉得很蠢的三个问题你怎么知道选完这个连通块下一个连通块可以随便选不需要考虑连通块和连通块之间的不合法情况吗我真想过显然我们的建图方式直接决定了只要两点之间没有边这两点一定有坐在同一个桌子上的合法性连通块和连通块之间呢互不影响为什么一个连通块内只能二选一我们的染色规则决定了一个连通块会被分为两个组二分图你选了一个组另一个组显然呢就不能选了那又不能一个组只选部分人那剩下一部分人显然会和另一组的人在一块这是非法的所以只能整组整组的二选一为什么这一个连通块染黑色的和那一个连通块染白色的可以坐在一块我们染的色不是真正意义上的染色而是将一个连通块内的人分为两个组这两个组内部互斥与外部的组没有任何的关系跨块没有任何限制所以每个连通块的选择完全独立这个块选A组那个块选B组或者A组都没有关系明确这三个问题我们现在来愉快地dp吧可行性dp转移时常常使用 |先看一下dp[j]的含义dp[j]1处理完若干个连通块后有方案可以能够使第一张桌子上坐满j个人dp[j]0处理完若干个连通块后没有任何方案可以使第一张桌子上坐满j个人那我们第二张桌子上的人数就是n-j再看一下转移对于每个块的两个组组a和组b来说我们一共有两种选择第一种选择第一张桌子坐组a的人第二种选择第一张桌子坐组b的人我们额外设立dp2这边是状态副本法在每次内部循环的时候dp[i]是存储的还没有考虑这个连通块的时候可行性dp2存储该连通块对状态产生的影响也就是新产生的可行性i表示没有考虑这个连通块的时候第一张桌子上有i个人选择a组dp2[ia] |dp[i]选择b组dp2[ib] |dp[i]那么此时问题来了为什么要有dp2还是那个问题你要在新状态考虑这个连通块之后上继承还是在旧状态没有考虑这个连通块上继承dp2不自继承dp也不自继承在这个状态中你选择了A组后续状态的更新你显然不会再基于这个选A组的状态来更新了而是基于你没选任何东西的状态再继承不然像连续选同连通块内两个A组一个A组一个B组的非合法情况都出来了这一点可以与昨天能重复选的背包进行区分倒序循环滚动数组的写法似乎可以保证了更新一个状态后下一次更新不会基于这个状态再更新但其实不行因为这样的话无法保证每组内至少选一个于是放弃答案的话呢如果dp[j]1证明第一个桌子放j个人可行这样直接循环比较在j和n-j的大值两张桌子中人多的那一张里面求最小值即有答案AC代码#includebits/stdc.h using namespace std; const int N520; int f[N][N],dp[N],dp2[N]; vectorintmp[N]; vectorpairint,int v; int col[N],flg1,c0,c1; void dfs(int x,int c){ col[x]c; if(c0) c0; if(c1) c1; for(auto i:mp[x]){ if(col[i]-1) dfs(i,c^1); else if(col[i]c) flg0; } } int main(){ int n; cinn; for(int i1;in;i){ for(int j1;jn;j){ cinf[i][j]; } } for(int i1;in;i){ for(int ji1;jn;j){ if(f[i][j]0||f[j][i]0){ mp[i].push_back(j);//单方认识和互不认识都可以啊 } } } for(int i1;in;i){ if(col[i]-1){ c0c10; dfs(i,0); v.push_back({c0,c1}); } } if(flg0){ coutNo\n; return 0; } coutYes\n; dp[0]1; for(pairint,int x:v){ int ax.first,bx.second; memset(dp2,0,sizeof dp2); for(int i0;in;i) dp2[ib]|dp[i],dp2[ia]|dp[i]; memcpy(dp,dp2,sizeof dp); } int ansn; for(int j0;jn;j){ if(dp[j]){ ansmin(ans,max(j,n-j)); } } coutansendl; }六总结挺好的今天解决了前年看都不敢看的题有一种莫名的成就感啊分数已经不重要了心态最重要啊挺喜欢一个博主说的话“没出没事出了好事”但同时也要紧迫一些做到松弛有度明天的比赛要认真对待七祝福祝稳稳的幸福