# # AtCoder Beginner Contest 179 题解

## # Problem A - Plural Form (opens new window)

s = input()
print(s + ('s' if s[-1] != 's' else 'es'))

1
2

## # Problem B - Go to Jail (opens new window)

n = int(input())
cnt = 0
ok = False
for _ in range(n):
x, y = map(int, input().split())
if x == y:
cnt += 1
if cnt >= 3:
ok = True
else:
cnt = 0
print('Yes' if ok else 'No')

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

## # Problem C - A x B + C (opens new window)

$n=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k}$

$\prod_{i=1}^k(a_i+1)$

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
int main() {
int n;
cin >> n;
vector<int> primes = {2, 3, 5, 7, 11, 13};
for (int i = 17; i <= n - 1; i += 2) {
bool is_prime = true;
for (int j = 0; primes[j] * primes[j] <= i; ++j) {
if (i % primes[j] == 0) {
is_prime = false;
break;
}
}
if (is_prime)
primes.emplace_back(i);
}
int ans = 0;
for (int i = 1; i < n; ++i) {
int k = i;
int fac = 1;
for (int j = 0; primes[j] * primes[j] <= k; ++j) {
if (k % primes[j] == 0) {
int cnt = 0;
while (k % primes[j] == 0)
cnt++, k /= primes[j];
fac *= (cnt + 1);
}
}
if (k != 1)
fac *= 2;
ans += fac;
}
cout << ans;
}
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

## # Problem D - Leaping Tak (opens new window)

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
const ll MOD = 998244353;

int main() {
int n, k;
cin >> n >> k;
vector<pair<int, int>> v(k);
for (int i = 0; i < k; ++i)
cin >> v[i].first >> v[i].second;
vector<ll> sum(n + 1);
sum[1] = 1;
for (int i = 2; i <= n; ++i) {
ll curr = 0;
for (int j = 0; j < k; ++j) {
if (v[j].first >= i)
continue;
int l = max(1, i - v[j].second);
int r = i - v[j].first;
curr += sum[r] - sum[l - 1];
}
curr %= MOD;
if (curr < 0)
curr += MOD;
sum[i] = (sum[i - 1] + curr) % MOD;
}
ll ans = sum[n] - sum[n - 1];
if (ans < 0)
ans += MOD;
cout << ans;
}

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

## # Problem E - Sequence Sum (opens new window)

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

using namespace std;
typedef long long ll;
int main() {
ll n, x, m;
cin >> n >> x >> m;
map<ll, int> mp;
int idx = 0;
vector<ll> path;
do {
mp[x] = idx++;
path.emplace_back(x);
x = x * x % m;
} while (!mp.count(x));
int start = mp[x];
int len = idx - start;
ll sum = 0;
for (int i = start; i < idx; ++i)
sum += path[i];
ll ans = 0;
if (n < start) {
for (int i = 0; i < n; ++i)
ans += path[i];
} else {
for (int i = 0; i < start; ++i)
ans += path[i];
ll loop = (n - start) / len;
ans += loop * sum;
ll rem = (n - start) % len;
for (int i = 0; i < rem; ++i)
ans += path[start + i];
}
cout << ans;
}
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

## # Problem F - Simplified Reversi (opens new window)

#include <iostream>
#include <vector>
#define MAXN 200005
#define lson (idx << 1)
#define rson (idx << 1 | 1)

using namespace std;
typedef long long ll;

struct Node {
int l, r, hi, lazy = 0;
};

struct SegTree {
Node s[MAXN << 2];
void calc(int idx) { s[idx].hi = max(s[lson].hi, s[rson].hi); }

void pushdown(int idx) {
if (s[idx].lazy) {
for (int i = lson; i <= rson; ++i) {
if (s[i].hi > s[idx].lazy) {
s[i].hi = s[idx].lazy;
s[i].lazy = s[idx].lazy;
}
}
}
s[idx].lazy = 0;
}

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

void update(int idx, int l, int r, int x) {
if (s[idx].hi <= x)
return;
if (s[idx].l >= l && s[idx].r <= r) {
s[idx].hi = x;
s[idx].lazy = x;
return;
}
pushdown(idx);
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
update(lson, l, r, x);
if (mid + 1 <= r)
update(rson, l, r, x);
calc(idx);
}

int query(int idx, int l, int r) {
if (s[idx].l >= l && s[idx].r <= r)
return s[idx].hi;
pushdown(idx);
int ans = 0;
int mid = (s[idx].l + s[idx].r) >> 1;
if (l <= mid)
ans = max(ans, query(lson, l, r));
if (mid + 1 <= r)
ans = max(ans, query(rson, l, r));
return ans;
}
};

int main() {
int n, q;
cin >> n >> q;
vector<int> col(n + 1, n), row(n + 1, n);
col[n] = 1, row[n] = 1;
SegTree C, R;
C.build(1, 1, n, col);
R.build(1, 1, n, row);
ll ans = (ll)(n - 2) * (n - 2);
for (int i = 0; i < q; ++i) {
int t, x;
cin >> t >> x;
if (t == 1) {
int hi = C.query(1, x, x);
ans -= hi - 2;
R.update(1, 1, hi, x);
C.update(1, x, x, 1);
} else {
int hi = R.query(1, x, x);
ans -= hi - 2;
C.update(1, 1, hi, x);
R.update(1, x, x, 1);
}
}
cout << ans;
}
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