牛客小白月赛57

传送门

A 最大面积

题目

输入

输出

示例1

输入

2 2 3 2

输出

4

---

代码

void solve() {
    int a, b, c, d; cin >> a >> b >> c >> d;
    cout << min(a, c) * min(b, d) << endl;
}
1
2
3
4

B 种树

题目

输入

输出

示例1

输入

7
0111110

输出

2

思路

注意题目说的：“一个地方可以种多棵树。”

左侧有 $0$ 可以由右侧某个 $1$ 向左种树

右侧有 $0$ 可以由左侧某个 $1$ 向右种树

即：字符串首尾两位 $0$ 的个数，决定了种的次数。

代码

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int res = 0;
    if (s[0] == '0') res++;
    if (s.back() == '0') res++;
    cout << res << endl;
}
1
2
3
4
5
6
7
8

---

C 奇怪的电梯

题目

输入

输出

示例1

输入

5
10 3 2 7
10 7 1 4
10 4 2 9
10 11 1 10
9 3 7 2

输出

YES
NO
YES
NO
YES

思路

事先声明：代码很丑，但思路非常简单！！！

题目问能否从$（a->b）$，那很容易第一想法就是分情况$（a>b，b>a，a==b）$

• $a==b$：yes

• $b>a$：（如上图所示）

  • 这里需要继续分情况，在此只考虑yes的情况
  • 1. $b-a>k$：$a->b$
  • 2. $n-b>k$：$a->n->b$
  • 3. $a-1>k$：$a->1->b$
  • 4. $n-a>k\&\&b-1>k$：$a->n->1->b$

• $a>b$：同上思路

以上情况已经列明，具体的逻辑也应该非常清晰了，不在叙述每一步之间的大小关系了（自己想。

代码

void solve() {
    int n, k, a, b; cin >> n >> k >> a >> b;
    if (a == b) { puts("YES"); return ; }
    if (a > b) {
        if (n - a > k || a - b > k || b - 1 > k) { puts("YES"); return ; }
        else if (a - 1 > k && n - b > k) { puts("YES"); return ; }
        else { puts("NO"); return ; }
    } else {
        if (a - 1 > k || b - a > k || n - b > k) { puts("YES"); return ; }
        else if (n - a > k && b - 1 > k) { puts("YES"); return ; }
        else { puts("NO"); return ; }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

D 最大gcd

题目

输入

输出

示例1

输入

3
1 2 2

输出

2

思路

这题一眼$n^2$暴力结束。。。T的飞起

考虑题目范围 $n\le 1e6$，并且每个数的大小 $a[i]\le 1e6$。

我们可以从原先找每两个数的 $gcd$ 取最大，转为找出每个数的约数，这样最大存在的约数并且个数大于等于$2$，那么就是答案。

我们考虑 $nlogn$的算法来实现，又已知 $nlogn$ 能打出 $1$ ~ $n$ 范围内的所有约数。

大概思路就是枚举每个数 $i$ 的倍数，那么 $i\ast j$ 的约数就有 $i$。和线性筛的思路有点相似，代码大概长这样：

// 求 1 ~ n 的约数
for (int i = 1; i <= n; i++) 
	for (int j = 1; j <= n / i; j++) 
			a[i * j].push_back(i);
1
2
3
4

不过这题还需要有一个特判（由于我的实现方式导致的），需要对重复的数也计入答案的贡献。即代码中的：if (a[x] == 2) res = max(res, x);
因为if (a[i * j]) c[i]++;，这行代码未考虑重数的情况。

代码

int a[N], c[N];

void solve() {
    int n; scanf("%d", &n);
    
    int res = -1;
    for (int i = 1; i <= n; i++) { int x; cin >> x; a[x]++; if (a[x] == 2) res = max(res, x); }
    
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N / i; j++)
            if (a[i * j]) c[i]++;
    
    for (int i = 1; i < N; i++) if (c[i] >= 2) res = max(res, i);
    cout << res << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

E 一道难题

题目

输入

输出

示例1

输入

2001

输出

3

说明
$1-2001$ 中，满足条件的数有：$111,1110,1111$。

思路

题目输入的是十进制的数，但是题目要求的是由 $0$ 或 $1$ 组成的。

所以可以发现，满足题目的条件的十进制数，实际上与相同位数的二进制数对应。

那么可以求出不超过 $n$ 的最大的二进制形式，应该对应的十进制数值。

对于每一个数，都当成一个二进制数看。然后在暴力枚举，判断符合条件即可。

代码

void solve() {
    string s; cin >> s;
    int n = 0;
    bool o = false;
    for (int i = 0; i < s.sz; i++) {
        if (o) { n += (1ll << (s.sz - i - 1)); continue; }
        if (s[i] > '1') n += (1ll << (s.sz - i - 1)), o = true;
        if (s[i] == '1') n += (1ll << (s.sz - i - 1));
    }
    
    auto check = [=](int x){
        int cnt = 0;
        while (x) {
            if (x & 1) cnt++;
            else cnt = 0;
            if (cnt == 3) return true; 
            
            x >>= 1;
        }
        return false;
    };
    
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (check(i)) res++;
    }
    cout << res << endl;
}
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

---

F 序列操作

---