abc461
AtCoder Beginner Contest 461
C
问题陈述
有 \(N\) 颗宝石。 \(i\) /th宝石的颜色（用整数表示）是 \(C _ i\) ，它的价值是 \(V _ i\) 。
从这些 \(N\) 颗宝石中选择 \(K\) 颗宝石。这里，所选的宝石必须至少有 \(M\) 种不同的颜色。
求所选宝石的最大可能总值。(在给定的输入中，这样的选择总是可能的)。
官方题解
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 | #pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<utility>
using namespace std;
using ll = long long;
const ll N=1e5+5,M=2e6+5,mod=998244353,inf=1LL<<60;
const long double pi=acos(-1);
using pii = pair<int,int>; // utility 头文件
void solve(){
int n,k,m;
cin >> n >> k >> m;
vector<vector<int>> t(M+1);
while(n--){
int c,v;
cin >> c >> v;
// 优先选择价值大的，选完每个颜色中价值最大的之后，选取剩余的价值最大的
t[c].push_back(v);
}
vector<int> top,tail;
for(auto & r:t){ // 直接操作原数据，避免复制
if(r.empty()) continue;
sort(r.rbegin(),r.rend());
top.push_back(r[0]);
for(int i = 1;i<r.size();i++){
tail.push_back(r[i]);
}
}
sort(top.rbegin(),top.rend());
for(int i = m;i<top.size();i++){
tail.push_back(top[i]);
}
sort(tail.rbegin(),tail.rend());
ll sum = 0;
for(int i = 0;i<m && i<top.size();i++){
sum += top[i];
}
int need = k-m;
for(int i = 0;i<need && i<tail.size();i++){
sum += tail[i];
}
cout << sum << endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cout << fixed << setprecision(10);
int T=1;
//cin >> T;
while(T--) solve();
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 | # 官方题解代码
N, K, M = map(int, input().split())
# 读取一行输入，按照空格切割字符串，转换成整数类型
t = [[] for _ in range(N + 1)]
# 循环 N + 1 次每次都创建一个空列表
for i in range(N): # 循环 N 次读入 N 个物品
C, V = map(int, input().split()) # 读取输入
t[C].append(V) # 把价值 V 放进对应类别 C 的列表里
# 声明了两个空列表
top = [] # 用来存储一开始每个相同颜色物品中价值最大的
tail = [] # 存储剩余的最大的
for r in t:
if len(r) > 0:
r.sort(reverse=True) # 把这个类别的价值从大到小进行排序
top.append(r[0])
tail += r[1:] # 把除了最大的那个元素，其余的元素全部追加到 tail 列表中
top.sort(reverse=True) # 降序排序
tail += top[M:] #
tail.sort(reverse=True) # 降序排序
print(sum(top[:M]) + sum(tail[: K - M]))
|
D
问题陈述
有一个 \(H \times W\) 网格，每个单元格都包含一个整数 \(0\) 或 \(1\) 。
每个单元格中写入的整数信息是长度为 \(W\) 的 \(H\) 字符串 \(S _ 1, S _ 2, \dots, S _ H\) 。如果 \(S _ i\) 的第 \(j\) 个字符是 0 ，那么 \(0\) 就会被写入网格中从上往下第 \(i\) 行、从左往上第 \(j\) 列的单元格中；如果 \(S _ i\) 的第 \(j\) 个字符是 1 ，那么 \(1\) 就会被写入该单元格中。
求写入的整数之和等于 \(K\) 的矩形区域的个数。
更具体地说，求满足以下所有条件的整数四元组 \((r _ 1, c _ 1, r _ 2, c _ 2)\) 的个数：
- \(1 \le r _ 1 \le r _ 2 \le H\)
- \(1 \le c _ 1 \le c _ 2 \le W\)
- 写在从上到下第 \(i\) 行和从左到右第 \(j\) 列的单元格中的整数，在满足 \(r _ 1 \le i \le r _ 2, c _ 1 \le j \le c _ 2\) 的所有整数对 \((i, j)\) 中的总和等于 \(K\) 。