Codeforces Round #708 (Div. 2) 解题报告 A, B, C1, C2, E1, E2
A. 最小排除值最大化
给定一个包含n个元素的数组，重新排序以求所有前缀的最大最小排除值和。如果一个前缀的最小排除值为x，则其自身的最小排除值应大于等于x。因此，较大的最小排除值越早出现越好，即顺序为0,1,2,3,...，后面的随意。
#include
using namespace std;
const int MAXN = 2005;
int num[MAXN];
void solve() {
memset(num, 0, sizeof(num));
int n; cin >> n;
for (int i = 0; i < n; ++i) {
int x; cin >> x;
num[x]++;
}
int maxMex = 0;
for (int i = 0; i <= 103; ++i) {
if (num[i] == 0) {
maxMex = i;
break;
}
}
for (int i = 0; i < maxMex; ++i) {
cout << i << " ";
num[i]--;
}
for (int i = 0; i <= 100; ++i) {
while (num[i]--) cout << i << " ";
}
cout << endl;
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
B. M-数组
给定一个包含n个数字的数组和一个m值，要求将这个数组划分成最少的子数组，使得每个子数组中任意两个相邻元素之和为m的倍数（单个元素的子数组默认满足）。
#include
using namespace std;
const int MAXN = 100005;
int cnt[MAXN];
void solve() {
int n, m; cin >> n >> m;
memset(cnt, 0, sizeof(cnt));
vector<int> arr(n);
for (auto &x : arr) {
cin >> x;
if (x % m == 0) continue;
cnt[x % m]++;
}
int ans = 0;
for (int i = 1; i < m; ++i) {
if (!cnt[i]) continue;
if (i * 2 == m) {
ans++;
continue;
}
int d = m - i;
if (cnt[d] > cnt[i]) swap(cnt[d], cnt[i]);
if (cnt[i] - cnt[d] <= 1) {
ans += 1;
} else {
cnt[i] -= (cnt[d] + 1);
ans += cnt[i] + 1;
}
cnt[d] = 0;
cnt[i] = 0;
}
cout << ans + 1 << endl;
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
C1. k-LCM (简单版)
给定一个数n，找出三个数x, y, z，满足x + y + z = n且lcm(x, y, z) ≤ n / 2。
#include
using namespace std;
void solve() {
int n; cin >> n;
if (n % 2) {
cout << 1 << " " << n / 2 << " " << n / 2 << endl;
} else {
if ((n - 2) % 4 == 0) {
cout << 2 << " " << (n - 2) / 2 << " " << (n - 2) / 2 << endl;
} else {
cout << n / 2 << " " << n / 4 << " " << n / 4 << endl;
}
}
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
C2. k-LCM (复杂版)
给定一个数n和k，找出k个数（k ≥ 3），满足a_1 + a_2 + ... + a_k = n且lcm(a_1, a_2, ..., a_k) ≤ n / 2。
#include
using namespace std;
void solve() {
int n, k; cin >> n >> k;
int s = k - 3;
n -= s;
for (int i = 0; i < s; ++i) cout << 1 << " ";
if (n % 2) {
cout << 1 << " " << n / 2 << " " << n / 2 << endl;
} else {
if ((n - 2) % 4 == 0) {
cout << 2 << " " << (n - 2) / 2 << " " << (n - 2) / 2 << endl;
} else {
cout << n / 2 << " " << n / 4 << " " << n / 4 << endl;
}
}
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
E1. 无平方因子分割 (简单版)
给定一个包含n个元素的数组，找到最少能将数组分成几段，使得每段中的任意两个数的乘积不是平方数。
#include
using namespace std;
map mp;
int divide(int x) {
int res = 1;
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) s++, x /= i;
if (s & 1) res *= i;
}
}
if (x != 1) res *= x;
return res;
}
void solve() {
mp.clear();
int n; cin >> n;
int ans = 0;
for (int i = 0; i < n; ++i) {
int sum = divide(cin.get());
if (mp.count(sum)) {
ans++;
mp.clear();
}
mp[sum] = 1;
}
cout << ans + 1 << endl;
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
E2. 无平方因子分割 (复杂版)
与上一题相同，但增加了最多可以修改其中k个数的条件。
#include
using namespace std;
const int MAXN = 200005;
int mask[MAXN], lef[MAXN][22], cnt[MAXN];
int divide(int x) {
if (mask[x]) return mask[x];
int res = 1, c = x;
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) s++, x /= i;
if (s & 1) res *= i;
}
}
if (x != 1) res *= x;
mask[c] = res;
return res;
}
void solve() {
int n, k; cin >> n >> k;
vector<int> arr(n);
for (auto &x : arr) x = divide(cin.get());
for (int i = 0; i <= k; ++i) {
int L = 1, sum = 0;
for (int j = 1; j <= n; ++j) {
cnt[arr[j]]++;
if (cnt[arr[j]] > 1) sum++;
while (sum > i) {
cnt[arr[L]]--;
if (cnt[arr[L]] >= 1) sum--;
L++;
}
lef[j][i] = L;
}
while (L <= n) cnt[arr[L++]]--;
}
int dp[MAXN][22];
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= k; ++j)
for (int q = 0; q <= j; ++q)
dp[i][j] = min(dp[i][j], dp[lef[i][q] - 1][j - q] + 1);
int ans = 2 * n;
for (int i = 0; i <= k; ++i) ans = min(ans, dp[n][i]);
cout << ans << endl;
}
int main() {
int t; cin >> t;
while (t--) solve();
return 0;
}
