|
Dashboard - Codeforces Round #545 (Div. 2) - Codeforces
C
o
d
e
f
o
r
c
e
s
?
R
o
u
n
d
?
#
545
?
(
D
i
v
.
?
2
)
\rm Codeforces~Round~\#545~(Div.~2)
Codeforces?Round?#545?(Div.?2)
A Sushi for Two（黄）
sol
从左往右扫描这个 01 串，并记录当前段的长度和前一段的长度，假如出现了一个新段的话（前提是下一个字符和当前字符不同），我们就计算出当前的答案并更新最优解（显然，当前的答案是当前段长度和前一段长度最小值的两倍）。
时间复杂度
O
(
n
)
\mathcal O(n)
O(n)。
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int n, ans, a, lst;
int cnt1, cnt2;
signed main()
{
n = read();
lst = read();
lst == 1 ? cnt1++ : cnt2++;
for(int i = 2; i <= n; ++i)
{
a = read();
if(a != lst)
{
ans = max(ans, min(cnt1, cnt2));
lst == 1 ? cnt2 = 1 : cnt1 = 1;
lst = a;
}
else
lst == 1 ? cnt1++ : cnt2++;
}
ans = max(ans, min(cnt1, cnt2));
printf("%d", ans << 1);
return 0;
}
B Circus（蓝）
sol
设每个人
i
i
i 的两个数分别为
a
i
,
b
i
a_i,b_i
ai?,bi?。
考虑用两个数的和来表示，那么有
3
3
3 种情况即和分别为
0
,
1
,
2
0,1,2
0,1,2 。
设你选的位于第一部分的
n
2
\frac{n}{2}
2n? 个人中这些情况的个数分别为
c
0
,
c
1
,
c
2
c0,c1,c2
c0,c1,c2。
设
s
u
m
sum
sum 表示所有人
b
i
b_i
bi? 中为
1
1
1 的数的个数。
那么有
c
0
×
0
+
c
1
×
1
+
c
2
×
2
=
s
u
m
c0\times 0+c1\times 1+c2 \times 2=sum
c0×0+c1×1+c2×2=sum 且
c
0
+
c
1
+
c
2
=
n
2
c0+c1+c2=\frac{n}{2}
c0+c1+c2=2n?。
即
c
1
+
c
2
×
2
=
s
u
m
c1+c2\times 2=sum
c1+c2×2=sum 且
c
0
+
c
1
+
c
2
=
n
2
c0+c1+c2=\frac{n}{2}
c0+c1+c2=2n?。
O
(
n
)
\mathcal O(n)
O(n) 枚举
c
2
c2
c2 的取值，求出
c
0
c0
c0 和
c
1
c1
c1，然后判断即可。
时间复杂度
O
(
n
)
\mathcal O(n)
O(n)。
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int n, sum;
char a[5007], b[5007];
vector<int> g0, g1, g2;
signed main()
{
n = read();
scanf("%s %s", a + 1, b + 1);
for(int i = 1; i <= n; ++i)
{
sum += b[i] - '0';
if(a[i] == '0' && b[i] == '0')
g0.push_back(i);
else if((a[i] == '0' && b[i] == '1') || (a[i] == '1' && b[i] == '0'))
g1.push_back(i);
else
g2.push_back(i);
}
int c0, c1;
for(int c2 = 0, len = g2.size(); c2 <= len; ++c2)
{
c1 = sum - c2 * 2, c0 = n / 2 - c2 - c1;
if(c0 >= 0 && c0 <= g0.size() && c1 >= 0 && c1 <= g1.size())
{
for(int j = 0; j < c0; ++j)
printf("%d ", g0[j]);
for(int j = 0; j < c1; ++j)
printf("%d ", g1[j]);
for(int j = 0; j < c2; ++j)
printf("%d ", g2[j]);
return 0;
}
}
printf("%d", -1);
return 0;
}
C Skyscrapers（蓝）
sol
对于每一行和每一列先分别离散，记录每个位置在离散后的值，然后合并之后取较大的那个，然后剩下的部分顺次编号就行了。
时间复杂度
O
(
n
2
log
?
n
)
\mathcal O(n^2\log n)
O(n2logn)。
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
const int _ = 1007;
int n, m;
int l[_], r[_];
int a[_][_], b[_][_], c[_][_];
int S[_], top;
inline int max2(int a, int b, int c, int d)
{
return max(max(a, b), max(c, d));
}
signed main()
{
n = read(), m = read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
a[i][j] = read();
for(int i = 1; i <= n; ++i)
{
top= 0 ;
for(int j = 1; j <= m; ++j)
S[++top] = a[i][j];
sort(S + 1, S + top + 1);
top = unique(S + 1, S + top + 1) - S - 1;
for(int j = 1; j <= m; ++j)
b[i][j] = lower_bound(S + 1, S + top + 1, a[i][j]) - S;
r[i] = top;
}
for(int i = 1; i <= m; ++i)
{
top = 0;
for(int j = 1; j <= n; ++j)
S[++top] = a[j][i];
sort(S + 1, S + top + 1);
top = unique(S + 1, S + top + 1) - S - 1;
for(int j = 1; j <= n; ++j)
c[j][i] = lower_bound(S + 1, S + top + 1, a[j][i]) - S;
l[i] = top;
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
printf("%d ", max2(r[i], l[j], b[i][j] + l[j] - c[i][j], c[i][j] + r[i] - b[i][j]));
printf("\n");
}
return 0;
}
D Camp Schedule（绿）
sol
要想出现的次数尽可能多，那么就要重复的利用，哪一部分是可以重复利用的呢？
就是前缀和后缀相同的部分，容易想到了 KMP 中 的
n
e
x
t
next
next 就是求这个东西的。
那么我们对于
T
T
T 跑 KMP 然后先建一次
T
T
T，然后每次跳到
n
e
x
t
next
next 接着往后放就行了。
当然，这里只需用到
n
e
x
t
∣
T
∣
next_{|T|}
next∣T∣?，也可以用哈希。
时间复杂度为
O
(
∣
S
∣
)
\mathcal O(|S|)
O(∣S∣)。
#include <bits/stdc++.h>
using namespace std;
char s[500005], t[500005], ans[500005];
int nxt[500005];
signed main()
{
scanf("%s", s + 1), scanf("%s", t + 1);
nxt[1] = 0;
int len = strlen(t + 1);
for (int i = 2, j = 0; i <= len; i++)
{
while (j && t[i] != t[j + 1])
j = nxt[j];
if (t[i] == t[j + 1])
j++;
nxt[i] = j;
}
int cnt1 = 0, cnt0 = 0, lens = strlen(s + 1), lent = strlen(t + 1);
for (int i = 1; i <= lens; i++)
s[i] == '0' ? cnt0++, 0 : cnt1++, 0;
for (int i = 1, j = 1; i <= lens; i++, j++)
{
if (t[j] == '0' && !cnt0)
ans[i] = '1', cnt1--;
else if (t[j] == '1' && !cnt1)
ans[i] = '0', cnt0--;
else
{
ans[i] = t[j];
t[j] == '0' ? cnt0-- : cnt1--;
}
if (j == lent)
j = nxt[j];
}
printf("%s\n", ans + 1);
return 0;
}
E Museums Tour（紫）
sol
考虑到每一天的博物馆开放情况是不同的，那么把每一个博物馆一周的每一天的情况存下来，
(
u
,
x
)
=
u
+
(
x
?
1
)
×
n
(u,x)=u+(x-1)\times n
(u,x)=u+(x?1)×n，即第
u
u
u 个博物馆第
x
x
x 天的编号是
u
+
(
x
?
1
)
n
u+(x-1)n
u+(x?1)n。
然后连边，对于原图上的一条边
(
u
,
v
)
(u,v)
(u,v)，连边
?
x
∈
[
1
,
d
]
,
(
u
,
x
)
→
(
v
,
x
?
m
o
d
?
d
+
1
)
\forall x \in[1,d],(u,x) \to (v,x\bmod d+1)
?x∈[1,d],(u,x)→(v,xmodd+1)。
由于图上有环，考虑 tarjan 缩点，记录每一个 scc 开启的不同博物馆个数。
最后跑一边最长路即可。
时空复杂度为
O
(
n
d
)
\mathcal O(nd)
O(nd)。
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
x = x * 10 + c - '0', c = getchar();
return x * f;
}
inline void write(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
const int _ = 1e5 + 10, N = 5e6 + 250;
int n, m, k;
long long sta[_];
struct edge
{
int to, nxt;
} e[N], e2[N];
int tot, head[N], tot2, head2[N];
inline void add(int u, int v)
{
e[++tot] = {v, head[u]};
head[u] = tot;
}
inline void add2(int u, int v)
{
e2[++tot2] = {v, head2[u]};
head2[u] = tot2;
}
int idx, scc, bel[N], dfn[N], low[N];
int f[N], val[N];
bool vis[N];
stack<int> s, q;
inline void tarjan(int u)
{
dfn[u] = low[u] = ++idx;
s.push(u);
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (!bel[v])
{
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u])
{
++scc;
while (1)
{
int v = s.top();
s.pop();
bel[v] = scc;
int x = (v - 1) % n + 1, day = (v - 1) / n;
if (!vis[x] && (sta[x] >> day & 1))
{
val[scc]++, vis[x] = 1;
q.push(x);
}
if (v == u)
break;
}
while (!q.empty())
vis[q.top()] = 0, q.pop();
}
}
inline int P(int i, int j)
{
return j * n + i;
}
int dfs(int u)
{
if (vis[u])
return f[u];
vis[u] = 1;
for (int i = head2[u]; i; i = e2[i].nxt)
{
int v = e2[i].to;
f[u] = max(f[u], dfs(v));
}
return f[u] += val[u];
}
int main()
{
n = read(), m = read(), k = read();
int u, v;
for (int i = 1; i <= m; ++i)
{
u = read(), v = read();
for (int j = 0; j < k; ++j)
add(P(u, j), P(v, (j + 1) % k));
}
char ch;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < k; ++j)
{
while (!isdigit(ch = getchar()))
;
sta[i] |= 1ll * (ch - '0') << j;
}
tarjan(1);
for (int i = 1; i <= n * k; ++i)
{
if (!dfn[i])
continue;
u = bel[i];
for (int j = head[i]; j; j = e[j].nxt)
{
v = e[j].to;
if (!dfn[v])
continue;
v = bel[v];
if (u != v)
add2(u, v);
}
}
printf("%d", dfs(bel[1]));
return 0;
}
F Cooperative Game（紫）
sol
一道好题，用到了一点 pollard-rho 的思想。
考虑 Floyd 判圈法。
两个人同时在一个环形跑道上起跑，一个人是另外一个人的两倍速度，那么这个人绝对会追上另外一个人。追上时，意味着其中一个人已经跑了一圈了。
这样就可以知道环的长度了。
由上面的方法，我们可以知道，慢人一定还没走完一圈，就被追上了。
以下注：
t
t
t 为链长，
c
c
c 为环长。
所以先把
0
,
1
0,1
0,1 拿出来。
设
0
0
0 为慢点，
1
1
1 为快点。
假设现在
0
,
1
0,1
0,1 相遇。
那么设
0
0
0 走了
t
+
k
t+k
t+k 步，则
1
1
1 走了
2
t
+
2
k
2t+2k
2t+2k 步（
0
≤
k
<
c
0\leq k < c
0≤k<c）。
忽略在链上的
t
t
t 步，则
0
0
0 在环上走了
k
k
k 步，
1
1
1 在环上走了
t
+
2
k
t+2k
t+2k 步。
于是有
t
≡
t
+
2
k
(
m
o
d
c
)
t \equiv t+2k \pmod c
t≡t+2k(modc)，即
t
+
k
≡
0
(
m
o
d
c
)
t+k\equiv 0 \pmod c
t+k≡0(modc)，即
t
≡
c
?
k
(
m
o
d
c
)
t \equiv c-k \pmod c
t≡c?k(modc)。
当前这两个人所处的位置再走
c
?
k
c-k
c?k 步恰好是目标位置，而由于
t
t
t 和
c
?
k
c-k
c?k 模
c
c
c 同余，所以再走
t
t
t 步就能到目标位置。
而现在
2
～
9
2 \sim 9
2～9 走
t
t
t 步后也能到目标位置。
所以我们让所有人继续走，那么一定会相遇。
一共花费步数为
3
t
+
2
k
<
3
t
+
3
c
3t+2k<3t+3c
3t+2k<3t+3c。
#include <bits/stdc++.h>
using namespace std;
char ch[20];
int read()
{
fflush(stdout);
int x;
scanf("%d", &x);
for (int i = 1; i <= x; ++i)
scanf("%s", ch);
return x;
}
signed main()
{
while (1)
{
printf("next 0\n");
read();
printf("next 0 1\n");
int tot = read();
if (tot == 2)
break;
}
while (1)
{
printf("next 0 1 2 3 4 5 6 7 8 9\n");
fflush(stdout);
if (read() == 1)
break;
}
printf("done");
fflush(stdout);
}
|