codeforces链接Dashboard - Codeforces Round 1101 (Div. 2) - Codeforces本蒟蒻第一次在 codeforces 的 div2 场做了两道题唯一可惜的就是 C1 题的 DP 似乎思考有点问题状态开多了而且还有些理解有点问题但是总体思路是正确的后续补题也很快就 AC 了。在此给大家分享一下我做前三题的个人思路及题解。A题A题读完就很好理解意思就是开始这 n 个人都处在各自的 $a_i$ 位置需要让 n 个人最终都集中在同一个位置。而我们的操作方法就是每次都可以打给两个人两个人位置分别是 ab假设 ab 可以让他们去到 [a,b] 之间任何一个位置。求我们最少操作几次才能让他们去到同一个位置。其实自己对数据模拟几次就能发现我们当然是想让每个人一步到位去到我们想让他去的位置但去到那个位置比较好就很难抉择。而且直觉来说我们应该更倾向于把两个相差大的位置进行一次操作因为这样就可以照顾一下其他那些相差小的位置去到更中心的位置减少操作次数了。比如数据 1 2 3 4我们如果操作 1,4 和 2,3 我们可以让他们去到 2 或者 3 点。但如果我们选 1,2 和 3,4 就发现我们还需要更多操作才可行了。所以我们的思路就是尽量每次操作选择两个相差大的位置这样他们可选择的去处就很多了。其次一个问题是我们应该让他们最终去到哪个地方。由于按照我们的思路最终选择的两个位置相差会越来越小大区间应该照顾一下小区间嘛去到小区间可到达的地方。就比如刚刚的 1 2 3 4 一样我们肯定选择去到 2 3 点而不是 1 4 点。最终其实就能确定我们要去的地方其实就是整个数组的中位数位置。知道了这个其实做法就显然了我们只需要先对数组排序然后两侧同时向内进行遍历如果两个人都已经处在了中位数位置那就说明不需要操作了。代码如下。#include bits/stdc.h #define int long long using namespace std; int arr[105]; void solve(){ int n; cinn; for(int i1;in;i) cinarr[i]; sort(arr1,arrn1); int parr[n1];//记录中位数 int ans0; for(int i1;i(n1);i){ if(arr[i]pparr[n-i1]) continue; ans; } coutans\n; } signed main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T1; cinT; while(T--){ solve(); } }虽然看着挺简单的但其实我也想了这题好久因为有点害怕自己的思路出问题嘛罚时可就不好了。还有就是我在这题提交的时候第一次忘记删掉了自己用来 debug 的输出导致了一次 WA 大家以后一定要记得删掉 debug 用的输出啊......B题这题理解起来感觉也稍微有一点点难度因为我英语太差了。不过主要我们是要理解这个抹糖霜的方法。首先其实可以看到我们能让这个 i 点能够达到多高的高度其实很大程度上取决于上一个点最大能达到多高的高度。可以发现题目给的数据答案都是单调不上升序列而且结合我们自己的理解也能推断出来这一点。可以这么说当前这个 i 的最高高度绝对不会超过上一个点 i-1 能达到的最高高度只有可能持平或者更矮。所以我们目前要解决的问题就是这个 i 点的高度到底应该和上一个持平还是应该更矮首先如果当前这个点的糖霜量本来就比上一个点达到的最高高度要大或者等于那就肯定可以持平了。但是我们也要注意如果这个点糖霜量比上一个最高高度小也不一定就一定不能持平。因为上一个点达到最高高度的时候很有可能还有糖霜剩下没填入最高高度而被抹掉的我们必须把这部分加上进行判断。最终就能得到我们可以直接继承上一个点 i-1高度的判断只有当前 i 点的糖霜量加上上一个点达到最高高度后剩下的糖霜能够大于或者等于上一个点 i-1 的最高高度才能直接继承上一个点 i-1 的最高高度。得到这个思路我们就要求快速算出 i-1 点达到最高高度时候剩下多少糖霜了。其实也很好做我们既然知道了 i-1 的最高高度了那为了达到这个最高高度需要的糖霜就是最高高度 × (i-1)。剩下多少糖霜只需要知道前 i-1 个点有多少糖霜然后减去达到最高高度所需糖霜即可。很明显我们需要一个前缀和来查询前 i-1 个点有多少糖霜。那如果都加上了之前剩下的糖霜了都不能和之前的 i-1 高度持平了那我们只能达到更矮的高度了。这个时候更简单我们只需要将前 i 个点所有的所有糖霜除以 i 平均分配一下就好了。这样确实是不会出问题的我当时觉得万一前面的糖霜很多导致最后得出高度比持平高度还高怎么办这不就不符合常理了吗所以我当时采用了一个二分来解出这个高度。但其实现在一想如果已经太矮不能达到持平了其实前面的糖霜量根本不可能平均分配后还能比上一次的 i-1 要高了。所以我们只需要将糖霜平均分配向下取整即可。最终代码如下。#include bits/stdc.h #define int long long using namespace std; const int maxn2e55; int arr[maxn];//每个点的糖霜量 int sum[maxn];//前缀和 int dp[maxn];//记录每个点的最高高度 void solve(){ int n; cinn; for(int i1;in;i){ cinarr[i]; sum[i]sum[i-1]arr[i]; } dp[1]arr[1];//第一个点肯定等于他自己的高度了 for(int i2;in;i){ int psum[i-1]-dp[i-1]*(i-1);//计算p是上一个点达到最高高度后剩下的糖霜 //如果加上剩下糖霜可以达到和上一个持平就直接更新等于dp[i-1] if(arr[i]pdp[i-1]){ dp[i]dp[i-1]; continue; } //达不到持平只能更矮直接平均分配就好了 dp[i]sum[i]/i; } for(int i1;in;i) coutdp[i] ; cout\n; } signed main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T1; cinT; while(T--){ solve(); } }C1题这个题目看起来就难很多了。事实上我刚开始还以为贪心地只要来一个符合条件的都让他入座A人既然这么好用我就为了 I 人腾位置只要坐过人的桌子有空位就坐就好了吧当我实操之后发现题目的最后一组数据就是一种反例了。如果 A 人我让他坐坐过人的位置那么 E 人就坐不进来了反之我如果让 A 人给 E 人入座去选择坐空桌那 I 人也进不来了。这时候面临一个巨大抉择A 人到底该坐去哪个位置比较好既然我们的选择这么困难贪心已经无法解决了那么很自然就能想到 DP 。而且他题目有个非常重要的一句话就是“Note that once a friend is seated, they are not allowed to move even if they are not seated according to their personality anymore.”翻译过来就是“注意一旦一个人被安排坐下即使之后该桌的座位情况不再符合他们的性格要求他们也不会再移动。”。那就是说前面坐过的人根本不影响后面的人后面的人能不能入座只取决于他们自己学术点说就是“无后效性”完全适配于动态规划 dp 。只不过我当时做题的时候的 dp 定义有点差错。我错误地以为我还需要记录第 i 个人选不选的情况实际上根本不需要因为也不用要求连续选几个人记录这个一点用也没有。这也很大程度导致我的做法非常复杂最后出错了。所以正常来想我们应该定义一个 dp[i] 来记录前 i 个人的最大情况。但是还不够我们进行抉择的时候还需要知道当前我们有几个桌子有人坐了知道这个还可以利用总桌子数来得到空桌子数这样才能决定是否能让人入座。最终我们应该定义dp[i][j] 前 i 个人坐了 j 个桌子能达到的最大人数定义好了这个之后我们推导状态转移方程其实就不难了。首先无论到了哪个人我们都可以不选他入座不选的话直接继承 i-1 情况即可。dp[i][j]dp[i-1][j]然后就要看看如果我现在要选择这个人它是否符合条件了。如果是I 人他必须要占据一个单独的空桌子那么剩给前面 i-1 个人就只有 j-1 个桌子能坐了。而且必须要 j0 才行否则不符合逻辑也不符合定义。所以如果是 I 人可以得出dp[i][j]max(dp[i][j],dp[i-1][j-1]1) (j0)如果是E 人他又必须坐到有人的桌子上。那我们就需要判定坐过人的桌子上是否还有空位给这个 E 人已知我们已经占据了 j 个桌子每个桌子都有 s 个座位而前 i-1 个人坐了 dp[i-1][j] 个位置。所以说只要 s × j - dp[i-1][j] 大于 0 那就是有空位给这个 E人入座了。而 E 人入座并不会给占据桌子数发生变化只需要继承 dp[i-1][j] 再加上他本身入座的 1 个人就好了。dp[i][j]max(dp[i][j],dp[i-1][j]1)如果是 A 人那就是以上 I 人和 E 人的结合了不再赘述。推导出来状态转移方程其实接下来就很好做了。但要注意的是题目的数据 3000 还是有点大了如果直接开一个 dp[3005][3005] 数组每次都要 memset 那很可能会超时所以最好进行滚动数组的优化也可以省一点内存。而且我们memset 的时候要注意最好全部初始化为一个极小值因为很显然我们的 dp 定义有很多地方是不合逻辑的。比如 dp[i][j] 如果这个状态存在那它的大小就不可能小于 j 因为占据 j 个桌子我们至少也要需要 j 个人。如果我们还是粗暴地初始化为 0 那很可能会让我们的答案错误。所以全部初始化为一个极小值然后令 dp[i][0]0才是可行的。如果对滚动数组不熟悉的可以查看我之前的关于滚动数组的博客有详细的写法教程链接【动态规划进阶】DP 空间优化背包 DP 滚动数组从正逆序遍历到奇偶滚动-CSDN博客最后的代码如下。#include bits/stdc.h #define int long long using namespace std; const int maxn2e55; int dp[2][3005]; void solve(){ int n,x,s; cinnxs; string str; cinstr; str str;//让下标从1开始 //初始化 memset(dp[0],0xc0,sizeof(dp[0])); dp[0][0]0; for(int i1;in;i){ int nii1; int bi(i-1)1; //每一次都要给新一次dp滚动数组初始化 memset(dp[ni],0xc0,sizeof(dp[ni])); dp[ni][0]0; for(int j0;jx;j){ dp[ni][j]dp[bi][j]; if(str[i]I){ if(j0) dp[ni][j]max(dp[ni][j],dp[bi][j-1]1); }else if(str[i]E){ if(s*jdp[bi][j]) dp[ni][j]max(dp[ni][j],dp[bi][j]1); }else{ if(j0) dp[ni][j]max(dp[ni][j],dp[bi][j-1]1); if(s*jdp[bi][j]) dp[ni][j]max(dp[ni][j],dp[bi][j]1); } } } int ans0; //找出最大值占据了几个桌子都有可能是最大值 for(int i0;ix;i) ansmax(ans,dp[n1][i]); coutans\n; } signed main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T1; cinT; while(T--){ solve(); } }