# # AtCoder Beginner Contest 177 题解

## # Problem A - Don't be late (opens new window)

### # 题目描述

$T$分钟，每分钟能跑$S$米，能不能到一个距离为$D$米的地方？

### # 题解

d, t, s = map(int, input().split(' '))
print('Yes' if s * t >= d else 'No')

1
2

## # Problem B - Substring (opens new window)

### # 题解

s = input()
t = input()
ls = len(s)
lt = len(t)
ans = lt
for i in range(ls - lt + 1):
diff = 0
for j in range(lt):
if s[i + j] != t[j]:
diff += 1
ans = min(ans, diff)
print(ans)

1
2
3
4
5
6
7
8
9
10
11
12

## # Problem C - Sum of product of pairs (opens new window)

### # 题目描述

$\prod_{i

### # 题解

$\prod_{i，注意取模意义下除以$2$要变为乘$2$的逆元。

mod = int(1e9 + 7)

def fexp(x, y):
ret = 1
while y > 0:
if y % 2 == 1:
ret = ret * x % mod
x = x * x % mod
y = y // 2
return ret

input()
a = list(map(int, input().split(' ')))
s = sum(a)
ans = 0
for i in a:
ans = (ans + i * (s - i)) % mod
print(ans * fexp(2, mod - 2) % mod)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

## # Problem D - Friends (opens new window)

### # 题目描述

$N$$N\leq2\times10^5$）个人和$M$$M\leq2\times10^5$）对朋友关系，朋友关系可以传递，求要让每个分组中任意两人都不是朋友，最少要分多少组？

### # 题解

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class UnionFind {
vector<int> parent, size;

public:
UnionFind(int n) {
parent = vector<int>(n);
size = vector<int>(n, 1);
for (int i = 0; i < n; ++i)
parent[i] = i;
}

int find(int idx) {
if (parent[idx] == idx)
return idx;
return parent[idx] = find(parent[idx]);
}

void connect(int a, int b) {
int fa = find(a), fb = find(b);
if (fa != fb) {
if (size[fa] > size[fb]) {
parent[fb] = fa;
size[fa] += size[fb];
} else {
parent[fa] = fb;
size[fb] += size[fa];
}
}
}

int solve() { return *max_element(size.begin(), size.end()); }
};

class Solution {
public:
void solve() {
int n, m;
UnionFind uf(n);
for (int i = 0; i < m; ++i) {
int u, v;
u--, v--;
uf.connect(u, v);
}
printf("%d", uf.solve());
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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

## # Problem E - Coprime (opens new window)

### # 题目描述

$N$$N\leq10^6$）个数，这些数都不超过$10^6$。如果这些数两两互质，输出pairwise coprime；如果这些数互质，输出setwise coprime，否则输出not coprime

### # 题解

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
vector<int> primes = {2, 3, 5, 7, 11, 13};
for (int i = 17; i < 1000; i += 2) {
bool ok = true;
for (int j = 0; primes[j] * primes[j] <= i; ++j) {
if (i % primes[j] == 0) {
ok = false;
break;
}
}
if (ok)
primes.emplace_back(i);
}
map<int, int> cnt;
for (int i : a) {
int t = i;
for (int j = 0; primes[j] * primes[j] <= t; ++j) {
if (t % primes[j] == 0)
cnt[primes[j]]++;
while (t % primes[j] == 0)
t /= primes[j];
}
if (t != 1)
cnt[t]++;
}
int hi = 0;
for (auto p : cnt)
hi = max(hi, p.second);
if (hi <= 1) {
printf("pairwise coprime");
return;
}
printf(hi < n ? "setwise coprime" : "not coprime");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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

## # Problem F - I hate Shortest Path Problem (opens new window)

### # 题解

• $[1,L-1]$$[R+1,W]$整段加一
• $[L,R]$区间更新为$f(L-1)+i-L+1$（因为这个区间必须从$L-1$这个位置走过来）

#include <cstdio>
#include <iostream>
#include <vector>

#define lson (idx << 1)
#define rson (idx << 1 | 1)
#define INF 1000000000000LL
#define MAXN 200010

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

// lo is the current minimum of the segment.
// lh is the current value of the left endpoint.
// lazy is the lazy tag for addition.
// flag is the lazy tag for assignment.
struct Node {
int l, r;
ll lo, lh, lazy = 0;
bool flag = false;
} s[MAXN << 2];
int h, w;

// Push up
void calc(int idx) {
s[idx].lo = min(s[lson].lo, s[rson].lo);
s[idx].lh = s[lson].lh;
}

void build(int idx, int l, int r) {
s[idx].l = l, s[idx].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
}

// Lazy propagation
void pushdown(int idx) {
if (s[idx].flag) {
ll L = s[idx].lh;
int l = s[idx].l;
for (int i = lson; i <= rson; ++i) {
s[i].lo = s[i].lh = L + s[i].l - l;
s[i].flag = true;
s[i].lazy = 0;
}
} else if (s[idx].lazy) {
for (int i = lson; i <= rson; ++i) {
s[i].lh += s[idx].lazy;
s[i].lo += s[idx].lazy;
s[i].lazy += s[idx].lazy;
}
}
s[idx].flag = false;
s[idx].lazy = 0;
}

// Assign segment [l, r] according to f[l-1] = L
void update(int idx, int l, int r, ll L) {
if (s[idx].l >= l && s[idx].r <= r) {
s[idx].lo = s[idx].lh = L + s[idx].l - l + 1;
s[idx].flag = true;
s[idx].lazy = 0;
return;
}
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
update(lson, l, r, L);
if (mid + 1 <= r)
update(rson, l, r, L);
calc(idx);
}

void add(int idx, int l, int r) {
if (s[idx].l >= l && s[idx].r <= r) {
s[idx].lh++;
s[idx].lo++;
s[idx].lazy++;
return;
}
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
if (mid + 1 <= r)
calc(idx);
}

// Range minimum query
ll query(int idx, int l, int r) {
if (r < 1 || l > w)
return INF;
if (s[idx].l >= l && s[idx].r <= r)
return s[idx].lo;
pushdown(idx);
ll ans = INF;
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
ans = min(ans, query(lson, l, r));
if (mid + 1 <= r)
ans = min(ans, query(rson, l, r));
return ans;
}

class Solution {
public:
void solve() {
vector<int> l(h), r(h);
for (int i = 0; i < h; ++i)
vector<ll> ans(h, INF);
build(1, 1, w);
for (int i = 0; i < h; ++i) {
if (l[i] > 1)
if (r[i] < w)
ll L = query(1, l[i] - 1, l[i] - 1);
update(1, l[i], r[i], L);
ans[i] = min(ans[i], query(1, 1, w));
if (ans[i] == INF)
break;
}
for (ll i : ans)
cout << (i == INF ? -1 : i) << endl;
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

#include <cstdio>
#include <iostream>
#include <vector>

#define lson (idx << 1)
#define rson (idx << 1 | 1)
#define INF 10000000000LL
#define MAXN 200010

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

// lo is the minimum of the segment.
// lh is the current value of the left endpoint.
// rh is the current value of the right endpoint.
// lazy is the lazy tag for addition.
// flag is the lazy tag for assignment.
struct Node {
int l, r;
ll lo, lh, rh, lazy = 0;
bool flag = false;
} s[MAXN << 2];
int h, w;

void calc(int idx) {
s[idx].lo = min(s[lson].lo, s[rson].lo);
s[idx].lh = s[lson].lh;
s[idx].rh = s[rson].rh;
}

void build(int idx, int l, int r) {
s[idx].l = l, s[idx].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
}

void pushdown(int idx) {
if (s[idx].flag) {
ll L = s[idx].lh, R = s[idx].rh;
int l = s[idx].l, r = s[idx].r;
for (int i = lson; i <= rson; ++i) {
s[i].lh = min(L + s[i].l - l, R + r - s[i].l);
s[i].rh = min(L + s[i].r - l, R + r - s[i].r);
s[i].lo = min(s[i].lh, s[i].rh);
s[i].flag = true;
s[i].lazy = 0;
}
} else if (s[idx].lazy) {
for (int i = lson; i <= rson; ++i) {
s[i].lh += s[idx].lazy;
s[i].rh += s[idx].lazy;
s[i].lo += s[idx].lazy;
s[i].lazy += s[idx].lazy;
}
}
s[idx].flag = false;
s[idx].lazy = 0;
}

void update(int idx, int l, int r, ll L, ll R) {
if (s[idx].l >= l && s[idx].r <= r) {
s[idx].lh = min(L + s[idx].l - l + 1, R + r - s[idx].l + 1);
s[idx].rh = min(L + s[idx].r - l + 1, R + r - s[idx].r + 1);
s[idx].lo = min(s[idx].lh, s[idx].rh);
s[idx].flag = true;
s[idx].lazy = 0;
return;
}
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
update(lson, l, r, L, R);
if (mid + 1 <= r)
update(rson, l, r, L, R);
calc(idx);
}

void add(int idx, int l, int r) {
if (s[idx].l >= l && s[idx].r <= r) {
s[idx].lh++;
s[idx].rh++;
s[idx].lo++;
s[idx].lazy++;
return;
}
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
if (mid + 1 <= r)
calc(idx);
}

ll query(int idx, int l, int r) {
if (r < 1 || l > w)
return INF;
if (s[idx].l >= l && s[idx].r <= r)
return s[idx].lo;
pushdown(idx);
ll ans = INF;
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
ans = min(ans, query(lson, l, r));
if (mid + 1 <= r)
ans = min(ans, query(rson, l, r));
return ans;
}

class Solution {
public:
void solve() {
vector<int> l(h), r(h);
for (int i = 0; i < h; ++i)
vector<ll> ans(h, INF);
build(1, 1, w);
for (int i = 0; i < h; ++i) {
if (l[i] > 1)
if (r[i] < w)
ll L = query(1, l[i] - 1, l[i] - 1);
ll R = query(1, r[i] + 1, r[i] + 1);
update(1, l[i], r[i], L, R);
ans[i] = min(ans[i], query(1, 1, w));
if (ans[i] == INF)
break;
}
for (ll i : ans)
cout << (i == INF ? -1 : i) << endl;
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156