ABC174 (2020.8.2) 全场题解
rui_er
2020-08-28 10:00:55
今天突然想到把所有 AK 的比赛都写一个全场题解，就从这场开始吧。
注：本文中给出的代码均为赛时 AC 代码。
**A - Air Conditioner [Link](https://atcoder.jp/contests/abc174/tasks/abc174_a)**
简单来说就是判断温度是否大于 $30$ 度。
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
scanf("%d", &n);
if(n >= 30) {
puts("Yes");
}
else {
puts("No");
}
return 0;
}
```
**B - Distance [Link](https://atcoder.jp/contests/abc174/tasks/abc174_b)**
判断二维平面内 $n$ 个点中，有多少个点到原点的距离不小于 $d$。我们代入距离公式，读入每个点都算一遍即可。我们这里设置的浮点数运算允许误差范围为 $10^{-6}$。
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, d, tot;
double dis(ll x, ll y) {
return sqrt(1.0*x*x+1.0*y*y);
}
int main() {
scanf("%lld%lld", &n, &d);
for(ll i=1;i<=n;i++) {
ll x, y;
scanf("%lld%lld", &x, &y);
if(dis(x, y) - d <= 1e-6) {
++tot;
}
}
printf("%lld\n", tot);
return 0;
}
```
**C - Repsept [Link](https://atcoder.jp/contests/abc174/tasks/abc174_c)**
求每个数位全部为 $7$ 的，是 $k$ 的倍数的第一个数的位数（即包含多少个 $7$）。
一道简单数学题，我们有如下推导：
$$
\begin{aligned}
\text{设}\ a_i=&\underbrace{77\cdots 7}_{\text{共}\ i\ \text{个}}\\
a_{i+1}=&a_i\times 10+7\\
\because&
\begin{cases}
a+b\equiv (a\mod k)+(b\mod k)&\pmod k\\
a\times b\equiv (a\mod k)\times (b\mod k)&\pmod k
\end{cases}
\\
\therefore& a_{i+1}\equiv (a_i\mod k)\times 10+7\pmod k
\end{aligned}
$$
发现余数有递推关系，我们只需要循环维护这个余数，到为 $0$ 或循环时退出循环即可。
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
bool _;
int k, md, i = 1;
int book[N];
int main() {
scanf("%d", &k);
md = 7 % k;
// printf("%d\n", md);
while(!book[md]) {
if(!md) {
_ = true;
break;
}
book[md] = 1;
md = (md * 10 + 7) % k;
// printf("%d\n", md);
++i;
}
if(!_) {
puts("-1");
}
else {
printf("%d\n", i);
}
return 0;
}
```
**D - Alter Altar [Link](https://atcoder.jp/contests/abc174/tasks/abc174_d)**
赛后找到这题的一个类似的题，忘了题号了，大概说男生女生排座位，通过交换使得所有女生在男生前面。
有一串由 `R` 和 `W` 组成的序列，每次可以选择任意两个位置交换，或者更改一个位置的字母。要使用最少的步数使得 `R` 全部在 `W` 前方。
我们统计最后一个 `W` 以及 `R` 的总个数，进行一些数学推导即可。
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
int n, tot, W, tot2;
string s;
int main() {
scanf("%d", &n);
cin>>s;
for(int i=0;i<n;i++) {
if(s[i] == 'W') {
if(!W) {
W = i;
}
}
else {
++tot;
}
}
for(int i=0;i<tot;i++) {
if(s[i] != 'R') {
++tot2;
}
}
printf("%d\n", min(tot2, n-W));
return 0;
}
```
**E - Logs [Link](https://atcoder.jp/contests/abc174/tasks/abc174_e)**
有 $n$ 个不同长度的木头，进行 $k$ 次切分，分成两个长度之和为切分前长度的木头。输出切分完成后长度最长的木头的最小长度（向上取整）。
我们考虑二分答案——在 $1$ 和最长的长度间二分，每次求出使最长木头的长度最小不超过 $mid$ 时，需要的切分次数，当满足题意时记录 $ans$。
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n, k, l = 1, r, ans;
int a[N];
bool f(int x) {
int t = 0;
for(int i=1;i<=n;i++) {
if(a[i] % x == 0) {
t += a[i] / x - 1;
}
else {
t += a[i] / x;
}
}
if(t > k) {
return false;
}
else {
return true;
}
}
int main() {
scanf("%d%d", &n, &k);
for(int i=1;i<=n;i++) {
scanf("%d", &a[i]);
r = max(r, a[i]);
ans = max(ans, a[i]);
}
while(l <= r) {
int mid = (l + r) >> 1;
if(f(mid)) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
printf("%d\n", ans);
return 0;
}
```
**F - Range Set Query [Link](https://atcoder.jp/contests/abc174/tasks/abc174_f)**
有一个长度为 $n$ 的数组，每个位置有一个颜色。$q$ 次询问，每次求出 $a_l\sim a_r$ 中共有多少种不同的颜色。
有没有感觉很熟悉？HH 的项链！
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int a[N], b[N], book[N], ans[N], n, q;
struct Node {
int l, r, id;
bool operator < (const Node &a) const {
return r < a.r;
}
}p[N];
void add(int n, int u) {
for(;n<=N;n+=n&(-n)) {
b[n] += u;
}
}
int sum(int n) {
int res = 0;
for(;n;n-=n&(-n)) {
res += b[n];
}
return res;
}
int main()
{
scanf("%d%d", &n, &q);
for(int i=1;i<=n;i++) {
scanf("%d", &a[i]);
}
for(int i=1;i<=q;i++) {
scanf("%d%d", &p[i].l, &p[i].r);
p[i].id = i;
}
sort(p+1, p+1+q);
// puts("Sorted. ");
int nxt = 1;
for(int i=1;i<=q;i++) {
// printf("For: i=%d\n", i);
for(int j=nxt;j<=p[i].r;j++) {
// printf("\tj=%d\n", j);
if(book[a[j]]) {
add(book[a[j]], -1);
}
add(j, 1);
book[a[j]] = j;
}
nxt = p[i].r + 1;
ans[p[i].id] = sum(p[i].r) - sum(p[i].l-1);
}
for(int i=1;i<=q;i++) {
printf("%d\n", ans[i]);
}
return 0;
}
```
完结撒花！