2023CSP-CCF前三题 田地丈量、垦田计划、LDAP解题分析_csp田地丈量

---

CCF考试系统传送门

2023.03第29次CCF-CSP计算机认证考试
CCF计算机软件能力认证考试系统

---

前言（吐槽，可跳过）

大二菜鸟第一次参加CSP考试，发挥得很烂（其实是实力太菜了 ），考前也没看往年题目套路，有很多不甘吧，不过拟打算六月再参加一次。如果早知道题目难度是依次递增的，就不写完两题就去啃最后一题了，最后写第三题的时候都在赶，最后一题还没啃下多少分…
话不多说，接下来分享我的思路。

---

一、田地丈量

1.题目内容

2.题意简述

在坐标轴上给定你一个矩形，再给若干个矩形（这些矩形之间无重合部分），算出这些矩形与你的矩形的重合部分面积总和为多少。

3.题解分析

枚举出矩形在不同情况下的不同计算方法，如在边上、被包含的情况等等，时间复杂度为O(n)。这种方法的好处在于几乎不用思考用什么算法，只需要注意边界条件。

不得不感谢出题人手下留情，给出了不会出现矩形多次覆盖同一区域的情况的条件，否则情况将会复杂一点。

思路图解：

补充： 求重叠线段长度从而算出重叠面积的方法更为简便。

4.完整代码

#include<bits/stdc++.h>
using namespace std;
int n, a, b;
long long ans;
int main()
{
	int x1, x2, y1, y2;
	scanf("%d%d%d", &n, &a, &b);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if(x1>=0&&y1>=0&&x2<=a&&y2<=b)
			ans+=(x2-x1)*(y2-y1);
		else if(x1<0&&x2>0&&y1<b&&y2>b)
			ans+=(b-y1)*x2;
		else if(x1<a&&a<x2&&y1<b&&b<y2)
			ans+=(b-y1)*(a-x1);
		else if(x1<0&&0<x2&&y1<0&&0<y2)
			ans+=x2*y2;
		else if(x1<a&&a<x2&&y1<0&&0<y2)
			ans+=(a-x1)*y2;
		else if(x1>=0&&x2<=a&&y1<b&&y2>b)
			ans+=(x2-x1)*(b-y1);
		else if(x1<a&&x2>a&&y1>=0&&y2<=b)
			ans+=(y2-y1)*(a-x1);
		else if(x1>=0&&x2<=a&&y1<0&&y2>0)
			ans+=(x2-x1)*y2;
		else if(y1>=0&&y2<=b&&x1<0&&x2>0)
			ans+=(y2-y1)*x2;
	}
	printf("%lld",ans);
	return 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

评测结果

---

二、垦田计划

1.题目内容

2.题意简述

有几块田，耕完需要的时间都不同，花的资源也不同，但是所有田可以同时耕。用资源能缩短耕田的天数，但是最少不能小于k天。需要思考如何分配资源使总天数最少。

3.题解分析

听一些大佬说是二分题。但是我没有这样做，提供一下我当时的思路。
这题让我想起木桶盛水的故事，“由长短不一的木板造出的木桶能盛多少水取决于最短的那块木板”。不过这题是反过来的，花费的总时间取决于最多天数的田，最多天数的田不变的情况下，就算分配所有资源给后面的田，需要的总时间也不变。于是我们考虑贪心法：每次分配资源给最大天数的田。

接下来，还需要考虑一个问题。如果存在若干个天数相同的田，只减少其中若干片田的时间，总时间仍不变。就是说，要使这种情况下的天数有效减少，必须同时削减所有相同天数的田，而且需要减少相同时间，使它们步伐保持一致，所以我们可以考虑合并方法，把所有具有相同天数的田所需的资源合并在一起，视为一块田。同时，在计算中削减某块田的天数后也要进行合并。

基于此，我想到了使用STL库的map。将键值对设置为<天数，所需资源>，方便将相同的天数合并它们的资源。另外，map具有自动对key进行排序的特点，正好满足我们对天数进行贪心的需求。需要注意map默认对key降序排列,所以要加greater。

map<ll,ll,greater<ll>>land;//按天数降序
1

在map的begin位置的是天数最大的田，要做的是将它与天数第二大的田合并资源，合并后，删除该键值对。循环执行，直到资源不够了或者所有天数都为k时结束。

m-=cost;
it1->second+=it->second;
land.erase(it->first);
1
2
3

还有一种情况，资源不够合并了。这时算算当前资源还能减多少天，算出来直接输出，程序结束。

ans=it->first;
while(m>=it->second)
{
	m-=it->second;
	ans--;
}
printf("%lld",ans);
break;
1
2
3
4
5
6
7
8

需要注意，无论是否存在天数为k的田，都需要加入key为k的键值对，以保证每次都能取出两个键值对进行合并。

land[k]+=0;//最少天数，保证每次能有两个合并
1

时间复杂度分析：需要分两种情况：
1.所有都能减少到k天，外层循环为O(n)，即总共扫过一遍表；map.erase操作复杂度为O(logn)，总共为O(nlogn)。
2.资源不够，设当前位置田在原来排第m位，则已进行mlogm次运算，内层循环不超过1e5-k次，复杂度为O(mlogm+1e5-k)。
由于m<=n，所以两种情况复杂度相差不大。

可以优化： 在每次合并操作之后让迭代器往后移一位（注意跳出循环条件和迭代器赋值需要些许改动），省去了erase，复杂度为O(n)。不过这题数据量不大，O(nlogn)和O(n)都行（map重度依赖 ）。

补充：又回来补了个二分法，就当练手

这题的二分主要坑点在于多数情况下是不能直接搜到答案的（资源不能恰好分完）,而是直接循环到low>high，最后停止处落在答案左侧或右侧，但一定经过答案。另外，从最小天数k到田的最大天数都是我们的搜索范围，low应该初始化为k。

对于如何找到答案，我们每次得到预测天数mid时，计算大于mid天的田全部减到mid天需要多少资源，此时有三种情况，我们用不同的返回值：

0——刚好用完，直接得出答案；
-1——资源不够；
1——资源盈余。

用这样的函数实现：

int dcs(int day)
{
	int sum=0;
	for(int i=n-1;land[i].first>day&&i>=0;i--)
		sum+=land[i].second*(land[i].first-day);
	if(m==sum)	return 0;//资源刚好
	else if(m<sum)	return -1;//不够资源
	else return 1;//资源盈余
}
1
2
3
4
5
6
7
8
9

在二分查找中调用这个函数，同时对返回值进行处理。最终答案如果不能恰好分配，那答案一定是在资源有盈余的情况下得出来的，所以我们用最小天数mind维护返回值为1的情况，查找结束后mind即为答案。

while(low<=high)
	{
		mid=(low+high)>>1;
		if(dcs(mid)==0)	{mind=mid;break;}
		else if(dcs(mid)==1)	{mind=min(mind,mid);high=mid-1;}
		else	low=mid+1;
	}
	return mind;
1
2
3
4
5
6
7
8

4.完整代码

贪心：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,k;
ll ans=-1;
map<ll,ll,greater<ll>>land;//按天数降序
int main()
{
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=0;i<n;i++)
	{
		ll t,c;
		scanf("%lld%lld",&t,&c);
		land[t]+=c;
	}
	land[k]+=0;//最少天数，保证每次能有两个合并
	map<ll,ll,greater<ll>>::iterator it=land.begin();
	while(m>=it->second&&it->first>k)//资源还够减少天数，且不是全部都为最小天数
	{
		map<ll,ll,greater<ll>>::iterator it1=it;
		it1++;
		ll cost=((it->first-it1->first)*it->second);
		if(m-cost<0)//不够减
		{
			ans=it->first;
			while(m>=it->second)
			{
				m-=it->second;
				ans--;
			}
			printf("%lld",ans);
			break;
		}
		else//足够合并
		{
			m-=cost;
			it1->second+=it->second;
			land.erase(it->first);
		}
		it=land.begin();
	}
	if(ans==-1)//其实这已经说明能全部减到最小天数了
		printf("%lld",it->first);
	return 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

评测结果（贪心）

二分：

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+10;
typedef pair<int,int>pit;
int n,m,k;
pit land[MAX_N];
bool cmp(pit p1,pit p2){return p1.first<p2.first;}
int dcs(int day)
{
	int sum=0;
	for(int i=n-1;land[i].first>day&&i>=0;i--)
		sum+=land[i].second*(land[i].first-day);
	if(m==sum)	return 0;//资源刚好
	else if(m<sum)	return -1;//不够资源
	else return 1;//资源盈余
}
int binsrch()
{
	int mind=1e6;
	int low=k,high=land[n-1].first,mid;
	while(low<=high)
	{
		mid=(low+high)>>1;
		if(dcs(mid)==0)	{mind=mid;break;}
		else if(dcs(mid)==1)	{mind=min(mind,mid);high=mid-1;}
		else	low=mid+1;
	}
	return mind;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<n;i++)
	{
		int t,c;
		scanf("%d%d",&land[i].first,&land[i].second);
	}
	sort(land,land+n,cmp);
	printf("%d",binsrch());
	return 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

评测结果（二分）

---

三、LDAP

1.题目内容

2.题意简述

给定用户的编号和他们各自的属性名称和属性值，再给出满足题目规定的表达式的用户：

a:b——有属性a且值为b的用户集合
a~b——有属性a且值不为b的用户集合
&(a :/~ b)(c :/~ d)——先分别求括号内的用户集合，再求集合交
|(a :/~ b)(c :/~ d)——先分别求括号内的用户集合，再求集合并

3.题解分析

这是一道模拟。数据有原子表达式、简单表达式和嵌套表达式三种。只要求拿70分的话很简单，表达式第一个字符为数字的是原子表达式，第三个字符为数字的是简单表达式。要拿到满分我们需要面对类似“&(&(3:1)(|(1:2)(2:3)))(|(&(2~5)(2~7))(2:5))”这样的字符串。
首先要做的就是解析字符串。因为怕递归可能会超时所以我这里提供一种迭代的方法（菜！ 后面知道递归方法也可以解决）。逆向思维从右往左，维护一个集合栈，遇到数字则说明是原子式，立即计算，算完入栈。同一括号内，遇到“&”“|”符号就取栈顶的两个集合进行交并，运算结果再入栈，可以保证我们的运算顺序是对的（因为这两个符号和它的两个表达式相邻）。此时，表达式中的括号成为了无效字符，可以跳过。

处理字符串，我们从len-1往前搜索，每次开始前先跳过括号，如果遇到了数字，则说明接下来要处理一个原子式了，设立一个左标记把它提取出来送到base_expr函数处理，然后更新游标。如果是操作符，则需要进行集合的交并运算。

		for(int r=len-1;r>=0;r--)
		{	
			while(str[r]==')'||str[r]=='(')r--;
			if(isdigit(str[r]))
			{
				int l=r-1;
				while(l>=0&&(isdigit(str[l])||str[l]==':'||str[l]=='~'))l--;
				base_expr(&str[l+1],&str[r+1]);
				r=l-1;
			}
		
			//集合的交和并
			if(r>=0&&str[r]=='&')
				its();
			else if(r>=0&&str[r]=='|')
				uni();
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

因为设计到集合交并，所以使用求集合交并方便且快的bitset。每次从栈中取两个，算完再入栈。
集合的交和并：

inline void its()//交运算
{
	bs b1=ss.top();
	ss.pop();
	b1=b1&ss.top();
	ss.pop();
	ss.push(b1);
}
inline void uni()//并运算
{
	bs b1=ss.top();
	ss.pop();
	b1=b1|ss.top();
	ss.pop();
	ss.push(b1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

bitset按位表示。第m位为1，则说明集合中有编号m的用户。要使用bitset直接表示max=1e9的DN显然不合理，但是用户数量最多为2500，所以可以使用哈希用数组dnlist下标来映射DN（对应的其他DN编号也换成下标）。

用一个类型为pair二维数组lib表示用户的属性，下标和dnlist一一对应。当求断言时，在lib中找有该属性且为指定值的用户，修改bitset。但是仅仅这样我们无法求反断言式，所以要unordered_map一个属性和用户集合，表示有该属性的用户有哪些，然后我们可以在这些用户里面查找指定pair，断言时查找成功，反断言时查找失败（有该属性但不是指定值），说明满足条件，标记。

void asrt(int aname,int aval,char oper)//断言与反断言
{
	bs b;
	pit p(aname,aval);
	if(oper==':')//断言
	{
		for(si it=ulib[aname].begin();it!=ulib[aname].end();it++)//获取有该属性的用户
		{
			if(binary_search(lib[*it].begin(),lib[*it].end(),p))
				b.set(*it);
		}
	}
	else//反断言
	{
		for(si it=ulib[aname].begin();it!=ulib[aname].end();it++)//获取有该属性的用户
		{
			if(!binary_search(lib[*it].begin(),lib[*it].end(),p))
				b.set(*it);
		}
	}
	ss.push(b);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最后就是提取bitset，按位映射回dnlist，内容存到ans数组，升序排序再输出。

4.完整代码

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=2510;
typedef pair<int,int> pit;
typedef set<int>::iterator si;
typedef set<int> sti;
typedef bitset<MAX_N> bs;
int n,m;
int dnlist[MAX_N];
int ans[MAX_N];
char str[2010];
vector<vector<pit>>lib;
unordered_map<int,sti>ulib;//键值对：<attname,set<DN>>
stack<bs>ss;//存每次运算结果
int mystoi(char *s,char *end)
{
	int base=1,sum=0;
	for(int i=end-s-1;i>=0;i--)
	{
		sum+=base*(s[i]-'0');
		base*=10;
	}
	return sum;
}
inline void its()//交运算
{
	bs b1=ss.top();
	ss.pop();
	b1=b1&ss.top();
	ss.pop();
	ss.push(b1);
}
inline void uni()//并运算
{
	bs b1=ss.top();
	ss.pop();
	b1=b1|ss.top();
	ss.pop();
	ss.push(b1);
}
void asrt(int aname,int aval,char oper)//断言与反断言
{
	bs b;
	pit p(aname,aval);
	if(oper==':')//断言
	{
		for(si it=ulib[aname].begin();it!=ulib[aname].end();it++)//获取有该属性的用户
		{
			if(binary_search(lib[*it].begin(),lib[*it].end(),p))
				b.set(*it);
		}
	}
	else//反断言
	{
		for(si it=ulib[aname].begin();it!=ulib[aname].end();it++)//获取有该属性的用户
		{
			if(!binary_search(lib[*it].begin(),lib[*it].end(),p))
				b.set(*it);
		}
	}
	ss.push(b);
}
void base_expr(char *expr,char *end)//解析原子表达式
{
	int op=0;
	while(expr[op]!=':'&&expr[op]!='~')op++;
	int num1,num2;
	num1=mystoi(expr,&expr[op]);
	num2=mystoi(&expr[op+1],end);
	asrt(num1,num2,expr[op]);
}
int main()
{
	scanf("%d",&n);
	lib.resize(n+1);
	for(int i=1;i<=n;i++)//建表
	{
		int DN,attnum,attname,attv;
		scanf("%d%d",&DN,&attnum);
		dnlist[i]=DN;
		lib[i].resize(attnum);
		for(int j=0;j<attnum;j++)
		{	
			scanf("%d%d",&attname,&attv);
			lib[i][j]=pit(attname,attv);
			ulib[attname].insert(i);
		}
		sort(lib[i].begin(),lib[i].end());
	}
	scanf("%d",&m);
	for(int i=0;i<m;i++)
	{
		scanf("%s",str);
		int len=strlen(str);
		for(int r=len-1;r>=0;r--)
		{	
			while(str[r]==')'||str[r]=='(')r--;
			if(isdigit(str[r]))
			{
				int l=r-1;
				while(l>=0&&(isdigit(str[l])||str[l]==':'||str[l]=='~'))l--;
				base_expr(&str[l+1],&str[r+1]);
				r=l-1;
			}	
			//集合的交和并
			if(r>=0&&str[r]=='&')
				its();
			else if(r>=0&&str[r]=='|')
				uni();
		}
		if(!ss.empty())
		{
			int index=0;
			bs ansbs=ss.top();
			for(int i=1;i<=n;i++)
				if(ansbs[i]==1)
					ans[index++]=dnlist[i];
			sort(ans,ans+index);
			for(int i=0;i<index;i++)
				printf("%d ",ans[i]);
		}
		printf("\n");
		while(!ss.empty())ss.pop();
	}
	return 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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

评测结果（好险啊 ）

---

后面可能还会分析历年的csp题目。实力实在有限，但在分析的过程中也学到了很多。
另外就是，都看到这里了，能不能给个小小的赞鼓励一下——