Burnling's Blog
0%

220317总结

发表于 更新于

暴零人，暴零魂，暴零人是人下人

我记得我T1样例和做的数据都过了来着…怎么交上去就暴零了（甚至样例都过不去（其实是每次输出都差了1

除了T1T2，其他的三道题全都是只过了样例那个点

题解

T1 活动选择

题面

学校在最近几天有 $n$ 个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。 现在给出n个活动使用礼堂的起始时间 $\text{begin}_i$ 和结束时间 $\text{end}_i(\text{begin}_i\lt \text{end}_i)$

请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。

【输入】 第一行一个整数$n(n \leq 1000)$； 接下来的$n$行，每行两个整数，第一个$\text{begin}i$，第二个是$\text{end}_i(\text{begin}_i\lt \text{end}_i\leq32767)$

【输出】 输出最多能安排的活动个数。

【样例输入】 

1
2
3
4
5
6
7
8
9
10
11
12
11 
3 5 
1 4 
12 14 
8 12 
0 6 
8 11 
6 10 
5 7 
3 8 
5 9 
2 13

【样例输出】 

1
4
分析

这个问题实际上是求最多不相交区间个数

按照每个活动的结束时间进行排序（因为前一个活动结束了才能开始下一个活动）

开一个数组 $\text{dp}$ 表示第 $i$ 个活动最多可以是第几个活动

1
2
3
4
5
for(int i = 1;i<n;i++){
	for(int j = i-1;j>=0;j--){
		if(eve[j].ed <= eve[i].st) dp[i] = max(dp[i],dp[j]+1);
	}
}

从前往后扫，第 $i$ 个活动的起始时间如果在第 $j(0\leq j\lt i)$ 个活动的结束时间之后，那么就可以将第 $i$ 个活动排在第 $j$ 个元素的后面，那么$\text{dp}_i=\max(\text{dp}_j+1,dp_i)$

代码
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
#include<bits/stdc++.h>
using namespace std;

bool nDEBUG = true;
const int maxN = 1500;

int n;
struct E{
	int st,ed;
	friend bool operator < (E a,E b){
		if(a.ed != b.ed) return a.ed < b.ed;
		return a.st > b.st;
	}
}eve[maxN];

int dp[maxN];

int main(){
    
//	nDEBUG = false;
	
	if(nDEBUG){
		freopen("act.in","r",stdin);
		freopen("act.out","w",stdout);
	}
	
	scanf("%d",&n);
	for(int i = 0;i<n;i++){
		scanf("%d%d",&eve[i].st,&eve[i].ed);
	}
	
	sort(eve,eve+n);

	int cnt = 0;
	for(int i = 1;i<n;i++){
		for(int j = i-1;j>=0;j--){
			if(eve[j].ed <= eve[i].st) dp[i] = max(dp[i],dp[j]+1);
		}
	}
	
	int ma = -1;
	for(int i = 0;i<n;i++){
		ma = max(dp[i],ma);
	}
	
	printf("%d",ma+1);
	if(nDEBUG){
		fclose(stdin);
		fclose(stdout);
	}
	return 0;
}

T2 拦截导弹

题面

【题目描述】

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是 $\le 50000$ 的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

【输入格式】

$1$ 行，若干个整数（个数 $\le 100000$）

NOIP 原题数据规模不超过 $2000$。

【输出格式】

$2$ 行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

【输入输出样例】

输入 #1

1
389 207 155 300 299 170 158 65

输出 #1

1
2
6
2
分析

即求最长不上升子序列的个数

考试的时候写的 $O(N^2)$ 算法，T了五个点嘤嘤嘤

$O(N\log N)$算法见 最长上升子序列（LIS）

代码
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
#include<bits/stdc++.h>
using namespace std;

bool nDEBUG = true;

int n;

int A[1005];
int dp[1005];
 
int main(){
	
//	nDEBUG = false;
	
	if(nDEBUG){
		freopen("missile.in","r",stdin);
		freopen("missile.out","w",stdout);
	}

	while(cin>>A[++n]);
	n--;

	int len = 1;
	dp[1] = A[1];
	
	for(int i = 2;i<=n;i++){
		if(dp[len] < A[i]) dp[++len] = A[i];//如果当前元素无法接在任何一个序列的后面就新开一个序列
		else{
			int p = lower_bound(dp+1,dp+1+len,A[i]) - dp;
			dp[p] = A[i];
		}
	}
    
	printf("%d",len);
	if(nDEBUG){
		fclose(stdout);
		fclose(stdin);
	}
	return 0;
}

T3 均分纸牌

题面

有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为2的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

【输入格式】 第一行一个整数 $N(1\leq N\leq100)$ ，代表有 $N$ 堆纸牌。接下来的一行有 $N$ 个正整数，分别为 $A_1,A_2,\dots,A_n(1\leq A_i \leq 10000)$ ，代表第 $i$ 堆纸牌的初始数量。

【输出格式】 所有堆均达到相等时的最少移动次数。

【样例输入】4 9 8 17 6

【样例输出】3

分析

因为纸牌总数必为 N 的倍数，所以结果必定为平均牌数

那么就可以求出来平均牌数，将每一堆牌都减去这个平均数，得到一个新的数列，表示与目标牌数的差值（多为正少为负）

如果某一堆牌与目标差值为0则跳过

然后因为只能移到相邻的牌堆上（当时没看到所以就过了一个点），所以可以从头开始，将与目标牌数的差值转移到右面的牌堆上

即 $Ai=A_i+A{i-1}$，（即使 $A_{i-1}$ 是负数也可以，因为加上一个负数就相当于减去一个正数）

代码
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
#include<bits/stdc++.h>
using namespace std;

bool DEBUG = false;

const int maxN = (1e4+5);

int N;
int A[maxN];

int main(){
	
//	DEBUG = true;
	
	if(!DEBUG){
		freopen("Playcard.in","r",stdin);
		freopen("Playcard.out","w",stdout);
	}
	
	int sumN = 0;
	scanf("%d",&N);
	for(int i = 0;i<N;i++){
		scanf("%d",&A[i]);
		sumN += A[i];
	}
	
	int toN = sumN / N;
	for(int i = 0;i<N;i++) A[i] -= toN;
    
	int cnt = 0;
	for(int i = 0;i<N;i++){
		if(A[i] == 0) continue;
		A[i+1] += A[i];cnt++;
	}
    
	printf("%d\n",cnt);
    
    if(!DEBUG){
        fclose(stdout);
		fclose(stdin);
    }
	return 0;
}

T4 删数问题

题面

输入一个高精度的正整数 $N$ ，去掉其中任意 $S$ 个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的 $N$ 和 $S$ ，寻找一种方案使得剩下的数字组成的新数最小。 输出新的正整数。（$N$ 不超过 $240$ 位）输入数据均不需判错。

【输入】 N S

【输出】 最后剩下的最小数。

【样例输入】 175438 4

【样例输出】 13

分析

由于正整数n的有效数位为$240$位，所以很自然地采用字符串类型存贮$n$。

那么如何决定哪$s$位被删除呢？是不是最大的$s$个数字呢？显然不是，大家很容易举出一些反例。

为了尽可能逼近目标，我们选取的贪心策略为：

每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减区间的首字符，这样删一位便形成了一个新数字串。然后回到串首，按上述规则再删下一个数字。

重复以上过程s次为止，剩下的数字串便是问题的解了。

注意事项

  • 每次删数之后需要去掉多余的前导零

    如 50074897 2 这组数据，删掉第一个 5 后字符串变成了 74897

代码
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
#include<bits/stdc++.h>
using namespace std;

bool nDEBUG = true;

int N,S;
int D[300];
int t[300];

int main(){
	
//	nDEBUG = false;
	
	if(nDEBUG){
		freopen("delete.in","r",stdin);
		freopen("delete.out","w",stdout);
	}
	
	while(true){
		char c = getchar();
		if(!isdigit(c)) break;
		D[N++] = c - '0';
	}
	
	scanf("%d",&S);
	
	int ed = N - 1;
	int st = 0;
	
	while(S--){
		bool isup = true;
		for(int i = 1;i<N;i++){
			if(t[i] == -1) continue;
			int j = i-1;
			while(t[j]==-1) j--;
			if(D[i] >= D[j]) continue;
			t[j] = -1;
			isup = false;
			break;
		}
		if(isup) t[ed--] = -1;
		while(true){
			if(t[st] == -1 || D[st] == 0) {
                if(D[st] == 0) t[st] = -1;
				st++;
				continue;	
			}else break;
		}
	}
	
	for(int i = 0;i<N;i++){
		if(t[i] == -1) continue;
		printf("%d",D[i]);
	}
	
	if(nDEBUG){
		fclose(stdout);
		fclose(stdin);
	}
	return 0;
}

T5 整数区间

题面

请编程完成以下任务：

1.从文件中读取闭区间的个数及它们的描述；

2.找到一个含元素个数最少的集合，使得对于每一个区间，都至少有一个整数属于该集合，输出该集合的元素个数。

【输入】 首行包括区间的数目$n$，$1\leq n\leq 10000$，接下来的$n$行，每行包括两个整数$a,b$，被一空格隔开，$0\leq a\leq b\leq 10000$，它们是某一个区间的开始值和结束值。

【输出】 第一行集合元素的个数，对于每一个区间都至少有一个整数属于该区间，且集合所包含元素数目最少。

【样例输入】

1
2
3
4
5
4
3 6
2 4
0 2
4 7

【样例输出】 

1
2
分析

做的时候压根没读明白题直接输出的最短区间长度

和 T1 挺像的但还不太一样（更像 YbtOJ 雷达装置 来着）

按照区间的右端点排序，并将第一个区间右端点 $k$ 放入集合

如果区间 $A_i$ 的左端点在 $k$ 前面，那么点 $k$ 可以覆盖到 $A_i$ 这个区间

否则将 $k$ 更新为区间 $A_i$ 的右端点，将其放入集合

代码
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
#include<bits/stdc++.h>
using namespace std;

bool nDEBUG = true;
struct ND{
	int l,r;
	friend bool operator < (ND a,ND b){
		if(a.r!=b.r) return a.r < b.r;
		return a.l > b.l;
	}
}A[10010];

int n;

int main(){
	
//	nDEBUG = false;
	
	if(nDEBUG){
		freopen("a.in","r",stdin);
		freopen("a.out","w",stdout);
	}
	
	scanf("%d",&n);
		
	for(int i = 0;i<n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		A[i].l = a;
		A[i].r = b;
	}
	sort(A,A+n);
	int ed = A[0].r;
	int cnt = 0;
	for(int i = 1;i<n;i++){
		if(A[i].l >= ed){
			ed = A[i].r;
			cnt++;
		}
	}
	printf("%d",cnt?cnt:1);//特判，至少要含有一个整数
	if(nDEBUG){
		fclose(stdin);
		fclose(stdout);
	}
	return 0;
}

总结

  • 好好审题
  • 不要过于依赖样例
  • 小心边界情况（带等/不带等）