Acwing: the 56th weekly match

AcWing： The first 56 Weekly match

4482. grouping - AcWing Question bank

Given a length of n Array of a1,a2,…,an.

Please take this n Regroup elements , The elements in each group are required to be different , And the number of groups should be as small as possible .

Please calculate the minimum number of groups required .

for example , Given an array a=[1,2,4,3,3,2], We need to divide all elements into at least two groups , A feasible grouping scheme is ：[1,2,3] and [2,3,4].

Input format

The first line contains an integer n.

The second line contains n It's an integer a1,a2,…,an.

Output format

An integer , Indicates the minimum number of groups required .

Data range

The first three test points meet 1≤n≤10.
All test points meet 1≤n≤100,1≤ai≤100.

sample input 1：

6
1 2 4 3 3 2

sample output 1：

2

Problem analysis

Imagine , We are going to put n The same thing is open , Then it is obviously necessary n Boxes , Only in this way can we ensure that there is only one same thing in a box .

This question directly counts the number of times of the number that appears most , How many times , Just how many groups .

AC Code

#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;
}

4483. The arena - AcWing Question bank

There is n A warrior , Among them the first i The combat effectiveness of soldiers is ai.

As a manager in the arena , You need to arrange a one-on-one duel for the soldiers .

These duels were fought one after another , The next one will be arranged after one .

In order to ensure the appreciation of the duel , Ensure that ：

• The fighting capacity of both sides of the duel cannot be the same .
• The difference in combat effectiveness between the two sides of the duel cannot exceed K.

It is known that , In the duel, the player with high combat effectiveness can certainly defeat the player with low combat effectiveness , And the loser will be driven out of the arena .

Please arrange the duel reasonably , So that when the remaining players can no longer arrange any duels , The smaller the number of remaining players, the better .

Please output the minimum possible number of remaining players .

Input format

The first line contains two integers n,K.

The second line contains n It's an integer a1,a2,…,an.

Output format

An integer , Indicates the minimum possible number of remaining players .

Data range

The first four test points meet 1≤n≤10.
All test points meet 1≤n≤2×10^5,1≤K≤106,1≤ai≤10^6.

sample input 1：

7 1
101 53 42 102 101 55 54

sample output 1：

3

Problem description

See if a number can survive , Just look at the array to see if there is a sum greater than it and not more than k Number of numbers , If there is , This number can obviously be excluded , without , Then this number can be left to the end .

You can sort the array in ascending order , Start with the smallest number , If there is more than it , And the difference does not exceed k Number of numbers , This number is eliminated , Let's go to the next , without , Then this number can be left to the end , Record it with a variable .

AC Code

#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;
}

4484. terminating decimal - AcWing Question bank

Given three integers p,q,b, Please calculate p/q The result is b Is it a finite decimal under base .

Input format

The first line contains integers T, Expressing common ownership T Group test data .

Each group of data occupies one row , Contains three integers p,q,b.

Output format

Output a row of results for each group of data , If p/q The result is b Base is a finite decimal , The output YES, Otherwise output NO.

Data range

The first five test points meet 1≤T≤10.
All test points meet 1≤T≤10^5,0≤p≤1018,1≤q≤10^{18,2≤b≤10}18.

sample input 1：

2
6 12 10
4 3 10

sample output 1：

YES
NO

Problem analysis

First, let's talk about the conversion of decimals into b The form of base ： Suppose a decimal is 0.abcd, To turn into x Base number , That's it **(a*x^-1 )+(b *x^-2 )+(c *x^-3)+(d *x^ -4)**.

If we multiply the decimal by one x, Then it will become ：**(a )+(b *x^-1 )+(c x^-2)+(d x^ -3)

So for a k Decimal place , We just need to take k individual x, You can convert all the decimals into integers .

in other words ： about p/q, as long as (p/q) * x^k Is an integer , Just explain p/q Decimals of can be used k A finite number of decimals .

（ See the notes for details ）

AC Code

#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 To be an integer ,b^k * p It is necessary to divide q, We can put p and q Apposition , So you don't have to worry about p 了 , Look directly at q and b Just go 
        q /= gcd(p, q);
        while (q > 1)
        {
            ll x = gcd(q, b);
            // If q and b The common divisor of is coprime , It means that they can't continue to make an appointment , End procedure 
            if (x == 1)break;
            while (q % x == 0)q /= x;
        }
        // If q Energy and harmony k individual b Make an appointment 1, Just explain q aliquot b^k , Not vice versa 
        if (q > 1)cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}