七段第二课：贪心

A -【提高组】第二课：最小字典序

No.1 - 题目大意

每次可以从S的开头或者结尾取出一个字符，放到一个T字符串的尾部。输出T字典序最小的可能。

No.2 - 解题思路

如果直接从两头看那个小取肯定是不行的，样例也告诉我们：不可以乱取

1
2
3
4
5
6
7
8
9
10
11
12
S : "ACDBCB"  T : ""
S : "CDBCB"   T : "A"  // A 小
S : "CDBC"    T : "AB" // B 小
// 方法 1 
S : "CDB"     T : "ABC" // 取右边的 C
S : "CD"      T : "ABCB" // B 小
S : "D"       T : "ABCBC" // C 小
S : ""        T : "ABCBCD" // 只剩下 D 了
// 方法 2
S : "DBC"     T : "ABC" // 取左边的 C
S : "DB"      T : "ABCC" // C 小
// 但是这里已经比方法1大了，所以不是最优解

而这里，是什么决定了取左边还是右边呢？只是因为单纯取右边可以达到最优吗？显然不是，真正决定字典序的是不是那一个 B。当方法2没有取到哪个 B 的时候，就已经奠定了比方法1大的结果了。

所以取字母只是表面，真正要做到的是：在保证字典序最小的情况下使得字典序小的字母漏到两端，从而使得之后的答案更优。

因此，贪心时需要判断之后的字母大小，而题目的数据是 $2000$ ，$O(n^2)$ 不会超时，所以方向去写便是了。

No.3 - 关键代码

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
bool Check(int l, int r) {
	for( ; l <= r; l++, r--) {
		if(s[l] < s[r]) {
			return 1;
		}
        else if(s[l] > s[r]) {
			return 0; 
		}	
	}
	return 1;
}

void Work(){
	int cnt = 0;
	for(int l = 1, r = n; l <= r; ) {
		if(Check(l, r)) {
			printf("%c", s[l++]);
			cnt++;
		}
        else {
			printf("%c", s[r--]);
			cnt++;
		}
		if(cnt == 80) { // 这个是题目要求80个字母一行
			printf("\n");
			cnt=0;
		}
	}
}

B -【提高组】第二课：雷达

No.1 - 题目大意

现在要在 $x$ 轴上放置若干雷达，每个雷达的辐射半径都是 $d$ 。
问至少需要几个雷达，才能够幅射所有点，如果辐射不到所有的点，则输出 $-1$ 。

No.2 - 解题思路

这道题一看是选择一些区间实现覆盖点的题目，但是显而易见如果这么写代码极其复杂而且不好理解。那就用转化的思想，可以不可以把点转化成区间然后找重合点呢？答案显然可以。

怎么实现呢？勾股定理。已知高度，半径，就可以求出一个点最左哪里放雷达可以，最右哪里放雷达可以。然后就是区间覆盖问题了。

No.3 - 关键代码

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
void Input() {
    scanf("%d%d", &n, &d);
    int x, y;
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        if(abs(y) > d) { // 扫不到，直接 -1
            printf("-1");
            return exit(0);
        }
        double sq = sqrt(d * d - y * y); // 转化成区间
        a[i].L = x - sq;
        a[i].R = x + sq;
    }
}

void Work() {
    sort(a + 1, a + n + 1, [](Seg &a, Seg &b) {
        return a.R < b.R;
    });
	double r1 = a[1].R;
	int cnt = 1;
    for(int i = 2; i <= n; i++) {
        if(a[i].L - r1 > eps) {
            cnt++;
            r1 = a[i].R;
        }
    }
	printf("%d",cnt);
}

C -【提高组】第二课：机器分配

No.1 - 题目大意

有 $N$ 个机器与 $M$ 个任务，每个机器或者任务都有两个属性 $(x,y)$ 。
机器的 $x$ 表示这个机器的最长工作时间，$y$ 表示机器的等级。
任务的 $x$ 表示完成这个任务需要花费的时间，$y$ 表示任务的等级。

每个机器只能做一个任务，机器的等级必须大于等于任务的等级。
每完成一个任务可以获得 $500\times x+2\times y$ 的价值（ $x,y$ 是任务的 $x,y$ ）。
请问最多可以完成多少个任务以及在此基础上最多可以获得多少的价值。

No.2 - 解题思路

这道题先观察给出的式子，发现：$x$ 在式子中占绝对优势，$x$ 的优先级一定是比 $y$ 高的。
所以，我们可以考虑按照 $x$ 排序后，再处理 $y$ 。

还有，这个式子是两个未知数越大才变大，所以应该优先处理价值大的任务才可以达到最大化的效果，因为如果先处理小的就会导致小的可能会抢走大的对应的机器。

最后，我们还发现，$y$ 的大小只有 $100$ 这意味着，我们可以使用数组统计 $y$ 应该处理那一个，这样就可以完美解决这一道题了。

No.3 - 关键代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Work() {
	sort(a + 1, a + n + 1); // 这边是以未知数大小排序的，x 大排前面，一样大再比 y
	sort(b + 1, b + m + 1);
	int now = 1, ans = 0;
	long long tot = 0;
	for(int i = 1; i <= m; i++) { // 枚举任务
        // 如果还有机器，且符合等级条件
		while(now <= n && a[now].a >= b[i].a) cnt[a[now++].b]++; // 统计所有y满足的机器
		for(int j=b[i].b; j<=100; j++){ // 寻找刚好可以满足y的机器，这样如果还有等级相同、时间比这个长的任务的话，可以继续使用别的机器
			if(cnt[j]>0){
				cnt[j]--;
				ans++;
				tot+=b[i].a*500+b[i].b*2;
                break; // 做完任务就跳开
			}
		}
        // cnt 相当于是把所有满足的都统计起来，因为这样的排序规则就确定了坐标小的可以覆盖之后的所有。
	}
	printf("%d %lld", ans, tot);
}

D -【提高组】第二课：田忌赛马

No.1 - 题目大意

田忌赛马。速度快的赢200两银子，速度慢的输200两银子，速度一样则不赢也不输。
最大化赢得的银子数量。

No.2 - 解题思路

先比较两个人最强的马：能赢，就赢。如果一定赢不了，那么就拿最小的马打掉。
再比较两个人最弱的马：能赢，就赢。如果赢不了，那就输掉。如果两个最弱的马一样，再比较。
如果两个最弱的马一样：如果有马不同，就拿最小马打掉最大马。如果所有马都一样，那就平局。

以上策略是站在田忌角度说的（因为要最大化田忌的银子）。

No.3 - 关键代码

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
// 田忌赛马的宗旨就在于，拿自己弱的去抵掉强的，使得自己的马打赢对方，如图
/*
原来的：
	田上  -->  国上 （输）
	田中  -->  国中 （输）
	田下  -->  国下 （输）
现在的：
反正打不过，不如把国王最强的打掉，使得自己还有翻身余地。打的就是马与马速度差
	田下  -->  国上 （输）
	田上  -->  国中 （赢）
	田中  -->  国下 （赢）
*/
void Work() {
	sort(a + 1, a + n + 1); // 从小到大排序
	sort(b + 1, b + n + 1); // 国王也一样
	long long ans = 0; // 赢得的银子
	int la = 1, ra = n, lb = 1, rb = n; // 本别表示：田忌最弱的，田忌最强的，国王最弱的，国王最强的马的下标
	while(la <= ra && lb <= rb) { // 还有马
		if(a[ra] > b[rb]) { // 最强的能打赢，那就赢
			ans += 200;
			ra--, rb--;
		}else if(a[ra] < b[rb]) { // 最强的都打不赢，那就用最弱的马抵掉 
			ans -= 200;
			la++, rb--;
		}
        else { // 最强的马一样快，肯定不可以直接平局，太浪费了。
			if(a[la] > b[lb]) { // 最弱的马能打赢，那就赢
				ans += 200;
				la++, lb++;
			}else if(a[la] < b[lb]) { // 最弱的马打不赢对方最弱的马，肯定不可以拿最快的马拿去抵对方最弱的马 
				ans -= 200;             // 相当于是说，这个最弱的马就是废物，不如拿去把最快的马抵掉
				la++, rb--;
			}
            else { // 最弱的马也一样快
				if(a[la] != a[ra]) { // 所有的马不是全都一样的，那就把最弱的马拿去抵消最强的马。
					ans -= 200;
				}
				la++, rb--; // 否则再平局
			}
		}
	}
	printf("%lld", ans);

E -【提高组】第二课：行列快乐值

No.1 - 题目大意

给定一 $n\times m$ 的矩阵，将对矩阵进行 $k$ 次操作。每次可以进行如下某一种操作：

  1. 将某行的元素相加作为快乐值，然后将该行元素都减去 $p$ 。

  2. 将某列的元素相加作为快乐值，然后将该列元素都减去 $p$ 。

问k次之后快乐值总和的最大值是多少？

No.2 - 解题思路

这道题看上去策略很明显，那就是大的优先取，但是还有一个要慎重考虑的是：某一列所有值减去 $p$ 以后，所有行的值都得减去 $p$，而这个很难考虑到如何动态去完成功能。

脑子转过来，我们发现，其实先减行还是先减列都是差不多的。给出如下画图证明：

而两者，整理后的结果都是：$b+h+d+f+e\times2-p$

也就是说，我们完全可以先考虑减列，再考虑减行。

定义一个 $\tt sum$ 数组表示前 $k$ 次取列 ，后几次取行的价值，然后模拟即可，另外不要忘记减去修改列所影响行的价值。

No.3 - 关键代码

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
void Work() {
    Init(); // 统计出每一行和列的价值存入到pq里
    long long toth = 0, totl = 0;
	for(int i = 1; i <= k; i++) {
		int hang = qhang.top(); qhang.pop(); // 计算行的价值
		qhang.push(hang - m * p);
		toth += hang;
		sum[i] += toth;

		int lie = qlie.top(); qlie.pop(); // 计算列的价值
		qlie.push(lie - n * p);
		totl += lie;
		sum[k-i] += totl;

		if(2 * i <= k) { // 如果没有相遇，即前几次处理完后之后的价值
			sum[i] -= 1LL * i * (k - i) * p; 
			if(i != k-i) {
				sum[k-i] -= 1LL * i * (k - i) * p;
			}
		}
	}
	long long ans = -(1LL << 60);
	for(int i = 0; i <= k; i++) {
		ans=max(ans, sum[i]);
	}
	printf("%lld", ans);
}

F- 第二课：取数求和

No.1 - 题目大意

给定 $m$ 个长度为 $n$ 的数组，要求从每一个数组中取出一个数字然后相加，这样的取法总共有 $n^m$ 种。
问相加之后和最小的 $n$ 种是多少。

No.2 - 解题思路

显而易见的，把所有数字从小到大排序后，一定是从最小的开始递推才可以得到最优解，然后记得哈希去重。

No.3 - 关键代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
   node p;
for(int i=1; i<=m; i++){
	p.v.push_back(1);
	p.sum+=a[i][1];
}
mp[hash_(p.v)]=1;
q.push(p);
int gMr=n;
while(gMr--){
	node now=q.top(); q.pop();
	printf("%d ", now.sum);
	for(int i=1; i<=m; i++){
		node nxt=now;
		if(nxt.v[i-1]==n) continue;
		nxt.sum-=a[i][nxt.v[i-1]];
		nxt.v[i-1]++;
		nxt.sum+=a[i][nxt.v[i-1]];
		int h=hash_(nxt.v);
		if(!mp[h]){
			q.push(nxt);
			mp[h]=1;
		}
	}
}