CSP-J T4 针对性复盘

· · 算法·理论

前言

哎呀，CSP-J 嘛，对于一个只想拿 300 分，或者只想拿 200 分，甚至只想呼呼的飘过一等线的 OIers 来说，T4 貌似是个废物，对提高分数没有任何帮助！
然而，真的是这样吗？当然不是咯。要不然，我为何还要写这篇文章，来针对性的总结 T4 呢？

T4，虽然你不奢望想出满分做法，但是部分分还是有的啊。有的时候纯暴力的那种部分分就有 20 来分，加点思考进去，可能就有 50 分甚至更多了，这分可不少啊。

因此，T4 还是很重要的啦。

做 T4，该抱着什么样的心理

正如这一段的标题所述，做 T4，该抱着什么样的心理去做呢？
做 T4，应该是你在前面几道题都已经没有什么再好拿分的点了，或者说虽然可能 T3 还能拿分，但你觉得 T4 拿分的性价比更高的话，你才会去做 T4。

做 T4 啊，作者认为，应该是抱着一种“我不追求满分，我只要尽可能多的部分分”的心理，认真地对待每一点部分分。如果多敲 20 行代码，多用掉 10 分钟，可以赚得 10 分甚至更多的话，那么，建议你还是去打一下。

做 T4 啊，还要学会把部分分结合到一起。
比方说我随便举个例：
你已经想好了一种 O(n^3) 的做法，在 n \le 500 的时候可以用，可以获得 40 分；
你还想到了一种 O(n) 的办法，但使用这种办法需要满足特殊性质 a_i < a_{i+1}，可以获得 20 分；
你最后还发现了一种答案就是 0 的解法，需要满足特殊性质 a_i=a_{i+1}，可以获得 10 分。
那么你可以学聪明点儿，把这三个部分分用大 if 框起来，比方说写成这样：

...//省略的头文件以及变量定义
bool Is1(){
    for(int i=1;i<n;i++)if(a[i]>=a[i+1])return 0;
    return 1;
}//判断是否满足前一个特殊性质
bool Is2(){
    for(int i=1;i<n;i++)if(a[i]!=a[i+1])return 0;
    return 1;
}//判断是否满足后一个特殊性质
int main(){
    ...//省略的输入和初始化等
    if(n<=500){
        //使用时间为 O(n^3) 的解法，获得 40 分
    }
    else if(Is1()){
        //使用时间为 O(n) 的特殊性质解法，获得 20 分
    }
    else if(Is2()){
        cout<<0;
        //特殊性质解法，直接得出结论并输出答案，获得 10 分
    }
    else{
        cout<<-1;
        //没有法子了，上一个不可以总司令，能有多少分听天由命吧
    }
}

这样子做，只要你保证这三种解法都是对的，那么你至少就拿到了 40 + 20 + 10 = 70 分！这个分数，有那么点儿吓人呢！所以这种 if 嵌套法要学会！

针对题目总结-2023 T4

讲完了大概的做 T4 的考场策略，现在我们来针对题目讲一讲吧。

先看最近的 2023 T4，这道题目考的呢是一个分层图 BFS，或者好像还可以用 Dijkstra 做？不过我没用，我是用的非超纲做法，即分层图 BFS 做的。

首先我们来看看我滴 AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+5;
struct road{int tg,te;};
struct walk{int id,T;}t,o;
int n,m,k,f[N][105];
vector<road> g[N];
queue<walk> q;
int up(int x,int y){
    int as=x/y;
    if(x%y!=0)as++;
    return as;
}
int main(){
    cin>>n>>m>>k;
    while(m--){
        int u,v,a;
        cin>>u>>v>>a;
        g[u].push_back(road{v,a});
    }
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    t.id=1,t.T=0;
    q.push(t);
    while(!q.empty()){
        t=q.front();
        q.pop();
        for(int i=0;i<g[t.id].size();i++){
            road rd=g[t.id][i];
            int dd;
            if(rd.te<=t.T)dd=t.T+1;
            else dd=t.T+up(rd.te-t.T,k)*k+1;
            if(f[rd.tg][dd%k]<=dd)continue;
            f[rd.tg][dd%k]=dd;
            o.id=rd.tg,o.T=dd;
            q.push(o);
        }
    }
    if(f[n][0]==0x3f3f3f3f)cout<<-1;
    else cout<<f[n][0];
    return 0;
}

我们来大致分析一下吧，从主函数开始。

首先呢前面的都是一些输入。我是用 vector 来存图的。

接下来我们遇到了一个 f 数组，它什么定义呢？
告诉你吧，f_{i,j} 表示走到第 i 个节点，且走到的时间 \mod k 为 j 时刻时，最早的时间。
初始化就是全为 \infty，因为这个节点还没去过嘛。但是 f_{1,0} 要设为 0，因为最早的到达 1 节点且 \mod k 为 0 的时刻就是 0 时刻。最终的答案当然就是 f_{n,0} 啦，当然要判断一下是不是 \infty，是的话要输出 -1 哒~

好的接下来就是一个分层图 BFS，其中中间的 dd=t.T+up(rd.te-t.T,k)*k+1; 这句话你可能不太理解。它的意思是，如果到了这条道路，但是还没有开放的话，最早要等到什么时候。等，肯定不是在景区等啦，是在家里等哇。

还是比较好理解的吧？就是一个 BFS 嘛，不过加了个分层，加了个时间限制而已！懂了以后还是很简单的！

我们再来看看部分分。

看看那些 a_i = 0 的部分分，完全就可以直接跑一个分层图最短路嘛，不是很难的 \dots \dots 那个有多少分呢？让我算算——10 + 10 + 15 = 35 分！哇呜！

还有那些 k \le 1 的分，就不需要分层了！处理一下开放时间就行了——把这两种部分分并在一起，一共就有 50 分了哇！

以及前面给的那些 n \le 10,m \le 15 的点，就是给你跑暴力 DFS 的吧，这三种加起来——天哪！我简直不敢相信！这有 65 分！多吓人啊！

所以说，一般 T4 还是会给不少部分分的！

针对题目总结-2022 T4

你确定吗？怎么觉得 2022 年的 T3 比 T4 要难呢？

好的，接下来我们来看 2022 T4。是一道小 DP 啦~
如果你想较为深入的了解 DP，请阅读文章 2 基础动态规划 总结一文。

首先我们来看看我滴 AC 代码：

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y;}a[505];
int n,k,dp[505][105],ans;
bool cmp(node p1,node p2){
    if(p1.x==p2.x)return p1.y<p2.y;
    return p1.x<p2.x;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)dp[i][j]=j+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[j].y>a[i].y)continue;
            int dis=a[i].x-a[j].x+a[i].y-a[j].y-1;
            for(int l=dis;l<=k;l++)dp[i][l]=max(dp[i][l],dp[j][l-dis]+dis+1);
        }
    }
    for(int i=1;i<=n;i++)ans=max(ans,dp[i][k]);
    cout<<ans;
    return 0;
}

代码比较简短啦！

我们来分析分析嘛。

一开始肯定要先给这些点排个序啦，否则就不好更新了！

那么，我们定义的那个 dp 数组是什么意思呢？可以先阅读 2 基础动态规划 总结学习方法，再回过头来回答我这个问题。
告诉你吧，这里的 dp_{i,j} 表示的是考虑了前 i 个点，并且已经用了 j 个自由添加的点，能得到的最长上升点列。

好的，那么该怎么转移呢？很简单，但你可以大概理解为，找到一个可能可以和 i 连成一条上升点阵的一个点，然后算出它们中间需要添加多少个自由点。
请看代码中对应的：

for(int j=1;j<i;j++){
    if(a[j].y>a[i].y)continue;
    int dis=a[i].x-a[j].x+a[i].y-a[j].y-1;
    for(int l=dis;l<=k;l++)dp[i][l]=max(dp[i][l],dp[j][l-dis]+dis+1);
}

或者你还不明白的话，请阅读一位 dalao 的题解，详细又易懂地为你讲述了状态转移方程。

接下来我们来看部分分：

那些 k=0 的，不就是让你求最长上升子序列么？那就有——哇，这就有 40 分了啊！

还有那些 n 和 k 都比较小的，好像也可以爆搜诶！不过我不太清楚，好像这题不太好爆搜，但是那 40 分一定要拿到

至少，我觉得最长上升子序列的这 40 分还是一定要去拿到手！你看嘛，部分分给的还是很多的！

盲猜今年 T4 考什么

我猜啊，今年 T4 考 DP 的概率会比较大 \dots \dots 因为去年没有考 DP，而且 DP 最好变形！

但是考图论也是有可能的，毕竟又没人说不能连着考一样的知识点！还有什么最小生成树呀，虽然超纲但是简单，也可以考！

其他的话——还有，哦对对，就是二分。二分也可以很难呢，可别小看！加点思维和数学，或者干脆用 BFS 啊 DFS 啊什么的来做 check，那，难度飙升啊！

还有就是一些难的思维题啦，这说不清楚的，有的就是思考过程难 \dots \dots

最后的，就是说，大模拟也是有可能考的，但是放在 T3 的概率会大些因为这就是 CSP 的风格。

所以，就算不管今年 T4 考的算法究竟是什么，拿部分分的方法要学到！

后记

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

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

请只要注意上面那两首打油诗的最后一句话，也就是关于 T4 的那两句话。
T4 总被认为很难，但是通常会给不少部分分。其实啊它也是一棵摇“分”树呢！哈哈！