Codeforces Round #708 (Div. 2)
A. Meximization
题意
重新排列数组，让所有前缀的 MEX 之和最大。MEX 就是没有出现过的最小非负整数，输出一种最优排列。
思路
MEX 想尽早变大，就要把小的、还没出现过的数尽早放进去。先把每个不同的数按从小到大输出一次，再把重复的数补到后面就行。
重复出现的数不会让 MEX 变大，提前放它只会把后面有用的数往后挤。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
using namespace std;
int T, n, a[111], c[111];
int main() {
cin >> T;
while(T--) {
memset(c, 0, sizeof(c));
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) c[a[i]]++;
for(int i = 0; i <= 100; i++) if(c[i]) printf("%d ", i), c[i]--;
for(int i = 0; i <= 100; i++) {
if(c[i]) {
for(int j = 1; j <= c[i];j++) printf("%d ", i);
}
}
printf("\n");
}
return 0;
}B. M-arrays
题意
把数组里的数分成尽量少的几组，每组内部可以任意重排。要求每组相邻两个数的和都能被 整除，只有一个数的组也合法。
思路
只用看每个数对 的余数。余数 只能和 相邻，所以这两类交替放；数量差不超过 1，就能放进同一组，否则剩下的只能各自成组，贡献就是两类数量之差。
余数 0 可以全放一组。 是偶数时，余数 也能自己连起来，非空就算一组。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
using namespace std;
const int maxn = 1e5 + 17;
int n, m, c[maxn + 17], ans, T;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
int tmp; scanf("%d", &tmp);
c[tmp % m]++;
}
for(int i = 1; i * 2 <= m; i++) {
int j = m - i;
if(!c[i] && !c[j]) continue;
if(abs(c[i] - c[j]) <= 1) ans++;
else {
ans += abs(c[i] - c[j]);
}
}
if(c[0]) ans++;
printf("%d\n", ans);
ans = 0;
for(int i = 0; i <= m; i++) c[i] = 0;
}
return 0;
}C2. k-LCM (hard version)
题意
把 拆成 个正整数，要求它们的和是 ，最小公倍数不超过 。输出任意一种拆法。
思路
先放 个 1，剩下的数记成 ，只要把它拆成三个数就行。1 不影响最小公倍数。
是奇数，就用 ； 能被 4 整除，就用 ；否则用 。最后一种里前两个数都是偶数，所以最小公倍数就是它们本身，也不会超过 。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
using namespace std;
const int maxn = 1e5 + 17;
int n, k, T;
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
k -= 3;
for(int i = 1; i <= k; i++) printf("1 ");
n -= k;
int o = n % 4;
if(o == 0) {
printf("%d %d %d\n", n / 2, n / 4, n / 4);
}
else if(o == 2) {
printf("%d %d %d\n", n / 2 - 1, n / 2 - 1, 2);
}
else {
printf("%d %d %d\n", n / 2, n / 2, 1);
}
}
return 0;
}E1. Square-Free Division (easy version)
题意
把数组切成尽量少的连续段，每一段里不能有两个不同位置的数相乘得到完全平方数。简单版里 ，不能修改元素。
思路
一个数里出现偶数次的质因子可以全部去掉，只保留出现奇数次的。两个数相乘是完全平方数，当且仅当剩下的质因子集合相同。
于是从左往右扫，用 set 记当前段里出现过的集合。一旦重复，就在这个数前面切开，清空集合重新开始。前面能放下就继续放，遇到重复又必须切，贪心就行。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;
const int maxn = 2e5 + 17;
const int mx = 1e7;
int n, k, T, ans;
set<vector<int>> s;
int vis[mx + 17], p[mx + 17], cnt, is[mx + 17];
int main() {
for(int i = 2;i <= mx; i++){
if(!vis[i]) p[++cnt] = i;
for(int j = 1; j <= cnt && 1ll * i * p[j] <= 1ll * mx; j++){
vis[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
}
for(int i = 1; i <= cnt; i++) is[p[i]] = 1;
// for(int i = 1; i <= cnt; i++) printf("%d%c", p[i], " \n"[i == cnt]);
scanf("%d", &T);
while(T--) {
s.clear(); ans = 0;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
vector<int> v;
for(int j = 1; p[j] * p[j] <= x && j <= cnt; j++) {
int flg = 0;
while(x % p[j] == 0) {
x /= p[j];
flg++;
}
if(flg & 1) {
v.push_back(p[j]);
}
}
if(x > 1) v.push_back(x);
if(v.empty()) v.push_back(1);
// for(int h = 0; h < v.size(); h++) {
// printf("%d ", v[h]);
// printf("\n");
// }
if(!s.count(v)) s.insert(v);
else{
s.clear();
s.insert(v);
ans++;
}
}
printf("%d\n", ans + 1);
}
return 0;
}