AcWing-周赛第95场题解

T1:AcWing 4873. 简单计算

给定四个整数 x1,y1,x2,y2，请你计算 max(|x1−x2|,|y1−y2|)。

输入格式

第一行包含两个整数 x1,y1。

第二行包含两个整数 x2,y2。

输出格式

一个整数，表示 max(|x1−x2|,|y1−y2|)的值。

数据范围

前 44 个测试点满足 −10≤x1,y1,x2,y2≤10。
所有测试点满足 −10e9≤x1,y1,x2,y2≤10e9。

输入样例1

1
2

0 0
4 5

输出样例1

输入样例2：

1
2

3 4
6 1

输出样例2

题解

#include <iostream>
using namespace std;

int main()
{
    int x1,x2,y1,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << max(abs(x1 - x2), abs(y1 - y2));
    return 0;
}

T2:AcWing 4874.约数

如果一个正整数的约数个数恰好为 33，则称该数为美丽数。

给定 n个正整数 a1,a2,…,an, 请你依次判断每个数是否是美丽数。

输入格式

第一行包含整数 n。

第二行包含 n个整数 a1,a2,…,an。

输出格式

共 n行，其中第 i行输出对 ai的判断，如果 ai是美丽数，则输出 YES，否则输出 NO。

数据范围

前 6个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤105，1≤ai≤10121。

输入样例

1
2

3
4 5 6

输出样例

1
2
3

YES
NO
NO

题解

参考y总的讲解，优化处理yyds!!!

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

const int N = 1e6 + 10; // 优化处理即判断r=sqrt(n)，看平方根r是否是质数
int primes[N]; // 用于存储N个待判断的整数
bool st[N]; // 用于标记该位置上的数是否为质数
typedef long long LL;

void get_primes(int n) // 筛质数(线性筛法)
{
    int cnt = 0;
    st[1] = true; // !!!需要手动特判一下，1的约数个数为1
    for (int i = 2; i <= n; i ++)
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] * i <= n; j ++)
        {
            st[primes[j] * i] = true; // 即将非质数的状态更新为true
            if (i % primes[j] == 0) break; // 即sqrt(x)是质数，等价于约数个数为（1, x, r=sqrt(x)）这三个
        }
    }
}

int main()
{
    get_primes(N - 1); // 预处理这N个数，标记状态
    int n;
    scanf("%d", &n);
    while (n --)
    {
        LL x; // 用long long存,12位数会爆int
        scanf("%lld", &x);
        LL r = sqrt(x); // 记得加<cmath>头文件
        if (r * r == x && !st[r]) // 满足x是平方数的且平方根为奇数的，才是美丽数
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}