CSP-J T3 针对性复盘

· · 算法·理论

前言

或许对于只是打打 CSP-J 初赛结果进去了的 OIers 来说，甚至连 T1 都不重要，T3 就更不用说了；
或许对那些只是想呼呼的飘过一等线、赚个 5 级勾的 OIers 来说，最重要的也不过是 T2 罢了；
但对于认认真真准备复赛并且想拿到 300 分及以上得 OIers 来说，T3 就至关重要了。

本篇文章的作者我是想冲 CSP-J 300 分以及更高的，因此我会将题目的正解介绍一下。但是会有一些只是想打部分分的朋友们也来阅读了这篇文章，那么很好，我不希望你们失望，我也会讲解部分分的写法。

做 T3，心里最好怎么想

你们来思考思考这个问题吧：做 T3，心里最好怎么想呢？
或许有小蒟蒻认为，T3 会比较难了，打它个 10 分 20 分啊，够够了；
或许有 AK 大佬认为，T3 太简单了，随随便便就 AC 了，用不着什么时间；
但是对于我，一个只是想拿一等高分的小废物来说，要尽量冲高分，冲 AC，实在是做不出来了，那么还是去多拿些部分分吧。你们觉得我说的有道理么？

做 T3，应该是拿稳了 T1 和 T2 的分数后，再去重点思考的一道题目。给个小小的技巧：{\color{purple} 先看题，看懂题后先暴力，暴力打完了再想正解，会让人觉得更安心}。

因此，做 T3，要抱着一种不忧虑、很快乐的心理去做，才会做得又快又准又有底！

针对题目总结-2020~2023 T3

这道题目，这道题目，这道题目，以及这道题目，它们真的没什么好总结的。

它们是恶心的大模拟，很容易写挂，所以——
我建议的做题步骤是：

  1. 如果发现 T3 是大模拟，最好先去看看 T4，因为大模拟太容易写挂了。
  2. 如果 T4 也做得差不多了没出入了，那么请先仔仔细细的把题面通读至少 3 遍，就算是一个字不懂也要联系上下文把它弄懂才行。
  3. 如果认为自己已经理解透彻题面的意图了，那么理清楚题目让你做什么，再以计算机的角度，手摇几个简单的样例，对照输出和样例解释，确保自己理解正确。
  4. 如果现在就是准备开始写大模拟了，可以先写写部分分的大模拟，帮助你进入状态。
  5. 如果部分分的大模拟写挂了，别着急，冷静下来，用注释把每句话的含义标一标，应该很快就能发现错误。
  6. 如果标完注释还是挂了，那么建议手动模拟一遍，一定要对着代码模拟，看看哪一步没有符合你对程序的预期。
  7. 如果部分分都写的差不多了，最终的正解代码你也就会知道个七七八八了，这个时候赶紧趁热打铁把它写完，别放弃！
  8. 如果最终的正解模拟又挂了，那么想想哪里写挂了，可以用上步骤五和六中的办法查一查，实在找不到，就让部分分解上！
  9. 确定自己真的写不下去了或者已经完全写完了以后，把小样例测对，再测大样例，如果错了那么找到错在了哪里！
  10. 如果大样例对了，但你还是觉得不保险，多编几组易错的数据，测一测，看看你的模拟会不会在某一步有出错的隐患！

综上所述，一道模拟题，我认为就是这样了！

你可能会问我，为什么不具体分析一下这四道大模拟题的具体细节呢？
因为单讲一道模拟题的细节，很浪费时间又没什么用，模拟题啊，实在是不好针对一道指定的题目来进行总结！

最后，针对大模拟，送你们一段废话。

针对题目总结-2019 T3

这道题目，倒还有点总结的价值。

它是一道多次完全背包，最近才做的，因此——
双手捧上 AC 代码：

#include<bits/stdc++.h>
using namespace std;
int days,n,m,p[105][105],dp[10005];
int main(){
    cin>>days>>n>>m;
    for(int i=1;i<=days;i++)
        for(int j=1;j<=n;j++)cin>>p[i][j];
    for(int t=1;t<days;t++){
        int ans=0;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            for(int j=p[t][i];j<=m;j++)
                dp[j]=max(dp[j],dp[j-p[t][i]]+p[t+1][i]-p[t][i]);
        for(int i=0;i<=m;i++)ans=max(ans,dp[i]);
        m+=ans;
    }
    cout<<m;
    return 0;
}

咦，为什么是这么做的呢？

其实上没有任何必要考虑留了好几天的纪念品，因为你可以理解为今年你把它卖了，然后又买回来了。因此我们不用考虑留了好几天的纪念品，只要贪心的让每一天结束后都能收获更多的纪念品就可以了。
你追求的是利润，所以你第 i 天买入这编号为 j 的纪念品，再在第 i+1 天卖出，其实上你的利润是 P_{i+1,j}-P_{i,j}。因此，DP 的核心代码中才会出现这个 dp[j]=max(dp[j],dp[j-p[t][i]]+p[t+1][i]-p[t][i]); 啊。

所以这道题其实上弄懂了很简单，不懂觉得很难。
T3，常常有这个特点。

盲猜今年 T3 考什么

我只是想说：别考大模拟了！其他的，考什么都行啊呜呜！我就是不想敲大模拟！

不过，就算是考大模拟，我们也不怕，可以根据上面讲到的做大模拟的十步法来做，一定能拿很高的分！

来，跟我一起，心中默念：
不考大模拟，不考大模拟，考了 4 年了，求别再考了；
允许考 DP，允许考 DP，考个 DP 吧，不过别太难；
考图论也行，考图论也行，最小生成树，单源最短路；
只要非模拟，什么都可以，求求发慈悲，我们来 AK！

哈哈哈哈哈哈哈，这是什么打油诗！

后记

T1，水的要死，你确定？
T2，没有道理，认真的？
T3，就是模拟，一定吗？
T4，很难很难，不是吧？

T1，水死了，一个暴力九十分，输出负一得十分；
T2，很简单，枚举一下五六十，贪心二分是正解；
T3，太奇怪，年年模拟细节多，一个小错挂三十；
T4，超级难，一年动规一年图，乱写搜索七十分。

请只要注意上面那两首打油诗的倒数第二句话，也就是关于 T3 的那两句话。
T3 总是是大模拟，细节多且容易挂，让人烦，但今年应该不会再考了。不过就算考，我们也有办法！不考，那当然更好！