终于有场正常时间的比赛了。。。毛子换冬令时还正是好啊233
做了ABCD，E WA了3次最后没搞定，F不会= =
那就来说说做的题目吧= =
A. Team Olympiad
水题嘛= =
就是个贪心什么的乱搞，貌似放A题难了
#include <cstdio>
#include <algorithm> using namespace std;
const int N = ; int cnt[], first[], next[N]; int main() {
int n ,i, x, ans;
int a, b, c;
scanf("%d", &n);
for (i = ; i <= n; ++i) {
scanf("%d", &x);
next[i] = first[x], first[x] = i;
++cnt[x];
}
ans = min(min(cnt[], cnt[]), cnt[]);
printf("%d\n", ans);
a = first[], b = first[], c = first[];
for (i = ; i <= ans; ++i) {
printf("%d %d %d\n", a, b, c);
a = next[a], b = next[b], c = next[c];
}
}
B. Queue
这放B题真的合适吗= =
就是模拟啦，但是但是，具体处理好麻烦的说！！！
#include <cstdio>
#include <algorithm> using namespace std;
const int N = (int) 1e6 + ;
int S = (int) 1e6 + ;
int T = (int) 1e6 + ; struct edges {
int next, to;
edges() {}
edges(int _next, int _to) : next(_next), to(_to) {}
}e[N << ]; int n, tot, first[N];
int ans[N], cnt;
int Cnt[N];
bool v[N]; inline void add_edges(int x, int y){
e[++tot] = edges(first[x], y), first[x] = tot;
e[++tot] = edges(first[y], x), first[y] = tot;
} int main() {
int i, x, y;
scanf("%d", &n);
for (i = ; i <= n; ++i) {
scanf("%d%d", &x, &y);
++Cnt[x], --Cnt[y];
if (x == ) x = S;
if (y == ) y = T;
add_edges(x, y);
}
v[S] = , cnt = ;
while () {
for (x = first[S]; x; x = e[x].next)
if (!v[e[x].to]) break;
if (x == ) break;
v[S = e[x].to] = ;
ans[cnt << ] = S, ++cnt;
}
if (n & == ) {
v[T] = , cnt = ;
while () {
for (x = first[T]; x; x = e[x].next)
if (!v[e[x].to]) break;
if (x == ) break;
v[T = e[x].to] = ;
ans[n + - (cnt << )] = T, ++cnt;
}
} else {
for (i = ; i <= N; ++i)
if (Cnt[i] == ) {
S = i;
break;
}
ans[] = S;
v[S] = , cnt = ;
while () {
for (x = first[S]; x; x = e[x].next)
if (!v[e[x].to]) break;
if (x == ) break;
v[S = e[x].to] = ;
ans[cnt << | ] = S, ++cnt;
}
}
for (i = ; i < n; ++i)
printf("%d ", ans[i]);
printf("%d\n", ans[n]);
return ;
}
C. Hacking Cypher
正这反着扫两遍，直接判断就好了，报noip高精模写错的一箭之仇！
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
typedef long long ll;
const int N = (int) 1e6 + ; ll a, b;
int len;
bool ok_a[N], ok_b[N];
char st[N]; int main() {
ll tmp, T;
int i, j;
scanf("%s", st + ); len = strlen(st + );
scanf("%I64d%I64d", &a, &b);
tmp = ;
for (i = ; i <= len; ++i) {
((tmp *= ) += st[i] - '' ) %= a;
if (tmp == ) ok_a[i] = ; else ok_a[i] = ;
}
tmp = , T = ;
for (i = len; i; --i) {
(tmp += (ll) T * (st[i] - '')) %= b;
(T *= ) %= b;
if (tmp == ) ok_b[i] = ; else ok_b[i] = ;
}
for (i = ; i <= len; ++i)
if (ok_a[i - ] && ok_b[i] && st[i] != '') break;
if (i == len + ) {
puts("NO");
return ;
}
puts("YES");
for (j = ; j < i; ++j)
putchar(st[j]); puts("");
for (j = i; j <= len; ++j)
putchar(st[j]); puts("");
return ;
}
D. Chocolate
第一眼神题Orz
后来发现，是指1 * 1的方格一样多。。。这尼玛是在逗我！
于是计算面积s1, s2，令s1 /= gcd, s2 /= gcd
然后判断s1 * (2 / 3) ^ x1 * (1 / 2) ^ y1 = s2 * (2 / 3) ^ x2 * (1 / 2) ^ y2 是否有非负整数解(x1, x2, y1, y2)且x1, x2; y1, y2中都至少有一个0
乱搞吧2333
#include <cstdio> using namespace std;
typedef long long ll; ll a, b, c, d, s1, s2, G;
int ans;
int cnt[][]; ll gcd(ll a, ll b) {
return !b ? a : gcd(b, a % b);
} int abs(int x) {
return x < ? -x : x;
} void work() {
ans += cnt[][] + cnt[][] + abs(cnt[][] + cnt[][] - cnt[][] - cnt[][]);
} int main() {
scanf("%I64d%I64d%I64d%I64d", &a, &b, &c, &d);
s1 = a * b;
s2 = c * d;
G = gcd(s1, s2);
s1 /= G, s2 /= G;
while (!(s1 & )) s1 >>= , ++cnt[][];
while (s1 % == ) s1 /= , ++cnt[][];
while (!(s2 & )) s2 >>= , ++cnt[][];
while (s2 % == ) s2 /= , ++cnt[][];
if (s1 > || s2 > ) {
puts("-1");
return ;
}
work();
printf("%d\n", ans);
cnt[][] += cnt[][], cnt[][] += cnt[][];
if (cnt[][] > cnt[][]) cnt[][] -= cnt[][], cnt[][] = ;
else cnt[][] -= cnt[][], cnt[][] = ;
while (cnt[][]--) {
if (a % == ) (a /= ) *= ;
else (b /= ) *= ;
}
while (cnt[][]--) {
if (c % == ) (c /= ) *= ;
else (d /= ) *= ;
}
while (cnt[][]--) {
if (!(a & )) a /= ;
else b /= ;
}
while (cnt[][]--) {
if (!(c & )) c /= ;
else d /= ;
}
printf("%I64d %I64d\n%I64d %I64d\n", a, b, c, d);
return ;
}
E. Restoring Increasing Sequence
字符串处理一下，然后贪心当前最小即可，然后我的bin数组少了个0，WA到死啊！！！
我的Div.2 Rank 10-快还我。。。呜呜呜
#include <cstdio>
#include <cstring> using namespace std;
const int bin[] = {, , , , , , , , };
const int N = ; int n, len, len_last;
char st[];
int ans[N]; int work(int p) {
int res = , i, j;
if (len_last > len) return ;
if (len_last < len) {
for (i = ; i <= len; ++i)
if (st[i] == '?')
if (i == ) res = ; else res *= ;
else (res *= ) += st[i] - '';
return res;
}
for (i = ; i <= len; ++i)
if (st[i] == '?')
(res *= ) += ;
else (res *= ) += st[i] - '';
if (res <= ans[p - ]) return ;
for (i = ; i <= len; ++i)
if (st[i] == '?')
for (j = ; j <= ; ++j)
if (res - bin[len - i] <= ans[p - ]) break;
else res -= bin[len - i];
return res; } int main() {
int i;
scanf("%d\n", &n);
ans[] = ;
len = ;
for (i = ; i <= n; ++i) {
scanf("%s\n", st + );
len_last = len, len = strlen(st + );
if (!(ans[i] = work(i))) {
puts("NO");
return ;
}
}
puts("YES");
for (i = ; i <= n; ++i)
printf("%d\n", ans[i]);
return ;
}
F. Treeland Tour
第一反应是树上DP，每个点一个平衡树维护。。。
后来发现怎么可能，应该是点分治 + 归并数组。。。
但是真的能写的出来？不明= =（话说至今No Tags，什么东西！）
反正Div.2里只有一个人A了F，但是Div.1里A掉的貌似很多啊？以后再说吧
于是蒟蒻喜闻乐见的Div.2 Rank 44，被各位神犇D飞啦~Orz跪
话说，蒟蒻的Rating曲线越来越了难看了233