Codeforces Round #696 (Div. 2)
A. Puzzle From the Future
题意
给一个长度为 的二进制串 ，要构造同长的二进制串 。两串逐位相加、不进位，再把连续相同的数字缩成一个，要求最后得到的数最大。
思路
先尽量让相邻两位的和不同，这样不会被缩短。每一位只有两种选择，至少有一种能和前一位错开。
能选 1 就选 1，只有它让当前和等于前一个和时才选 0。这样既保住长度，也让前面的位尽量大。代码按前后两位的 分类来算，时间 。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 17;
int T, n, b[maxn], a[maxn];
string str;
int main() {
cin >> T;
while(T--) {
cin >> n;
cin >> str;
for(int i = 1; i <= n; i++) b[i] = str[i - 1] - '0';
for(int i = 1; i <= n; i++) {
if(b[i]) {
if(b[i - 1]) {
a[i] = 1 - a[i - 1];
}
else {
a[i] = 1;
}
}
else {
if(b[i - 1]) {
a[i] = a[i - 1];
}
else {
a[i] = 1 - a[i - 1];
}
}
}
for(int i = 1; i <= n; i++) printf("%d", a[i]);
puts("");
}
return 0;
}B. Different Divisors
题意
给一个正整数 ，找最小的正整数，要求至少有四个约数，而且任意两个不同约数的差都不小于 。
思路
用两个不同的质数 相乘，约数就是 。先找不小于 的最小质数 ，再找不小于 的最小质数 ，答案就是 。
这样前两段间隔都至少是 ，最后一段 也足够大。先用线性筛把质数列出来，每组沿着质数表找这两个数就行。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e6 + 17;
int T, d, n = 1000000;
int p[maxn], vis[maxn], cnt;
int main() {
vis[0] = vis[1] = 1;
for(int i = 2; i <= n; i++) {
if(!vis[i]) p[++cnt] = i;
for(int j = 1; j <= cnt && 1ll * p[j] *i <= n; j++) {
vis[i * p[j]] = p[j];
if(!(i % p[j])) break;
}
}
// for(int i = 1; i <= 20; i++) cout << p[i] << endl;
cin >> T;
while(T--) {
cin >> d;
int p1, p2;
for(p1 = 1; p[p1] - 1 < d; p1++);
for(p2 = p1; p[p2] - p[p1] < d; p2++);
cout << 1ll * p[p1] * p[p2] << endl;
}
return 0;
}C. Array Destruction
题意
有 个正整数，先自己选一个目标和 。每次删掉和为 的两个数，再把 改成这两个数里较大的那个，问能不能全部删完，并输出一种方案。
思路
当前最大的数必须这一轮就删掉。否则目标和变成了别的较小数，后面更不可能再和一个正数凑出它。
所以只需要枚举最大值第一次和谁配对。第一轮定下来以后，每次拿剩下的最大值，另一个数就是当前目标和减去它，没有别的分支。
排序后用频次表记剩余数量，递归处理，返回时把数量恢复。找不到补数就换一个初始配对；两个值相同的时候，要确实还剩两份。枚举加扫描是 。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
const int maxn = 2e6 + 17;
int T, n, a[maxn], c[maxn];
int ans[maxn][2], f;
bool cmp(int x, int y) {
return x > y;
}
void dfs(int u, int p) {
while(p <= n * 2 && c[a[p]] == 0) p++;
if(p > n * 2) {
f = 1;
return;
}
int tmp = ans[u - 1][1] - a[p];
if(tmp > 0 && c[tmp] > 0 && (tmp != a[p] || c[tmp] >= 2)) {
c[a[p]]--, c[tmp]--;
ans[u][0] = tmp, ans[u][1] = a[p];
dfs(u + 1, p + 1);
c[a[p]]++, c[tmp]++;
}
}
int main() {
scanf("%d", &T);
while(T--) {
int flg = 0;
scanf("%d", &n);
for(int i = 1; i <= 2 * n; i++) scanf("%d", &a[i]), c[a[i]]++;
sort(a + 1, a + 1 + 2 * n, cmp);
for(int i = 2; i <= n * 2; i++) {
f = 0;
ans[0][1] = a[1] + a[i];
dfs(1, 1);
if(f) {
puts("YES");
flg = 1;
printf("%d\n", ans[1][0] + ans[1][1]);
for(int j = 1; j <= n; j++) printf("%d %d\n", ans[j][0], ans[j][1]);
break;
}
}
if(!flg) puts("NO");
for(int i = 1; i <= 2 * n; i++) c[a[i]]--;
}
return 0;
}