真是上分场啊.
机房的奆佬们一个个都上了红名,只有我还是蓝......
(SV) 奆佬:本场比赛高分的关键是有没有早开 (F).
然而我这个蒟蒻被 (B) 续了 (1space hr).
A
Descripition
在 (n) 个数(0/1)中找到最长的子串使得0/1左右对半.
Solution
水题,模拟即可.
Code
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n;
int a[MAXN];
int g[MAXN][2], f[MAXN][2];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), --a[i];
for (int i = 1; i <= n; ++i) {
if (a[i] == a[i - 1]) f[i][a[i]] = f[i - 1][a[i]] + 1;
else f[i][a[i]] = 1;
}
for (int i = n; i; --i) {
if (a[i] == a[i + 1]) g[i][a[i]] = g[i + 1][a[i]] + 1;
else g[i][a[i]] = 1;
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans = max(max(min(f[i][0], g[i + 1][1]), min(f[i][1], g[i + 1][0])), ans);
}
printf("%d
", ans << 1);
return 0;
}
B
Descripition
给出 (a_1cdots a_n) , (b_1cdots b_n), 选出 (1le c_1lecdotsle c_{frac{n}{2}}le n),使得 (sum_{i=1}^{frac{n}{2}}a_{c_i}=sum_{iinleft[1,n ight]&i ot= c_jleft(jinleft[1,frac{n}{2} ight] ight)}b_i).
输出任意一组 (c_i).
Solution
将每个有序对 (left(a_i,b_i ight)) 分成 (4) 类.
然后分类讨论即可.
具体过程详见代码.
(刚开始一直过不了样例 (QAQ))
Code
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
const int MAXN = 5005;
int n;
char s[2][MAXN];
int A, B, C, D;
bool calc(int A, int B) {
return ~A&& A <= B;
}
void print(int A, int B, int C, int D) {
for (int i = 1; A && i <= n; ++i) if (s[0][i] == '0' && s[1][i] == '0') printf("%d ", i), --A;
for (int i = 1; B && i <= n; ++i) if (s[0][i] == '0' && s[1][i] == '1') printf("%d ", i), --B;
for (int i = 1; C && i <= n; ++i) if (s[0][i] == '1' && s[1][i] == '0') printf("%d ", i), --C;
for (int i = 1; D && i <= n; ++i) if (s[0][i] == '1' && s[1][i] == '1') printf("%d ", i), --D;
puts("");
return;
}
inline void QAQ() {
puts("======QAQ======");
return;
}
int main() {
scanf("%d", &n);
scanf("%s%s", s[0] + 1, s[1] + 1);
rep(i, 1, n) {
if (s[0][i] == '0' && s[1][i] == '0') ++A;
if (s[0][i] == '0' && s[1][i] == '1') ++B;
if (s[0][i] == '1' && s[1][i] == '0') ++C;
if (s[0][i] == '1' && s[1][i] == '1') ++D;
}
rep(i, 0, n >> 1) rep(d1, 0, D) {
int d2 = D - d1;
int c1 = i - d1, c2 = C - c1;
int b2 = i - d2, b1 = B - b2;
int a1 = n / 2 - b1 - c1 - d1, a2 = A - a1;
// QAQ();
if (calc(a1, A) && calc(a2, A) && calc(b1, B) && calc(b2, B) && calc(c1, C) && calc(c2, C) && calc(d1, D) && calc(d2, D) && a1+a2 == A && b1+b2 == B && c1+c2 == C && d1+d2 == D) {
print(a1, b1, c1, d1);
// QAQ();
return 0;
}
}
return puts("-1"), 0;
}
C
Descripition
对于每个点,将其行和列所在元素离散化,这个点的答案为离散化后最大的数.
Solution
按题意做即可.
反正 (C++) 自带离散化.
Code
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10, MAXM = 1e3 + 10;
int n, m;
int a[MAXN][MAXM], b[MAXN][MAXM], c[MAXN][MAXM], ans[MAXN][MAXM];
int p[MAXN], q[MAXM];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%d", &a[i][j]), b[i][j] = a[i][j], c[j][i] = a[i][j];
for (int i = 1; i <= n; ++i) {
sort(b[i] + 1, b[i] + m + 1);
p[i] = unique(b[i] + 1, b[i] + m + 1) - b[i] - 1;
}
for (int i = 1; i <= m; ++i) {
sort(c[i] + 1, c[i] + n + 1);
q[i] = unique(c[i] + 1, c[i] + n + 1) - c[i] - 1;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
int x = lower_bound(b[i] + 1, b[i] + p[i] + 1, a[i][j]) - b[i];
int y = lower_bound(c[j] + 1, c[j] + q[j] + 1, a[i][j]) - c[j];
ans[i][j] = max(x, y) + max(p[i] - x, q[j] - y);
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
printf("%d%c", ans[i][j], "
"[j == m]);
return 0;
}
D
Descripition
给出 (01) 串 (S), (T), 要求对 (S) 重新排列, 使得 (T) 在 (S) 中出现的次数最大.
Solution
(KMP) 简单题.
只要用一下 (next/fail) 数组的性质就可以了.
Code
不要太在意变量名.
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i=(l);i<=(r);++i)
#define per(i, r, l) for(int i=(r);i>=(l);--i)
const int MAXN = 500010;
char S[MAXN], T[MAXN];
int fuck[MAXN], n, m, j, A, B;
inline void FUCK(int now) {
puts("FUCK");
puts("The Computer Is Stupid!!!");
printf("i=%d,j=%d
", now, j);
return;
}
int main() {
scanf(" %s %s", S + 1, T + 1);
n = strlen(S + 1), m = strlen(T + 1);
fuck[1] = 0, j = 0;
rep(i, 2, m) {
while (j && T[i] != T[j + 1]) j = fuck[j];
if (T[i] == T[j + 1]) ++j;
//FUCK(i);
fuck[i] = j;
}
rep(i, 1, n) {
if (S[i] == '0') ++A;
else if (S[i] == '1') ++B;
}
j = 0;
rep(i, 1, n) {
if (j == m) j = fuck[j]; ++j;
if ((T[j] == '0' && !A) || (T[j] == '1' && !B)) break;
if (T[j] == '0') --A;
else --B;
putchar(T[j]);
}
rep(i, 1, A) putchar('0');
rep(i, 1, B) putchar('1');
return 0;
}
E
比赛的时候把题意看错了以为不可做.
然后就没有做.
赛后知道题意后发现可做.
但既然比赛时没有做那赛后也就理所当然的不做了.
F
Descripition
交互题.
有一张图,一条链后是一个环,开始有 (10) 个棋子在链的起点.要求通过不超过 (3n)((n) 为点数)次操作,使得所有棋子均在环的起点.
每次操作格式如下:
(next) 后跟若干个数字,表示将这些棋子均向下一个节点移动一格.
交互库会返回在同一个节点的棋子.
Solution
前几天 (Siyuan) 拉我做 「WC2015」未来程序.
里面有一个点要用 (Floyd) 判圈.
我就顺便学了一下.
然后,就过了.(有史以来第一次考场过(F))
每次让一个棋子走一格,另一个棋子走两格(这样一次会花费 (2) 次操作).
当着两个棋子在同一个节点时(显然此时最多用了 (2n) 次操作),让所有棋子一起向前移动,最终所有棋子一定会到达同一个点(可以证明一定在 (n) 次操作内),则那个点就是环的起点.
证明?
好像很显然?
Code
#include <bits/stdc++.h>
using namespace std;
int n;
char S[20];
inline void ask1() {
puts("next 1");
puts("next 0 1");
return;
}
inline void ask2() {
puts("next 0 1 2 3 4 5 6 7 8 9");
return;
}
int main() {
while (2333) {
ask1();
fflush(stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf(" %s", S);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf(" %s", S);
if (n == 2) break;
}
while (2333) {
ask2();
fflush(stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf(" %s", S);
if (n == 1) break;
}
puts("done");
return 0;
}
后记
好不容易苟上 (rank) 前 (10).
如果先开 (F) 应该还能更前面.
看来我还是 ( exttt{too naive}).