AtCoder Beginner Contest 159
https://atcoder.jp/contests/abc159
EF 是打基础的好题
D - Banned K
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
int a[N], n;
int main () {
cin >> n;
map<int, int> mp;
for (int i = 1; i <= n; i++) cin >> a[i], mp[a[i]] ++;
ll ans = 0;
for (auto i : mp) ans += max (0ll, 1ll * i.second * (i.second - 1) / 2);
for (int i = 1; i <= n; i++) cout << ans - mp[a[i]] + 1 << endl;
}
E - Dividing Chocolate
二进制枚举 + 贪心 + 前缀和处理
这题思路主要是来源于 \(n\) 那不同寻常小的范围
#include <bits/stdc++.h>
using namespace std;
const int N = 15, M = 1005;
int a[N][M], n, m, k, ans;
int sum[N][M]; //sum[i][j]: 第i行的前缀和(分行考虑)
int count (int x) {
int cnt = 0;
while (x) cnt += (x & 1), x /= 2;
return cnt;
}
int main () {
cin >> n >> m >> k;
ans = n * m;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
int cnt = 0;
for (int j = 1; j <= m; j++) {
a[i][j] = s[j-1] - '0';
sum[i][j] = sum[i][j-1] + a[i][j];
//cout << sum[i][j] << ' ';
}
//cout << endl;
}
for (int st = 0; st < (1ll << (n - 1)); st++) {
//如果有单列都超了的就直接剪枝
int lst = 0, maxn = 0, tsum = 0;
bool suc = true;
for (int j = 1; j <= m; j++) {
tsum = 0;
for (int i = 1; i <= n; i++) {
tsum += a[i][j];
if (tsum > k) {
suc = false;
break;
}
if (st >> (i - 1) & 1) tsum = 0;
}
}
if (!suc) continue;
//cout << st << ": ";
int cnt = count (st);
//cout << cnt << endl;
lst = 0; //列的上一个切割点
for (int j = 1; j <= m; j++) { //列贪心切割s
maxn = tsum = 0; //目前最大的一块
for (int i = 1; i <= n; i++) {
tsum += sum[i][j] - sum[i][lst];
maxn = max (maxn, tsum);
if (st >> (i - 1) & 1) tsum = 0;
}
//cout << maxn << ' ';
if (maxn > k) {
cnt ++;
lst = j - 1;
}
}
ans = min (ans, cnt);
//cout << endl;
}
cout << ans << endl;
}
//二进制枚举行的切割状态,然后贪心切割列
F - Knapsack for All Segments
魔改背包
关键在于状态的设计。
\(f_i\):和为 \(i\) 的左端点选择方案数
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3005, mod = 998244353;
ll n, s, a[N], f[N], ans; //f[i]:和为i的左端点选择方案数
int main () {
cin >> n >> s;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
f[s] = 0; //因为上次统计了fs所以要清空防止重复计算
for (int j = s; j >= a[i]; j--) { //01背包
(f[j] += f[j-a[i]]) %= mod;
}
(f[a[i]] += i) %= mod; //1-i共i种左端点选择
(ans += (n - i + 1) * f[s]) %= mod; //乘上右端点贡献
}
cout << ans;
}
- Beginner AtCoder Contest 159beginner atcoder contest 159 atcoder regular contest 159 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332