2020 牛客寒假算法基础集训营 2

解题报告(ABDEG/10)

链接:https://ac.nowcoder.com/acm/contest/3003

A. 做游戏

题目链接:https://ac.nowcoder.com/acm/contest/3003/A

分析:签到题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
LL a, b, c, x, y, z;
 
int main() {
    cin >> a >> b >> c >> x >> y >> z;
    cout << (min(a, y) + min(b, z) + min(c, x)) << endl;
    return 0;
}

B. 排数字

题目链接:https://ac.nowcoder.com/acm/contest/3003/B

分析:贪心,拼“61616161...”就行了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
 
using namespace std;
 
int n;
string s;
int one, six;
 
int main() {
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') one++;
        else if (s[i] == '6') six++;
    }
    int res = 0;
    if (six >= 2 && one >= 1) {
        res++, six -= 2, one--;
        while (six && one) res++, six--, one--;
    }
    cout << res << endl;
    return 0;
}

C. 算概率

题目链接:https://ac.nowcoder.com/acm/contest/3003/C

分析:

1

D. 数三角

题目链接:https://ac.nowcoder.com/acm/contest/3003/D

分析:暴力枚举,判钝角三角形,结果还因为精度问题WA了几次。

 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
#include <bits/stdc++.h>
 
#define x first
#define y second
 
using namespace std;
 
typedef pair<int, int> PII;
 
const int N = 510;
 
int n;
PII p[N];
 
double dist(PII a, PII b) {
    int dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(1.0 * dx * dx + 1.0 * dy * dy);
}
 
bool check(int x, int y, int z) {
    PII a = p[x], b = p[y], c = p[z];
    double ab = dist(a, b);
    double bc = dist(b, c);
    double ac = dist(a, c);
    if ((a.x == b.x && a.x == c.x) || (a.y == b.y && a.y == c.y)) return false;
    if ((ab + bc <= ac) || (ab + ac <= bc) || (bc + ac <= ab)) return false;
    if ((ab * ab - bc * bc - ac * ac > 1e-6) || (bc * bc - ab * ab - ac * ac > 1e-6) || (ac * ac - bc * bc - ab * ab > 1e-6)) return true;
    return false;
}
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y);
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            for (int k = j + 1; k <= n; k++) {
                if (check(i, j, k)) res++;
            }
        }
    }
    cout << res << endl;
    return 0;
}

E. 做计数

题目链接:https://ac.nowcoder.com/acm/contest/3003/E

分析:推一下公式可得,$2\sqrt {i \times j}=k-i-j$,即 $i \times j$ 为完全平方数,只要在 $i \times j \le n$ 的限制下枚举即可。需要考虑 $i,j$ 的大小关系。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    long long res = 0;
    for (int i = 1; i <= n / i; i++) {
        for (int j = 1; j < i; j++) {
            if (i * i % j == 0) res++;
        }
    }
    res = res * 2 + (int)sqrt(n);
    cout << res << endl;
    return 0;
}

F. 拿物品

题目链接:https://ac.nowcoder.com/acm/contest/3003/F

分析:

1

G. 判正误

题目链接:https://ac.nowcoder.com/acm/contest/3003/G

分析:碰运气,直接看快速幂取模后等式是否成立,模数用1e9+7就WA,用1e9+9就AC。

 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
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
const int mod = 1e9 + 9;
 
int qmi(int a, int k) {
    int res = 1 % mod;
    while (k) {
        if (k & 1) res = (LL)res * a % mod;
        k >>= 1;
        a = (LL)a * a % mod;
    }
    return res;
}
 
int main() {
    int T;
    cin >> T;
    while (T--) {
        int a, b, c, d, e, f, g;
        cin >> a >> b >> c >> d >> e >> f >> g;
        int p1 = qmi(a, d), p2 = qmi(b, e), p3 = qmi(c, f);
        if (((p1 + p2) % mod + p3) % mod == g % mod) puts("Yes");
        else puts("No");
    }
    return 0;
}

H. 求函数

题目链接:https://ac.nowcoder.com/acm/contest/3003/H

分析:

1

总结

挺难的一场,枯。

第三场官方说明考点:枚举,贪心,DP,数论,思维,数据结构,哈希

updatedupdated2020-07-022020-07-02
加载评论
点击刷新