AcWing-周赛第97场题解

T1: AcWing 4944. 热身计算

给定两个正整数 a, b，请你分别计算 min(a,b) 以及 ⌊|a−b|/2⌋的值。⌊|a−b|/2⌋表示不大于 |a−b|/2的最大整数。

输入格式

共一行，包含两个正整数 a,b。

输出格式

共一行，输出两个整数，分别表示 min(a,b)以及 ⌊|a−b|/2⌋。

数据范围

所有测试点满足 1 ≤ a, b ≤ 100。

输入样例1

3 1

输出样例1

1 1

输入样例2

2 3

输出样例2

2 0

输入样例3

7 3

输出样例3：

3 2

题解

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    cout << min(a, b) << ' ' << abs(a - b) / 2 << endl;
    return 0;
}

T2: AcWing 4945. 比大小

题目

给定一个 n 位 bx 进制数 X 和一个 m位 by进制数 Y。

X 和 Y 都为正整数，且都不含前导 0。

请你比较它们的大小。

输入格式。

第一行包含两个整数 n, bx。

第二行包含 n 个整数 x1,x2,…,x，表示 X的各位数字，它们按照从最高有效位到最低有效位的顺序给出。

第三行包含两个整数 m,by。

第四行包含 m 个整数 y1,y2,…,y，表示 Y 的各位数字，它们按照从最高有效位到最低有效位的顺序给出。

X 和 Y 的各位数字在输入中均按十进制表示给出。

输出格式

共一行：

如果 X < Y，则输出 <。
如果 X > Y，则输出 >。
如果 X = Y，则输出 =。

数据范围

前 6 个测试点满足 2 ≤ bx, by ≤ 16。
所有测试点满足 1 ≤ n, m ≤ 1，2 ≤ bx, by ≤ 40，bx ≠ by，0 ≤ xi < bx，0 ≤ yi< by。

输入样例1

6 2
1 0 1 1 1 1
2 10
4 7

输出样例1

输入样例2

输出样例2

输入样例3

7 16
15 15 4 0 0 7 10
7 9
4 8 0 3 1 5 0

输出样例3

题解

直接模拟，快速幂计算

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n, bx, x, m, by, y;

    cin >> n >> bx;
    long long X = 0;
    while(n --)
    {
        cin >> x; // 共循读n次（n-1 ~ 0）
        X += pow(bx, n) * x;
    }

    cin >> m >> by;
    long long Y = 0; // 最大到40^9级别（会爆int）
    while(m --)
    {
        cin >> y;
        Y += pow(by, m) * y;
    }

    if(X < Y) puts("<");
    else if (X > Y) puts(">");
    else puts("=");

    return 0;
}

秦九韶算法，数学公式推导

#include <iostream>
using namespace std;

typedef long long LL;

LL get()
{
    int n, b;
    cin >> n >> b;
    LL res = 0;
    while(n --) // n最大是10位
    {
        int x;
        cin >> x;
        res = res * b + x; // 秦九韶算法，数学公式推导
    }
    return res;
}

int main()
{
    LL x = get();
    LL y = get();

    if(x > y) puts(">");
    else if(x < y) puts("<");
    else puts("=");
    return 0;
}

T3: AcWing 4946. 叶子节点

给定一棵 n 个节点的树，节点编号 1 ∼ n。

1号节点为树的根节点。

每个节点要么是黑色的，要么是白色的。

对于一个叶子节点，如果从该节点到根节点的路径（包括两端节点）中有超过 m 个

黑色节点连续的排列在一起，则称该节点为无效叶子节点。

有效叶子节点数量 = 总叶子节点数量 - 无效叶子节点数量

请你统计，给定树中有效叶子节点的数量。

输入格式

第一行包含两个整数 n, m。

第二行包含 n 个整数 a1, a2, …, an，其中 ai表示第 i 个节点的颜色，1 表示黑色，0 表示白色。

接下来 n−1 行，每行包含两个整数 x, y，表示节点 x 和节点 y 之间存在一条无向边。

保证输入给定的是一棵树。

输出格式

一个整数，表示给定树中有效叶子节点的数量。

数据范围

前 66 个测试点满足 2 ≤ n ≤ 10。
所有测试点满足 2 ≤ n ≤ 10e5，1 ≤ m ≤ n，0 ≤ ai ≤ 1，1 ≤ x, y ≤ n，x ≠ y。

输入样例1

输出样例1

输入样例2

7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7

输出样例2

题解

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, M = 2 * N; // 无向边，需存两次 10万范围O(N)或O（nlogn）
int h[N], e[M], ne[M], idx; // 定义邻接表
int c[N]; // 存结点颜色
int n, m;

void add(int a, int b) // 加边，头插法
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u, int fa, int cnt, bool vaild)
{
    if(c[u]) cnt ++;
    else cnt = 0; // 不连续就清零
    
    if(cnt > m) vaild = false; // 无效叶子结点
    
    int res = 0, sons = 0; // 存子节点数量
    for(int i = h[u]; i != -1; i = ne[i]) // 树的遍历
    {
        int j = e[i];
        if(j == fa) continue; // j是父结点，继续遍历
        else sons ++; // 是子结点
        // j是当前结点, u是父结点
        res += dfs(j, u, cnt, vaild); // 递归下一个节点，加上子树中满足有效子节点数量 
    }
    
    if(!sons && vaild) res ++; // 若sons为0则代表没有子节点，即叶子节点
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &c[i]); // 颜色数组c[]下标1开始读
    
    memset(h, -1, sizeof h); // 初始化头结点,加<cstring>
    for(int i = 1; i <= n - 1; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    
    // 初始化dfs, 第4个参数表示该叶子结点是有效的
    printf("%d\n", dfs(1, -1, 0, true)); // 树的深度优先遍历
    return 0;
}