Czj's Blog

第三讲-贪心、模拟与二分

发表于 更新于 分类于 ，
本文字数： 10k 阅读时长 ≈ 9 分钟

作业链接

[蓝桥杯] 第三讲：贪心、模拟与二分 - 题单 - 洛谷 | 计算机科学教育新生态

AC 代码

P8697 [蓝桥杯 2019 国 C] 最长子序列 - 洛谷

双指针分别维护当前枚举到的 s 和 t 串的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
string s, t;
int n, m, i = 0, j = 0, ans;
int main() {
	cin >> s >> t;
	n = s.size(), m = t.size();
	while (i < n && j < m) {
//		cout << i << " " << j << endl;
		if (s[i] == t[j]) {
			j++;
//			ans++;
		}
		i++;
//		cout << s[i] << " " << t[j] << endl;
	}
	cout << j;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
s = input()
t = input()
n, m = len(s), len(t)
i, j = 0, 0

while i < n and j < m:
    if s[i] == t[j]:
        j += 1
    i += 1

print(j)

P1106 删数问题 - 洛谷

由于数字太大，C++ 中无法表示这种数值。

要求删除后的数字更小，显然应该删除大的数字。考虑到删除数字后原始顺序不变，故高位的数字影响比低位要大。综合来看，可以从高位向低位（高位影响大）遍历，当遇到单调增加的顶点时（大数字）就将其删除。这个做法可以保证每一次得到的结果都是删一个数字时最优的，从而可以得知最终的答案也是最优的。

2024 年算法设计与分析期末原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
//找高峰
string s;
int k;
int main() {
	cin >> s >> k;
	while (k) {
		int i = 0;
		while (s[i] <= s[i + 1]) i++; //i会一直加，直到一个当前单调的最大值
		s.erase(i, 1); //erase删除第i个位置往后长度为1的部分
		k--;
	}
	while (s.size() > 1 && s[0] == '0') s.erase(0, 1); // 消除前导零
	cout << s;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
s = input()
k = int(input())

while k:
    i = 0
    while i < len(s) - 1 and s[i] <= s[i + 1]:
        i += 1
    s = s[:i] + s[i + 1:]
    k -= 1

s = s.lstrip('0')
print(s if s else '0')

P1090 [NOIP 2004 提高组] 合并果子 - 洛谷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int n, x, ans;
priority_queue<int, vector<int>, greater<int> > q;
int main() {
	scanf("%d", &n);
	while (n--) {
		scanf("%d", &x);
		q.push(x);
	}
	while (q.size() > 1) {
		auto t1 = q.top();
		q.pop();
		auto t2 = q.top();
		q.pop();
		ans += t1 + t2;
		q.push(t1 + t2);
	}
	printf("%d", ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq

n = int(input())
q = []

for _ in range(n):
    x = int(input())
    heapq.heappush(q, x)

ans = 0
while len(q) > 1:
    t1 = heapq.heappop(q)
    t2 = heapq.heappop(q)
    ans += t1 + t2
    heapq.heappush(q, t1 + t2)

print(ans)

P8769 [蓝桥杯 2021 国 C] 巧克力 - 洛谷

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;
int day, n;
const int N = 1e5 + 9;
using ll = long long;
struct node {
	ll a, b, c;
};
ll ans, idx = 1;
node food[N];
bool cmp(node x, node y) {
	return x.b > y.b;
}
// 比较器类
struct compare {
	bool operator()(node x, node y) {
		return x.a > y.a;
	}
};
priority_queue<node, vector<node>, compare> q;

int main() {
	cin >> day >> n;
	for (int i = 1; i <= n; i++) {
		cin >> food[i].a >> food[i].b >> food[i].c;
	}
	sort(food + 1, food + n + 1, cmp);
//	for (int i = 1; i <= n; i++) {
//		cout << food[i].a << food[i].b << food[i].c << endl;
//	}
	for (int i = day; i; i--) { // 时间倒流
		while (food[idx].b >= i) {
			q.push(food[idx++]);
		}
		if (q.empty()) {
			cout << -1;
			return 0;
		}
		auto t = q.top();
		q.pop();
		ans += t.a;
//		cout << t.a << " " << t.b << " " << t.c << " " << endl;
		if (t.c > 1)q.push((node) {
			t.a, t.b, t.c - 1
		});
	}
	cout << 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
import heapq

day, n = map(int, input().split())
food = []

for _ in range(n):
    a, b, c = map(int, input().split())
    food.append((b, a, c))

food.sort(reverse=True)
q = []
ans = 0
idx = 0

for i in range(day, 0, -1):
    while idx < n and food[idx][0] >= i:
        heapq.heappush(q, (food[idx][1], food[idx][0], food[idx][2]))
        idx += 1
    if not q:
        print(-1)
        exit()
    t = heapq.heappop(q)
    ans += t[0]
    if t[2] > 1:
        heapq.heappush(q, (t[0], t[1], t[2] - 1))

print(ans)

B3962 [语言月赛 202404] 游乐场 - 洛谷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, x, ans, day, money;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		money += (x - day);
		money = min(money, 50LL);
		day = x;
		ans += money / 8;
		money %= 8;
	}
	cout << ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
money = 0
day = 0
ans = 0

for _ in range(n):
    x = int(input())
    money += (x - day)
    money = min(money, 50)
    day = x
    ans += money // 8
    money %= 8

print(ans)

P8685 [蓝桥杯 2019 省 A] 外卖店优先级 - 洛谷

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
#define x first
#define y second
int n, m, T;
typedef pair<int, int> PII;
PII order[N];
bool hot[N];
int last[N], sorce[N];
int main() {
	scanf("%d %d %d", &n, &m, &T);
	for (int i = 0; i < m; i++) scanf("%d %d", &order[i].x, &order[i].y);
	sort(order, order + m);
	for (int i = 0; i < m;) {
		int j = i;
		while (j < m && order[j] == order[i]) j++;
		int id = order[i].y, t = order[i].x, cnt = j - i;
		i = j;
		sorce[id] -= t - 1 - last[id];
		last[id] = t;
		if (sorce[id] < 0) sorce[id] = 0;
		if (sorce[id] <= 3) hot[id] = 0;

		sorce[id] += cnt * 2;
		if (sorce[id] > 5) hot[id] = 1;
	}
	for (int i = 1; i <= n; i++) {
		if (last[i] < T) {
			sorce[i] -= T - last[i];
			if (sorce[i] <= 3) {
				hot[i] = 0;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (hot[i]) ans++;
	}
	printf("%d", 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
34
35
36
37
38
n, m, T = map(int, input().split())
order = []
for _ in range(m):
    x, y = map(int, input().split())
    order.append((x, y))

order.sort()
hot = [False] * (n + 1)
last = [0] * (n + 1)
sorce = [0] * (n + 1)

i = 0
while i < m:
    j = i
    while j < m and order[j] == order[i]:
        j += 1
    id = order[i][1]
    t = order[i][0]
    cnt = j - i
    i = j
    sorce[id] -= t - 1 - last[id]
    last[id] = t
    if sorce[id] < 0:
        sorce[id] = 0
    if sorce[id] <= 3:
        hot[id] = False
    sorce[id] += cnt * 2
    if sorce[id] > 5:
        hot[id] = True

for i in range(1, n + 1):
    if last[i] < T:
        sorce[i] -= T - last[i]
        if sorce[i] <= 3:
            hot[i] = False

ans = sum(hot)
print(ans)

P1601 A+B Problem（高精） - 洛谷

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
#include <bits/stdc++.h>
using namespace std;
vector<int> A, B, C;
string a, b;

vector<int> add(vector<int> a, vector<int> b) {

	vector<int> c;
	int i  = 0, t = 0;
	while (i < a.size() || i < b.size()) {
		if (i < a.size())t += a[i];
		if (i < b.size())t += b[i];
		c.push_back(t % 10);
		t = t / 10;
		i++;
	}
	if (t == 1) c.push_back(1);
	return c;
}

int main() {
	cin >> a >> b;
	for (int i = a.size() - 1; i >= 0; --i) A.push_back(a[i] - '0');
	for (int i = b.size() - 1; i >= 0; --i) B.push_back(b[i] - '0');
	C = add(A, B);
	for (int i = C.size() - 1; i >= 0; --i) {
		cout << C[i];
	}
	return 0;
}
1
2
3
a = int(input())
b = int(input())
print(a + b)

P10390 [蓝桥杯 2024 省 A] 因数计数 - 洛谷

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
#include <iostream>
#define int __int128 // 使用 __int128 需要手写输入输出
using namespace std;

const int N = 1e5 + 9;

int n, a[N], x, mp[N], yinzi[N], beishu[N], ans;
// mp yinzi beishu 分别记录 x 的出现次数，因子个数，倍数个数

int read() {
	int res = 0, p = 1;
	char c;
	c = getchar();
	// 非数字
	while (c < '0' || c > '9') {
		if (c == '-')p = -1;
		c = getchar();
	}
	// 数字
	while (c >= '0' && c <= '9') {
		res = res * 10 + (c - '0');
		c = getchar();
	}
	return p * res;
}

void print(int x) {
	if (x >= 10)print(x / 10);
	putchar((x % 10) + '0');// 输出要是字符
}

signed main() {
	n = read();
	for (int i = 1; i <= n; i++)mp[read()]++;
	// 预处理每个数字的因子和倍数
	for (int i = 1; i < N; i++) {
		if (mp[i]) {
			for (int j = i + i; j < N; j += i) {
				if (mp[j]) {
					// i 和 j 都存在
					beishu[i] += mp[j], yinzi[j] += mp[i];
				}
			}
			// 相同的值既是倍数也是因子（不能计自己）
			beishu[i] += mp[i] - 1, yinzi[i] += mp[i] - 1;
		}
	}
	for (int i = 1; i < N; i++) {
		if (mp[i])ans += beishu[i] * mp[i];// 原始数存在才能记
	}
	ans *= (ans + 1);
	for (int i = 1 ; i < N; i++) {
		if (mp[i]) {
			ans -= mp[i] * beishu[i] * beishu[i];
			ans -= mp[i] * yinzi[i] * yinzi[i];
			ans -= 2 * (mp[i] * beishu[i] * yinzi[i]);
			ans += mp[i] * (mp[i] - 1);
		}
	}
	print(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
34
35
36
def read():
    return int(input())

N = 100000 + 9
n = read()
a = [0] * N
mp = [0] * N
yinzi = [0] * N
beishu = [0] * N

for _ in range(n):
    mp[read()] += 1

for i in range(1, N):
    if mp[i]:
        for j in range(i + i, N, i):
            if mp[j]:
                beishu[i] += mp[j]
                yinzi[j] += mp[i]
        beishu[i] += mp[i] - 1
        yinzi[i] += mp[i] - 1

ans = 0
for i in range(1, N):
    if mp[i]:
        ans += beishu[i] * mp[i]

ans *= (ans + 1)
for i in range(1, N):
    if mp[i]:
        ans -= mp[i] * beishu[i] * beishu[i]
        ans -= mp[i] * yinzi[i] * yinzi[i]
        ans -= 2 * (mp[i] * beishu[i] * yinzi[i])
        ans += mp[i] * (mp[i] - 1)

print(ans)

P8647 [蓝桥杯 2017 省 AB] 分巧克力 - 洛谷

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
#include <bits/stdc++.h>
using namespace std;
int n, k;
const int N = 1e5 + 9;
typedef pair<int, int> PII;
#define x first
#define y second
PII ckl[N];
bool check(int h) {
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans += (ckl[i].x / h) * (ckl[i].y / h);
		if (ans >= k) return true; //符合
	}
	return false;
}
int main() {
	ios::sync_with_stdio(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> ckl[i].x >> ckl[i].y;
	}
	int l = 1, r = N;
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << endl;
	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
def check(h):
    ans = 0
    for i in range(n):
        ans += (ckl[i][0] // h) * (ckl[i][1] // h)
        if ans >= k:
            return True
    return False

n, k = map(int, input().split())
ckl = []

for _ in range(n):
    x, y = map(int, input().split())
    ckl.append((x, y))

l, r = 1, 100000 + 9
while l < r:
    mid = (l + r + 1) // 2
    if check(mid):
        l = mid
    else:
        r = mid - 1

print(l)

P10389 [蓝桥杯 2024 省 A] 成绩统计 - 洛谷

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

ll n,k,t,ans = -1;
const int N = 1e5+9;
ll a[N];

bool check(int len)
{
    vector<ll> tmp(len+1,0);
    for(int i = 1;i<=len;i++)tmp[i] = a[i];
    sort(tmp.begin()+1,tmp.end());
    vector<ll> s(len+1,0);
    vector<ll> ps(len+1,0);
    for(int i = 1;i<=len;i++)
    {
        s[i] = s[i-1]+tmp[i];
        ps[i] = ps[i-1]+tmp[i]*tmp[i];
    }
    for(int i = k;i<=len;i++)
    {
        if((double)(ps[i]-ps[i-k]) - (double)(s[i]-s[i-k])*(s[i]-s[i-k])/k < (double)t*k)return 1;
    }
    return 0;
}

int main()
{
    cin>>n>>k>>t;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
    }
    /*
    可以发现当检查了x名同学发现存在有k名的方差小于t时，自然检查[x+1,n]名通过都能成立
    因此这个条件是单调的，在[0,k-1]上一定不成立，在[k,n]上存在x使得条件成立
    故可以二分来求这个x
    */
    int l = k,r = n;
    while(l<r)
    {
        int mid = (l+r)>>1;
        if(check(mid))
        {
            ans = mid;
            r = mid;
        }
        else l = mid+1;
    }
    cout<<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
def check(len):
    tmp = [0] * (len + 1)
    for i in range(1, len + 1):
        tmp[i] = a[i]
    tmp.sort()
    s = [0] * (len + 1)
    ps = [0] * (len + 1)
    for i in range(1, len + 1):
        s[i] = s[i - 1] + tmp[i]
        ps[i] = ps[i - 1] + tmp[i] * tmp[i]
    for i in range(k, len + 1):
        if (ps[i] - ps[i - k]) - (s[i] - s[i - k]) * (s[i] - s[i - k]) / k < t * k:
            return True
    return False

n, k, t = map(int, input().split())
a = [0] * (n + 1)

for i in range(1, n + 1):
    a[i] = int(input())

l, r = k, n
ans = -1
while l < r:
    mid = (l + r) // 2
    if check(mid):
        ans = mid
        r = mid
    else:
        l = mid + 1

print(ans)