抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

ARC119A - 119 × 2^23 + 1

给定 n 1\le n\le 1\times 10^{18} ),将 n 分解为 a \times 2^b + c 的形式,求 a + b + c 的最小值。

b 0 61 枚举即可。

ARC119B - Electric Board

Description

给定两个 01 串 S T ,每次对 S 的操作可以选取 (l,r) ,满足

  • S_l = 0\land S_{l+ 1} = S_{l + 2} = \cdots = S_{r} = 1
  • S_l = S_{l + 1} = \cdots = S_{r - 1} = 1 \land S_r = 0

然后交换 S_l S_r 。问最少多少次操作之后可以将 S 变成 T

Solution

我们不妨将每次操作看为 0 的移动操作,因为 1 是连续动的,不好考虑。那么就只需要从左往右进行贪心,把 S 的每个 0 依次往右移直到与 T 0 对应。记录下每个 0 的位置然后直接贪心就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <cstring>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

template<typename T> inline void swap(T &a,T &b)
{
T t = a;
return void(a = b, b = t);
}

const int maxn = 5e5 + 5;

int n;
char s[maxn], t[maxn];
int pos1[maxn], pos2[maxn];

int main()
{
scanf("%d", &n);
scanf("%s", s + 1);
scanf("%s", t + 1);
FOR(i, 1, n) if (s[i] == '0') pos1[++pos1[0]] = i;
FOR(i, 1, n) if (t[i] == '0') pos2[++pos2[0]] = i;
int ans = 0;
if (pos1[0] != pos2[0])
return puts("-1"), 0;
for (int i = 1, j = 1; i <= pos2[0]; ++i, ++j)
{
if (j > pos1[0])
return puts("-1"), 0;
++ans;
if (pos1[j] == pos2[i]) --ans;
}
printf("%d\n", ans);
return 0;

}

ARC119C - ARC Wrecker 2

Description

给定长度为 n 的序列 A_i ,对于区间 [l,r] ,每次可选择 [l, r - 1] 间的一个整数 x ,然后将 A_x A_{x + 1} 同时加一或减一。问有多少个 [l,r ] 可以在有限次操作之后变为全 0

Solution

比较妙的思路。

每次操作相当于是给奇数下标的数和偶数下标的数同时加减 1 ,所以为了最后得到全 0 ,一开始选的区间中奇下标和偶下标数的和必须相等。

注意到这条性质之后记录一下前缀和,然后用 map 随便记录以下就可以做了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <cctype>
#include <map>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

const int maxn = 3e5 + 5;

int read()
{
int s = 0, x = 0;
char c = getchar();
while (!isdigit(c))
x |= (c == '-'), c = getchar();
while (isdigit(c))
s = s * 10 + c - '0', c = getchar();
return x ? -s : s;
}

typedef long long ll;

int n;

ll ans, a[maxn], s[maxn];

std::map<ll, ll> m;

int main()
{
n = read();
FOR(i, 1, n) a[i] = read() * ((i & 1) ? -1 : 1);
FOR(i, 1, n) s[i] = a[i] + s[i - 1], ++m[s[i]];
++m[0];
for (std::map<ll, ll>::iterator it = m.begin(); it != m.end(); ++it)
ans += (*it).second * ((*it).second - 1ll) / 2;
printf("%lld\n", ans);
return 0;
}

答案的上界是会爆 int,要开 long long

ARC119D - Grid Repainting 3

Description

给定一 H W 列的方格,每个方格一开始涂了红色或者蓝色。进行如下操作:对于当前的每个红色格子,可以选择它并将其所在的一行或一列全部涂满白色。问最后最多多少个格子可以是白色并构造方案。

Solution

对于这种方格并且操作是对于整行或整列的题,很容易想到构建一张二分图来解决问题。左部的点代表每行,右部的点代表每列,一个红格子代表一条边。

然后我们分析这个涂色方案。涂掉一整行/列相当于废掉这一个点,同时把这个点相关的所有边全部废掉(即为废掉在这行/列上的红格子)。当然废掉这个点的条件是它能引出至少一条边(即必须有至少一个红格子在这行/列上面)。依据这个想法,我们肯定希望一个连通分量内,废掉的点(即涂掉的行/列)越多越好,考虑如何使它最多。

注意到,一个连通分量删到最后一定会剩下一个点(至于为什么可以自己思考一下)。我们尝试构造一下方案:假设我们剩点 u ,那么就可以从 u 构建这个连通分量的 dfs 生成树,然后从叶子节点往上删点,这样一定可以保证是合法而且除了 u ,其他的点会被删干净。

一张图是有很多个连通分量的,而我们需要对每个连通分量进行决策:留下哪个点最优。我们要涂白的格子最多,假设涂了 r c 列,则剩下的蓝格子为 (h - r)(w - c) 个,我们需要将其最小化。不难发现我们可以直接枚举留下来的行点和列点的个数,然后找到最优解就直接决策每个连通分量剩下行还是列(反正哪一行哪一列不重要),这题就做完了。

主要的流程:

  • 染色标记连通分量
  • 决策剩下多少列点和多少行点
  • dfs 记录答案
  • 输出

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstring>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define GO(u) for (int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])

const int maxn = 2500 + 5, maxm = 2 * maxn * maxn + 5;

int h, w;

int head[maxn << 1], to[maxm], nxt[maxm], cnte;

void add(int u, int v)
{
to[++cnte] = v;
nxt[cnte] = head[u];
head[u] = cnte;
return;
}

int bel[maxn << 1], vis[maxn << 1], L[maxn << 1], R[maxn << 1];

void color(int u, int fa, int c)
{
if (bel[u]) return;
bel[u] = c;
u > h ? ++R[c] : ++L[c];
GO(u) if (v != fa) color(v, u, c);
return;
}

int calced[maxn];

char type[maxm];
int X[maxm], Y[maxm], ans;

void dfs(int u, int fa)
{
vis[u] = 1;
GO(u)
{
if (vis[v] || v == fa) continue;
dfs(v, u);
++ans;
type[ans] = v > h ? 'Y' : 'X';
X[ans] = u > v ? v : u;
Y[ans] = u > v ? u - h : v - h;
}
return;
}

int main()
{
scanf("%d %d", &h, &w);
FOR(i, 1, h)
{
char s[maxn];
scanf("%s", s + 1);
FOR(j, 1, w)
{
if (s[j] == 'R')
add(i, j + h), add(j + h, i);
}
}
int cccnt = 0, sumr = 0, sumc = 0;
FOR(i, 1, h)
{
if (bel[i]) continue;
if (!to[head[i]]) continue;
else color(i, 0, ++cccnt), sumr += L[cccnt], sumc += R[cccnt];
}
int mintmp = h * w, resr, resc;
for (int r = 0, c = cccnt; r <= cccnt; ++r, --c)
if ((h - sumr + r) * (w - sumc + c) < mintmp)
resr = r, resc = c, mintmp = (h - sumr + r) * (w - sumc + c);
FOR(i, 1, h + w)
{
if (L[bel[i]] + R[bel[i]] <= 1 || calced[bel[i]]) continue;
if (resr && i <= h) dfs(i, 0), resr--, calced[bel[i]] = 1;
else if (resc && i > h) dfs(i, 0), resc--, calced[bel[i]] = 1;
}
printf("%d\n", ans);
FOR(i, 1, ans) printf("%c %d %d\n", type[i], X[i], Y[i]);
return 0;
}

评论




Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme