总览
不太常打CF。后来想了想，虽然退休了，还是决定给名字换点颜色。
A. String Similarity
答案字符串可以由(s[1..n])的第(1)位, (s[2..n+1])的第(2)位, (s[3..n+2])的第(3)位...构成。即原字符串的奇数位。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 60;
typedef long long LL;
const int inf = 0x3f3f3f3f;
char s[MAXN * 2];
int n, t;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
scanf("%s", s);
for (int i = 0; i < 2*n; i++) {
if (i%2 == 0) printf("%c", s[i]);
}
printf("
");
}
}
B. RPG Protagonist
枚举第一个人取剑的数量，那么第一个人取战斧的数量是可以计算的。第二个人只要贪心从剑和战斧先取重量较小的，再用较大的填满背包即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 60;
typedef long long LL;
const int inf = 0x3f3f3f3f;
int n, t;
int main() {
scanf("%d", &t);
while(t--) {
LL p, f, cnts, cntw, s, w;
scanf("%lld%lld%lld%lld%lld%lld", &p, &f, &cnts, &cntw, &s, &w);
LL ans = 0;
for (LL i = 0; i <= cnts; i++) {
if (i*s > p) break;
LL j = min( (p-i*s)/w, cntw );
LL x, y;
if (s > w) {
x = min( f/w, cntw-j );
y = min( (f - x*w) / s, cnts-i );
} else {
y = min( f/s, cnts-i );
x = min( (f - y*s) / w, cntw-j );
}
ans = max(ans, y + x + i + j);
}
printf("%lld
", ans);
}
}
C. Binary String Reconstruction
(0)的两边一定都是(0)。所以可以先遍历处理(0)的位置，标记两边为(0)，被标记的地方都看作(1)，然后通过剩下的(1)判断是否合法。当1的两边都已经被标记为(0)的时候为不合法。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
typedef long long LL;
const int inf = 0x3f3f3f3f;
char s[MAXN];
int v[MAXN];
int n, t, x;
bool solve() {
int len = strlen(s+1);
for (int i = 1; i <= len; i++) v[i] = 1;
for (int i = 1; i <= len; i++) {
if (s[i] == '0') {
if (i-x > 0) v[i-x] = 0;
if (i+x <= len) v[i+x] = 0;
}
}
for (int i = 1; i <= len; i++) {
if (s[i] == '1') {
int flag = 0;
if (i-x > 0 && v[i-x] != 0) flag++;
if (i+x <= len && v[i+x] != 0) flag++;
if (!flag) return false;
}
}
for (int i = 1; i <= len; i++)
printf("%d", v[i]);
puts("");
return true;
}
int main() {
scanf("%d", &t);
while(t--) {
scanf("%s%d", s+1, &x);
if (!solve()) printf("-1
");
}
}
D. Zigzags
预处理(sum[i][j])，即前(i)个数中存在的数字(j)的个数。
枚举元组((i,j,k,l))中(j)和(k)的位置，设为(l)和(r)。
那么此时满足题意的元组数量即为 (l)前面的(a[r])的个数( * r)后面的(a[l])的个数。更新答案即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3000 + 100;
typedef long long LL;
const int inf = 0x3f3f3f3f;
int a[MAXN];
int sum[MAXN][MAXN];
int n, t, x;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
for (int j = 1; j <= n; j++) sum[i][j] = sum[i-1][j];
sum[i][a[i]]++;
}
LL ans = 0;
for (int i = 1; i <= n; i++)
for (int j = i+1; j <= n; j++)
ans += 1ll * sum[i-1][a[j]] * (sum[n][a[i]] - sum[j][a[i]]);
printf("%lld
", ans);
}
}
E. Clear the Multiset
最优解可能是全都竖着消，或者横着消min次+剩余连通块的处理次数之和。min为数组最小值。
剩余连通块可以递归求解。
写挫了一发。第二发过了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000 + 100;
typedef long long LL;
const int inf = 0x3f3f3f3f;
int a[MAXN];
int n, t, x;
int solve(int l, int r, int h) {
if (l == r) return a[l]-h != 0; //这里直接写return 1结果被hack了。hack数据1 0
int ans = 0, minX = inf, cnt = 0;
for (int i = l; i <= r; i++) minX = min(minX, a[i]-h);
for (int i = l; i <= r; i++) ans += a[i]-h != 0;
int s = -1, tmp = 0;
for (int i = l; i <= r; i++) {
if (s == -1 && a[i]-h > minX) s = i;
if (s != -1 && (i == r || a[i+1]-h == minX)) {
tmp += solve(s, i, minX+h);
s = -1;
}
}
ans = min(ans, minX + tmp);
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
printf("%d", solve(1, n, 0));
}
F. x-prime Substrings
too vegetable to solve
G. Mercenaries
too vegetable to solve