AtCoder Regular Contest 103 题解

AtCoder Regular Contest 103

C - /\/\/\/

题目大意

如果一个$n$项的序列$(n是偶数)$满足奇数项都是$a$,偶数项都是$b$,并且满足$a != b$,那么称为这个数列是一个/\/\/\/。

现在给出一个$n$项的序列${a_i}$,问你至少要改变多少个元素才能使这个序列变成一个/\/\/\/。

题解

分别对于奇数位和偶数位,如果要改变的元素最少,又要让改变之后的元素都相同,贪心法则是改变为原数列出现次数最多的元素。

如果不存在相同的情况,那么最优答案一定是奇数项最多元素与偶数项最多元素组合而成的。

如果奇数项最多元素与偶数项最多元素相同,那么我们不能这样组合。

此时最优答案就是奇数项最多和偶数项次多组合而成,或者奇数项次多和偶数项最多组合而成。

很显然先需要进行两次次桶排序,然后扫一遍两个桶。分别找出奇数项的最大值和次大值,偶数项的最大值和次大值,再根据上述过程组合出答案即可。

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
#include<bits/stdc++.h>
using namespace std;
inline int read () {
int num = 0;
char c = ' ';
bool flag = true;
for (;c > '9' || c < '0';c = getchar())
if (c == '-')
flag = false;
for (;c >= '0' && c <= '9';num = (num << 1) + (num << 3) + c - 48, c = getchar());
return flag ? num : -num;
}
namespace INIT {
const int maxn = 200200;
int n, a[maxn];
void init () {
n = read ();
for (int i = 1;i <= n;i ++)
a[i] = read ();
}
} using namespace INIT;
struct node {
int num, val;
} c1[maxn], c2[maxn];
//这里我为了节省空间
//没有直接用下标作为桶的标志
//而是用了一个映射函数来找桶
int which[maxn],cnt1 = 0, cnt2 = 0;
void work1 () {
memset (which, 0, sizeof which);
for (int i = 1;i <= n;i += 2) {
if (which[a[i]] == 0) {
which[a[i]] = ++ cnt1;
c1[cnt1].num = a[i];
}
c1[which[a[i]]].val ++;
}
}
void work2 () {
memset (which, 0, sizeof which);
for (int i = 2;i <= n;i += 2) {
if (which[a[i]] == 0) {
which[a[i]] = ++ cnt2;
c2[cnt2].num = a[i];
}
c2[which[a[i]]].val ++;
}
}//两次桶排序
node a1,a2,b1,b2;
//奇数项最大次大、偶数项最大次大。
void find () {
for (int i = 1;i <= cnt1;i ++) {
if (c1[i].val > a1.val) {
a2 = a1;//更新次大值
a1 = c1[i];//更新最大值
}
else if (c1[i].val > a2.val)
a2 = c1[i];//更新次大值
}
for (int i = 1;i <= cnt2;i ++) {
if (c2[i].val > b1.val) {
b2 = b1;
b1 = c2[i];
}
else if (c2[i].val > b2.val)
b2 = c2[i];
}
}
void work () {
int ans = 0x7fffffff;
if (a1.num != b1.num)
ans = min (ans,n - a1.val - b1.val);
if (a1.num != b2.num)
ans = min (ans,n - a1.val - b2.val);
if (a2.num != b1.num)
ans = min (ans,n - a2.val - b1.val);
printf ("%d\n", ans);
}
int main () {
init ();
work1 (); work2 ();
find (); work ();
return 0;
}

D - Robot Arms

题目大意

给出$N$个坐标。让你设计一个长度为$M$的序列($M$可以自定,本题$SPJ$)${d_i}$。你从坐标系原点出发,依次使用这个$M$个数;对于每一个数$d_i$,你可以从你当前的位置向四个不同的方向移动(移动规则下面会给出)。依次使用之后,需要恰好能到达这$N$个坐标。移动规则如下:

如果你在$(x,y)$这个位置,那么:

  • 可以向$(x - d_i,y)$ 移动,记作$’L’$;
  • 可以向$(x + d_i,y)$ 移动,记作$’R’$;
  • 可以向$(x,y - d_i)$ 移动,记作$’D’$;
  • 可以向$(x,y + d_i)$ 移动,记作$’U’$ 。

要求你第一行输出$M$,第二行输出序列${d_i}$,第三行开始的$N$行输出从原点出发经过$M$次的移动恰好能到达这些坐标的移动方式。

题解

这道题目是本次比赛最毒的构造题。

首先,总体的思想是二进制拆分;也就是说,我们生成的$m​$个数,都是$2​$的幂。我们可以先打表一下,看看对于${1,2,4}​$,能够到达的点和不能到达的点有哪些区别,我们可以发现,能够到达的点的坐标若是$(x,y)​$,那么$x +y​$一定是奇数。我们这里定义一个坐标点的奇偶性为它横纵坐标之和的奇偶性。

如果要到达偶数点,那么一定先要把偶数点的其中一个坐标$-1$,那么偶数点就化为了奇数点。也就是说,偶数点和奇数点的差别就在于多一个$1$。

所以我们构造的序列中,最大的$2$的幂只要大于数据范围$1e9$即可;我们可以构造$2^0,2^1,2^2……2^{31}(对于奇数点)或者2^0,2^0,2^1,2^2……2^{31}(对于偶数点)$。

判定无解的方式就是,看一看这些坐标的奇偶性是否相同。

对于每一个点,都选择横纵坐标中绝对值较大者,正数减,负数加,我们可以发现,用完这$31$或者$32$个数之后,坐标一定是$(0,0)$。

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
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>
using namespace std;
inline int read () {
int num = 0;
char c = ' ';
bool flag = true;
for (;c > '9' || c < '0';c = getchar())
if (c == '-')
flag = false;
for (;c >= '0' && c <= '9';num = (num << 1) + (num << 3) + c - 48, c = getchar());
return flag ? num : -num;
}
namespace INIT {
const int maxn = 1020;
struct ques {
long long x, y;
} q[maxn];
int n;
void init () {
n = read ();
for (int i = 1;i <= n;i ++)
q[i].x = read(), q[i].y = read ();
}
} using namespace INIT;

namespace CHECK {
bool odd = 0;
void check () {
for (int i = 1;i < n;i ++)
if (((q[i].x + q[i].y) & 1) != ((q[i + 1].x + q[i + 1].y) & 1)) {
printf ("%d\n", -1);
exit (0);
}
odd = (q[1].x + q[1].y) & 1;
}//判定奇偶性是否相同
} using namespace CHECK;

namespace get_Di {
long long d[50]; int m = 0;
void work1 () {
d[++ m] = 1;
while (d[m] <= 1e9)
d[++ m] = 1ll * d[m - 1] << 1;
if (!odd) d[++ m] = 1;
printf ("%d\n", m);
for (int i = 1;i <= m;i ++)
printf ("%lld ",d[i]);
printf ("\n");
}//生成序列
} using namespace get_Di;

namespace get_direct {
vector <char> ans;
void work2 () {
for (int i = 1;i <= n; i ++) {
ans.clear ();
long long x = q[i].x, y = q[i].y;
for (int j = m;j >= 1;j --)
if (abs (x) > abs (y)) {
//绝对值较大的先操作
if (x < 0) {//负数+
ans.push_back ('L');
x += d[j];
}
else {//正数-
ans.push_back ('R');
x -= d[j];
}
}
else {
if (y < 0) {
ans.push_back ('D');
y += d[j];
}
else {
ans.push_back ('U');
y -= d[j];
}
}
//倒序输出。
for (int i = ans.size () - 1;i >= 0;i --)
printf ("%c",ans[i]);
printf ("\n");
}
}
} using namespace get_direct;
int main () {
init ();
check ();
work1 ();
work2 ();
return 0;
}

E - Tr/ee

题目大意

一道构造题。给你一个$01$串$s$。长度为$n(1<n\leq 100000)$

我们先来定义一棵树的子树。如果在一棵树上删除一条边,那么它将被分成两棵子树。

现在要求你根据这个01串构造一棵树。对于这个01串,如果$s[i]= 1$,那么你的树上必须含有一个大小为$i$的子树;如果$s[i]= 0$,那么你的树上必须不含有一个大小为$i$的子树。

现在要求你输出你构造的树上的所有边。

题解

先考虑有解的情况。我们知道一棵树一定有一个大小为$1$的子树;而且一棵树一定不含有一个大小为$n$的子树。所以$s[1]$ 必须为$1$,而且$s[n]$必须为0。如果一棵树有一个大小为$x$的子树,那么它一定对称的拥有一个大小为$n - x$的子树。所以$s$在$[1, n - 1]$上一定是对称的。

我们再考虑菊花图,它是一个只含有大小为$1$的子树的树。那么我们可以根据这个性质,考虑到让你构造的树,一定是一个个菊花图构成的树,每个菊花图的大小就是$s[i]=1$的时候的$i$。

这样就简单很多了,纯模拟。

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
#include<bits/stdc++.h>
using namespace std;
inline int read () {
int num = 0;
char c = ' ';
bool flag = true;
for (;c > '9' || c < '0';c = getchar())
if (c == '-')
flag = false;
for (;c >= '0' && c <= '9';num = (num << 1) + (num << 3) + c - 48, c = getchar());
return flag ? num : -num;
}
const int maxn = 100200;
int n;
char s[maxn];
void init () {
scanf ("%s",s + 1);
n = strlen (s + 1);
}
void work () {
int bj = 1;
for (int i = 1;i < n;i ++) {
printf ("%d %d\n",bj,i + 1);
if (s[i] == '1')
bj = i + 1;
}
}//构造菊花图
bool check () {
if (s[1] != '1' || s[n] != '0') return false;
//判定可行性
int l = 1, r = n - 1;
while (l < r)
if (s[l ++] != s[r --]) return false
//是否对称
return true;
}
int main () {
init ();
if (check ()) work ();
else printf ("-1\n");
return 0;
}

F - Distance Sums

题目大意

给你一个长度为$N$的数组${d[i]}$ ,要求你构造一棵树,满足,编号为$i$的点到其他的点的距离和是$d[i]$。输出所有的边。

题解

对于一条边$ (x,y)$如果去掉之后会形成两个连通块,记这两个连通块的大小分别为$n_x ,n_y$,显然有$d[x] + n _ x = d[y] + n _ y$。

证明:从$x$到$y$,到$n_x$里面的点全部距离$+1$,到$n_y$里的点全部距离$-1$,得证。

所以可以通过一个点来找跟他相连的另外一个点。

另外,我们可以证明,叶子结点的$d[x]$永远是最大的(因为此时$n_y$最小)。

所以可以先排序然后自下而上找父亲。

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
86
#include<bits/stdc++.h>
using namespace std;
inline long long read () {
long long num = 0;
char c = ' ';
bool flag = true;
for (;c > '9' || c < '0';c = getchar())
if (c == '-')
flag = false;
for (;c >= '0' && c <= '9';num = (num << 1) + (num << 3) + c - 48, c = getchar());
return flag ? num : -num;
}
namespace graph {
const int maxn = 100020;
struct node {
int y, next;
} a[maxn << 1];
int head[maxn], top = 0;
void insert (int x, int y) {
a[top].y = y;
a[top].next = head[x];
head[x] = top ++;
}
} using namespace graph;

namespace INIT {
map <long long, int> m;
int n; long long d[maxn];
void init () {
n = read ();
for (int i = 1;i <= n;i ++) {
d[i] = read ();
m[d[i]] = i;
}
sort (d + 1,d + 1 + n);
}
} using namespace INIT;

namespace WORK {
int size[maxn];
void work () {
memset (head, -1, sizeof head);
for (int i = 1;i <= n;i ++)
size[i] = 1;
for (int i = n;i > 1;i --) {
int x = m[d[i]];
long long t = n - 2 * size[x];
t = d[i] - t;
if (m.count(t) == 0) {
printf ("-1\n");
exit (0);
}
int y = m[t];
insert (y, x);
insert (x, y);
size[y] += size[x];
}
}
} using namespace WORK;

namespace CHECK {
int dis[maxn];
void dfs (int x, int fa) {
for (int i = head[x];i + 1;i = a[i].next) {
int y = a[i].y;
if (y == fa) continue;
dis[y] = dis[x] + 1;
dfs (y, x);
}
}
void check () {
dfs (m[d[1]], -1);
long long s = 0;
for (int i = 1;i <= n;i ++)
s += dis[i];
if (s != d[1]) printf ("-1\n");
else for (int i = 0;i < top;i += 2)
printf ("%d %d\n",a[i].y, a[i ^ 1].y);
}
} using namespace CHECK;
int main () {
init ();
work ();
check ();
return 0;
}
文章目录
  1. 1. AtCoder Regular Contest 103
    1. 1.1. C - /\/\/\/
      1. 1.1.1. 题目大意
      2. 1.1.2. 题解
      3. 1.1.3. code
    2. 1.2. D - Robot Arms
      1. 1.2.1. 题目大意
      2. 1.2.2. 题解
      3. 1.2.3. code
    3. 1.3. E - Tr/ee
      1. 1.3.1. 题目大意
      2. 1.3.2. 题解
      3. 1.3.3. code
    4. 1.4. F - Distance Sums
      1. 1.4.1. 题目大意
      2. 1.4.2. 题解
      3. 1.4.3. code