IOI赛制，600+，y神 关键思路，C D 题的对 P 取模
D 题是一个完全背包，不优化可过
E 因为边界导致没 a 出来，30 分
F 暴力可以过…
A
签到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int main() {
int n = 0;
vector<ll> nums(6);
ll sum = 0;
for (int i = 0; i < 6; i++) {
cin >> nums[i];
sum += nums[i];
}
if (nums[0] * 30 < sum) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
|
B
从大到小排序，模拟即可
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;
typedef long long ll;
const int N = 2e6 + 10;
int main() {
ll n = 0, k;
cin >> n >> k;
vector<ll> nums(n);
ll sum = 0;
for (int i = 0; i < n; i++) {
cin >> nums[i];
sum += nums[i];
}
sort(nums.begin(), nums.end(), greater<ll>());
ll yu = sum % k;
if (yu == 0) {
cout << 0 << endl;
return 0;
} for (int i = 0; i < n; i++) {
if (nums[i] <= yu) {
yu -= nums[i];
} else {
yu = 0;
} if (yu == 0) {
cout << i + 1 << endl;
return 0;
} } cout << n << endl;
return 0;
}
|
C
因为 p == 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
43
44
45
46
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int main() {
ll n, p;
cin >> n >> p;
vector<ll> v(n);
for (auto &it: v) {
cin >> it;
it = it % 3;
}
unordered_map<int, int> M;
for (auto it: v) {
if (it == 0) {
cout << 1 << endl;
return 0;
} else if (it == 1) {
M[1]++;
} else if (it == 2) {
M[2]++;
}
}
if (M.count(1) && M.count(2)) {
cout << 2 << endl;
return 0;
}
if (M.count(1)) {
cout << 3 << endl;
return 0;
}
if (M.count(2)) {
cout << 3 << endl;
return 0;
}
return 0;
}
|
D
Bfs ，加剪枝，暴力即可过
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int main() {
ll n, p;
cin >> n >> p;
vector<ll> v(n);
set<ll> s;
for (auto &it: v) {
cin >> it;
it = it % p;
s.insert(it);
}
vector<ll> nv;
queue<pair<int, int>> q;
vector<bool> vis(p, false);
for (auto it: s) {
nv.push_back(it);
q.push({it, 1});
vis[it] = true;
}
if (s.count(0)) {
cout << 1 << endl;
return 0;
}
while (!q.empty()) {
auto [cur, step] = q.front();
q.pop();
if (cur == 0) {
cout << step << endl;
return 0;
}
for (auto it: nv) {
int to = (cur + it) % p;
if (vis[to]) continue;
q.push({to, step + 1});
vis[to] = true;
}
}
cout << -1 << endl;
return 0;
}
|
E
求有多少种 1 <= i <= p, 1 <= j <= m, 1 <= k <= p, 注意去重
满足 i x j + 2 x i x k + 2 x j x k == x
思路 枚举+二分找答案
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ll n = 0, k, p, ans = 0, x, m;
cin >> n >> m >> p >> x;
unordered_set<ll> s;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
ll l = 1, r = p + 1;
while (l <= r) {
ll mid = l + (r - l) / 2;
if (i * j + 2 * i * mid + 2 * j * mid == x && mid <= p) {
s.insert(i + j * 3001 + 1ll * mid * 3001 * 3001);
break;
} else if (i * j + 2 * i * mid + 2 * j * mid < x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
}
cout << s.size() << endl;
}
|
F
暴力能过，数据很弱
看到有并查集，二分，线段树的解法