AcWing：第56场周赛

4482. 分组 - AcWing题库

给定一个长度为 n 的数组 a1,a2,…,an。

请你将这 n 个元素重新分组，要求每个组内的元素两两不等，且分组数量应尽可能少。

请你计算最少所需的分组数量。

例如，给定一个数组 a=[1,2,4,3,3,2]，我们至少需要将所有元素分为两组，一种可行分组方案为：[1,2,3] 和 [2,3,4]。

输入格式

第一行包含一个整数 n。

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

输出格式

一个整数，表示最少所需的分组数量。

数据范围

前三个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤100，1≤ai≤100。

输入样例1：

6
1 2 4 3 3 2
1
2

输出样例1：

2
1

问题解析

想象一下，我们要把n个相同的东西分开放，那么显然是需要n个盒子，这样才能保证一个盒子里只有一个相同的东西。

这题直接统计出现最多的那个数的次数就行，次数为多少，就要分多少组。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,res=0;
    unordered_map<int, int>mymap;
    cin >> n;
    vector<int>v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        mymap[v[i]]++;
        res = max(res, mymap[v[i]]);
    }
    cout << res;
    return 0;
}
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

4483. 格斗场 - AcWing题库

一个格斗场内有 n 个战士，其中第 i 个战士的战斗力为 ai。

作为格斗场内的经理人，你需要给战士们安排一对一的决斗。

这些决斗是一场接一场进行的，一场结束后才会安排下一场。

为了保证决斗的观赏性，在安排时需保证：

• 决斗双方的战斗力不能相同。
• 决斗双方的战斗力差距不能超过 K。

已知，在决斗中战斗力高的选手一定可以将战斗力低的选手击败，并且失败的选手会被赶出格斗场。

请你合理安排决斗，使得当剩余选手之间无法再安排任何决斗时，剩余选手的数量越少越好。

请你输出剩余选手的最小可能数量。

输入格式

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

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

输出格式

一个整数，表示剩余选手的最小可能数量。

数据范围

前四个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤2×10^{5，1≤K≤10}6，1≤ai≤10^6。

输入样例1：

7 1
101 53 42 102 101 55 54
1
2

输出样例1：

3
1

问题描述

看一个数能不能活下来，只要看数组里有没有和大于它且不超过k的数，如果有，那这个数显然可以被排除掉，如果没有，那这个数就能留到最后面。

可以对数组升序排序，从最小的数开始找起，如果有大于它，且差值不超过k的数，这个数就被排掉，我们去找下一个，如果没有，那这个数可以留到最后，用一个变量记录下来。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    priority_queue<int, vector<int>, greater<>>que;
    int n, res = 0, mn = -1, ans = 0, k;
    cin >> n >> k;
    vector<int>v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        que.push(v[i]);
    }
    while (!que.empty())
    {
        ans = 1;
        mn = que.top();
        que.pop();
        while (!que.empty() && que.top() == mn)
        {
            que.pop();
            ans++;
        }
        if (que.empty() || que.top() - mn > k)
        {
            res += ans;
        }
    }
    cout << res;
    return 0;
}
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
45
46
47
48
49
50
51
52
53
54
55
56

4484. 有限小数 - AcWing题库

给定三个整数 p,q,b，请你计算十进制表示下的 p/q 的结果在 b 进制下是否为有限小数。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据占一行，包含三个整数 p,q,b。

输出格式

每组数据输出一行结果，如果 p/q 的结果在 b进制下是有限小数，则输出 YES，否则输出 NO。

数据范围

前五个测试点满足 1≤T≤10。
所有测试点满足 1≤T≤10^{5，0≤p≤10}18，1≤q≤10^{18，2≤b≤10}18。

输入样例1：

2
6 12 10
4 3 10
1
2
3

输出样例1：

YES
NO
1
2

问题解析

首先讲一下小数转化成b进制的形式：假设有个小数是0.abcd，要转成x进制，那就是**(a*x^-1 )+(b *x^-2 )+(c *x^-3)+(d *x^ -4)**。

如果我们给十进制下的小数乘上一个x，那就会变成：**(a )+(b *x^-1 )+(c x^-2)+(d x^ -3)

那么对于一个k位小数，我们只要乘上k个x，就可以把这个小数全部转化成整数。

也就是说：对于p/q，只要(p/q) * x^k 是整数，就说明p/q的小数可以用k个有限小数表示出来。

（具体看注释）

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>

#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;

ll gcd(ll a, ll b)
{
    return a == 0 ? b : gcd(b % a, a);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        ll p, q, b;
        cin >> p >> q >> b;
        //(p/q)*b^k要想是整数，b^k * p就要整除q，我们可以直接把p和q约分，这样就不用管p了，直接看q和b就行
        q /= gcd(p, q);
        while (q > 1)
        {
            ll x = gcd(q, b);
            //如果q和b的公约数互质，说明他俩无法继续约分了，结束程序
            if (x == 1)break;
            while (q % x == 0)q /= x;
        }
        //如果q能和k个b约分约到1，就说明q能整除b^k ,反之不行
        if (q > 1)cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}
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
45
46
47
48
49
50
51
52
53
54
55