CCF-CSP模拟考笔记

竞赛 / CCF-CSP认证 / 第二题
Word count: 6.9k   |   Reading time≈ 33 min

CCF-CSP模拟考笔记

官网模拟题：首页 - 计算机软件能力认证考试系统

第二题

一般会涉及到动态规划以及对应的空间压缩，前缀和进行时间优化，找规律得到共性进行时间优化，存储特殊坐标进行空间优化而不是直接存储整个矩阵……

202212-2、训练计划

问题描述

100分参考代码：(99条消息) CCF CSP202212-2训练计划【100分】详细注释_Brienzz的博客-CSDN博客

输入：

1
2
3
4
5
6
7
8
9
10
11
10 5
0 1 0 2 0
1 2 3 2 10
----------
10 5
0 1 2 3 4
1 2 3 2 1
----------
10 7
0 1 0 3 2 3 0
2 1 2 3 1 4 3

输出：

1
2
3
4
5
6
7
8
1 2 1 4 1
6 7 8 9 1
----------
1 2 4 7 9
2 3 5 8 10
----------
1 3 1 3  4   3  1
7 9 5 8  10  7  8

关键：

  1. 正向遍历易求最早开始时间。

  2. 反向遍历要注意找到具有依赖关系的后项post存储值的数学表达式。（post[dependency[i]]=-T[i]+post[i]）

  3. 是否输出最晚开始时间要看求出的最晚开始时间last数组中是否有小于1的值。若有，则不输出；没有，则输出。

提醒：直接暴力求解最早开始时间就能够得到70分。

解决代码：

1
2
//写出的代码有问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//网上100分参考代码：
#include<iostream> 
#include<cmath>
#include<map>
#include<climits>
using namespace std;
const int maxn = 365+5;
const int maxm = 100+5;
int p[maxm];
int t[maxm];
int early[maxm];
int last[maxm];
typedef multimap<int,int>::iterator Iterator;
int main(){
    multimap<int,int> rel;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        cin>>p[i];
        /*
        (p[i],i)表示项目i的依赖项目为p[i],称i是依赖对象,p[i]是被依赖对象
        依赖关系可以用multiset表示 
        */
        rel.insert(make_pair(p[i],i)); 
    }
    for(int i=1;i<=m;i++){
        cin>>t[i];
    }
    bool flag = true;//默认最早开始时间满足n天训练 
    for(int i=1;i<=m;i++){
        if(p[i]==0){
            early[i] = 1;
        }else{
            early[i] = early[p[i]]+t[p[i]]; 
        }
        if(early[i]+t[i]-1>n) flag = false;//最早开始时间不满足n天训练 
    }
    for(int i=1;i<=m;i++){
        cout<<early[i]<<" ";
    }
    cout<<endl;
    if(flag==true){
        /*
        由于满足依赖科目编号p[i]小于当前项目i的编号，因此可以从编号大的开始往前计算最晚开始时间 
        */
        for(int i=m;i>=1;i--){
            //找项目i的被依赖对象，如果项目i没有被依赖对象，则依赖关系(i,p[i])不存在 
            pair<Iterator,Iterator> it = rel.equal_range(i);
            if(it.first==it.second){//依赖关系不存在 
                last[i] = n - t[i] +1; 
            }else{//依赖关系存在 
                Iterator it1;
                int value = INT_MAX;
                for(it1 = it.first;it1 != it.second; ++it1) {
//                    cout<<it1->first<<" ==== "<<it1->second<<"---";
                    value = min(value,last[it1->second]);
//                    cout<<value<<endl;
                }
                last[i] = value - t[i];
            }
//            cout<<last[i]<<" ";
        }    
        for(int i=1;i<=m;i++){
            cout<<last[i]<<" ";
        }
    }
    return 0;
}

202209-2、何以包邮？

问题描述

思路：

  1. 动态规划（0-1背包问题）
  2. 第一种方法：
    • img
  3. 第二种方法：
    • img

参考：(99条消息) 202209-2 CCF 何以包邮？ （01背包解法（两种解法） + 详细思路）_一只可爱的小猴子的博客-CSDN博客

PS：在某些情况下，使用vector定义数组可能会导致空间使用增加。

image-20230307092308900

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
*	0-1动态规划求出在需要删去的书中的最大的价格总和，再将所有书的价格总和减去前面的总和得到的就是最小但是能够包邮的花费。
*/
#include<bits/stdc++.h>
using namespace std;

const int N=35,M=3e5+10;
//vector<int>a(N);
//vector<vector<int>>f(N+1,vector<int>(M+1,0));
int f[N][M];
int a[N]; 

//第一种解法 ——从 [0，sum-x]区间中选出使得花费最大的，再减去最大的就是最小的 
int main() {
	int n,x,sum=0;
	cin>>n>>x;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		sum+=a[i];
	}
	int res=0;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=sum-x;++j){//在[0，sum-x]中求出最大值，那么最后的花费就会最小且满足包邮条件 
			f[i][j]=f[i-1][j];//没选第i本书
			if(j>=a[i]) f[i][j]=max(f[i][j],f[i-1][j-a[i]]+a[i]);	//j>=a[i]时才能继续往背包里加东西 
			res=max(res,f[i][j]);
		}
	}
	printf("%d",sum-res);
	return 0;
}

//第二种解法 ——从总的中删去不要的 
int main() {
	int n,x,sum=0;
	cin>>n>>x;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		sum+=a[i];
	}
	for(int i=1;i<=n;++i)f[i][sum]=sum;//在容量为sum的情况下最大总价值为sum 
	for(int j=x;j<=sum;++j)f[0][j]=sum;//在容量在[x,sum]的情况下，未删去书籍时的初始情况为sum
	
	int res=INT_MAX;
	for(int i=1;i<=n;++i){
		for(int j=sum;j>=x;--j){//每一次循环j都会减少，j代表的是最终要支付的金额
			f[i][j]=f[i-1][j];//没删去第i本书 
			if(j+a[i]<=sum)f[i][j]=min(f[i][j],f[i-1][j+a[i]]-a[i]);//删去第i本书 
			if(f[i][j]>=x)res=min(res,f[i][j]);
		}
	} 
	cout<<res;
	return 0;
}

202206-2、寻宝！大冒险！

问题描述

注意：本题有30%的数据会有很大的绿化图，这样的绿化图不能够直接使用二维数组存储，需要对空间进行优化。采用vector<pair<int,int>>A;对绿化图进行空间优化。

参考：(99条消息) 202206-2 CCF 寻宝！大冒险！ （简单模拟 满分题解）_ccf20220602_一只可爱的小猴子的博客-CSDN博客

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//70分代码：——主要是因为绿化图的大小很大的情况下，用二维数组存储是不行的，因此需要进行空间优化
#include<bits/stdc++.h>
using namespace std;

const int L=2010,S=60;
int A[L+1][L+1];
int B[S+1][S+1];

int main() {
	int n,L,S,count=0;
	cin>>n>>L>>S;
//	vector<vector<int>>A(L+1,vector<int>(L+1,0));
//	vector<vector<int>>B(S+1,vector<int>(S+1,0));
	int x1,y1;
	for(int i=0;i<n;++i){
		cin>>x1>>y1;
		A[x1][y1]=1;
	}
	for(int i=S;i>=0;--i){
		for(int j=0;j<=S;++j){
			cin>>B[i][j];
		} 
	} 
	//在矩阵A的L-S范围内查找树的位置作为藏宝图的B[0][0]，再看A与B之间是否能够匹配（也就是A是否完全包含了B） 
	for(int i=0;i<=L;++i){
		for(int j=0;j<=L;++j){
			bool flag=true;
			if(A[i][j]==1&&i+S<=L&&j+S<=L){
				int x=0,y=0;
				for(int x=0;x<=S;++x){
					for(int y=0;y<=S;++y){
						if(A[i+x][j+y]==B[x][y])continue;
						else{
							flag=false;
							break;
						}
					}
					if(!flag)break; 
				}
				if(flag)++count;
			}		
		}
	}
	cout<<count;
	return 0;
}
//-----------------------------------------------
//100分代码：
#include<bits/stdc++.h>
using namespace std;

const int s=60;
int n,L,S;
//int A[L+1][L+1];//绿化图 
vector<pair<int,int>>A;//绿化图 
int B[s+1][s+1];

bool check(int x,int y){
	for(int i=0;i<=S;++i){
		for(int j=0;j<=S;++j){
			if(x+i<0||x+i>L||y+j<0||y+j>L)return false;//藏宝图有部分超过了绿化图，因此不匹配 
			bool flag=false;
			for(auto &p:A){//当前藏宝图B[i][j]的位置与绿化图中树的位置集合A中有一个相等即可 
				if(x+i==p.first&&y+j==p.second){
					flag=true;
					break;
				}
			}
			//判断藏宝图 B[i][j]是否为一个树并结合前面判断好的关于当前藏宝图的位置是否在集合A中 
			if((B[i][j]&&!flag)||(!B[i][j]&&flag))return false;//不用考虑 B[i][j]=0以及 flag=false的情况：因为如果 B[i][j]=0则表明其不是一棵树，那么自然不可能存在于集合A中 
		}
	}
	return true;
}

int main() {
	int count=0;
	cin>>n>>L>>S;
//	vector<vector<int>>A(L+1,vector<int>(L+1,0));
//	vector<vector<int>>B(S+1,vector<int>(S+1,0));
	int x1,y1;
	for(int i=0;i<n;++i){
		cin>>x1>>y1;
		A.push_back({x1,y1});
	}
	for(int i=S;i>=0;--i){
		for(int j=0;j<=S;++j){
			cin>>B[i][j];
		} 
	} 
	//对绿化图中每一棵树作为藏宝图B[0][0]点，并由此为起点进行一次判断看否能够满足藏宝图的要求 
	for(int i=0;i<n;++i){
		if(check(A[i].first,A[i].second)){
			++count;
		}
	} 
	cout<<count;
	return 0;
}

202203-2、 出行计划

问题描述

q时刻做核酸之后经过k时刻得到核酸证明，此时q+k时刻能够进入场所的条件是：（q+k）+ci>ti，并且q+k<=ti；

也就是有（q+k）+ci>=ti+1，并且q+k<=ti⟶\longrightarrowq应该在区间[ti+1-k-ci,ti-k]中

参考：(99条消息) CSP CCF： 202203-2 出行计划 （C++）_猫娜Lisa的博客-CSDN博客

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//70分代码：——运行超时
#include<bits/stdc++.h>
using namespace std;
//前缀和？ 

int main() {
	int n,m,k,t,c;
	cin>>n>>m>>k;
	pair<int,int>p[n];
	vector<int>q(m);
	for(int i=0;i<n;++i){
		cin>>t>>c;
		p[i]=make_pair<>(t,c);
	}
	for(int i=0;i<m;++i){
		cin>>q[i];
	} 
	for(int i=0;i<m;++i){
		int num=0;
		for(int j=0;j<n;++j){
			if(q[i]+k+p[j].second>p[j].first&&p[j].first>=q[i]+k){
				++num;
			}
		}
		printf("%d\n",num);
	}
	return 0;
}
//-----------------------------------------------
//修改后的100分代码：
#include<bits/stdc++.h>
using namespace std;
//前缀和？ 
//由（q+k）+ci>=ti+1，并且q+k<=ti得到q的区间[ti+1-k-ci,ti-k]
int main() {
	int n,m,k,t,c,q;
	cin>>n>>m>>k;
	vector<int>Q(200002,0);//Q取200002容量的原因是 --Q[r+1]中r就是qi其最大取值可以是200000，所以r+1=200001，所以最多有200002个元素 
//	int Q[200002]={0};
	for(int i=0;i<n;++i){
		cin>>t>>c;
		int l=max(0,t+1-k-c);//左边界 
		int r=max(0,t-k);//右边界 
		++Q[l];//当左边界小于0时l=0，此时有 ++Q[0]（并且qi>0），表示所有的qi取值都可以进入当前第i个场所，便于后面的求前缀和操作 
		--Q[r+1];//r+1表示的是大于右边界的qi不能够进入当前第i个场所 
	}
	//求前缀和
	for(int i=1;i<=200001;++i){
		Q[i]+=Q[i-1];
	} 
	for(int i=0;i<m;++i){
//		int q; 
		cin>>q;
		cout<<Q[q]<<endl;
	} 
	return 0;
}

//-----------------------------------------------
//网上100分参考代码：
#include <iostream>
 
using namespace std;
 
int main()
{
    int n, m, k;
    cin>>n>>m>>k;
 
    int Q[200002] = {0};
 
    for (int i = 0; i < n; ++i) {
        int t, c;
        cin>>t>>c;
        int l = max(0, t - k - c + 1);//t-k-c+1代表的是qi的左边界，如果左边界为负数，则可以判定当前第i个场所可以进入，因此有下面的++Q[l]操作。当左边界是1，则有++Q[1]
        int r = max(0, t - k);//t-k代表的是qi的右边界，如果右边界为负数，则可以判定当前第i个场所不可能进入，因此有下面的--Q[r + 1]操作。当右边界为1，则有--Q[2]表示的是qi取2时是不能够进入当前第i和场所的。
        ++Q[l];
        --Q[r + 1];
    }
 
    for (int i = 1; i < 200002; ++i) {//计算数组Q的前缀和
        Q[i] += Q[i-1];
    }
 
    for (int i = 0; i < m; ++i) {
        int q;
        cin>>q;
        cout<<Q[q]<<endl;
    }
    return 0;
}

202112-2、序列查询新解

问题描述

lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素。

通过/实现向下取整。

思路参考：(100条消息) CCF - 202112-2 - 序列查询新解_Coco091的博客-CSDN博客

代码参考：(100条消息) 【CCF-CSP】202112-2-序列查询新解100分（读过必懂）_ccf序列查询新解_怪&的博客-CSDN博客

关键：

  1. 因为A[n]<N，所以为了后面方便计算，我们设A[n+1]=N

  2. 根据数组A将f(i)划分为多个区间，保证每个区间内的f的值都相同

  3. 由数组A划分的多个区间[A[i-1],A[i]-1，这个区间也是f的区间,f在每一个区间之内的值都是i-1

  4. 根据示例数据g(i)可以发现g是以r个相同元素递增的等差数列，每r个相同元素的g的右边界就是（g(i)+1）*r-1,并且g的左边界就是j

  5. 最后通过delta+=abs(i-1-g(j,r))*length;简化累和计算，提高时间效率

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//70分代码：——运行超时
#include<bits/stdc++.h>
using namespace std;


int main() {
	int n,N,r;
	cin>>n>>N;
	r=(int)(N/(n+1));
//	cout<<r<<endl;
	int delta=0;
	vector<int>A(n+1,0);
	for(int i=1;i<=n;++i){
		cin>>A[i];
	}
	int g,f;
	for(int i=0;i<N;++i){
		f=lower_bound(A.begin(),A.end(),i)-A.begin();//lower_bound返回一个迭代器
		if(A[f]!=i)f=f-1;	//注意如果A[f]的值等于N的值则返回的f不减1
		g=(int)(i/r);
		delta+=abs(g-f);
//		cout<<"f"<<f<<endl;
//		cout<<"g"<<g<<endl;
	} 
	cout<<delta;
	return 0;
}
//-----------------------------------------------
//优化后100分代码：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;


ll g(ll i,ll r){
	return i/r;
}

int main() {
	ll n,N,r;
	cin>>n>>N;
	r=(N/(n+1));
//	cout<<r<<endl;
	ll delta=0;
	vector<ll>A(n+2,0);	//因为A[n]<N，所以为了后面方便计算，我们设A[n+1]=N
	for(ll i=1;i<=n;++i){
		cin>>A[i];
	}
	A[n+1]=N;
	for(ll i=1;i<=n+1;++i){//根据数组A将f(i)划分为多个区间，保证每个区间内的f的值都相同 
		ll length=0;
		for(ll j=A[i-1];j<=A[i]-1;j+=length){//由数组A划分的多个区间[A[i-1],A[i]-1]，这个区间也是f的区间,f在每一个区间之内的值都是i-1 
			int index_End=(g(j,r)+1)*r-1;//根据示例数据g(i)可以发现g是以r个相同元素递增的等差数列，每r个相同元素的g的右边界就是（g(i)+1）*r-1,并且g的左边界就是j 
//			cout<<index_End<<endl;
			if(index_End>A[i]-1)index_End=A[i]-1;//确保右边界不会超过N，最大只能取N-1 
			length=index_End-j+1;//更新区间长度 
			delta+=abs(i-1-g(j,r))*length;
		}
	}
	cout<<delta;
	return 0;
}

202109-2、非零段划分

问题描述

大佬参考：(100条消息) CCF202109-2 非零段划分（100分）【序列处理】_海岛Blog的博客-CSDN博客

解法三：差分法（Difference method）

  • 借用岛屿情况来分析这个题。考虑p足够大的情况，所有的数都被海水淹没了，只有0个岛屿。然后，海平面逐渐下降，岛屿数量出现变化。每当一个凸峰出现，岛屿数就会多一个；每当一个凹谷出现，原本相邻的两个岛屿就被这个凹谷连在一起了，岛屿数减少一个。使用数组sum[]，sum[i] 表示海平面下降到i时，岛屿数量的变化。

  • 差分法是最简洁的解题程序。数组元素D[i]中存储该元素被替换为0时，划分数变化的差分值。最大值则只需要从其前缀和（程序中实际为后缀和）中找出最大值就是所要的结果。

  • 程序代码中，STL算法函数unique()用来去除相邻重复的元素。相邻的重复元素对于结果并不会有任何影响。

  • 语句A[0] = A[n + 1] = 0;用来设置边界值，起辅助计算作用，可以简化程序代码。

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//100分代码：
#include<bits/stdc++.h>
using namespace std;

const int M=10000;

int main() {
	int n;
	cin>>n;
	vector<int>A(n+2,0);//注意对于vector来说指向第一个元素的迭代器是A.begin(),而对于int A[n+2]来说，指向第一个元素的迭代器是A(这很重要！！！) 
	vector<int>D(M+1,0);//A[i]<=M=10000，D数组存储数量差分数量 
	for(int i=1;i<=n;++i){
		cin>>A[i];
	}
	A[0]=A[n+1]=0;//辅助计算
	//去除相邻的重复元素
	n=unique(A.begin(),A.begin()+n+2)-A.begin()-2+1;//剩下无相邻重复的总元素个数
	int ans=0,sum=0;
	for(int i=1;i<=n;++i){
		if(A[i-1]<A[i]&&A[i]>A[i+1])++D[A[i]];//A[i]为山峰则+1
		else if(A[i-1]>A[i]&&A[i]<A[i+1])--D[A[i]];//A[i]为山谷则-1
	} 
	//求后缀和
	for(int i=M;i>=1;--i){//1<=p<=10000
		sum+=D[i],ans=max(ans,sum);
	} 
	cout<<ans;
	return 0;
}

//-----------------------------------------------
//网上100分参考代码：
/* CCF202109-2 非零段划分 */

#include <bits/stdc++.h>

using namespace std;

const int N = 500000;
const int M = 10000;
int a[N + 2], d[M + 1];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    a[0] = a[n + 1] = 0;//设置边界，不影响1……n个元素的存储，起辅助计算的作用

    n = unique(a, a + n + 2) - a - 1;//去除相邻且重复的元素的个数——unique左闭右开，并且返回的是去重之后容器中不重复序列的最后一个元素的下一个元素。因此需要将此迭代器减去迭代器a并再减1，得到的是不存在重复的元素个数。（包含了a[0] 与 a[n + 1]）

    memset(d, 0, sizeof d);//相当于对d初始化为全0
    for (int i = 1; i < n; i++)
        if (a[i - 1] < a[i] && a[i] > a[i + 1]) d[a[i]]++;
        else if (a[i - 1] > a[i] && a[i] <a[i + 1]) d[a[i]]--;

    int ans = 0, sum = 0;   // 差分前缀和即为答案
    for (int i = M; i >= 1; i--)	//从最大的p开始递减遍历
        sum += d[i], ans = max(ans, sum);

    printf("%d\n", ans);

    return 0;
}

202104-2、邻域均值

问题描述

思路：

  1. 由Aij构成的领域将会是一个小矩阵，该小矩阵可以通过减去3个矩阵得到。
  2. 将整个矩阵的值求和之后存储在矩阵的最右下位置（这里采用预计算处理）
  3. 二维前缀和
  4. 为了避免/可能带来的错误，我们将除改为乘，即阈值t乘以Aij领域的像素个数再与Aij领域的和进行比较：t*num>=sum

注意：

  1. 如果不用前缀和会有许多重复计算，运行时间肯定无法满足

  2. 使用前缀和可以很容易地避免多余的重复计算，可以使用行前缀和或是二维前缀和

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//100分代码：
#include<bits/stdc++.h>
using namespace std;
//二维前缀和 
int main() {
	int n,L,r,t;
	cin>>n>>L>>r>>t;
	int A[n+1][n+1],psum[n+1][n+1];
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			cin>>A[i][j];
			psum[i][j]=psum[i-1][j]+psum[i][j-1]-psum[i-1][j-1]+A[i][j];//二维前缀和 
		} 
	} 
	int counts=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
//			int left=j-r>0?j-r:1;
//			int down=i+r<n+1?i+r:n;
//			int right=j+r<n+1?j+r:n;
//			int up=i-r>0?i-r:1;
			//Aij领域内矩阵的四个角的坐标 
			int left=max(j-r,1);
			int down=min(i+r,n);
			int right=min(j+r,n);
			int up=max(i-r,1);
			int sum=psum[down][right]-psum[up-1][right]-psum[down][left-1]+psum[up-1][left-1];//这里要注意下标要减1的情况 
			int num=(down-up+1)*(right-left+1);
			if(t*num>=sum)++counts;
		} 
	}
	cout<<counts;
	return 0;
}

202012-2、 期末预测之最佳阈值

问题描述

参考：(99条消息) CCF-CSP 202012-2 期末预测之最佳阈值（前缀和、set去重、代码极简）_AngleCavalier的博客-CSDN博客

关键：

  1. 考前缀和的应用

  2. 两层for循环暴力求解只能通过70%的数据

img

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//70分代码：——运行超时
#include<bits/stdc++.h>
using namespace std;

int main() {
	int m;
	cin>>m;
	vector<int>fit_selta(m,0);
	unordered_map<int,pair<int,int>>hash(m);
	int y,result;
	for(int i=0;i<m;++i){
		cin>>y>>result;
		hash[i]=make_pair<>(y,result);
	}
//	for(int i=0;i<m;++i){
//		cout<<hash[i].first<<" ";
//	} 
	int selta,predict,max_num=INT_MIN,max_index;
	for(int i=0;i<m;++i){
		selta=hash[i].first;
		for(int j=0;j<m;++j){
			if(hash[j].first>=selta)predict=1;
			else predict=0;
			if(predict==hash[j].second)++fit_selta[i];
		}//确保输出的预测次数最多且selta值最大的值 
		if(max_num<fit_selta[i]||(max_num==fit_selta[i]&&hash[max_index].first<selta)){
			max_num=fit_selta[i];
			max_index=i;
		}
	}
	cout<<hash[max_index].first;
	return 0;
}
//-----------------------------------------------
//100分代码:——关键是利用前缀和进行预处理，减少运行时间,提高效率
#include<bits/stdc++.h>
using namespace std;

int main() {
	int m;
	cin>>m;
	pair<int,int>hash[m+1];
	int sum[m+1]={0};//注要赋sum[0]的初值 ——也可以写成：int sum[m+1]={0} 
	set<int>st;
	int y,result;
	for(int i=1;i<=m;++i){
		cin>>y>>result;
		hash[i]=make_pair<>(y,result);
	}
	//按照阈值进行升序排序
	sort(hash+1,hash+1+m);
	//求前缀和
	for(int i=1;i<=m;++i){
		sum[i]=sum[i-1]+hash[i].second;
	} 
	int max_sum=INT_MIN,ans=0;
	for(int i=1;i<=m;++i){
		int selta=hash[i].first;//选定阈值 
		if(st.count(selta))continue;//跳过选定的阈值(set去重，相同阈值得到的正确预测次数相等)
		st.insert(selta);//存储已经被选定过的阈值,方便去重操作 
		int p1=sum[m]-sum[i-1];//大于等于阈值selta并且预测结果中为1的个数
		int p0=i-1-sum[i-1];//求小于阈值selta并且预测结果中为0的个数
		int all=p1+p0;//总正确预测次数 
		if(all>=max_sum){//确保是大于等于，如果阈值更大且正确预测次数相同的情况下也需要执行函数体 
			max_sum=all;
			ans=selta;
		}
	} 
	cout<<ans;
	return 0;
}

//-----------------------------------------------
//GitHub上100分参考代码：
#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    map<gg, array<gg, 2>> r;
    gg mi, y, res;
    cin >> mi;
    for (gg i = 0; i < mi; ++i) {
        cin >> y >> res;
        r[y][res]++;
    }
    gg p0 = 0, p1 = 0, ans = 0, c = 0;
    for (auto& i : r) {
        gg t = p0 + mi - p1;
        if (t >= c) {
            c = t;
            ans = i.first;
        }
        p0 += i.second[0];
        p1 += i.second[1];
    }
    cout << ans << "\n";
    return 0;
}

202009-2、风险人群筛查

image-20230310172253047

关键：这道题主要是在输入t个时刻的坐标时就进行判断处理是否为逗留还是经过。

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//100分代码：
#include<bits/stdc++.h>
using namespace std;
//连续k个或k个时刻以上位于高危区才算是“逗留” 

int main() {
	int n,k,t,x_l,y_d,x_r,y_u;
	cin>>n>>k>>t>>x_l>>y_d>>x_r>>y_u;
	int xi,yi,pass_counts=0,stay_counts=0;
//	vector<int>psum(n,0);
	for(int i=0;i<n;++i){
		int max_sum=0,p_sum=0;
		for(int j=0;j<t;++j){
			cin>>xi>>yi;
			if((x_l<=xi&&xi<=x_r)&&(y_d<=yi&&yi<=y_u)){
				++p_sum;
			}else{
				max_sum=max(max_sum,p_sum);//存储连续时刻的最大次数 
				p_sum=0;//非连续则置为0 
			}
		}
		max_sum=max(max_sum,p_sum);//避免出现一个人对应的t个连续时刻都在高危区内而导致的Bug 
//		cout<<"max_sum: "<<max_sum<<endl;
		if(max_sum>=k){
//			cout<<"test"<<endl;
			++stay_counts;
			++pass_counts;
		}else if(max_sum>0){//只要某一个时刻在高危区就算经过 
			++pass_counts;
		}		
	}
	cout<<pass_counts<<endl;
	cout<<stay_counts;
	
	return 0;	
}

202006-2、稀疏向量

问题描述

分析：

  1. 根据题目的输入和输出的提示我们只定义vector_u，之后的向量v则在输入时便结合vector_u判断是否具有相同的index，以此少定义一个vector，提升效率。

注意：

  • unsigned int的范围是0~65536 int的范围是 -32768 ~ +32767

输入输出：

1
2
3
4
5
6
7
8
10 3 4
4 5
7 -3
10 1
1 10
4 20
5 30
7 40

参考代码：[(103条消息) 满分代码] CCF CSP 202006-2 稀疏向量_江南蜡笔小新的博客-CSDN博客

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//60分代码——运行超时：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;//long long就是long long int 

struct points{
	ll first,second;
};

bool comp(points &p,ll i){
	return i>p.first;//第一个大于等于i的位值，如果i>p.first为true，则表明当前元素均满足条件；如果为false，则表明不满足判定规则，那么将会返回 
}

const ll A=5e5+1,B=5e5+1;


points u[A],v[B];

int main() {
	ll n,a,b;
	cin>>n>>a>>b;
//	vector<pair<int,ll>>u(a+1);
//	vector<pair<int,ll>>v(b+1);
	for(ll i=1;i<=a;++i){
		cin>>u[i].first>>u[i].second;
	}
	for(ll j=1;j<=b;++j){
		cin>>v[j].first>>v[j].second;
	}
	ll ans=0,be,end;
	//较大的index作为遍历的初始点，这样可以减少遍历的次数
	if(u[1].first>=v[1].first){
		be=u[1].first;
	}else{
		be=v[1].first;
	}
	//较小的index作为遍历的结束点，这样可以减少遍历的次数
	if(u[a].first>=v[b].first){
		end=v[b].first;
	}else{
		end=u[a].first;
	}
//	cout<<"be:"<<be<<"end:"<<end<<endl;
	for(ll i=be;i<=end;++i){
		ll u_index=lower_bound(u,u+a,i,comp)-u;
//		cout<<"u_index:"<<u[u_index].first<<endl;
		if(u[u_index].first!=i)continue;//i不存在u中 
		ll v_index=lower_bound(v,v+b,i,comp)-v;
//		cout<<"v_index:"<<v[v_index].first<<endl;
		if(v[v_index].first!=i)continue;//i不存在v中 
		if(u[u_index].first==v[v_index].first){
			ans+=u[u_index].second*v[v_index].second;
		}
	}
	cout<<ans<<endl;
//	cout<<u[2].first<<u[2].second;
	return 0;
}

//修改后100分代码：
#include<bits/stdc++.h>
using namespace std;

using ll=long long;//long long就是long long int 

int main() {
	ll n,a,b,ans=0;
	cin>>n>>a>>b;
	vector<pair<int,int>>u;
	int x,y;
	for(int i=0;i<a;++i){
		cin>>x>>y;
		u.push_back(make_pair(x,y));
//		cout<<u[i].first<<endl;
	}
	int x1,y1,i=0;
	for(int j=0;j<b;++j){//少定义一个vector，提高效率 
		cin>>x1>>y1;
		while(i<a){
			if(x1<u[i].first)break;
			else if(x1>u[i].first)++i;
			else{
				ans+=y1*u[i].second;
				++i;
			}
		}
	}
	cout<<ans;
	return 0;
}
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2023-2024 Guijie Wang
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信