Codeforces Round 1101 (Div. 2) A-C1题思路解析及题解

codeforces链接：Dashboard - Codeforces Round 1101 (Div. 2) - Codeforces

本蒟蒻第一次在 codeforces 的 div2 场做了两道题，唯一可惜的就是 C1 题的 DP 似乎思考有点问题，状态开多了而且还有些理解有点问题，但是总体思路是正确的，后续补题也很快就 AC 了。在此给大家分享一下我做前三题的个人思路及题解。

A题

A题读完就很好理解，意思就是开始这 n 个人都处在各自的 $a_i$ 位置，需要让 n 个人最终都集中在同一个位置。而我们的操作方法就是每次都可以打给两个人，两个人位置分别是 a，b（假设 a<=b ），可以让他们去到 [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; cin>>n; for(int i=1;i<=n;++i) cin>>arr[i]; sort(arr+1,arr+n+1); int p=arr[n>>1];//记录中位数 int ans=0; for(int i=1;i<=(n>>1);++i){ if(arr[i]==p&&p==arr[n-i+1]) continue; ++ans; } cout<<ans<<'\n'; } signed main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T=1; cin>>T; 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 maxn=2e5+5; int arr[maxn];//每个点的糖霜量 int sum[maxn];//前缀和 int dp[maxn];//记录每个点的最高高度 void solve(){ int n; cin>>n; for(int i=1;i<=n;++i){ cin>>arr[i]; sum[i]=sum[i-1]+arr[i]; } dp[1]=arr[1];//第一个点肯定等于他自己的高度了 for(int i=2;i<=n;++i){ int p=sum[i-1]-dp[i-1]*(i-1);//计算p是上一个点达到最高高度后剩下的糖霜 //如果加上剩下糖霜可以达到和上一个持平就直接更新等于dp[i-1] if(arr[i]+p>=dp[i-1]){ dp[i]=dp[i-1]; continue; } //达不到持平只能更矮直接平均分配就好了 dp[i]=sum[i]/i; } for(int i=1;i<=n;++i) cout<<dp[i]<<' '; cout<<'\n'; } signed main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T=1; cin>>T; 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 个桌子能坐了。而且必须要 j>0 才行，否则不符合逻辑，也不符合定义。所以如果是 I 人，可以得出

dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1) (j>0)

如果是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 maxn=2e5+5; int dp[2][3005]; void solve(){ int n,x,s; cin>>n>>x>>s; string str; cin>>str; str=" "+str;//让下标从1开始 //初始化 memset(dp[0],0xc0,sizeof(dp[0])); dp[0][0]=0; for(int i=1;i<=n;++i){ int ni=i&1; int bi=(i-1)&1; //每一次都要给新一次dp滚动数组初始化 memset(dp[ni],0xc0,sizeof(dp[ni])); dp[ni][0]=0; for(int j=0;j<=x;++j){ dp[ni][j]=dp[bi][j]; if(str[i]=='I'){ if(j>0) dp[ni][j]=max(dp[ni][j],dp[bi][j-1]+1); }else if(str[i]=='E'){ if(s*j>dp[bi][j]) dp[ni][j]=max(dp[ni][j],dp[bi][j]+1); }else{ if(j>0) dp[ni][j]=max(dp[ni][j],dp[bi][j-1]+1); if(s*j>dp[bi][j]) dp[ni][j]=max(dp[ni][j],dp[bi][j]+1); } } } int ans=0; //找出最大值，占据了几个桌子都有可能是最大值 for(int i=0;i<=x;++i) ans=max(ans,dp[n&1][i]); cout<<ans<<'\n'; } signed main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int T=1; cin>>T; while(T--){ solve(); } }