2019 CSP-J 复赛总结——戳我进入

MC_Launcher · 2020-10-30 23:04:33 · 个人记录

关于2019年CSP-J复赛题目总结

——本文章由MC_Launcher编写，未经授权，请勿转载

一)比赛前置知识

A)关于CSP

CSP于2019年第一次举办，原因或因为NOIP与教育部产生矛盾，CSP分为S组和J组，S组较难，J组较简单，S组只有是高中生及以上或被推荐(据说)才能参加。

而NOIP于2020年复活，获悉，只有通过CSP-S初赛才能参加。

B)输入输出

对于这种大型比赛，为了较好地判断程序正确性，一般使用重定向输入输出流，而C++比赛常用为freopen函数

此函数包含在cstdio头文件中

使用格式如下：

在main函数开头添加以下内容（最好这么办)

freopen("文件名.拓展名" , "r" , stdin) ;//读
freopen("文件名.拓展名" , "w" , stdout) ;//写

而在程序末尾应使用以下语句以防出bug

fclose(stdin) ;
fclose(stdout) ;

在你需要调试时，可以将freopen语句注释掉，注意！调试完后一定要删去

C)关于头文件

C++有一个头文件，bits/stdc++.h，叫万能头文件，这个头文件包含了大部分C++头文件，但不是全部，例如windows.h就没有包含在内

目前CSP部分省区评测机貌似不能使用万能头，因此大家还是要背记一些常用头文件，如下：

#include <iostream> //数据流输入/输出
#include <cstdio> //标准输入/输出函数
#include <iomanip>  //参数化输入/输出
#include <cstring> //字符处理
#include <cmath> //数学函数
#include <float> //浮点数处理
#include <fstream> //文件输入/输出
#include <limits.h> //定义各种数据类型最值常量
#include <algorithm> <queue> <stack> <set> <vector> //STL汇总

以上即是一些常见头文件，万能头有不能用的时候，编译失败就会惨遭爆零。

update2022/11/25:显然万能头啥时候都能用,wssb

二)T1部分 （题目：P5660）

A)前置知识

关于T1，是字符串的题目，常用的字符串类型有：string(不定长),char(定长)，char需要注意越界问题。

获取字符串长度方法：

//string类型：length() 头文件：<string>
//例子
#include <string>
#include <iostream>
using namespace std;
int main()
{
    string a ;
    cin >> a ;
    int b = a.length() ;
    cout << b << endl ;
    return 0 ;
}
//输入 ：12345  
//输出 ：5

//char类型：strlen() 头文件：<cstring>或<string.h>
//例子
#include <cstring>
#include <iostream>
using namespace std ;
int main()
{
    char a[5] ;
   cin >> a ;
   int b = strlen(a) ;
   cout << b << endl ;
   return 0 ;
}
//输入 ： 234
//输出 ： 3

B)T1讲评

如题，题目要求为输入一个长度为8的01串，求1的个数

既然已经知道字符串长度，那么我们直接用char定义一个长度为8的字符串并遍历一遍，用一个计数器求1个数

代码如下

#include <iostream>
using namespace std ;
int main()
{
    char a[8] ;//字符串数组
    int x = 0 ;//计数器
    cin >> a ;
    for(int i = 0 ; i < 8 ; i++)
    {
        if(a[i] == '1')//判断是否为1
        {
            x++;
        }
    }
    cout << x ;//输出
    return 0 ;
}

此题题目难度极低，基本上送分。

三）T2部分 （题目：P5661）

A)前置知识

此题为了更简洁明了，建议使用结构体(struct)

struct不需要头文件，直接使用即可，使用方式如下

struct 结构体名称
{
    包含的变量或数组
};

结尾需要加上一个分号，否则会编译失败。

结构体排序

定义一个bool类型函数，在函数内只需写return xx.xx < xx.xx;或是大于号，表示按一个函数的某个变量或数组从小到大或从大到小排序。

定义完再用sort排序即可

sort使用方法

头文件：algorithm

sort(数组名,数组名+a+b,排序方式)，a+b表示从数组的第a项到第b-1项，其中a和排序方式可以不写。

例题

一所学校要统计学生期末考试成绩，并按成绩从高到低排序，请你为他们帮帮忙。

输入格式：

第一行包含一个正整数n，表示学生人数

第1到n+1行，每行有一个字符串a_i一个正整数b_i，分别表示学生名字和考试成绩

输出格式：

共n行，每行一个字符串a_i和一个正整数b_i，分别表示学生名字和考试成绩

简略看题，可直接定义包含两个变量(名字，成绩)的结构体，再进行sort排序即可。

代码如下

#include <iostream>
#include <algorithm>
using namespace std ;
struct student//"学生"结构体
{
    string name ;//名字
    int grade ;//成绩
};
bool cmp(student k,student j)//从大到小排序
{
    return k.grade > j.grade ;
}
student a[1001] ;
int main()
{
    int n ;
    cin >> n ;
    for(int i = 0 ; i < n ; i++)//输入
    {
        cin >> a[i].name >> a[i].grade;
    }
    sort(a,a + n,cmp);
    for(int i = 0 ; i < n ; i++)//输出
    {
        cout << a[i].name << " " << a[i].grade << endl;
    }
    return 0 ;
}
//输入：
//3
//Jack 120
//Marry 105
//Cindy 130
//输出：
//Cindy 130
//Jack 120
//Marry 105

B)T2讲评

T2题意简述：给你了一些乘车记录，0是地铁，1是公交车，如果一张地铁的票价小于一张公交车的票价且是在45分钟之内，并是最早的满足条件的一张，公交车车票免费。

那么直接将全部记录在一个数组里，将每张公交车票逐一判断。但是数据范围10^5，暴力的复杂度为O(n^2)，那么大约需要10^{10}次循环，而时限1s，必定超时(TLE)，只能得30tps，因此我们要优化。

如何优化？

因为保证任意两次乘车记录不在一分钟，且乘车记录最多10^5条，所以只需要开一个10^5的数组即可。

对于每张公交车票，只有45分钟前的车票有效，因此我们不用去想得太复杂，每次往前遍历45张票即可。

代码如下

#include <iostream>
#include <algorithm>
using namespace std ;
struct ticket
{
    bool type ;//0地铁1公交车 
    int pay,time ;//花费和时间 
};
ticket t[1000001] ;
int main()
{
    int n , ans = 0 , flag = 0 ;//乘车记录条数，最终花费，判断是否有地铁票优惠券使用
    cin >> n ;
    for(int i = 0 ; i < n ; i++)//输入
    {
        cin >> t[i].type >> t[i].pay >> t[i].time ; 
        if(!t[i].type)
        {
            ans += t[i].pay ;//地铁票需要付款，直接加上
        }
    }
    for(int i = 0 ; i < n ; i++)
    {
        if(t[i].type)//对于一张公交车票
        {
            flag=0;
            if(i >= 45)//判断是否会越界
            {
                for(int j = i-45 ; j < i ; j++)
                {
                    if( (!t[j].type) && t[i].time - t[j].time <= 45 && t[i].pay <= t[j].pay)//如果同时满足是地铁票、在45分钟之内、花费比公交车票多
                    {
                        t[j].type = -1 ;//标记已经被用过
                        flag = 1 ;//已经使用标记一下
                        break ;//只需一张优惠券即可
                    }
                }
            }
            else
            {
                for(int j = 0 ; j < i ; j++)//同上
                {
                    if( (!t[j].type) && t[i].time-t[j].time <= 45 && t[i].pay <= t[j].pay)
                    {
                        t[j].type = -1 ;
                        flag = 1 ;
                        break ;
                    }
                }
            }
            if(!flag) ans += t[i].pay ;//如果不能用优惠券就需要付款
        }
    }
    cout << ans ;//输出
    return 0 ;
}

该题比较简单，用暴力思想稍加优化就能解决。

三）T3部分 （题目：P5662）

A)前置知识

memset——初始化函数

该函数用于将一个数组全部赋值，头文件为string.h(不是string)或cstring(等效)

用法memset(数组名 , 值 , sizeof(数组名))

其中，值只能为0，-1或0x3f(多加点3f也没问题，但最好用0或-1)。

动态规划

动态规划是将一个问题分成若干个子问题，求出每一个子问题的最优解，以求得整体最优解，与分治思想相近。

经典动态规划问题：01背包问题

给你若干个物品和一个容量为n的背包，每个物品有一个体积w_i和一个价值v_i，求最多能装进多少价值的物品。

如果用贪心的思想，先装价值最大的物品或性价比最高的物品，显然不能得到最优解。如果是这么一组数据

假如背包容量是10，那么按照贪心思想，必定先选第一个，价值为10，那么如果装第二、三个，价值为12，显然更优

按照性价比，如果第一个物品体积是6，那么肯定先选第一个，第二、三个无法装入，不是最优解。

所以我们要运用动态规划的思想

定义一个数组a_{i,j}，i表示第i个物品，j表示背包容量，合起来就是当背包容量为j的时候是否装第i个物品。

如果我们不装这个物品，那么最大值就是a_{i-1,j}，即前i-1个物品装进容量为j的背包的最大值；如果装进去，最大值就是a_{i-1,j-w[i]}+v_i，即装进这个物品，这个物品的价值加上前i-1个物品中剩余容量最多能装入的价值，而且需要判断目前背包容量是否能装入这么大的物品(或让j从w_i开始循环)。

状态转移方程如下

a[i][j] = max (a[i-1][j] , a[i-1][j-w[i]] + v[i]) ;

滚动数组优化(一维数组优化)

这个空间占用有点大，因此我们要考虑压缩空间以免内存超过限制(MLE)

思考一下，对于每一个a_{i,j}，只需要知道a_{i-1,j}与a_{i-1,j-w[i]}，即对于每一个物品i容量j，我们只需要知道i-1的j。因此我们用一个一维数组记录对于每一个物品i背包容量为j时的最值。

对于每一个背包容量j，它的值取决于前面的j-w[i]，但不取决于后面的任何j，因此我们需要从后向前循环判断，这里给出一个例题和模板。

[P1060]开心的金明

模板(不是P1060代码)

#include <bits/stdc++.h>
using namespace std ;
int main()
{
    int n , m ;//背包容量和物品个数
    cin >> n >> m ;//输入
    int v[1001] , w[1001] , dp[30001] = {} ;//物品价值、重量和背包容量
    for(int i = 1 ; i <= m ; i++) cin >> w[i] >> v[i] ;//输入
    for(int i = 1 ; i <= m ; i++)
    {
        for(int j = n ; j > = w[i] ; j--)
        {
            dp[j] = max(dp[j] , dp[j - w[i]] + v[i]) ;//求第i个物品放入与不放入时的最值并比较
        }
    }
    cout << dp[n] ;//输出
    return 0;
}

多重背包问题

即物品有多个，将一个物品的多个分开看即可。

完全背包物品

即物品有无数多个，那么最朴素，最容易想到的方法就是三重循环，即在01背包二维基础上加一个数量。但是我们可以很容易想到，如果知道a_{i,j+w[i]}的最值，显然可以求得a_{i,j+2×w[i]}的最值。那么如果放第i件物品，那么它至少放一件，而背包容量从1或w[i]开始循环，所以每次能放进去一件这种物品的时候都能判断最值，因此这种方法是正确的。

由此可见，我们只需把01背包的第二重循环从前向后搜，因为后面需要用到前面的最值，模板就不给出了，可以直接根据01背包模板改。

B)T3讲评

很显然，这道题是完全背包题，因为买入股票不限量。

但是价值是什么呢？是第二天的股票价格减去第一天股票价格，即这一天决策只会影响第二天。

这里给出证明

假设只有一种股票，共三天，设第一天股票价值为a，第二天为b，第三天为c，现有金币为w

那么现在尽量买入，第二天卖出，可以赚w/a(b-a)，现在背包容量为w+w/a(b-a)，此时再买入可以买(w+w/a*(b-a))/b即w/a张票，与不卖出拥有的票完全相同。那么第三天不卖出与第三天卖出，收入结果相同。因此我们为了便于dp，设第二天卖出第一天全部股票即可。

还有要注意的一个点，如果某一天某种股票价值为负，就不买(其实无需判断，在dp中会自动选最优方案)，因为不买比买赚的金币更少。

代码如下

#include <iostream>
#include <string.h>
using namespace std ;
int p[105][105] , w[105] , v[105] , dp[10005] ;//第i个纪念品第j天的价格，dp中的重量、价值以及dp数组 
int t , n , m ;//天数，纪念品数量，金币数量 
int main()
{   
    cin >> t >> n >> m ;//输入
    for(int j = 1 ; j <= t ; j++)//输入
    {
        for(int i = 1 ; i <= n ; i++)
        {
            cin >> p[i][j] ;
        }
    }
    for(int i = 2 ; i <= t ; i++)//这里从第二天开始循环，因为最后一天买了股票也没用
    {
        for(int j = 1 ; j <= n ; j++)
        {
            v[j] = p[j][i] - p[j][i-1] ;//计算每天股票价值(已证明)
            w[j] = p[j][i-1] ;//"重量"即为股票价格
        }
        memset( dp , 0 , sizeof(dp)) ; //初始化数组
        for(int j = 1 ; j <= n ; j++)
        {
            for(int k = w[j] ; k <= m ; k++)
            {
                dp[k] = max(dp[k] , dp[k-w[j]] + v[j]);//状态转移方程
            }
        }
        m += dp[m] ;
    }
    cout << m ;//输出
    return 0 ;
}

该题需要一定的分析能力，总体来讲还是比较弱的。

五)T4部分 （题目：P5663）

A)前置知识

邻接表

假如给出一个无向图(有向图也可以)，每次给你两个相邻的节点，那么我们可以用邻接表来记录，用a_{i,i}表示i和j有路径直接连接。

但是空间耗费太大，因此我们需要用邻接矩阵，而这个需要用到vector，接下来介绍一下vector

vector 不定长数组

如何定义：vector<数据类型>数组/变量名

需要头文件vector

一般vector有这么两种操作

a.push_back(x) ;在a的末尾加入x这个元素

a.size() ;获取a的长度

那么接下来继续解释邻接矩阵

有了vector便简单很多，我们只需要用一个vector数组vector <int> a[1000] ;对于每一个a_i，它每次有一条相邻边就push进一个元素，遍历时用size获取长度，遍历方法与常规数组相同。

图的遍历

对于图的遍历，一般使用DFS(深度优先搜索)或BFS(广度优先搜索)

DFS

这里给出一个图，便于理解DFS遍历模式。

可以看出，DFS是按照节点深度进行遍历，即为"深度优先"，这里遍历模式并不是唯一的，遍历顺序也可能是1245736，或1362457，或1362574。DFS像是"不撞南墙不回头"的一种方法，每个节点向它的相邻节点走，直到没有路可走再回溯，因此，DFS一般用函数方法实现。

这边给出一个DFS经典例题：走迷宫问题

给你一个n*m的迷宫，0表示墙，1表示路，判断是否能从(1,1)走到(m，n)走出迷宫，如果能，输出最短路径，否则输出-1。

我们搜索最短路即可。

代码如下

#include <iostream> 
using namespace std ;
int a[1005][1005] , m , n , ans=-1 ;//记录图的数组，图的长，宽，最短路径 
void dfs(int x , int y , int now)//现在的坐标，走的路径 
{
    if(x == m && y == n)//走到终点就更新答案 
    {
        if(ans == -1) ans = now ;//如果这是第一次走到终点那么目前最短就是这个距离 
        else ans = min(now , ans) ;//不是就更新答案 
        return ;//到了就不必搜了，返回 
    }
    if(a[x + 1][y])//右边是否走过 
    {
        a[x + 1][y] = 0 ;//标记 
        dfs(x + 1, y , now+1) ;//搜索 
        a[x + 1][y] = 1 ;//回溯，即标为没走过，否则只能算出一条到中点的路径 
    }
    if(a[x - 1][y])//同前 
    {
        a[x - 1][y] = 0 ; 
        dfs(x - 1, y , now+1) ;
        a[x - 1][y] = 1 ;
    }
    if(a[x][y + 1]) 
    {
        a[x][y + 1] = 0 ;
        dfs(x , y + 1 , now+1) ;
        a[x][y + 1] = 1 ;
    }
    if(a[x][y - 1]) 
    {
        a[x][y - 1] = 0 ;
        dfs(x , y - 1 , now+1) ;
        a[x][y - 1] = 1 ;
    }
    return ;
}
int main() 
{
    cin >> m >> n ;//输入 
    char x;//便于逐个字符读入 
    for(int i = 1 ; i <= m ; i++)
    {
        for(int j = 1; j <= n ; j++)
        {
            cin >> x ;//输入
            if(x == '0') a[i][j] = 0 ;
            else a[i][j] = 1 ;
        }
    }
    a[1][1] = 0 ;//第一个点已经走过了 
    dfs(1 , 1 , 0) ;//从1，1开始搜 
    cout << ans ;//输出
    return 0 ;
}
//样例
//输入
//5 5
//1 1 1 1 1
//1 0 0 1 0
//1 0 0 1 1
//1 1 1 0 1
//1 1 1 1 1
//输出
//8

那么这个可以用记忆化搜索来优化一下，即添加一个记录步数的数组，如果到达某一个点，目前步数比之前还多，那么剪枝，代码不再给出，自行实现。

那么BFS是这样遍历的

即"广度优先"，每次都遍历与根节点距离相同的节点，代码实现的话我们用一个队列queue，queue和生活中的排队是一样的，有先进先出的原则。

queue用法

需要头文件queue

定义queue<类型>数组/变量名

入队q.push(x) ;推入元素

出队q.pop() ;推出元素

判断队列是否为空q.empty() ;

获取队首元素q.front() ;

那么因为BFS用队列做，所以我们需要用一个pair类型(类似于struct，可以当作特殊的struct)来储存坐标

定义pair<类型,类型> ;

调用第一个元素a.first

第二个a.second

将一个pair推入STLq.push(make_pair(元素,元素)) ;

BFS可以不回溯，因为它是广度优先，每次都遍历与根节点距离相同的点，那么第一个走到终点的必定是最短路径。

题目与刚刚的相同，那么我们BFS的代码如下

#include <iostream>
#include <queue>
using namespace std ;
int a[1002][1002] , b[1002][1002] ;//一个记录图，一个记录路长度 
queue<pair<int,int> > q;//定义pair类型的STL时两个大于号或小于号一定要分开 
int main() 
{
    int m , n , flag = 1 ;//长、宽、是否能到底 
    cin >> m >> n ;//输入 
    char x;//便于逐个字符读入 
    for(int i = 1 ; i <= m ; i++)
    {
        for(int j = 1; j <= n ; j++)
        {
            cin >> x ;//输入
            if(x == '0') a[i][j] = 0 ;
            else a[i][j] = 1 ;
        }
    }
    q.push(make_pair(1 , 1)) ;//从1开始走
    a[1][1] = 0;
    while(!q.empty())
    {
        int x = q.front().first ;//记录坐标 
        int y = q.front().second ;
        if(x == m && y == n)//如果到达 
        {
            cout << b[x][y] ;//输出路径长度 
            flag = 0 ;//标记为能到达 
            return 0 ;//不用再搜了 
        }
        if(a[x + 1][y])//如果是路 
        {
            q.push(make_pair(x + 1 , y)) ;//那么继续走 
            a[x + 1][y] = 0 ;//标记 
            b[x + 1][y] = b[x][y] + 1 ;//步数增加 
        }
        if(a[x - 1][y])//同前 
        {
            q.push(make_pair(x - 1 , y)) ;
            a[x - 1][y] = 0 ;
            b[x - 1][y] = b[x][y] + 1 ;
        }
        if(a[x][y + 1])
        {
            q.push(make_pair(x, y + 1)) ;
            a[x][y + 1] = 0 ;
            b[x][y + 1] = b[x][y] + 1 ;
        }
        if(a[x][y - 1])
        {
            q.push(make_pair(x, y - 1)) ;
            a[x][y - 1] = 0 ;
            b[x][y - 1] = b[x][y] + 1 ;
        }
        q.pop();//当前出队 
    } 
    if(flag) cout<< -1 ;//走不到就输出-1 
    return 0 ;
}

BFS复杂度看起来低一些，代码也短一些，还不容易出错，所以能用BFS尽量用。

B)T4讲解

那么这道题说，每两个工人只有一条传送带，两个工人间至少有一条传送带，一个零件的生产需要旁边两个工人提供零件，现在a号工人要生产一个阶段为l的零件，求是否1号工人需要生产原材料。

那么我们把样例的图拿过来。

那么我们假设只需要一边的工人提供零件

假设4号工人要生产一个阶段3的零件

那么5号工人要生产阶段2的零件，1号工人要生产阶段1的零件，2号工人提供原材料

假设4号工人要生产一个阶段2的零件

那么5号工人需要生产阶段1的零件，1号工人要生产阶段原材料。

两边的工人都需要生产也是如此。

不难发现，如果4号工人生产阶段3的零件，1号工人不需要提供原材料，那么4号工人生产任意奇数阶段零件，1号工人都不需要提供原材料。

如果4号工人生产阶段2的零件，1号工人需要生产原材料，那么4号工人生产阶段2+2n(n为大于等于0的整数)阶段的零件时1号工人都需要生产原材料。

所以这题演变成了求每个节点到1号点的奇、偶最短路径问题了。

路径可逆，因此我们从1号点开始搜即可。

我们只需要一个二维数组，一层记录奇数最短路径，一层记录偶数最短路径。

需要注意的是，如果现在是一个奇数步数，那么下一个是奇数+1，即偶数步数，反之亦然。洛谷上的民间数据加入了一个单独的节点，要加特判，当然如果你的BFS本身就是不用加的可以不加，但是保险为好。

代码如下

#include <iostream>
#include <cstring>
#include <queue>
using namespace std ;
queue<pair<int,int> >bf;//BFS用队列
vector <int> way[1000010] ;//存图
int count_to , sum_walk ;//记录BFS走到的节点和当前步数
int way_shortest[1000010][2] ;//记录最短路径，第一层是偶数，第二层是奇数
void bfs()
{ 
    memset(way_shortest , 0x3f , sizeof(way_shortest));//初始化
    bf.push(make_pair(1,0)) ;//1节点到它本身的距离是1
    way_shortest[1][0] = 0 ;//记录一下
    while(bf.size())
    {
        count_to = bf.front().first ;
        sum_walk = bf.front().second ;//临时记录
        for(int i=0 ; i < way[count_to].size() ; i++)//遍历相临边
        {
            if(way_shortest[way[count_to][i]][!(sum_walk % 2)] >= sum_walk)//因为奇偶接替，因此相临边要01反转一下。判断相临边是否已经有比目前更短的路径
            {
                way_shortest[way[count_to][i]][!(sum_walk % 2)] = sum_walk + 1 ;//没有就更新
                bf.push(make_pair(way[count_to][i],sum_walk + 1));//推入队列
            }
        }
        bf.pop() ;//出队
    }
}
int main()
{
    int n , m , q , a , l;//工人，传送带，工单，工人编号，零件阶段 
    int c_l,c_r;//两个连接着的工人 ;
    cin >> n >> m >> q ;//输入
    for(int i = 1 ; i <= m ; i++)//输入
    {
        cin >> c_l >> c_r ;
        way[c_l].push_back(c_r) ;
        way[c_r].push_back(c_l) ; 
    }
    bfs();
    for(int i = 0 ; i < q ; i++)
    {
        cin >> a >> l ;//工人与零件阶段
        if(l % 2)//如果是偶数阶段就在偶数最短路径中判断
        {
            if(way_shortest[a][1] <= l) cout << "Yes" << endl ; //如果阶段大于最短路径就需要生产
            else cout << "No" << endl ;//否则不需要
        } 
        else
        {
            if(way_shortest[a][0]  <= l)cout << "Yes" << endl ; //同理
            else cout << "No" << endl ;
        }
    }
    return 0 ;
}

这道题是一个比较简单的图论题，转化一下就好了。

以上内容便是关于2019 CSP-J 四道题的讲解，如有不足之处，还请赐教。